ILockProvider.cs

using System;
using System.Collections.Generic;
using System.Text;
using System.Threading;
using System.Threading.Tasks;

namespace Polly.Utilities
{
	/// <summary>
	/// Defines operations for locks used by Polly policies.
	/// </summary>
	public interface ILockProviderAsync
	{
		/// <summary>
		/// Waits to acquire the lock.
		/// </summary>
		/// <param name="key">A string key being used by the execution.</param>
		/// <param name="context">The Polly execution context consuming this lock.</param>
		/// <param name="cancellationToken">A cancellation token to cancel waiting to acquire the lock.</param>
		/// <throws>OperationCanceledException, if the passed <paramref name="cancellationToken"/> is signaled before the lock is acquired.</throws>
		/// <throws>InvalidOperationException, invalid lock state</throws>
		ValueTask<IDisposable> AcquireLockAsync(string key, Context context, CancellationToken cancellationToken);
	}

	/// <summary>
	/// Defines operations for locks used by Polly policies.
	/// </summary>
	public interface ILockProvider
	{
		/// <summary>
		/// Waits to acquire the lock.
		/// </summary>
		/// <param name="key">A string key being used by the execution.</param>
		/// <param name="context">The Polly execution context consuming this lock.</param>
		/// <throws>InvalidOperationException, invalid lock state</throws>
		IDisposable AcquireLock(string key, Context context);
	}

	/// <summary>
	/// Lock provider that locks on a key per process. The locking mechanism is designed to be able
	/// to be requested and released on different threads if needed.
	/// </summary>
	public class ProcessLockProviderAsync : ILockProviderAsync
	{
		// TODO: Pass via IOC or other method instead of hard-coding static
		internal static readonly int[] keyLocks = new int[1024];

		private class ProcessLockAsync : IDisposable
		{
			private uint hash;
			private bool gotLock;

			[System.Runtime.CompilerServices.MethodImpl(System.Runtime.CompilerServices.MethodImplOptions.AggressiveInlining)]
			public void Dispose()
			{
				if (gotLock)
				{
					gotLock = false;
					ProcessLockProviderAsync.keyLocks[hash] = 0;
				}
                // else we do not care, it can be disposed in an error case and we will simply ignore that the key locks were not touched
			}

			[System.Runtime.CompilerServices.MethodImpl(System.Runtime.CompilerServices.MethodImplOptions.AggressiveInlining)]
			public async ValueTask<IDisposable> AcquireLockAsync(string key, Context context, CancellationToken cancellationToken)
			{
				// Monitor.Enter and Monitor.Exit are tied to a specific thread and are
				//  slower than this spin lock, which does not care about threads and will execute very
				//  quickly, regardless of lock contention
				// https://stackoverflow.com/questions/11001760/monitor-enter-and-monitor-exit-in-different-threads

				// Get a hash based on the key, use this to lock on a specific int in the array. The array is designed
				// to be small enough to not use very much memory, but large enough to avoid collisions.
				// Even if there is a collision, it will be resolved very quickly.
				hash = (uint)key.GetHashCode() % (uint)ProcessLockProviderAsync.keyLocks.Length;

				// To get the lock, we must change the int at hash index from a 0 to a 1. If the value is
				//  already a 1, we don't get the lock. The return value must be 0 (the original value of the int).
				// it is very unlikely to have any contention here, but if so, the spin cycle should be very short.
				// Parameter index 1 (value of 1) is the value to change to if the existing value (Parameter index 2) is 0.
				while (!cancellationToken.IsCancellationRequested && Interlocked.CompareExchange(ref ProcessLockProviderAsync.keyLocks[hash], 1, 0) == 1)
				{
					// give up a clock cycle, we want to get back and try to get the lock again very quickly
					await Task.Yield();
				}

				if (cancellationToken.IsCancellationRequested)
				{
					throw new OperationCanceledException(cancellationToken);
				}

				gotLock = true;
				return this;
			}
		}

		[System.Runtime.CompilerServices.MethodImpl(System.Runtime.CompilerServices.MethodImplOptions.AggressiveInlining)]
		public ValueTask<IDisposable> AcquireLockAsync(string key, Context context, CancellationToken cancellationToken)
		{
			return new ProcessLockAsync().AcquireLockAsync(key, context, cancellationToken);
		}
	}

	/// <summary>
	/// Lock provider that locks on a key per process. The locking mechanism is designed to be able
	/// to be requested and released on different threads if needed.
	/// </summary>
	public class ProcessLockProvider : ILockProvider
	{
		private class ProcessLock : IDisposable
		{
			private uint hash;
			private bool gotLock;

			[System.Runtime.CompilerServices.MethodImpl(System.Runtime.CompilerServices.MethodImplOptions.AggressiveInlining)]
			public void Dispose()
			{
				if (gotLock)
				{
					gotLock = false;
					ProcessLockProviderAsync.keyLocks[hash] = 0;
				}
                // if constructor had exception, we will not get in Dispose as the object will never be created, if the constructor succeeds, gotLock will always be true
                // we still use the gotLock bool in case of multiple dispose calls
			}

