HekaFS encryption layer:
Managing requests on a client and server sides
Shared and exclusive accesses. Accumulating events.
DRAFT
Transparent encryption layer brings in specific problems inherent for stackable file systems. One of such problems is conflicting read-modify-write requests, see (*) below for details.
This is in addition complicated with the "hole problem", see (**) below, and with the EOF (end-of-file) problem specific for CBC encryption mode, which is the most preferable mode in our case.
All the problems above should be resolved with active participation of a special server-side manager. So we introduce a special xlator of "features" type called for historical reasons "oplock".
Client issues (submits) read/write requests. That said, client informs an oplock xlator, that he wants to read/write a chunk of data [offset, offset + count] and asks for access to disk. Oplock xlator, in turn, grants or refuses access to disk.
If the access hasn't been provided, then oplock puts this requests in special maintained database and provide the client with unique request-id so that oplock will be able to find that request in the data-base and check its status when client will repeatedly asks for access.
So we distinguishes the following types of requests:
FIRST_REQ_TYPE /* primary request: client asks for access for the * first time */
REPEAT_REQ_TYPE /* repeated request: client has already asked for * access, oplock refused and provide the client * with request-id. * When making repeated request clients needs to * pass this request-id to oplock xlator */
Oplock (the server-side manager) provides accesses of 2 types:
. shared access . exclusive access
For any request oplock must provide an exclusive or shared access in a finite stretch of time (oplock periodically updates "local priority" of every request in the respective databases).
For every file oplock maintains "File Size Of the Future" (FSOF). FSOF is initialized as ia_size via ->fstat() at open() time. Then it gets updated by special way depending on arrived requests.
For every arrived request of FIRST_REQ_TYPE type oplock assigns one of the following statuses:
. OVRWR /* overwrite, if request doesn't change current FSOF */ . APPTRUNC /* append-or-truncate, if request changes current FSOF */
That said, if for any write request (off, count) (off + count <= FSOF), then request is OVWR, otherwise APPTRUNC. Every (expanding or shrinking) truncate request is APPTRUNC.
For every arrived APPTRUNC request oplock xlator updates FSOF by the following way:
. FSOF = off + count (in the case of appending writes); . FSOF = off (in the case of truncates).
Oplock xlator doesn't update FSOF for arrived OVRWR requests.
For every file oplock xlator maintains a Common Set of Locks (CSL), which includes a pair of the following databases:
. subset of exclusive locks (ESL); . subset of shared locks (SSL).
ESL is a queue. Every element of this queue represents a pending request, which waits for an exclusive access to the file. This element contains a record - unique (for the whole CSL!) request-id.
SSL is an rb-tree of extents. Every such extent (off, count) points to a queue of pending requests which want to write to this interval (off, count). Every such request contains a unique (for the whole CSL!) request-id.
If a primary arrived request is APPTRUNC, then oplock xlator assigns him a unique id as the next non-busy serial number and puts the request to ESL queue.
If a primary arrived request (off, len) is OVRWR, then oplock xlator assigns him a unique id as the next non-busy serial number and puts this request to SSL by the following steps:
. find all extents in SSL overlapped with (off, len); . replace all those extents and (off, len) with a single one and merge all their queues properly (in the resulted queue requests must be ordered by request-id).
All requests are sent to oplock xlator by clients via ->fgetxattr(). Offset, count, request-id, etc. are encoded to the "name" of extended attribute prefixed with a special magic string.
Checking global priorities
For every file oplock xlator maintains NEXT, an id of request which must get an access (exclusive, or shared) next time. The value of NEXT is initialized with zero value, as the first request-id is always zero. NEXT is incremented by oplock xlator with every access is granted to a secondary request.
Also for every file oplock xlator maintains NR_WRITEBACK, a number of requests, which have been provided an access and which are currently in progress. NR_WRITEBACK is incremented every time when an access is granted to some request. ->writev_cbk() decrements NR_WRITEBACK counter and drops CSL_WRITEBACK flag, if it has become 0.
For every arrived secondary request oplock checks its global priority: if its id coincides with NEXT, then arrived request has the highest global priority. Otherwise, if it is larger then NEXT, it has low global priority.
Arrived secondary request can not have id smaller then NEXT.
For every set of locks (ESL and SSL) oplock xlator maintains a number of their elements (NR_ESL and NR_SSL).
Handling primary requests by oplock xlator
If a primary APPTRUNC request has arrived and the common set of lock (CSL) is empty (NR_ESL + NR_SSL == 0) and the flag CSL_WRITEBACK is not set, then oplock . updates FSOF . sets a CSL_WRITEBACK flag and . grants an exclusive access to the client. In this case no requests are put to CSL (a kind of optimization).
If a primary OVRWR request has arrived, or a primary APPTRUNC request has arrived and CSL_WRITEBACK is set, or the common set of lock (CSL) is not empty, then oplock xlator . updates FSOF (for APPTRUNC request); . assigns a request-id; . put the request to respective set (ESL or SSL).
Handling repeated requests by oplock xlator
For any arrived secondary request oplock xlator checks its global priority (see above).
If the request has low global priority, then EBUSY is returned.
Suppose arrived request (off, len) has the highest global priority.
If CSL_WRITEBACK flag is not set, then there is no executing requests (NR_WRITEBACK must be 0 in this case), so oplock . grants respective access to the arrived request; . sets CSL_WRITEBACK flag; . increments NR_WRITEBACK counter; . increments NEXT.
If CSL_WRITEBACK flag is set and the arrived request is APPTRUNC, then exclusive lock can not be granted and oplock xlator returns EBUSY.
If CSL_WRITEBACK flag is set and the arrived request is OVRWR, then oplock checks NR_ESL.
If NR_ESL != 0, then an exclusive access is hold (in this case NR_ESL must be 1), so we can not provide shared access and oplock returns EBUSY.
Else If NR_ESL == 0, then a shared access is hold and oplock xlator looks for respective extent in the SSL rb-tree and check the local priority of the request in the respective queue.
If the request has the highest local priority, then oplock grants shared access, and . increments NR_WRITEBACK counter; . increments NEXT.
Else if the request has low local priority, then oplock xlator returns EBUSY.
With every granted exclusive access oplock returns file size encoded to "xattr" value, so that client will be able to perform proper hole conversion. This is a kind of optimization: the client also can find file size by calling ->fstat().
->writev_cbk() removes completed request from respective queue of ESL or SSL. If the respective queue of SSL has become empty, then respective extent has been removed from the rb-tree.
Comments
Exclusive locks are needed to avoid holes on a local file systems (see (**)), we need to make sure that nobody except us will change file size.
Example of conflict between appending writes:
Suppose file is 20K Process A performs ->writev(size = 10, off = 20); Process B performs ->writev(size = 10, off = 30);
Process A checks file size (20K); Process B checks file size (20K); Process A writes 10K bytes from offset 20K; Process B converts a 10K "hole" at offset 20K. Process B writes from offset 30K.
As the result we'll have unexpected 10K of zeros at offset 20K. Obviously "shared" locks don't work here in spite of writes to disjoint intervals.
Such conflicts don't take place in local file systems, which update hole metadata "in place".
Some improvements of this locking protocol are possible.
Non-precise APPTRUNC requests (with offset < file size) can be split into precise APPTRUNC and OVRWR requests to increase a number of requests that can be handled in parallel. However, this will require additional support from server and client sides.
In the degenerated case (of infinite merges) shared lock acts like exclusive one.
------------------------------------------------------------------------------
(*) http://lists.gnu.org/archive/html/gluster-devel/2011-05/msg00002.html
(**) http://fedorahosted.org/pipermail/cloudfs-devel/2011-November/000172.html
All comments, suggestions are welcome.
Edward.
On Mon, 14 Nov 2011 20:09:53 +0100 Edward Shishkin edward@redhat.com wrote:
For every arrived APPTRUNC request oplock xlator updates FSOF by the following way:
. FSOF = off + count (in the case of appending writes); . FSOF = off (in the case of truncates).
It's very important to specify *when* this FSOF update takes place. If it's done too early - when a request is received rather than when it's "issued" (allowed to proceed) - then we run the risk of mischaracterizing later-received requests as OVWR even though they're APPTRUNC at the time they're issued.
ESL is a queue. Every element of this queue represents a pending request, which waits for an exclusive access to the file. This element contains a record - unique (for the whole CSL!) request-id.
SSL is an rb-tree of extents. Every such extent (off, count) points to a queue of pending requests which want to write to this interval (off, count). Every such request contains a unique (for the whole CSL!) request-id.
What about the case where an incoming request needs to go on more than one queue? Consider the following sequence of requests.
A: offset 0, length 10 B: offset 10, length 10 C: offset 0, length 20
When A and B are received, this will result in two queues, but C needs to follow both. An rb-tree of non-overlapping extents is both insufficient for this case and too complex for common ones. In the several systems I've worked on that had to deal with the same problem of overlapping byte ranges, it has always been sufficient to maintain a single queue and let the dispatch code handle overlaps by checking the queue head against *already issued* requests (guaranteed to be few because it's under control of the dispatcher) instead of other enqueued requests (probably still few in practice but not guaranteed to be so). We don't even need a separate ESL and SSL (bad names BTW) because the conflict-detecting function can serve the same purpose.
If a primary arrived request is APPTRUNC, then oplock xlator assigns him a unique id as the next non-busy serial number and puts the request to ESL queue.
If a primary arrived request (off, len) is OVRWR, then oplock xlator assigns him a unique id as the next non-busy serial number and puts this request to SSL by the following steps:
. find all extents in SSL overlapped with (off, len); . replace all those extents and (off, len) with a single one and merge all their queues properly (in the resulted queue requests must be ordered by request-id).
All requests are sent to oplock xlator by clients via ->fgetxattr(). Offset, count, request-id, etc. are encoded to the "name" of extended attribute prefixed with a special magic string.
Checking global priorities
For every file oplock xlator maintains NEXT, an id of request which must get an access (exclusive, or shared) next time. The value of NEXT is initialized with zero value, as the first request-id is always zero. NEXT is incremented by oplock xlator with every access is granted to a secondary request.
Also for every file oplock xlator maintains NR_WRITEBACK, a number of requests, which have been provided an access and which are currently in progress. NR_WRITEBACK is incremented every time when an access is granted to some request. ->writev_cbk() decrements NR_WRITEBACK counter and drops CSL_WRITEBACK flag, if it has become 0.
For every arrived secondary request oplock checks its global priority: if its id coincides with NEXT, then arrived request has the highest global priority. Otherwise, if it is larger then NEXT, it has low global priority.
Arrived secondary request can not have id smaller then NEXT.
For every set of locks (ESL and SSL) oplock xlator maintains a number of their elements (NR_ESL and NR_SSL).
Handling primary requests by oplock xlator
If a primary APPTRUNC request has arrived and the common set of lock (CSL) is empty (NR_ESL + NR_SSL == 0) and the flag CSL_WRITEBACK is not set, then oplock . updates FSOF . sets a CSL_WRITEBACK flag and . grants an exclusive access to the client. In this case no requests are put to CSL (a kind of optimization).
If a primary OVRWR request has arrived, or a primary APPTRUNC request has arrived and CSL_WRITEBACK is set, or the common set of lock (CSL) is not empty, then oplock xlator . updates FSOF (for APPTRUNC request); . assigns a request-id; . put the request to respective set (ESL or SSL).
Handling repeated requests by oplock xlator
For any arrived secondary request oplock xlator checks its global priority (see above).
If the request has low global priority, then EBUSY is returned.
...and the client has to keep polling until it gets some other result? NO. There is no way this should be our first choice, especially since we *already have a proposal on the table* for a mechanism that uses leases instead of polling. There is no need to consider polling unless and until we conclusively determine that the alternative is insufficient.
On 11/15/2011 03:57 PM, Jeff Darcy wrote:
On Mon, 14 Nov 2011 20:09:53 +0100 Edward Shishkinedward@redhat.com wrote:
For every arrived APPTRUNC request oplock xlator updates FSOF by the following way:
. FSOF = off + count (in the case of appending writes); . FSOF = off (in the case of truncates).
It's very important to specify *when* this FSOF update takes place. If it's done too early - when a request is received rather than when it's "issued" (allowed to proceed) - then we run the risk of mischaracterizing later-received requests as OVWR even though they're APPTRUNC at the time they're issued.
FSOF is an attribute of the CSL. FSOF precisely means a size that the file will have after all requests (including the last one which updated the FSOF) in the CSL are completed.
So we update FSOF, NEXT, NR_APPTRUNC, and other CSL attributes under a special lock for CSL protection. I don't see any problems here.
ESL is a queue. Every element of this queue represents a pending request, which waits for an exclusive access to the file. This element contains a record - unique (for the whole CSL!) request-id.
SSL is an rb-tree of extents. Every such extent (off, count) points to a queue of pending requests which want to write to this interval (off, count). Every such request contains a unique (for the whole CSL!) request-id.
What about the case where an incoming request needs to go on more than one queue?
we'll jump to (**) below
Consider the following sequence of requests.
A: offset 0, length 10 B: offset 10, length 10 C: offset 0, length 20
When A and B are received, this will result in two queues, but C needs to follow both.
So in accordance with (**) extents (0, 10), (10, 10) will be replaced with a single one (0, 20) and instead of 2 queues we'll have a single one (A->B->C)
An rb-tree of non-overlapping extents is both
insufficient for this case and too complex for common ones. In the several systems I've worked on that had to deal with the same problem of overlapping byte ranges, it has always been sufficient to maintain a single queue and let the dispatch code handle overlaps by checking the queue head against *already issued* requests (guaranteed to be few because it's under control of the dispatcher) instead of other enqueued requests (probably still few in practice but not guaranteed to be so). We don't even need a separate ESL and SSL (bad names BTW) because the conflict-detecting function can serve the same purpose.
We allow different processes to write to non-overlapping regions of a file in parallel. So instead of locking the whole filer we need to lock respective non-overlapping regions. That said we need to maintain a data-base of _non-overlapping_ extents, so that every such extent has a queue of pending requests which want to write to this extent.
We can not allow processes to write to overlapping regions in parallel: it will be a conflict with the following data corruption. Respectively overlapping extents won't help us.
If a primary arrived request is APPTRUNC, then oplock xlator assigns him a unique id as the next non-busy serial number and puts the request to ESL queue.
If a primary arrived request (off, len) is OVRWR, then oplock xlator assigns him a unique id as the next non-busy serial number and puts this request to SSL by the following steps:
(**)
. find all extents in SSL overlapped with (off, len); . replace all those extents and (off, len) with a single one and merge all their queues properly (in the resulted queue requests must be ordered by request-id).
All requests are sent to oplock xlator by clients via ->fgetxattr(). Offset, count, request-id, etc. are encoded to the "name" of extended attribute prefixed with a special magic string.
Checking global priorities
For every file oplock xlator maintains NEXT, an id of request which must get an access (exclusive, or shared) next time. The value of NEXT is initialized with zero value, as the first request-id is always zero. NEXT is incremented by oplock xlator with every access is granted to a secondary request.
Also for every file oplock xlator maintains NR_WRITEBACK, a number of requests, which have been provided an access and which are currently in progress. NR_WRITEBACK is incremented every time when an access is granted to some request. ->writev_cbk() decrements NR_WRITEBACK counter and drops CSL_WRITEBACK flag, if it has become 0.
For every arrived secondary request oplock checks its global priority: if its id coincides with NEXT, then arrived request has the highest global priority. Otherwise, if it is larger then NEXT, it has low global priority.
Arrived secondary request can not have id smaller then NEXT.
For every set of locks (ESL and SSL) oplock xlator maintains a number of their elements (NR_ESL and NR_SSL).
Handling primary requests by oplock xlator
If a primary APPTRUNC request has arrived and the common set of lock (CSL) is empty (NR_ESL + NR_SSL == 0) and the flag CSL_WRITEBACK is not set, then oplock . updates FSOF . sets a CSL_WRITEBACK flag and . grants an exclusive access to the client. In this case no requests are put to CSL (a kind of optimization).
If a primary OVRWR request has arrived, or a primary APPTRUNC request has arrived and CSL_WRITEBACK is set, or the common set of lock (CSL) is not empty, then oplock xlator . updates FSOF (for APPTRUNC request); . assigns a request-id; . put the request to respective set (ESL or SSL).
Handling repeated requests by oplock xlator
For any arrived secondary request oplock xlator checks its global priority (see above).
If the request has low global priority, then EBUSY is returned.
...and the client has to keep polling until it gets some other result? NO.
Another approach is that fgetxattr (which asks for access) sleeps on the server while the request has low priority. I am not sure if it will work: we can not control the number of requests in CSL, so client will receive en error (time out is over).
There is no way this should be our first choice, especially since
we *already have a proposal on the table* for a mechanism that uses leases instead of polling.
Could you please say more? Leases are what? At least I can not find such concept related to computer science in wikipedia..
There is no need to consider polling unless
and until we conclusively determine that the alternative is insufficient.
On Thu, 17 Nov 2011 16:43:14 +0100 Edward Shishkin edward@redhat.com wrote:
It's very important to specify *when* this FSOF update takes place. If it's done too early - when a request is received rather than when it's "issued" (allowed to proceed) - then we run the risk of mischaracterizing later-received requests as OVWR even though they're APPTRUNC at the time they're issued.
FSOF is an attribute of the CSL. FSOF precisely means a size that the file will have after all requests (including the last one which updated the FSOF) in the CSL are completed.
Then that sounds like it's prone to exactly the problem I described. If we treat a request as OVWR only because a subsequent request in the CSL will extend the file, then we will mis-handle that first request.
So we update FSOF, NEXT, NR_APPTRUNC, and other CSL attributes under a special lock for CSL protection. I don't see any problems here.
This isn't a problem of multiple simultaneous data-structure updates colliding. It's a problem of simultaneous requests at a higher level, and a different kind of coordination is necessary.
ESL is a queue. Every element of this queue represents a pending request, which waits for an exclusive access to the file. This element contains a record - unique (for the whole CSL!) request-id.
SSL is an rb-tree of extents. Every such extent (off, count) points to a queue of pending requests which want to write to this interval (off, count). Every such request contains a unique (for the whole CSL!) request-id.
What about the case where an incoming request needs to go on more than one queue?
we'll jump to (**) below
Consider the following sequence of requests.
A: offset 0, length 10 B: offset 10, length 10 C: offset 0, length 20
When A and B are received, this will result in two queues, but C needs to follow both.
So in accordance with (**) extents (0, 10), (10, 10) will be replaced with a single one (0, 20) and instead of 2 queues we'll have a single one (A->B->C)
Fair enough, but an rb-tree with coalescence still seems much more complicated than a simple queue. If either is sufficient, why not choose the simpler?
If the request has low global priority, then EBUSY is returned.
...and the client has to keep polling until it gets some other result? NO.
Another approach is that fgetxattr (which asks for access) sleeps on the server while the request has low priority. I am not sure if it will work: we can not control the number of requests in CSL, so client will receive en error (time out is over).
Yes, we have to deal with the timeout case, but we have to deal with the functional equivalent with polling too (infinite polling is evil). In the vast majority of cases, a fgetxattr enqueued on the server will be released well before any timeout and provide *efficient* notification that the client may proceed.
There is no way this should be our first choice, especially since
we *already have a proposal on the table* for a mechanism that uses leases instead of polling.
Could you please say more? Leases are what? At least I can not find such concept related to computer science in wikipedia..
Leases were originally proposed by Gray and Cheriton[1]. Subsequent uses in NQNFS[2], MPFS[3], and NFSv4[4][5] are probably relevant as well.
[1] ftp://db.stanford.edu/pub/cstr/reports/cs/tr/90/1298/CS-TR-90-1298.pdf [2] http://docs.freebsd.org/44doc/papers/nqnfs.html [3] http://www.patents.com/us-6389420.html (my first patent BTW) [4] http://www.ietf.org/rfc/rfc3530.txt [5] http://www.faqs.org/rfcs/rfc5661.html
The original HekaFS proposal involving leases, which led to an extensive discussion in which you were involved, is here:
https://fedorahosted.org/pipermail/cloudfs-devel/attachments/20110708/cc6f63...
cloudfs-devel@lists.fedorahosted.org