Subject: [nfsv4] File Layout change proposal

From: "Anatoly Pinchuk" <[email-masked]>
Date: Wed, 28 Nov 2007 12:34:50 -0800

I have been thinking about improving file layout. Here is an example of
how file layout structures might look like.

Highlights of file layout changes
- The existing two layer (device - layout) hierarchy is extended into
three (device - layout item - layout) layered one. As a result of this
only one layout4 structure is returned as a result of LAYOUTGET.
According to the current specification an array of layout4 is returned.
- Packing type (sparse/dense) and COMMIT operation acceptance
(NFL4_UFLG_COMMIT_THRU_MDS) are defined per data server instead of the
layout.
- Stripe unit size is defined per device instead of the layout.
- Number of data file handles in the layout item is not linked to
packing and can be equal to number of data server lists or stripe units.

/* Data server address type */
typedef netaddr4    ds_addr4;

const NFL4_DS_UFLG_DENSE		= 0x00000001;
const NFL4_DS_UFLG_COMMIT_THRU_MDS	= 0x00000002;

/* Data server structure to be used in a device definition. In
particular, this allows us to have packing type specified per data
server. A given layout can be based on both sparse and dense data
servers. This gives us the flexibility of having a given client file
spread between the data servers with different packing implementation.
This is not allowed currently. */
struct nfsv4_1_fl_ds4 {
	ds_addr4	nflds_addr;
	uint32_t	nflds_util;
};

nflds_addr
Data server address.

nflds_util 
A compact representation of whether dense or sparse packing is used
(nflds_util & NFL4_DS_UFLG_DENSE). Also the field defines if the client
SHOULD send COMMIT operations to the data server or metadata server
(nflda_util & NFL4_DS_UFLG_COMMIT_THRU_MDS).

/* List of equivalent data servers */
typedef nfsv4_1_fl_ds4    nfsv4_1_file_layout_multipath_list4<>;
The same data server address MUST NOT be presented more than once in the
list. 

const NFL4_DEV_UFLG_STRIPE_UNIT_SIZE_MASK = 0xFFFFFFC0;

/* Encoded in the da_addr_body field of type device_addr4 and represents
a device */
struct nfsv4_1_file_layout_ds_addr4 {
	nfsv4_1_file_layout_multipath_list4
nflda_multipath_ds_list<>;
	uint32_t
nflda_stripe_indices<>;
	uint32_t					nflda_util;
};

nflda_multipath_ds_list
An array of lists of data servers, where each list can be one or more
elements and	each element represents an equivalent data server.

nflda_stripe_indices
An array of indexes used to index into nflda_multipath_ds_list. The
number of elements in nflda_stripe_indices is always equal to the stripe
count.

nflda_util
Defines stripe unit size
(nflda_util & NFL4_DEV_UFLG_STRIPE_UNIT_SIZE_MASK). Stripe unit size is
considered as part of data distribution and, therefore, belongs to the
device.

Each element in nflda_multipath_ds_list MUST be referenced by at least
one stripe index from nflda_stripe_indices array. Thus number of the
elements in nflda_stripe_indices array is more or equal than in
nflda_multipath_ds_list one.

/* The layout item corresponds to a segment of the client file. It
allows the segment to be represented with different devices. Thus each
segment can be of different length, based on its own data file handles,
array of equivalent data servers, and/or striping */
struct nfsv4_1_fl_item4 {
	deviceid4	nfli_deviceid;
	offset4	nfli_off;
	uint32_t	nfl_first_stripe_index;
	nfs_fh4	nfli_fh_list<>;
};

nfli_deviceid
Device ID maps to a value of type nfsv4_1_file_layout_ds_addr4.

nfli_off
Offset of first byte of the client file the layout item is applicable
to. In segments (see above) terminology it is offset of the first byte
of the corresponding segment.

nfl_first_stripe_index
The index into the first element of the nflda_stripe_indices array to
use.

