Subject: [nfsv4] Proposal for New Striping Approach in NFSv4.1 file layout type

From: Mike Eisler <[email-masked]>
Date: Tue, 12 Jun 2007 17:10:12 -0700 (PDT)

During today's NFSv4.1 file layout type inspection,
there was pushback on the the complexity of the striping
algorithm. Several inspectors felt it would be hard
for a client sharing the same device IDs for two different
file handles to factor the striping data structures.

The point of the striping algorithm in draft-10 is to
provide a very compressed way to represent complex patterns.

I proposed an outline of a new algorithm and promised to
send it to the WG list today.

Here it is:

typedef netaddr4 multipath_list4<>;

%/* Encoded in the da_addr_body field of type device_addr4: */
enum stripetype4 {
        STRIPE4_SPARSE = 1,
        STRIPE4_DENSE = 2
};

struct nfsv4_1_file_layout_ds_addr4 {
	stripetype4			nflda_stripetype;
	uint32_t			nflda_stripe_unit_size;
	uint32_t			nflda_stripe_indices<>;
	multipath4_list4		nflda_multipath_ds_list<>;
};

A device address consists of:

- The stripe packing type, STRIPE4_SPARSE or STRIPE4_DENSE.
  It makes sense that this is an attribute that multiple files
  would share so it moves from the layout to draft-10 to
  the device address in this proposal.

- For similar reasons the stripe_unit_size moves to
  the device address.

- An array (nflda_striple_indices) of
  indexes used to index into the second array
  (nflda_multipath_ds_list). This array MUST be
  at least one element in length. No element in this
  array can have an value that is outside the bounds of
  the second array.

- The second array is an array of lists of network
  addresses of data servers (nflda_multipath_ds_list).
  Each list of network addresses in the second array is
  an array data servers that are equivalent to each other
  for multipatching purposes (and SHOULD be capable of
  session trunking).

%/* Encoded in the loc_body field of type layout_content4: */
struct nfsv4_1_file_layout4 {
	 deviceid4			nfl_deviceid;
         bool                           nfl_commit_through_mds;
	 uint32_t			nfl_first_stripe_index;
         nfs_fh4      			nfl_fh_list<>;
};

Each layout returns:

- A deviceid (nfl_deviceid) that corresponds to the device address.

- nfl_commit_through_mds, as defined in draft-10.

- An initial index, nfl_first_stripe_index,
  which is an index into the device address's
  nflda_stripe_indices array. As will be seen from
  the algorithm presented after this bullet list,
  there is in fact no bounds limit on the initial index,
  is it is combined with the stripe united being addressed.

- An array of data server file handles,
  nfl_fh_list. Either array MUST have the same number of
  elements as the nflda_multipath_ds_list field from the
  device address, and if so, each file handle at index X in
  nfl_fh_list[X] corresponds to the element at index X in
  nflda_multipath_ds_list[X]; or the array has exactly one
  element, and nfl_fh_list[0] corresponds to each element
  at index X in nflda_multipath_ds_list[X]. I.e. the file handle
  for each data server is the same.

In general the algorithm for the file handle and set
of data server network addresses to write stripe unit i
(SUi) is:

	idx = nflda_stripe_indices[
		( SUi + nfl_first_stripe_index ) % 
		( number of elements in nflda_stripe_indices )]

	// per specification idx is within bounds of nfl_fh_list
	if (number of elements in nfl_fh_list > 1) {
		fh = nfl_fh_list[idx];
	} else {
		fh = nfl_fh_list[0];
	}
	
	// per specification idx is within bounds of
	// nflda_multipath_ds_list.
	addrlist = nflda_multipath_ds_list[idx];

Advantages of this proposal:

- it is trivial for clients and servers to produce and grok
  a single striping pattern that can be common to multiple
  files.

- it is trivial for servers to customize the pattern per
  file by adjusting the nfl_first_stripe_index. So one file could
  start offset 0 at one data server, and another could
  start offset 0 at an different data server.

Suppose we have a device address consisting of
7 data servers, arranged in 3 equivalent classes:

	{ A, B, C, D }, { E }, { F, G }

where A-G are network addresses.

Then
	nflda_multipath_ds_list<> =
	{ A, B, C, D }, { E }, { F, G }

	i.e.
	nflda_multipath_ds_list[0] = { A, B, C, D }
	nflda_multipath_ds_list[1] = { E }
	nflda_multipath_ds_list[2] = { F, G }

Suppose the striping index array is:
	nflda_stripe_indices<> = { 2, 0, 1, 0 }

Now suppose the client gets a layout which has a device ID
that maps to the above device address.  The initial index,
nfl_first_stripe_index, is 2, and the nfl_fh_list is {
0x36, 0x87, 0x67 }.

Each stripe unit is equal to one block of data (say 4
KByte).

If the client wants to write block 0, the
set of valid { network address, file handle } combinations
are block 0 are determined by:

	nfl_first_stripe_index = 2
