On 05/30/2011 10:04 AM, Edward Shishkin wrote:

On 05/27/2011 11:52 PM, Edward Shishkin wrote:

...

fixed bad tabs/whitespaces stuff

/*

• Oplock translator:
• Serialize rmw requests submission with a quarantee
• of progress.
• Maintain per-inode queues of submission requests;
• Glossary:
• Read-modify-write request (rmw-request)
• is a write request, which contains extra-data
• to write. Such requests are specific to atoimic
• cipher modes.
• Submitting an rmw request can make other pending
• rmw-requests out-of-date, and it will lead to loss
• of operations. In order to prevent this we serialize
• rmw-requests submission and make sure that every
• request which is going to be submitted contains
• uptodate information.

I don't think there's any reasonable way, without wire-protocol changes, to pass a serial number along with a write. The server needs to be able to associate a write request which consumes a lease with an earlier request that established the lease based only on the write request's "normal" characteristics such as fd/start/end. Another way of looking at it is that those normal characteristics can be combined/encoded into an ID for the write which ends a lease, and that same ID can be used in the request that begins a lease. Since the "read" part of a read-modify-write needs to transfer at most 2*(atom_size-1) bytes, it need not be an actual readv but a "magic" fgetxattr containing the ID as part of the xattr name. Thus, we end up with the following sequence.

* client generates the ID as encode(fd,offset,length)

* client generates the xattr name as "trusted.oplock." + ID

* client issues an fgetxattr using the generated name

* server checks for conflicts, either grants a lease or queues the fgetxattr behind one that's already granted

* (assuming grant) client regains control, along with head/tail pieces for the read-modify-write

* client encrypts and issues writev

* server processes writev, ends lease, unblocks any conflicting fgetxattr

The only case where this seems to fall down is when the server receives two requests with the same ID on the same connection (i.e. from the same client). Is that a retry/renewal or a separate request? Only the client knows, but the server doesn't actually need to care. The only reason a client should be retrying is after a connection timeout, so the sequence of events would be as follows:

* client issues a lease-acquire fgetxattr, which for some reason doesn't complete for a long time

* client's connection times out and it establishes a new one

* client retries its lease-acquire, which the server sees on a different connection than the original

* server detects conflict, queues the second lease-acquire

* first lease-acquire times out, server throws it away

* . . . progress is made . . .

* second lease-acquire reached the front of the queue, is granted *with current head/tail data*

* client completes read-modify-write normally and correctly

I think a lot of the logic below still applies; mostly the change is to how we communicate information between client and server.

...

• Request for submission (sub-request)
• An element in inode's rmw_queue. A sub-request is
• issued for every new rmw-request in the case when
• the file is "busy" (i.e. the rmw_queue is not empty).
• In this case a sub-request with a unique serial number
• is issued and put to the rmw-queue. With this number
• the process will uptodate and try to re-submit the
• rmw request later.
• struct _inode {
• ...
• gf_lock_t rmwq_lock; /* protects the rmw-queue */
• rmw_queue_head_t head; /* queue of submission requests */
• uint64_t generation; /* last allocated serial number */
• }

Extending an existing structure like this would require a patch to code that's part of another project/package. That means we'd have to overcome any resistance upstream to have the patch accepted, then wait for it to work its way through both Gluster's release process and the distro-specific (e.g. Fedora) packaging on a version that includes it. That could mean months before we even get back glusterfs-devel headers that we can compile against, let alone executables we can run against. Therefore it's *highly* preferable to use the inode_ctx functions to associate our own private data with an inode, instead of patching.

...

• lock_queue(inode) is LOCK(&inode->rmwq_lock)
• unlock_queue(inode) is UNLOCK(&inode->rmwq_lock)

*/

/*

• oplock_witev():
• Pre-condition: a read-modify-write request rmw_req
• has been received.
• Check if we can proceed with this.
• If we can not, then allocate a serial number and issue
• a sub-request if the rmw-req is new (i.e. it doesn't
• have a serial number and we didn't try to submit this
• request before). Than return error to re-submit this
• later.

*/