nfli_fh_list
An array of data server file handles. Once we mapped the handle into
nflda_multipath_ds_list, it is used for all data servers in the list.
The mapping of handles into the lists is defined below. Number of
elements in nfli_fh_list MUST be
- Zero means that the data file handles used for each data server list
MUST be the same as the one returned by the OPEN operation from the
metadata server.
- One element in the list means that each data server MUST use the same
file handle what is specified in nfli_fh_list[0].
- The number of elements as nflda_multipath_ds_list array. Thus, in this
case, when issuing an I/O to any data server in
nflda_multipath_ds_list[nflda_stripe_indices[X]], the filehandle in
nfli_fh_list[nflda_stripe_indices[X]] MUST be used.
- The number of elements as in nflda_stripe_indices array. Thus, in this
case, when issuing an I/O to any data server in
nflda_multipath_ds_list[nflda_stripe_indices[X]], the filehandle in
nfli_fh_list[X] MUST be used.

Note that number of the data file handles is not related to sparse/dense
packing anymore.

/* file layout - encoded in the loc_body field of type layout_content4
*/
typedef nfsv4_1_fl_item4	nfsv4_1_file_layout4<>;

A nfsv4_1_file_layout4 fl MUST satisfy to the following consistency
rules.
- fl[i].nfli_off < fl[j].nfli_off, for i < j. The offset presented by
subsequent layout items within a layout MUST be increasing.
- if fl[i] is not last item in the array, then it covers client bytes
exactly from fl[i].nfli_off to fl[i+1].nfli_off - 1. There MUST not be
any holes in view of client range provided by the layout.
- bytes range ([lo_offset, lo_offset + lo_length - 1]) returned to the
client in layout4 structure is completely covered with corresponding
file layout fl packed into the same structure

File layout SHOULD NOT contain the items not covering bytes from the
range returned in layout4 structure - [lo_offset, lo_offset + lo_length
- 1].

The file layout definitions above establish a mapping between data file
handles and multi-set of nfsv4_1_fl_ds4 structures. The multi-set MS for
a handle fh is constructed by processing all the layouts of a given
client file. For each layout having fh we identify all the data server
lists the handle is used to do IO. Then we add each nfsv4_1_fl_ds4
structure from the lists to the multi-set MS. The mapping is called
overlapping if for some handle fh there are two elements ds1 and ds2
from the multi-set the handle is mapped into, such that ds1.nflds_addr
equal to ds2.nflds_addr and dense packing is used in ds1 or ds2. The
layout items defined in the system MUST NOT introduce overlapping
mapping. As follows from the definition, overlapping is not possible if
dense packing is not used. In practice, even if dense packing is defined
for some data servers, there is no need to build that map. The only
requirement is to generate the layout items in such way that mapping is
not overlapping if we build one.

Here is an algorithm for performing IO using the above data structures.
It uses the file layout returned by the metadata server and client file
offset provided to determine the data server network addresses and data
file handle, length, offset. 

Let's assume that fl represents the nfsv4_1_file_layout4 layout and
client_off represents the client offset provided. The first step is to
select appropriate nfsv4_1_fl_item4 fli using client_off and fl. The
layout item fli would be the item with maximum nfli_off which is less or
equal than client_off. Also, using fli we can get corresponding
nfsv4_1_file_layout_ds_addr4 dev. 

Given that a pattern allows data server list can be used more than once
in a given stripe, we need an auxiliary function ds_stripe_count(i, j,
k). The function is used to calculate data file offset for dense packing
and handle per data server list distribution (see handle_per_su below).

This function essentially counts the number of references to the server
list nflda_multipath_ds_list[k] in array nflda_stripe_indices from
element i to item j. If i is more than j then wraparound occurs. For
example if nflda_stripe_indices array is
{1, 2, 1, 2, 0, 1} then
ds_stripe_count(2, 5, 0) = 1,
ds_stripe_count(5, 1, 1) = 2,
ds_stripe_count(0, 2, 2) = 1.

More formally the function is defined for all i, j, k such that 
0 <= i, j < stripe_count 
0 <= k < ds_list_count