So
	idx	= nflda_stripe_indices[(0 + 2) % 4]
		= nflda_stripe_indices[2] =
		= 1
So
	nflda_multipath_ds_list[1] = { E }
and
	nfl_fh_list[1] = { 0x87 }

The client can thus write block 0 to { E, 0x87 );

The first 13 blocks are:

SUi	fh	devices 

0	87	E
1	36	A,B,C,D
2	67	F,G
3	36	A,B,C,D
4	87	E

5	36	A,B,C,D
6	67	F,G
7	36	A,B,C,D
8	87	E

9	36	A,B,C,D
10	67	F,G
11	36	A,B,C,D
12	87	E

=============

Here is an Excel spreadsheet. Save as layout.xml and load
into Excel.

<?xml version="1.0"?>
<?mso-application progid="Excel.Sheet"?>
<Workbook xmlns="urn:schemas-microsoft-com:office:spreadsheet"
 xmlns:o="urn:schemas-microsoft-com:office:office"
 xmlns:x="urn:schemas-microsoft-com:office:excel"
 xmlns:ss="urn:schemas-microsoft-com:office:spreadsheet"
 xmlns:html="http://www.w3.org/TR/REC-html40">
 <DocumentProperties xmlns="urn:schemas-microsoft-com:office:office">
  <Author>NetApp</Author>
  <LastAuthor>NetApp</LastAuthor>
  <Created>2007-06-12T22:41:04Z</Created>
  <LastSaved>2007-06-12T23:58:44Z</LastSaved>
  <Company>Network Appliance Inc.</Company>
  <Version>11.6408</Version>
 </DocumentProperties>
 <ExcelWorkbook xmlns="urn:schemas-microsoft-com:office:excel">
  <WindowHeight>10485</WindowHeight>
  <WindowWidth>5595</WindowWidth>
  <WindowTopX>120</WindowTopX>
  <WindowTopY>60</WindowTopY>
  <ProtectStructure>False</ProtectStructure>
  <ProtectWindows>False</ProtectWindows>
 </ExcelWorkbook>
 <Styles>
  <Style ss:ID="Default" ss:Name="Normal">
   <Alignment ss:Vertical="Bottom"/>
   <Borders/>
   <Font/>
   <Interior/>
   <NumberFormat/>
   <Protection/>
  </Style>
  <Style ss:ID="s23">
   <Alignment ss:Horizontal="Right" ss:Vertical="Bottom"/>
  </Style>
  <Style ss:ID="s25">
   <Alignment ss:Horizontal="Left" ss:Vertical="Bottom"/>
  </Style>
  <Style ss:ID="s26">
   <Alignment ss:Horizontal="Center" ss:Vertical="Bottom"/>
  </Style>
 </Styles>
 <Worksheet ss:Name="Sheet1">
  <Table ss:ExpandedColumnCount="5" ss:ExpandedRowCount="40"
x:FullColumns="1"
   x:FullRows="1">
   <Column ss:AutoFitWidth="0" ss:Width="123.75"/>
   <Column ss:AutoFitWidth="0" ss:Width="103.5"/>
   <Column ss:Index="4" ss:AutoFitWidth="0" ss:Width="55.5"/>
   <Column ss:AutoFitWidth="0" ss:Width="62.25"/>
   <Row>
    <Cell><Data ss:Type="String">device address</Data></Cell>
   </Row>
   <Row ss:Index="3">
    <Cell ss:StyleID="s23"/>
    <Cell><Data ss:Type="String">indices</Data></Cell>
   </Row>
   <Row>
    <Cell ss:StyleID="s26"><Data ss:Type="String">number of
indices</Data></Cell>
    <Cell><Data ss:Type="Number">2</Data></Cell>
    <Cell><Data ss:Type="Number">0</Data></Cell>
    <Cell><Data ss:Type="Number">1</Data></Cell>
    <Cell><Data ss:Type="Number">0</Data></Cell>
   </Row>
   <Row>
    <Cell ss:StyleID="s26" ss:Formula="=COUNT(R[-1])"><Data
ss:Type="Number">4</Data></Cell>
   </Row>
   <Row ss:Index="9">
    <Cell ss:Index="2" ss:StyleID="s23"><Data ss:Type="String">device
addresses</Data></Cell>
   </Row>
   <Row>
    <Cell ss:Index="2"><Data ss:Type="String">A,B,C,D</Data></Cell>
    <Cell><Data ss:Type="String">E</Data></Cell>
    <Cell><Data ss:Type="String">F,G</Data></Cell>
   </Row>
   <Row ss:Index="15">
    <Cell ss:StyleID="s25"><Data ss:Type="String">layout</Data></Cell>
   </Row>
   <Row ss:Index="17">
    <Cell ss:StyleID="s23"><Data ss:Type="String">first