			[System.Runtime.CompilerServices.MethodImpl(System.Runtime.CompilerServices.MethodImplOptions.AggressiveInlining)]
			public ProcessLockAsync(string key, Context context)
			{
				hash = (uint)key.GetHashCode() % (uint)ProcessLockProviderAsync.keyLocks.Length;
				while (Interlocked.CompareExchange(ref ProcessLockProviderAsync.keyLocks[hash], 1, 0) == 1)
				{
					Task.Yield().GetAwaiter().GetResult();
				}
				gotLock = true;
			}
		}

		/// <inheritdoc />
		public IDisposable AcquireLock(string key, Context context)
		{
			return new ProcessLock(key, context);
		}
	}
}

You are very welcome. Would I add the striping to InstanceScopedLockProvider.cs I assume then? I'll do a PR for it...

…

-- Jeff

On Thu, Feb 6, 2020 at 5:07 PM Dylan Reisenberger ***@***.***> wrote: @jjxtra <https://github.com/jjxtra> Again, thanks for everything on the locking! Some notes just on what turned out different in the main Policy implementation <https://github.com/Polly-Contrib/Polly.Contrib.DuplicateRequestCollapser/tree/master/src/Polly.Contrib.DuplicateRequestCollapser>, compared to what discussed previously and what we have in this gist: - I was wrong in this case about the benefit of using a struct for the releasers. The compiler does have a special transform for when a using statement directly references a struct (ie using (<some-struct>) { }), to avoid boxing, but here we are returning an IDisposable from a method due to the lock interfaces, so it gets boxed to IDisposable first anyway 🙁 . So I switched back to class in the v0.1.0 basic lock implementation. - There were a couple of places in my early spike which used the non-thread-safe members on ConcurrentDictionary<,> incl. outside the lock - switched to thread-safe. - I'm thinking that AcquireLockAsync needs to return IAsyncDisposable <https://github.com/Polly-Contrib/Polly.Contrib.DuplicateRequestCollapser/blob/master/src/Polly.Contrib.DuplicateRequestCollapser/IAsyncLockProvider.cs>, not just ValueTask<IDisposable>. If the lock-releasing is across network I/O (like to Redis), we want the implementation of that release to be able to be fully async. IAsyncDisposable uses ValueTask as the return type of its release method <https://github.com/Polly-Contrib/Polly.Contrib.DuplicateRequestCollapser/blob/master/src/Polly.Contrib.DuplicateRequestCollapser/AsyncWrapperLockProvider.cs#L38>, so when we are just wrapping a sync implementation, we still get the benefit of ValueTask. Assuming you push on forward to bring the stripe-locking idea into Polly.Contrib.DuplicateRequestCollapser: - We probably wouldn't need the async implementation ProcessLockProviderAsync? There's nothing async in the work it does (setting aside the need to yield asynchronously given it's async), so we could just use a shallow async-over-sync wrapper <https://github.com/Polly-Contrib/Polly.Contrib.DuplicateRequestCollapser/blob/master/src/Polly.Contrib.DuplicateRequestCollapser/AsyncWrapperLockProvider.cs>. (Just running it async when it doesn't have any need for async work will create extra allocations for the state machines, async continuations etc.) - I dug into the source code around Task.Yield(), to be sure I understood what Task.Yield().GetAwaiter().GetResult() would do. Looks like it doesn't offer any yielding behaviour if used sync like that, .GetAwaiter() returns a YieldAwaitable <https://github.com/dotnet/corefx/blob/26a505faf6d27283f3e9bca33371e19c91f88082/src/Common/src/CoreLib/System/Runtime/CompilerServices/YieldAwaitable.cs#L45>, GetResult() on that is a no-op <https://github.com/dotnet/corefx/blob/26a505faf6d27283f3e9bca33371e19c91f88082/src/Common/src/CoreLib/System/Runtime/CompilerServices/YieldAwaitable.cs#L162>. Looks like the benefit of Task.Yield() only comes if it's genuinely used in an async context; the await then schedules the async continuation back onto one or other TaskScheduler <https://github.com/dotnet/corefx/blob/26a505faf6d27283f3e9bca33371e19c91f88082/src/Common/src/CoreLib/System/Runtime/CompilerServices/YieldAwaitable.cs#L75-L116>, which looks like the mechanism by which await Task.Yield() gets its value - that async continuation has to compete with other async tasks in the scheduler. NB Moot now that we can now drop .Net Standard 1.x (👍 ), just sharing what I found cos I had dug into this. Thanks again for everything you are doing on the locking. 👍 — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <https://gist.github.com/f6116180b2ef5c1550e60567af506c2a?email_source=notifications&email_token=AAJWQGCMJALY6FHELYNLCNTRBSQ5LA5CNFSM4KIE6FYKYY3PNVWWK3TUL52HS4DFVNDWS43UINXW23LFNZ2KUY3PNVWWK3TUL5UWJTQAGBNL4#gistcomment-3168958>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AAJWQGDE5RZOLBGT3KE7HCTRBSQ5LANCNFSM4KIE6FYA> .

Yep, PR onto Polly.Contrib.DuplicateRequestCollapser.

My recommendation would be a PR to add a new ISyncLockingProvider, not replace/modify InstanceScopedLockProvider, leaving both as options. Curating a widely-used OSS project really brings home (if it is not already obvious) that different users have different needs. Some will benefit from a striped-lock provider; some will have no need. Giving users options (provided not confusing), rather than pre-deciding on one option to suit all users, can work well. 👍

Thanks again for helping drive this forward!

You are welcome!