Support Multi-Key Distributed Locking for Composite Operations

[moeen]

Description

We need a feature to acquire distributed locks on multiple keys simultaneously. The solution must:

• Acquire locks in a deterministic order (e.g., alphabetical) to prevent deadlocks.
• Return a composite lock that implements IDistributedLock so it can be used in a using block.
• Roll back all acquired locks if any single lock cannot be acquired within a timeout.

Real-World Use Case

Imagine we have three data banks (A, B, C) and users want to extract records from them. Each bank uses a cursor to mark the last retrieved record so that subsequent extractions don’t return duplicates. Users might request a combination—say, N records from Bank A, M from Bank B, and O from Bank C—in a single operation. To ensure data consistency and proper cursor advancement without overlap, we need to atomically lock the selected banks during the extraction.

Example Code Use Case

// Operation: extract records from Banks A, B, and C simultaneously.
var keysToLock = new[] { "BankA", "BankB", "BankC" };
var compositeLock = await distributedLockProvider.TryAcquireMultiLockAsync(keysToLock, TimeSpan.FromSeconds(2), cancellationToken);

I’m ready to implement this feature. Please let me know if you have any feedback or additional requirements.

[madelson]

@moeen thanks for your interest in the library. I can think of 2 ways to go about this depending on what exactly you're trying to achieve. One approach is to build a "composite" IDistributedLock instance composed of multiple other instances. This is relatively easy to implement, instantly supports all providers, and has other potential use-cases (see #38).

What this approach doesn't do is enable you to acquire multiple locks in a single round-trip to the provider (see what was asked for in #50). Think about issuing a single SQL Server query that calls sp_getapplock many times with conditional logic to bail out in the middle. If we were to support that, it needs to be implemented provider-by-provider and isn't going to be feasible for all of them. I suspect this code will be fairly complex to get right.

In theory, we could also build approach 1, and then circle back and do approach 2. You could imagine that the composite lock from approach 1 is able to inspect its internal lock list and determine whether lock attempts can be combined.

Anyway, as a starting point, which feature set more matches what you were hoping for? I have thoughts about the implementation path for each.

[moeen]

Thanks @madelson for the reply!

I was initially considering Approach 1 (composite IDistributedLock instances) for its simplicity and flexibility. However, I understand your point about the inefficiency of multiple round-trips. So, I agree that Approach 2 (single round-trip multi-lock acquisition) is the way to go.

I can think on implementing Approach 2 for the following providers:

• Redis
  • Use Lua scripts to atomically acquire multiple locks in one call.
• SQL Server
  • Transactions with sp_getapplock.
• PostgreSQL
  • Advisory locks within a transaction.

We’re currently using Redis for our locking mechanism, and I think Redis is one of the most straight-forward ones to implement.

For the other providers (MySQL/MariaDB, Oracle, Azure Blobs, Apache ZooKeeper, lock files, and OS Global WaitHandles), I’ll need to research the best approaches to achieve atomic multi-lock acquisitions.

Any insights or recommendations on implementing this would be greatly appreciated!

[madelson]

@moeen I wasn’t trying to imply that option 2 was the “right” answer, more that we should pick a direction depending on what you’re hoping to accomplish.

Anyway, let me know what you decide; I can point you in the right direction.

[moeen]

Thanks @madelson!

After thinking it through, I don’t find any issues using multi-key locks with multi-round-trips (composite IDistributedLock instances) for our use case, aside from the added latency.

Since it’s simpler, I’d like to go ahead and start with implementing the composite IDistributedLock.

Could you guide me on the best direction to take for this?

[madelson]

Sounds good @moeen. I should have a chance to engage on this soon.

[madelson]

@moeen I've thought a bit about this and I think what makes the most sense is to add 4 new methods to DistributedLockProviderExtensions:

public static ValueTask<IDistributedSynchronizationHandle?> TryAcquireAllLocksAsync(
    this IDistributedLockProvider @this,
    IReadOnlyList<string> names,
    TimeSpan timeout = default,
    CancellationToken cancellationToken = default);

// + sync version

public static ValueTask<IDistributedSynchronizationHandle> AcquireAllLocksAsync(
    this IDistributedLockProvider @this,
    IReadOnlyList<string> names,
    TimeSpan? timeout = null,
    CancellationToken cancellationToken = default);

// + sync version

• The semantics of this is that either all locks are acquired or none of them are (e.g. if it acquires 2 and the third fails, it releases the 2 that were acquired before returning).
• The order of acquisition matches the order of lock names in the IReadOnlyList; leave it up to the caller to decide whether they want to order alphabetically or in some other way. I'm going for principle of least surprise here but also different lock types disagree on how name equality works e.g. whether it is case-sensitive so its safest not to make assumptions.
• If the list of names is empty, acquisition and release are both noops
• The sync methods should delegate to the async methods using SyncViaAsync
• The Acquire method should delegate to the TryAcquire method using ThrowTimeoutIfNull()
• A nice thing about this API is that it can easily be extended to support efficient batched locking in the future. For example, you could imagine code like this:

public static ValueTask<IDistributedSynchronizationHandle?> TryAcquireAllLocksAsync(...)
{
    if (@this is IBatchDistributedLockProvider batchProvider)
    {
        return batchProvider.TryAcquireAllLocksAsync(...);
    }

    // portable implementation
}

This implementation path is really oriented around the idea of acquiring multiple locks on the same provider, which seems like a good fit for the use-case you describe. It does require you to use a provider instance instead of a lock instance, though.

Does this make sense?

[moeen]

@madelson That totally makes sense and is suitable for our use case. And we are already using provider instance. Thanks!

[madelson]

@moeen if you end up building this out, feel free to contribute it :-)

[moeen]

@madelson Sorry I wasn’t able to work on this until the weekend.

After running some tests, here’s what I’m proposing:

• Composite handle
  Introduce CompositeDistributedSynchronizationHandle (implements IDistributedSynchronizationHandle) that wraps multiple handles and links their HandleLostTokens into a single CancellationTokenSource.

• Provider extensions
  In GenerateProviders, add two new methods on IDistributedLockProvider:

  • TryAcquireAllLocksAsync(IReadOnlyList<string> names, TimeSpan timeout = default, CancellationToken cancellationToken = default)
    Acquires each lock in sequence and returns null (disposing any already-acquired locks) if any fail within the timeout.

  • AcquireAllLocksAsync(IReadOnlyList<string> names, TimeSpan? timeout = null, CancellationToken cancellationToken = default)
    Same semantics but throws TimeoutException on failure.

My only hesitation is that these new methods are noticeably longer than the existing single-lock helpers (e.g. TryAcquireLock/AcquireLockAsync).

Does this approach fit the project’s conventions? If so, I’ll open a PR.

[madelson]

Introduce CompositeDistributedSynchronizationHandle (implements IDistributedSynchronizationHandle) that wraps multiple handles and links their HandleLostTokens into a single CancellationTokenSource.

Makes sense. This should be an internal type in DistributedLockProvider.Core.

In GenerateProviders, add two new methods on IDistributedLockProvider

I'd forgotten that the extensions methods are auto-generated. However, this actually works nicely because we'd like to support versions of this method for the other sync primitives too:

• (Try)AcquireAllReadLocksAsync
• (Try)AcquireAllWriteLocksAsync
• (Try)AcquireAllUpgradeableReadLocksAsync
• (Try)AcquireAllSemaphoresAsync

We'd also like to have synchronous versions alongside the async versions (use the SyncViaAsync system to achieve this). This works nicely with how GenerateProviders is structured since we're basically creating an All version for each Acquire method and it is already set up to operate on each Acquire method.

My only hesitation is that these new methods are noticeably longer than the existing single-lock helpers

This is a good callout. Luckily, I think we can factor out all of the logic into a single internal helper method, perhaps on CompositeDistributedSynchronizationHandle:

internal sealed class CompositeDistributedSynchronizationHandle
{
    ...

    public static ValueTask<IDistributedSynchronizationHandle> TryAcquireAllAsync<TProvider>(
        TProvider provider,
        Func<TProvider, string, TimeSpan, CancellationToken, ValueTask<IDistributedSynchronizationHandle>> acquireAsync,
        IReadOnlyList<string> names,
        TimeSpan timeout,
        CancellationToken cancellationToken)
    {
        // common impl here
    }
}

This way, TryAcquireAllLocks can be implemented as:

public static TryAcquireAllLocksAsync(this IDistributedLockProvider @this, IReadOnlyList<string> names, TimeSpan timeout = default, CancellationToken cancellationToken = default) =>
    CompositeDistributedSynchronizationHandle.TryAcquireAllAsync(
        @this,
        static (p, n, t, c) => p.TryAcquireLockAsync(n, t, c),
        names,
        timeout,
        cancellationToken);

This minimizes the amount of logic in the generated code. Does that make sense?

[moeen]

@madelson That all makes sense. The only concern left for me is the IDistributedSemaphore and IDistributedUpgradeableReaderWriterLock helper implementations since they have different method signatures than others:

• IDistributedSemaphore helpers take an extra int maxCount param.
• IDistributedUpgradeableReaderWriterLock helpers return IDistributedLockUpgradeableHandle instead of IDistributedSynchronizationHandle.

[moeen]

@madelson Any thoughts on this?

[madelson]

@moeen sorry I missed your previous message.

I think you’re correct regarding semaphore.

However, for upgrade operations we can’t offer composites since there’s no downgrade. E.g. if you have 2 upgradable handles and you upgrade the first but fail to upgrade the second, there’s no way to go back and downgrade the first. Does that make sense?

[moeen]

Yes. Thanks @madelson

#248 is up for review.