index</Data></Cell>
    <Cell><Data ss:Type="Number">2</Data></Cell>
   </Row>
   <Row>
    <Cell ss:Index="2" ss:StyleID="s23"><Data ss:Type="String">fh
list</Data></Cell>
   </Row>
   <Row>
    <Cell ss:StyleID="s25"><Data ss:Type="String">number of file
handles</Data></Cell>
    <Cell ss:StyleID="s23"><Data ss:Type="Number">36</Data></Cell>
    <Cell><Data ss:Type="Number">87</Data></Cell>
    <Cell><Data ss:Type="Number">67</Data></Cell>
   </Row>
   <Row>
    <Cell ss:StyleID="s26" ss:Formula="=COUNT(R[-1])"><Data
ss:Type="Number">3</Data></Cell>
   </Row>
   <Row ss:Index="27">
    <Cell><Data ss:Type="String">Logical Storage Unit
Index</Data></Cell>
    <Cell><Data ss:Type="String">index into indices array</Data></Cell>
    <Cell><Data ss:Type="String">final index</Data></Cell>
    <Cell><Data ss:Type="String">fh</Data></Cell>
    <Cell><Data ss:Type="String">devices</Data></Cell>
   </Row>
   <Row>
    <Cell ss:StyleID="s25"><Data ss:Type="Number">0</Data></Cell>
    <Cell ss:Formula="=MOD(RC[-1]+R17C2, R5C1)"><Data
ss:Type="Number">2</Data></Cell>
    <Cell ss:Formula="=INDEX(R4,1,RC[-1]+2)"><Data
ss:Type="Number">1</Data></Cell>
    <Cell ss:Formula="=IF(R20C1&gt;1,INDEX(R19,1,RC[-1]+2),
R19C2)"><Data
      ss:Type="Number">87</Data></Cell>
    <Cell ss:Formula="=INDEX(R10,1,RC[-2]+2)"><Data
ss:Type="String">E</Data></Cell>
   </Row>
   <Row>
    <Cell ss:StyleID="s25"><Data ss:Type="Number">1</Data></Cell>
    <Cell ss:Formula="=MOD(RC[-1]+R17C2, R5C1)"><Data
ss:Type="Number">3</Data></Cell>
    <Cell ss:Formula="=INDEX(R4,1,RC[-1]+2)"><Data
ss:Type="Number">0</Data></Cell>
    <Cell ss:Formula="=IF(R20C1&gt;1,INDEX(R19,1,RC[-1]+2),
R19C2)"><Data
      ss:Type="Number">36</Data></Cell>
    <Cell ss:Formula="=INDEX(R10,1,RC[-2]+2)"><Data
ss:Type="String">A,B,C,D</Data></Cell>
   </Row>
   <Row>
    <Cell ss:StyleID="s25"><Data ss:Type="Number">2</Data></Cell>
    <Cell ss:Formula="=MOD(RC[-1]+R17C2, R5C1)"><Data
ss:Type="Number">0</Data></Cell>
    <Cell ss:Formula="=INDEX(R4,1,RC[-1]+2)"><Data
ss:Type="Number">2</Data></Cell>
    <Cell ss:Formula="=IF(R20C1&gt;1,INDEX(R19,1,RC[-1]+2),
R19C2)"><Data
      ss:Type="Number">67</Data></Cell>
    <Cell ss:Formula="=INDEX(R10,1,RC[-2]+2)"><Data
ss:Type="String">F,G</Data></Cell>
   </Row>
   <Row>
    <Cell ss:StyleID="s25"><Data ss:Type="Number">3</Data></Cell>
    <Cell ss:Formula="=MOD(RC[-1]+R17C2, R5C1)"><Data
ss:Type="Number">1</Data></Cell>
    <Cell ss:Formula="=INDEX(R4,1,RC[-1]+2)"><Data
ss:Type="Number">0</Data></Cell>
    <Cell ss:Formula="=IF(R20C1&gt;1,INDEX(R19,1,RC[-1]+2),
R19C2)"><Data
      ss:Type="Number">36</Data></Cell>
    <Cell ss:Formula="=INDEX(R10,1,RC[-2]+2)"><Data
ss:Type="String">A,B,C,D</Data></Cell>
   </Row>
   <Row>
    <Cell ss:StyleID="s25"><Data ss:Type="Number">4</Data></Cell>
    <Cell ss:Formula="=MOD(RC[-1]+R17C2, R5C1)"><Data
ss:Type="Number">2</Data></Cell>
    <Cell ss:Formula="=INDEX(R4,1,RC[-1]+2)"><Data
ss:Type="Number">1</Data></Cell>
    <Cell ss:Formula="=IF(R20C1&gt;1,INDEX(R19,1,RC[-1]+2),
R19C2)"><Data
      ss:Type="Number">87</Data></Cell>
    <Cell ss:Formula="=INDEX(R10,1,RC[-2]+2)"><Data