Another auxiliary function we need is prev(i). The function is defined
for all 0 <= i < stripe_count as
prev(i) = i - 1, if i > 0
prev(0) = stripe_count - 1;

The value of ds_stripe_count(i, j, k) equal to number of occurrences of
k in elements dev.nflda_stripe_indices[i], ...,
dev.nflda_stripe_indices[j]. Definitions of stripe_count and
ds_list_count are given below. 

/* various numbers and sizes associated with the layout item and its
device */
fh_count = number of elements in fli.nfli_fh_list;
ds_list_count = number of elements in dev.nflda_multipath_ds_list;
stripe_count = number of elements in dev.nflda_stripe_indices;
stripe_size = dev.nflda_util & NFL4_DEV_UFLG_STRIPE_UNIT_SIZE_MASK;
stripe_width = stripe_count * stripe_size;

/* offsets and indices */

/* offset inside a layout item */
rel_off = client_off - fli.nfli_client_off;

/* number of times a pattern has been repeated */
stripe_rep_idx = floor(rel_off / stripe_width);

/* the stripe unit within the stripe that this offset applies to */
stripe_unit_idx = floor((rel_off % stripe_width) / stripe_size);
stripe_unit_idx = (stripe_unit_idx + nfl_first_stripe_index) %
stripe_count;

/* the offset in the stripe unit the client offset represents */
stripe_unit_byte_off = rel_off % stripe_size;

/* index into data servers list array */
ds_list_indx = dev.nflda_stripe_indices[stripe_unit_idx];

/* handle_per_su indicates if file handle is defined per data server
list or stripe unit */

/* calculate data file handle */
switch (fh_count) {
	case 0:
		handle_per_su = FALSE;
		fh = filehandle returned by OPEN;
		break;
	case 1:
		handle_per_su = FALSE;
		fh = fli.nfli_fh_list[0];
		break;
	case ds_list_count:
		handle_per_su = FALSE;
		fh = fli.nfli_fh_list[ds_list_idx];
		break;
	case stripe_count:
		/* this is the only case of file handle per stripe unit
*/
		handle_per_su = TRUE;
		fh = fli.nfli_fh_list[stripe_unit_idx];
		break;
	default:
		throw a fatal exception;
		break;
}

/* the maximum number of bytes for IO in stripe unit */
len = stripe_size - stripe_unit_byte_off;

/* list of equivalent data servers to perform IO to */
ds_list = dev.nflda_multipath_ds_list[ds_list_indx];

/* number of equivalent data servers in ds_list */
ds_count = number of elements in ds_list;
for ( i = 0; i < ds_count; i++ ) {
	/* define data server for already defined data file handle fh
and 	length len */
	ds = ds_list[i];
	/* The actual calculation is based on whether DENSE or SPARSE
packing 	is used. Calculate offset for already defined fh, len,
and ds */
	if ( ds.nflds_util & NFL4_DS_UFLG_DENSE ) {
		/* rep_off_count counts number of the stripe units of
stripe 		related to data file with handle fh. su_off_count is
similar but 		counts stripe units from nfl_first_stripe_index
to 				prev(stripe_unit_idx) */
		if  ( handle_per_su == TRUE ) {
			/*only one reference for fh in case of handle
per stripe 			unit distribution */
			rep_off_count = 1;
			su_off_count = 0;
        	}
		else {
			/* this is the only case when we need
ds_stripe_count() 			and prev() functions */
            	rep_off_count = ds_stripe_count(0, stripe_count,
ds_list_indx);
			if ( nfl_first_stripe_index == stripe_unit_idx )
su_off_count = 0;
            	else
				su_off_count =
	
ds_stripe_count(nfl_first_stripe_index,
prev(stripe_unit_idx), ds_list_indx);
		}
		off = (rep_off_count * stripe_rep_idx  + su_off_count )
* 					stripe_size +
stripe_unit_byte_off;
	}
	else
		off = client_off;

	/* Now we can do IO using ds.nflds_addr, fh, off, and len */
}

- Anatoly

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