oplock_witev() { lock_queue(inode);

if (the inode's rmw_queue is empty) {

empty: /* * submit this rmw_req, but first * we need to "occupy the queue */ allocate a serial number; create a sub-request and insert it to the queue"; goto submit; } else { if (is_new_request(rmw_req)) { /* * queue is not empty, so we are not * allowed to proceed (there are * requests with higher priorities */

	allocate a serial number,
	create a sub-request and insert it to the queue;

	/*
	 * refuse to proceed, will be
	 * restarted with this serial
	 * number later
	 */
	goto refuse;
}
/*
 * queue is not empty and rmw_req is
 * not new (has serial number)
 */

next: find the next sub_req in the queue; if (sub_req is too old, timeout is over) { /* the owner has died */ remove sub_req; if (rmw_queue is empty) goto empty; else goto next; } if (serial_number_of(rmw_req) != serial_number_of(next_sub_req){ /* * this is not our turn to submit */ refuse: unlock_queue(inode); /* * refuse to proceed, * will be re-submitted */ op_errno = EBUSY; STACK_UNWIND(); return; } submit: /* * our turn to submit, * allow to proceed */

The above might be a bit clearer this way:

/* Called from fgetxattr, writev, writev_cbk, "cleaner" thread. */ drain_queue (queue) { while (!is_empty(queue) && is_timed_out(queue->head)) { /* Client's request is waiting, must reply */ STACK_UNWIND(queue->head); dequeue_and_discard(queue); } }

...

lock_queue(); if (!is_empty(queue) && id_match(queue->head,new_req)) { status = OK; } else { status = LEASE_EXPIRED; } unlock_queue(); if (status == OK) { STACK_WIND(...); } return status;

Note that things become more complex if we allow a fully aligned write to be processed as a single writev without a preceding lease-acquire read/getxattr. In that case we do want to check for conflicting leases, but create a lease "on the fly" and let the write progress if it's fully aligned, so the middle part of the snippet above becomes:

if (is_fully_aligned(new_req)) { if (is_empty(queue)) { status = OK; } else { status = BLOCKED; } create_and_enqueue_request(new_req); } else { /* empty/id_match checks as above */ }

Hmm, bad... this is out turn to submit, but rmw-request can be not uptodate. So we'll need to visit server at least 2 times. The common scenario is:

1. go to the server side and put a sub-request to the queue, return EBUSY to the client.
2. check the queue. If this is our turn to submit, then update a rmw-request on the client side and go back to the server to submit (our sub-request is waiting for us in the queue). Otherwise repeat step (2).

...

unlock_queue(inode);
STACK_WIND();
return;

} }

/*

• this is called only if we
• were allowed to submit.

*/ oplock_writew_cbk() { if (op_ret> = 0) { /* * it was our turn to submit, and our * rmw-request has been successfully * submitted */ lock_queue(inode); remove the sub-request from the queue; unlock_queue(inode); } else { /* * it was our turn to submit, but error * happened in other layers, so don't remove * sub-request, will retry. */ STACK_UNWIND(); } }

I think we want to dequeue and STACK_UNWIND regardless, and *also* STACK_WIND if another request was blocked behind us. For example:

lock_queue(); old_req = dequeue_request(queue); /* this one must be ours */ drain_queue(); need_wind = !is_empty(queue); unlock_queue(); if (need_wind) { STACK_WIND(queue->head); } STACK_UNWIND(old_req); This depends on the STACK_WIND working regardless of whether the request we're unblocking is an fgetxattr (for an unaligned read-modify-write) or a writev (for an aligned write). I think we can ensure that by using the "stub" mechanism developed for the dht translator; if not, we'll have to store flags etc. and deal with it ourselves.

On 06/02/2011 04:39 PM, Edward Shishkin wrote:

...

I don't think there's any reasonable way, without wire-protocol changes, to pass a serial number along with a write.

It's a pity: I kept a hope that there are "legal" means of inter-translator communication..

There are, in the form of "xattr" operations, but those are separate network requests. If we want to pass additional information *as part of the read or write request*, that requires a protocol change.

...

The server needs to be able to associate a write request which consumes a lease with an earlier request that established the lease based only on the write request's "normal" characteristics such as fd/start/end.

Our initial goal is to serialize writes to the same atoms, i.e. writes with the same (fd, start, end). So making associations based on those parameters would be a logical mistake. Since per-atom serialization is not easy to implement, I suggest to consider per-file serialization for now.

The start/end can be tweaked to the same atom boundaries we'll use for the final write, but as a starting point file granularity is probably OK. We're not optimizing for fine-grain concurrent access to the same file; we just need to make sure we don't corrupt data when there's occasional contention.

Thus, any rmw-request should have a unique id on the server. Yes, we can obligate clients to generate such ids, so that server won't need to pass it to the client. I think we need a simple generator, which increments the last used value. No collisions are possible.

Since the ID is only used for conflict detection, which is only done on the server, I don't think the client even needs to see it. As soon as the fgetxattr reaches the head of the queue, the server can return the head/tail bits and the client can proceed without an ID (which it has no way to pass back anyway).

So you suggest to pass a generated id to the server as an xattr value for some "magic" xattr name via ->fgetxattr(). Seems to be interesting idea. Oplock will need to terminate such calls to not involve IO operations though. I'll try to develop such approach.

Yes, the magic fgetxattr starts out doing three things on the server.

(1) Generates a unique ID based on inode and (tweaked) start/end.

(2) Adds an entry with that ID.

(3) Checks the queue.

When the entry reaches the head, which will be immediately unless there's contention, it does two more things.

(4) Reads the unaligned head/tail bits.

(5) Returns those bits to the client.

This is all part of one network round trip, with a possible delay in the middle when there's contention, leaving only the final write. Without keys on the server, I don't think we can do any better than that.