ss:Type="String">E</Data></Cell>
   </Row>
   <Row>
    <Cell ss:StyleID="s25"><Data ss:Type="Number">5</Data></Cell>
    <Cell ss:Formula="=MOD(RC[-1]+R17C2, R5C1)"><Data
ss:Type="Number">3</Data></Cell>
    <Cell ss:Formula="=INDEX(R4,1,RC[-1]+2)"><Data
ss:Type="Number">0</Data></Cell>
    <Cell ss:Formula="=IF(R20C1&gt;1,INDEX(R19,1,RC[-1]+2),
R19C2)"><Data
      ss:Type="Number">36</Data></Cell>
    <Cell ss:Formula="=INDEX(R10,1,RC[-2]+2)"><Data
ss:Type="String">A,B,C,D</Data></Cell>
   </Row>
   <Row>
    <Cell ss:StyleID="s25"><Data ss:Type="Number">6</Data></Cell>
    <Cell ss:Formula="=MOD(RC[-1]+R17C2, R5C1)"><Data
ss:Type="Number">0</Data></Cell>
    <Cell ss:Formula="=INDEX(R4,1,RC[-1]+2)"><Data
ss:Type="Number">2</Data></Cell>
    <Cell ss:Formula="=IF(R20C1&gt;1,INDEX(R19,1,RC[-1]+2),
R19C2)"><Data
      ss:Type="Number">67</Data></Cell>
    <Cell ss:Formula="=INDEX(R10,1,RC[-2]+2)"><Data
ss:Type="String">F,G</Data></Cell>
   </Row>
   <Row>
    <Cell ss:StyleID="s25"><Data ss:Type="Number">7</Data></Cell>
    <Cell ss:Formula="=MOD(RC[-1]+R17C2, R5C1)"><Data
ss:Type="Number">1</Data></Cell>
    <Cell ss:Formula="=INDEX(R4,1,RC[-1]+2)"><Data
ss:Type="Number">0</Data></Cell>
    <Cell ss:Formula="=IF(R20C1&gt;1,INDEX(R19,1,RC[-1]+2),
R19C2)"><Data
      ss:Type="Number">36</Data></Cell>
    <Cell ss:Formula="=INDEX(R10,1,RC[-2]+2)"><Data
ss:Type="String">A,B,C,D</Data></Cell>
   </Row>
   <Row>
    <Cell ss:StyleID="s25"><Data ss:Type="Number">8</Data></Cell>
    <Cell ss:Formula="=MOD(RC[-1]+R17C2, R5C1)"><Data
ss:Type="Number">2</Data></Cell>
    <Cell ss:Formula="=INDEX(R4,1,RC[-1]+2)"><Data
ss:Type="Number">1</Data></Cell>
    <Cell ss:Formula="=IF(R20C1&gt;1,INDEX(R19,1,RC[-1]+2),
R19C2)"><Data
      ss:Type="Number">87</Data></Cell>
    <Cell ss:Formula="=INDEX(R10,1,RC[-2]+2)"><Data
ss:Type="String">E</Data></Cell>
   </Row>
   <Row>
    <Cell ss:StyleID="s25"><Data ss:Type="Number">9</Data></Cell>
    <Cell ss:Formula="=MOD(RC[-1]+R17C2, R5C1)"><Data
ss:Type="Number">3</Data></Cell>
    <Cell ss:Formula="=INDEX(R4,1,RC[-1]+2)"><Data
ss:Type="Number">0</Data></Cell>
    <Cell ss:Formula="=IF(R20C1&gt;1,INDEX(R19,1,RC[-1]+2),
R19C2)"><Data
      ss:Type="Number">36</Data></Cell>
    <Cell ss:Formula="=INDEX(R10,1,RC[-2]+2)"><Data
ss:Type="String">A,B,C,D</Data></Cell>
   </Row>
   <Row>
    <Cell ss:StyleID="s25"><Data ss:Type="Number">10</Data></Cell>
    <Cell ss:Formula="=MOD(RC[-1]+R17C2, R5C1)"><Data
ss:Type="Number">0</Data></Cell>
    <Cell ss:Formula="=INDEX(R4,1,RC[-1]+2)"><Data
ss:Type="Number">2</Data></Cell>
    <Cell ss:Formula="=IF(R20C1&gt;1,INDEX(R19,1,RC[-1]+2),
R19C2)"><Data
      ss:Type="Number">67</Data></Cell>
    <Cell ss:Formula="=INDEX(R10,1,RC[-2]+2)"><Data
ss:Type="String">F,G</Data></Cell>
   </Row>
   <Row>
    <Cell ss:StyleID="s25"><Data ss:Type="Number">11</Data></Cell>
    <Cell ss:Formula="=MOD(RC[-1]+R17C2, R5C1)"><Data
ss:Type="Number">1</Data></Cell>
    <Cell ss:Formula="=INDEX(R4,1,RC[-1]+2)"><Data
