Subject: [nfsv4] pnfs: efficient file-layout striping proposal

From: Garth Goodson <[email-masked]>
Date: Thu, 06 Jul 2006 18:12:38 -0700

Our striped file-system implementation uses a complex algorithm to 
generate a large table (1000s of entries) where each entry contains a 
data server ID.  The order of these entries dictate the striping order; 
data server IDs can be repeated multiple times within this table and the 
order may be pseudo random.  For example:

5 Data servers: 0, 1, 2, 3, 4

Stripe table example: 0 1 3 1 4 2 0 3 2 4 ...

To efficiently represent large stripe rules like this the client will 
use a huge amount of memory to store these layouts given the current 
representation; currently each table entry holds the <device_id, 
equivalent device_ids; filehandle>.

There are a number of optimizations that can be made to increase the 
amount of the layout that can be shared between files.  I'll describe 
two such optimizations, going from simplest to more aggressive.  Lastly, 
I'll describe another optimization that can be made putting these together.

1) Simplest:
------------

struct nfsv4_file_layout {
         pnfs_deviceid4          dev_id<>;
         nfs_fh4                 fh;
};

struct nfsv4_file_layouttype4 {                /* Per file */
     stripetype4             stripe_type;
     bool                    commit_through_mds;
     length4                 stripe_unit;
     length4                 file_size;
     uint32_t                stripe_devs<>;    <---- NEW
     nfsv4_file_layout       dev_list<>;
};

This modification changes the nfsv4_file_layouttype4 structure by 
introducing a new array.  This array ('stripe_devs') is simply an array 
of indices into the 'dev_list' array.

 From the example above, the stripe_devs array holds: 0 1 3 1 4 2 0 3 2 
4 ...  Each entry in the stripe_devs array indexes into the dev_list 
array.  The dev_list array is of length 5 and holds the device IDs and 
Filehandles for each of the 5 devices.  As one can see, depending on the 
length of stripe_devs, there can be a significant space reduction by 
using this structure; Filehandles aren't repeated multiple times.

If the size of stripe_devs is zero, the layout reverts to its previous 
layout behavior (striping across the entries listed in dev_list).

2) More agressive space optimization:
-------------------------------------

struct nfsv4_file_layout_simple_device4 {
     string  r_netid<>; /* network ID */
     string  r_addr<>;  /* universal address */
};

union nfsv4_file_layout_device4 switch (file_layout_device_type) {
     case SIMPLE:                                 <--- NEW
         nfsv4_file_layout_simple_device4 dev;    <--- NEW
     case COMPLEX:                                <--- NEW
         pnfs_deviceid4 dev_list<>;               <--- NEW
     default:
         void;
};

This step adds slightly more complexity.  It replaces the device ID for 
file layouts with a union of either a 'SIMPLE' or a 'COMPLEX' device.  A 
simple device is the same as the device structure we had in the past 
({r_netid<>, r_addr<>}).  We have added a COMPLEX device which can be 
constructed out of multiple SIMPLE devices.  My initial feeling is that 
the COMPLEX device is simply an array of other SIMPLE device IDs.

We could extend this such that COMPLEX devices may be made up of other 
COMPLEX devices.  In this case there MUST be no loops, each device must 
resolve down to a simple device.  My feeling is that we won't have 
complicated structures of devices, just COMPLEX devices made up of 
simple devices.

There are also two ways of striping over these COMPLEX devices.  1) 
distributing the stripe_unit uniformly across all devices once the 
device list has been flattened.  2) distributing the stripe_unit across 
the top level devices and let the next level take a share of the top 
level node's.

E.g.  With Complex devices 1 and 4 constructed as such:
1 -> {2,3} 4 -> {5,6}

Device tree:
   1       4
  / \     / \
2   3   5   6  <- leaf devices (actual data servers)

If stripe unit is 256KB, then in (1) 2, 3, 5, 6 uniformly striped with 
256KB on each node.  In (2) 2,3 each have 128KB (half of 1's 256KB), 5,6 
also each have 128KB (half of 4's 256KB).

I think my preference is for the simplicity of (1). The main idea is 
that once the client has this set of devices, it flattens it and uses it 
as the device list over which to stripe data.

3) One more optimization -- offsets into COMPLEX devices...
------------------------

It may also be useful to shift the layouts of files slightly for each 
new file.  For instance using the above example of: 0 1 3 1 4 2 0 3 2 4. 
  The second file created may use the same layout, shifted 1, or 
starting at offset 1, wrapping offset 0 to the end: 1 3 1 4 2 0 3 2 4 0.
Today, these two files would have two totally different layouts -- 
although there really is a lot of sharing between them.

In order to achieve the greatest degree of sharing it is necessary to 
encode the starting offset within the table.  The offset can either be 
given in the layout itself as an offset within a complex device (in the 
'nfsv4_file_layout' structure), or it can be given within the COMPLEX 
device structure; this allows complex devices to be defined in terms of 
another (e.g., device B is device A with a shift of X).

My preference is the former: adding an offset to the 'nfsv4_file_layout' 
structure indicating the starting offset within the complex device. 
This works well if we either a) limit ourselves to complex devices 
comprised of simple devices, b) flatten complex devices completely 
before use.

Lastly: Device Equivalence
--------------------------

COMPLEX devices make it harder to think about device equivalence for 
multi-pathing.  Device equivalence is currently indicated by an array of 
device ids ('dev_id<>') within the 'nfsv4_file_layout' structure.

Since COMPLEX devices can be constructed from multiple devices, it may 
not make sense for device equivalence to be conveyed through the layout.

My suggestion is to push it down to the device structure 
('nfsv4_file_layout_device4') by changing the SIMPLE device type to be 
an array of equivalent SIMPLE devices.

So, the following changes:

struct nfsv4_file_layout {
         pnfs_deviceid4          dev_id;  <--- Changed
         nfs_fh4                 fh;
};

union nfsv4_file_layout_device4 switch (file_layout_device_type) {
     case SIMPLE:
         nfsv4_file_layout_simple_device4 dev<>;  <--- Changed
     case COMPLEX:
         pnfs_deviceid4 dev_list<>;
     default:
         void;
};

Conclusion
----------

For our implementation these optimizations can result in a huge space 
savings at a small increase in complexity.  It allows the client to 
share layouts and device striping patterns much more efficiently.  It 
also allows for complex stripe patterns.

Please read this carefully and provide constructive feedback.

PS. Thanks to Dave Noveck for helping with this design.

-Garth

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

---

From: Marc Eshel <[email-masked]>
Date: Thu, 6 Jul 2006 22:11:39 -0700

Garth,
There is no question that number one (Simplest) is a big space saver. 
Repeating the FH for each is segment in a one to one mapping is silly. So 
I definitely vote for the first option. I am not sure that the second 
option is saving much more so I would vote for skipping the additional 
complexity unless you have some realistic examples that show the actual 
space saving. I would vote against the last option to have the client 
share parts of the layouts among different files, it sounds to complicated 
for the client to manage and it is a big change to introduce at this 
point.
Marc.