pluggable backends: serialize backend operations on a shareset #1869

New issue

Closed

opened 2012-11-20 01:11:26 +00:00 by daira · 10 comments

daira commented

2012-11-20 01:11:26 +00:00

Now that backend operations are asynchronous, they can run concurrently. That needs to be fixed. Note that operations on different sharesets do not need to be serializable with respect to each other. (That would impose unnecessary delays.)

The simplest way to implement this is probably to have a weak cache mapping storage indices to ShareSet objects, so that there can only be one ShareSet object per actual shareset, and then use a deferred queue in the ShareSet object to serialize operations. I'm not sure exactly where the cache should go yet.

The following issue needs to be fixed before the pluggable backends code is merged to trunk (#1819). Before pluggable backends, operations that access share storage were synchronous, and so two or more such operations could not run concurrently. This is important because clients make the assumption of serializability for accesses to a mutable share on a given server (if they are the only such client, which is implied by the Prime Coordination Directive). Now that backend operations are asynchronous, they can run concurrently. That needs to be fixed. Note that operations on different sharesets do *not* need to be serializable with respect to each other. (That would impose unnecessary delays.) The simplest way to implement this is probably to have a weak cache mapping storage indices to ShareSet objects, so that there can only be one ShareSet object per actual shareset, and then use a deferred queue in the ShareSet object to serialize operations. I'm not sure exactly where the cache should go yet.

daira added the

labels 2012-11-20 01:11:26 +00:00

daira added this to the 1.10.1 milestone 2012-11-20 01:11:26 +00:00

daira self-assigned this 2012-11-20 01:11:26 +00:00

daira commented

2013-04-21 11:28:49 +00:00

Author

Hmm, but the ShareSet object returns Share objects, and accesses to those also need to be serialized, which makes it inconvenient to have the queue in the ShareSet. Maybe we need to have only one Share object at a time for a given share, but that would require Share objects to be reusable. Gahh, complicated.

Hmm, but the ShareSet object returns Share objects, and accesses to those also need to be serialized, which makes it inconvenient to have the queue in the [ShareSet](wiki/ShareSet). Maybe we need to have only one Share object at a time for a given share, but that would require Share objects to be reusable. Gahh, complicated.

daira removed their assignment 2013-04-21 11:28:49 +00:00

daira self-assigned this 2013-04-21 11:28:49 +00:00

daira commented

2013-04-23 21:05:20 +00:00

Author

Oh, I've been thinking about this in the wrong way. The operations that need to be serialized (or as-if serialized) are only remote operations, i.e. on RIStorageServer, RIBucketReader or RIBucketWriter. That simplifies things a lot.

daira commented

2013-04-23 22:53:13 +00:00

Author

A subtle complication is that because the locks are associated with sharesets, the get_sharesets_for_prefix method on a backend needs to have a rather weak specification:

    def get_sharesets_for_prefix(prefix):
        """
        Return a Deferred that fires with an iterable of IShareSet objects
        for all storage indices matching the given base-32 prefix, for
        which this backend holds shares.

        Separate locks are taken for each shareset, and nothing prevents
        sharesets matching the prefix from being deleted or added between
        listing the sharesets and taking these locks. Callers must be able
        to tolerate this.
        """

Okay, I think I understand how this will work now. We'll have a WeakValueDictionary of DeferredLocks, indexed by storage index, in each backend object. The lock object will be passed on to ShareSet, BucketReader, and BucketWriter objects for that SI, and will be used to lock the remote operations. (Most of this can be done generically with only minimal support in the backend-specific objects.) A subtle complication is that because the locks are associated with sharesets, the `get_sharesets_for_prefix` method on a backend needs to have a rather weak specification: ``` def get_sharesets_for_prefix(prefix): """ Return a Deferred that fires with an iterable of IShareSet objects for all storage indices matching the given base-32 prefix, for which this backend holds shares. Separate locks are taken for each shareset, and nothing prevents sharesets matching the prefix from being deleted or added between listing the sharesets and taking these locks. Callers must be able to tolerate this. """ ```

daira removed their assignment 2013-04-23 22:53:13 +00:00

daira commented

2013-04-24 00:08:16 +00:00

Author

Zooko asked for clarification on the problem this ticket is trying to solve.

Consider a remote operation such as RIStorageServer.slot_testv_and_readv_and_writev. The specification of that operation says that the tests, reads, and writes are done atomically with respect to other remote operations. So for example if the operation succeeds, then the reads will always be consistent with the tests.

Before pluggable backends, that was achieved by the implementation of slot_testv_and_readv_and_writev being synchronous. But for a cloud backend, the implementation cannot be synchronous because it must make HTTPS requests. Using a synchronous HTTP implementation would be a bad idea because the latency of HTTP (especially the worst-case latency) is much greater than the latency of local disk, and the reactor would be blocked for the whole sequence of requests, even though operations on other sharesets could safely proceed in parallel. So what happens is that the backend code creates a Deferrred for the result of the operation and immediately returns it. Nothing prevents the subsequent callbacks for distinct operations on a shareset from interleaving.

While developing the cloud backend, we filed this ticket for the problem and glossed over it. In practice, race conditions between concurrent operations on a shareset are rarely hit, especially when there are few concurrent operations because there is only one user. Nevertheless, the implementation is clearly incorrect as it stands.

Note that the problem isn't restricted to operations where the atomicity requirements were spelled out in the operation's specification. There were implicit assumptions about atomicity between other operations that were implemented synchronously -- for example that reads of mutable files cannot interleave with writes. This doesn't just apply to mutable sharesets, because an immutable shareset has mutable state (the bucket allocations made by RIStorageServer.allocate_buckets).

Zooko asked for clarification on the problem this ticket is trying to solve. Consider a remote operation such as `RIStorageServer.slot_testv_and_readv_and_writev`. The specification of that operation says that the tests, reads, and writes are done atomically with respect to other remote operations. So for example if the operation succeeds, then the reads will always be consistent with the tests. Before pluggable backends, that was achieved by the implementation of `slot_testv_and_readv_and_writev` being synchronous. But for a cloud backend, the implementation *cannot* be synchronous because it must make HTTPS requests. Using a synchronous HTTP implementation would be a bad idea because the latency of HTTP (especially the worst-case latency) is much greater than the latency of local disk, and the reactor would be blocked for the whole sequence of requests, even though operations *on other sharesets* could safely proceed in parallel. So what happens is that the backend code creates a Deferrred for the result of the operation and immediately returns it. Nothing prevents the subsequent callbacks for distinct operations on a shareset from interleaving. While developing the cloud backend, we filed this ticket for the problem and glossed over it. In practice, race conditions between concurrent operations on a shareset are rarely hit, especially when there are few concurrent operations because there is only one user. Nevertheless, the implementation is clearly incorrect as it stands. Note that the problem isn't restricted to operations where the atomicity requirements were spelled out in the operation's specification. There were *implicit* assumptions about atomicity between other operations that were implemented synchronously -- for example that reads of mutable files cannot interleave with writes. This doesn't just apply to mutable sharesets, because an immutable shareset has mutable state (the bucket allocations made by `RIStorageServer.allocate_buckets`).

daira commented

2013-04-24 00:14:29 +00:00

Author

Also note that even for the disk backend on the cloud-backend branch, remote operations are no longer implemented synchronously, because they share implementation with the cloud backend (for example, slot_testv_and_readv_and_writev and slot_readv are implemented generically in src/allmydata/storage/backends/base.py, not separately for each backend).

Also note that even for the disk backend on the cloud-backend branch, remote operations are no longer implemented synchronously, because they share implementation with the cloud backend (for example, `slot_testv_and_readv_and_writev` and `slot_readv` are implemented generically in `src/allmydata/storage/backends/base.py`, not separately for each backend).

daira commented

2013-04-24 12:56:45 +00:00

Author

Replying to daira:

Okay, I think I understand how this will work now. We'll have a WeakValueDictionary of DeferredLocks, indexed by storage index, in each backend object. The lock object will be passed on to ShareSet, BucketReader, and BucketWriter objects for that SI, and will be used to lock the remote operations.

Actually it doesn't need to be passed on to BucketReader and BucketWriter because they only handle individual immutable shares.

Replying to [daira](/tahoe-lafs/trac/issues/1869#issuecomment-391852): > Okay, I think I understand how this will work now. We'll have a WeakValueDictionary of DeferredLocks, indexed by storage index, in each backend object. The lock object will be passed on to ShareSet, BucketReader, and BucketWriter objects for that SI, and will be used to lock the remote operations. Actually it doesn't need to be passed on to BucketReader and BucketWriter because they only handle individual immutable shares.

daira commented

2013-04-24 13:05:46 +00:00

Author

Replying to daira:

    Separate locks are taken for each shareset, and nothing prevents
    sharesets matching the prefix from being deleted or added between
    listing the sharesets and taking these locks. Callers must be able
    to tolerate this.

should be:

    A caller will typically perform operations that take locks on some
    of the sharesets returned by this method. Nothing prevents sharesets
    matching the prefix from being deleted or added between listing the
    sharesets and taking any such locks; callers must be able to tolerate
    this.

Replying to [daira](/tahoe-lafs/trac/issues/1869#issuecomment-391852): > ``` > Separate locks are taken for each shareset, and nothing prevents > sharesets matching the prefix from being deleted or added between > listing the sharesets and taking these locks. Callers must be able > to tolerate this. > ``` should be: ``` A caller will typically perform operations that take locks on some of the sharesets returned by this method. Nothing prevents sharesets matching the prefix from being deleted or added between listing the sharesets and taking any such locks; callers must be able to tolerate this. ```

zooko commented

2013-04-24 21:44:11 +00:00

Thanks for the explanation! I'm glad you're focusing on fixing this issue!

daira commented

2013-04-25 23:39:43 +00:00

Author

Fixed in https://github.com/LeastAuthority/tahoe-lafs/commit/81e33c5aafb732810aa44121885943ec0a72ffad on the cloud-rebased2 branch, but I also want to add a test. (It's a bit tricky because it the test has to reliably trigger the situation that would be a race condition without the lock.)

Fixed in <https://github.com/LeastAuthority/tahoe-lafs/commit/81e33c5aafb732810aa44121885943ec0a72ffad> on the cloud-rebased2 branch, but I also want to add a test. (It's a bit tricky because it the test has to reliably trigger the situation that would be a race condition without the lock.)

daira commented

2013-05-01 15:04:42 +00:00

Author

Test added in 9384bd49 on the cloud-rebased2 branch. Review of the fix and test needed.

Test added in [9384bd49](https://github.com/LeastAuthority/tahoe-lafs/commit/9384bd491e09bdc46597f3aef9a7a8eb10fce296) on the cloud-rebased2 branch. Review of the fix and test needed.