ss:Type="Number">0</Data></Cell>
    <Cell ss:Formula="=IF(R20C1&gt;1,INDEX(R19,1,RC[-1]+2),
R19C2)"><Data
      ss:Type="Number">36</Data></Cell>
    <Cell ss:Formula="=INDEX(R10,1,RC[-2]+2)"><Data
ss:Type="String">A,B,C,D</Data></Cell>
   </Row>
   <Row>
    <Cell ss:StyleID="s25"><Data ss:Type="Number">12</Data></Cell>
    <Cell ss:Formula="=MOD(RC[-1]+R17C2, R5C1)"><Data
ss:Type="Number">2</Data></Cell>
    <Cell ss:Formula="=INDEX(R4,1,RC[-1]+2)"><Data
ss:Type="Number">1</Data></Cell>
    <Cell ss:Formula="=IF(R20C1&gt;1,INDEX(R19,1,RC[-1]+2),
R19C2)"><Data
      ss:Type="Number">87</Data></Cell>
    <Cell ss:Formula="=INDEX(R10,1,RC[-2]+2)"><Data
ss:Type="String">E</Data></Cell>
   </Row>
  </Table>
  <WorksheetOptions xmlns="urn:schemas-microsoft-com:office:excel">
   <Selected/>
   <TopRowVisible>2</TopRowVisible>
   <Panes>
    <Pane>
     <Number>3</Number>
     <ActiveRow>19</ActiveRow>
     <ActiveCol>3</ActiveCol>
    </Pane>
   </Panes>
   <ProtectObjects>False</ProtectObjects>
   <ProtectScenarios>False</ProtectScenarios>
  </WorksheetOptions>
 </Worksheet>
 <Worksheet ss:Name="Sheet2">
  <WorksheetOptions xmlns="urn:schemas-microsoft-com:office:excel">
   <ProtectObjects>False</ProtectObjects>
   <ProtectScenarios>False</ProtectScenarios>
  </WorksheetOptions>
 </Worksheet>
 <Worksheet ss:Name="Sheet3">
  <WorksheetOptions xmlns="urn:schemas-microsoft-com:office:excel">
   <ProtectObjects>False</ProtectObjects>
   <ProtectScenarios>False</ProtectScenarios>
  </WorksheetOptions>
 </Worksheet>
</Workbook>

_______________________________________________
nfsv4 mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/nfsv4

---

From: Trond Myklebust <[email-masked]>
Date: Wed, 13 Jun 2007 15:48:07 -0400

> send it to the WG list today.

I think this proposal addresses my concerns with the current striping
algorithm. By moving the list of stripe indices to the device address,
you convert the entire stripe pattern into shared information that the
client can apply to several layouts. That makes perfect sense.

I do still have one question that I'd like to see clarified: is the
client actually allowed to trunk READ and WRITE requests across the
"equivalent" servers in the multipath_list4, or is the list of
equivalent servers only meant for dealing with failover scenarios?

IOW, can I write one stripe unit to the first server in the list, and
then write the equivalent stripe unit for the next stripe to the second
server in order to further scale out the network bandwidth?

Cheers
  Trond

---

From: Mike Eisler <[email-masked]>
Date: Wed, 13 Jun 2007 13:19:31 -0700 (PDT)

> server in order to further scale out the network bandwidth?

My interpretation is that the client can trunk I/O across
the equivalent servers. Perhaps though we should make it clear
that trunking is only guaranteed to work if the data servers supports
client ID or session trunking, and the trunking tests described
in the spec indicate two servers are the same in addition to
their appearance in the same multipath list.

---

From: Trond Myklebust <[email-masked]>
Date: Wed, 13 Jun 2007 16:31:58 -0400

> their appearance in the same multipath list.

It would be great if we could see a short mention of this in chapter
13.6. Currently it just mentions the failover usage.

---

From: "Noveck, Dave" <[email-masked]>
Date: Wed, 13 Jun 2007 16:34:08 -0400

I don't think you need that additonal level of trunking
support in this case.  The reason is that the metadata
is providing the stateids and that giving you those 
network addresses he is guranteeing togtehre with the
data servers that those stateid's will be honored by 
all the data servers, and since the data servers each
agree with metadata server regarding that state, they
have to agree with each other.

-----Original Message-----
From: Mike Eisler [mailto:[email-masked]] 
Sent: Wednesday, June 13, 2007 4:20 PM
To: [email-masked]
Subject: Re: [nfsv4] Proposal for New Striping Approach in NFSv4.1 file
layouttype

---

From: Garth Goodson <[email-masked]>
Date: Wed, 13 Jun 2007 14:38:38 -0700

> their appearance in the same multipath list.

The original intention was for fail-over only.  I agree that trunking 
could work.  Whatever we decide should be specified clearly.

-Garth

---

From: Garth Goodson <[email-masked]>
Date: Wed, 13 Jun 2007 14:53:59 -0700

> 	 uint32_t			nfl_first_stripe_index;

There are a couple of things that concern me.  This proposal has 
certainly simplified things, but at the cost of flexibility -- pushing 
more into the device structure.

Now, there can only be 1 device ID per layout.  This seems overly 
restrictive.  A new device ID structure is required for every striping 
pattern that isn't a rotation of an existing pattern with the same 
stripe unit size.  Is it really that much more complex to have a list of 
deviceids in the layout?

The second thing is the inclusion of the stripe type and unit size into 
the device structure; however, the unit size is of more concern to me. 
As it stands, if I want to change the stripe unit size, I again need a 
new device ID.  There seems to be little benefit in moving it into the 
device structure.  However, if we went with an array of devices in the 
layout, a different stripe size for each device may be overly complex 
for the client.

My two recommended changes would be:

1) to change the layout nfl_deviceid to nfl_deviceid<>
2) to move nflda_stripetype and nflda_stripe_unit_size back to the layout.

-Garth

---

From: Trond Myklebust <[email-masked]>
Date: Wed, 13 Jun 2007 18:58:23 -0400

> 2) to move nflda_stripetype and nflda_stripe_unit_size back to the layout.

Which again leaves the client with no idea how to cache the sucker...

     1. Are these extraordinarily complex layouts realistic? The server
        has to actually track how the files are striped. Is that really
        going to be done on a per-file basis?
     2. You have a deviceid which is 32 bits wide. What makes you think
        that you are going to exhaust that space?

Trond

---

From: Garth Goodson <[email-masked]>
Date: Wed, 13 Jun 2007 17:02:19 -0700

>         that you are going to exhaust that space?

I'm not sure why it is so hard to cache layout with multiple devices 
(1).  I agree we may not get very complex mappings today, but I think a 
little flexibility in a specification isn't a bad thing.  We could have 
very large device structures (in terms of the number of entries -- order 
1000s) today and if the stripe unit size is encoded within each device 
structure it can limit the server and require it hand out multiple 
devices structures with very little change between them.

I'm not concerned about the device ID space (2) -- the point is to 
reduce the amount of data the client must cache.  If every layout needs 
a separate device (each with multiple entries) then we've failed on this 
point.  Thus the idea of having COMPLEX or composite devices that form a 
shallow hierarchy.

Going back to (1) -- the complexity of client caching. The device cache 
is separate from the layout cache -- layouts have pointers (or 
references) into the device cache.  Each device is cached as we 
currently cache them (as an entire device object).  Since data is 
striped round-robin across the devices, the client can determine from 
the layout which device it needs for a particular I/O -- to aid with 
this, for 'very' complex layouts, the client can maintain a simple map 
representing a single stripe and how much of that stripe each 'logical' 
device covers (with pointers to the device structures).  The client then 
looks into the device structure as determined by the offset and 
determines which physical device to go to. The devices are shared across 
layouts and stored separately.  Is this really that complex?

You already have to handle this to some extent since there is no 
guarantee by the MDS that each layout for the same file (different byte 
ranges) need to share the same striping pattern.  I suppose you could 
keep the layouts separate, but that doesn't seem much less complex than 
the map I propose the client keeps.

-Garth

---

From: Mike Eisler <[email-masked]>
Date: Wed, 13 Jun 2007 19:09:09 -0700 (PDT)

--- Garth Goodson <[email-masked]> wrote:

Before I respond to your objections, I want to understand

> 1) to change the layout nfl_deviceid to nfl_deviceid<>

So what does this mean then?

Does the first index, index into the nfs_deviceid<> array, or into
the first indices array of each device ID's corresponding device
address
structure?

Or are there two starting indices, one for the nfs_deviceid, and one
for
indices array in the device address?

Or does the indices array move back into the layout?

Regardless, what is an example pattern your recommendation can
produce that what I've proposed cannot.

> 2) to move nflda_stripetype and nflda_stripe_unit_size back to the

It occurred to me that the boolean for commiting to MDS, has 31 free
bits. Rahul pointed out that the lower bits of 
nflda_sripe_unit_size could be the MDS commit bit, and the 
dense/sparse thing another bit, and the actually stripe unit size
would always have those bits masked off. I think we could reserve 8
lower bits, leaveing the stripe_unit size as somethign that ranges
from (2^9 to 2^31) & 0xFFFFFF00. I reckon stripe unit sizes of
under 512 bytes, or with not aligned at 256 bytes are not not
anything we need to consider. So if we need the MDS commit bit 
in the layout, I'd be OK with moving unit size and stripe type back
to the layout.

---

From: Trond Myklebust <[email-masked]>
Date: Wed, 13 Jun 2007 23:28:15 -0400

> devices structures with very little change between them.

You are missing the point. I want to cache _STRIPES_, not IP addresses.

> point.  Thus the idea of having COMPLEX or composite devices that form a 

You appear to be considering a future where each file needs a completely
separate striping pattern. I'm asking you whether that reflects the
99.9999% case. If it doesn't then why are we optimising for that case?
With 32-bits of deviceIDs you can almost certainly cater for the
remaining 0.0001% of servers.

> layouts and stored separately.  Is this really that complex?

You are basically stating that the client has to allow for arbitrary
stripe patterns on a per-file basis instead of just dealing with a
limited number of patterns per filesystem.

> the map I propose the client keeps.

"There is no guarantee" is not the same as saying "most cases require".

See the comment above about optimisation. If you have a 32-bit address
space, then you can accommodate quite a lot of different striping
patterns, however if the common case is that the server is asking you to
write in a round-robin fashion to 8 or 10 data servers, then what you
are proposing is way overkill: it may indeed allow for more compact
definitions of arbitrary layout patterns, but such layouts will impose
arbitrary memory constraints on the clients and are not a realistic
proposal either on the server side (the server has also to track all the
information associated with the layout) or on the client (which may very
well be keeping 100000s of files open at the same time).

What then is the value of allowing for such a scenario in the protocol?

Trond

---

From: "Iyer, Rahul" <[email-masked]>
Date: Wed, 13 Jun 2007 21:58:17 -0700

Hi all,
>From what I read, in essence, the new proposal abolishes the "SIMPLE"
device and replaces it with 1 "COMPLEX" device. This, causes at least 1
problem. It makes striping across multiple "COMPLEX" devices
problematic. For example,

If I wanted to stripe a file across 2 "COMPLEX" devices:
D0 -> devices A, B, C
D1 -> devices D, E, F

The indices array in the layout is <0, 1> and the nfldf_ds_index in the
nfs_ds_fh_list are <1, 0>
This leads to a flattened space of B, C, A, D, E, F. 

In the new striping proposal, this would be a single device with devices
A, B, C, D, E, F and an index array of 1, 2, 0, 3, 4, 5.

Now suppose I wanted to stripe another file over the same "COMPLEX"
devices, but now I have the nfldf_ds_index in the nfs_ds_fh_list as <0,
1>. 
This leads to a flattened space of A, B, C, E, F, D. 
In the new proposal, this would be another device with the same device
list of A, B, C, D, E, F with an index array of 0, 1, 2, 4, 5, 3. 

This is actually worse as far as device caching is concerned. This is
two whole deviceids with 6 devices each. In the former case, it was 2
COMPLEX devices. The overhead in the previous case was more bytes on the
wire. Personally, I'd rather have those extra bytes on the wire than
cache 2 large devices. 

Regards
Rahul

> Sent: Wednesday, June 13, 2007 7:09 PM
> To: [email-masked]
> Subject: Re: [nfsv4] Proposal for New Striping Approach in 
> NFSv4.1 file layouttype
> 
> 
> Does the first index, index into the nfs_deviceid<> array, or 
> into the first indices array of each device ID's 
> corresponding device address structure?
> 
> Or are there two starting indices, one for the nfs_deviceid, 
> and one for indices array in the device address?
> 
> Regardless, what is an example pattern your recommendation 
> can produce that what I've proposed cannot.
> 
> It occurred to me that the boolean for commiting to MDS, has 
> 31 free bits. Rahul pointed out that the lower bits of 
> dense/sparse thing another bit, and the actually stripe unit 
> size would always have those bits masked off. I think we 
> could reserve 8 lower bits, leaveing the stripe_unit size as 
> somethign that ranges from (2^9 to 2^31) & 0xFFFFFF00. I 
> reckon stripe unit sizes of under 512 bytes, or with not 
> aligned at 256 bytes are not not anything we need to 
> consider. So if we need the MDS commit bit in the layout, I'd 
> be OK with moving unit size and stripe type back to the layout.
> 
> 
>

---

From: "Iyer, Rahul" <[email-masked]>
Date: Wed, 13 Jun 2007 22:09:30 -0700

> From: Trond Myklebust [mailto:[email-masked]] 
> Sent: Wednesday, June 13, 2007 8:28 PM
> To: Goodson, Garth
> Cc: [email-masked]; [email-masked]
> NFSv4.1file layout type
> > (1).  I agree we may not get very complex mappings today, 
> but I think 
> > a little flexibility in a specification isn't a bad thing.  
> We could 
> > have very large device structures (in terms of the number 
> of entries 
> > -- order

I'm confused. Why do you want to cache stripes? The way we do it now is
that we cache file data, much like regular NFS. When it is time to write
it, we do the calculation to figure out to which data server it goes.

> > reduce the amount of data the client must cache.  If every layout 
> > needs a separate device (each with multiple entries) then 
> we've failed 
> > on this point.  Thus the idea of having COMPLEX or 
> composite devices 
> > that form a shallow hierarchy.
> 
> You appear to be considering a future where each file needs a 
> completely separate striping pattern. I'm asking you whether 
> that reflects the 99.9999% case. If it doesn't then why are 
> we optimising for that case?
> With 32-bits of deviceIDs you can almost certainly cater for 
> the remaining 0.0001% of servers.
>

You're probably right. It may well be the 0.0001% case. But we aren't
optimizing for it. The SIMPLE device exists exactly for that purpose.
It's a list of multipathed netaddrs. So, the common case of striping
over 8 devices can simply be handled by a list of 8 SIMPLE devices. 

Regards
Rahul

> > Going back to (1) -- the complexity of client caching. The device 
> > cache is separate from the layout cache -- layouts have pointers (or
> > device covers (with pointers to the device structures).  The client 
> > then looks into the device structure as determined by the 
> offset and 
> > determines which physical device to go to. The devices are shared 
> > across layouts and stored separately.  Is this really that complex?
> 
> You are basically stating that the client has to allow for 
> arbitrary stripe patterns on a per-file basis instead of just 
> dealing with a limited number of patterns per filesystem.
> 
> > keep the layouts separate, but that doesn't seem much less complex 
> > than the map I propose the client keeps.
> 
> See the comment above about optimisation. If you have a 
> 32-bit address space, then you can accommodate quite a lot of 
> different striping patterns, however if the common case is 
> that the server is asking you to write in a round-robin 
> fashion to 8 or 10 data servers, then what you are proposing 
> is way overkill: it may indeed allow for more compact 
> definitions of arbitrary layout patterns, but such layouts 
> will impose arbitrary memory constraints on the clients and 
> are not a realistic proposal either on the server side (the 
> server has also to track all the information associated with 
> the layout) or on the client (which may very well be keeping 
> 100000s of files open at the same time).
>

---

From: Marc Eshel <[email-masked]>
Date: Wed, 13 Jun 2007 23:03:28 -0700

It might be useful to extend multipath_list to further scale out the 
network bandwidth, but if we do that I would like to add an option with 
which the server can tell the client if this behavior is preferred or not. 
Like it was said the initial purpose for the multipath_list was for 
fail-over. The server needs to know where to expect the I/O so it can 
prefetch data, in that case we don't want client deciding how to 
distribute the I/O. Other than that I like the new proposal. 
Marc.

---

From: Mike Eisler <[email-masked]>
Date: Thu, 14 Jun 2007 08:48:20 -0700 (PDT)

> problematic. For example,

I'm not seeing the problem. Both proposals support the same
striping pattern.

> A, B, C, D, E, F and an index array of 1, 2, 0, 3, 4, 5.

The latter is much clearer to me.

> This leads to a flattened space of A, B, C, E, F, D. 

Why would you want to do that?

Why wouldn't you simply rotate the next file's pattern
to have a flattened arrangement of:

C, A, D, E, F, B

which is trivially accomplished with the new proposal
by bumping thr first index field in the layout.

> This is actually worse as far as device caching is concerned. This is

Regardless, how worse is it? You seem to be imagining
that the server will provide all 3! * 2! = 12 combinations of
patterns. That's 12 addresses to cache in the new proposal, shared
by all files that use the device ID.

> wire. Personally, I'd rather have those extra bytes on the wire than

It isn't about bytes on the wire; it is about how the clients
will implement caches that allow the the common patterns to be
shared by layouts that have the same patterns. The flattening steps
make this harder to pull off. By putting the pattern
entitely in the address, it is trivial to pull off.

> > > 2) to move nflda_stripetype and nflda_stripe_unit_size back to
> the 
> > > layout.
> >

---

From: Garth Goodson <[email-masked]>
Date: Thu, 14 Jun 2007 11:10:21 -0700

> entitely in the address, it is trivial to pull off.

Your solution trades client cache space for complexity.  Yes, your 
solution solves the problem and can represent all striping patterns. 
The same could be said of getting rid of device structures and putting 
the entire striping pattern into the layout. For complex striping 
patterns your scheme reduces to this, which in turn increases the demand 
for client cache space even though many of the patterns may have many 
devices in common.

The real question is, is it worth increasing complexity (slightly, in my 
opinion) to avoid these cases -- I think so.  I still haven't heard why 
it is harder to implement or why supporting more complex patterns 
imposes greater constraints on client memory.  If the patterns are 
simple, like they are today with our small scale tests, the memory usage 
is the same as in today's clients.

One last comment:  The COMPLEX/SIMPLE proposal was made almost exactly 1 
year ago to this mailing list (and has not changed since).  It is a 
shame we are only getting these comments now -- but I guess that is what 
reviews are for.  For more background on the original proposal please 
see the thread starting 07/06/06.

-Garth

---

From: Garth Goodson <[email-masked]>
Date: Thu, 14 Jun 2007 11:17:50 -0700

> Or does the indices array move back into the layout?
Yeah, you are right.  In order to support these, it may degrade back 
into the layout structure we have today.

> produce that what I've proposed cannot.

I've answered this in reply to your other email.  It isn't about not 
being able to support patterns it is about the trade off in complexity 
and client cache space.

-Garth