Ronin Building Blocks - Resource Pools
In Azure, just as most other shared resource situations, there are policies put in place to govern fairness of use (most limits can be found here). These limits are the best friend of solutions that do not over consume, protecting them from abusers etc., but must be handled appropriately by solutions that push up against them. Take for example a solution that performs a lot of IO operations against an Azure Storage Account. If the solution is not architected to handle this scale will be limited to the maximum limits of the resource, which may not be acceptable.
I am a firm believer that any requirement written on paper today is most likely going to change at some point in the future, it just seems to happen that way. What this means to me is even if my solution does not currently exceed the maximum limits of a resource I should make a conscious decision on how to handle it.
One way I can overcome these solutions is to use more than one instance of the resource, but this introduces a couple of important decisions.
1. How do I determine which resource instance to use at what point in time?
2. Once chosen for a specific context do I need to be sticky to that instance?
This is a great example of a time when a Resource Pool is the right fit. The best-known example of a Resource Pool is your local public library. Books cost money to buy and many people cannot afford the associated cost so the library buys a defined quantity of each book and allows people to check them out. When the person is done with the book they check it back into the library, freeing it up for others to use.
A key piece that makes this possible is the fact that the resources are not permanently mutated by the consumer, so for the library example the person checking it out does not rip pages out at random. Every consumer gets the book in a known acceptable condition.
In most use cases a solution that implements a Resource Pool either
1. Request a resource without providing any information leaving it to the Resource Pools logic to decide which resource to offer.
2. Request a resource providing a single piece of information (a key) and get a resource that is specifically assigned to process that value.
To keep the pools as simple as possible I will focus on pools with immutable, pre-allocated resources. More advanced pooling can offer the ability to adjust pool levels but this comes with a series of challenges including locking in most cases.
The basic functions of any of the Resource Pools I will use at this point will provide the ability set a maximum reference count per instance (e.g. an instance will not be handed out to anymore than 50 consumers at any point in time) and some general health metrics. The interface for the basic pool constructs look like
namespace Ronin.ResourcePools
{
#region Using Clauses
using System;
#endregion
/// <summary>
/// An interface that all pool objects implement
/// </summary>
public interface IPool : IDisposable
{
#region Pool Health
/// <summary>
/// The combined percentage of reference count to max reference count of all resources
/// </summary>
double PercentFull { get; }
/// <summary>
/// The number of resources that are full
/// </summary>
int NumberOfFull { get; }
/// <summary>
/// The number of resources in the pool
/// </summary>
int Count { get; }
/// <summary>
/// The number of resources in the pool that have no references allowed
/// </summary>
int MaxZeroCount { get; }
/// <summary>
/// The number of resources in the pool that have no references
/// </summary>
int ZeroCount { get; }
/// <summary>
/// The number of references
/// </summary>
int ReferenceCount { get; }
/// <summary>
/// The percent of resources in the pool that have handed out all of their instances
/// </summary>
double PercentFullResources { get; }
#endregion
}
}
As mentioned previously the pools will either be generic algorithms like Round Robin that hand the next available resource without worrying about affinity between calls. These simple pools will implement the following interface.
namespace Ronin.ResourcePools
{
/// <summary>
/// The interface implemented by a pool that does not use a key to determine the resource to retrieve
/// </summary>
/// <typeparam name="TResource">The resource type</typeparam>
public interface INonKeyedPool<TResource> : IPool
{
/// <summary>
/// Takes an instance from the pool if available
/// </summary>
/// <returns>The container holding the resource that was checked out or the default if not available</returns>
ResourceContainer<TResource> Take();
}
}
For more advanced pools that handle things like affinity of resources we will offer the ability to provide a key string. This could easily be changed to any other type but string is a good general all around key.
namespace Ronin.ResourcePools
{
/// <summary>
/// The interface implemented by a pool that uses a key to determine the resource to retrieve
/// </summary>
/// <typeparam name="TResource">The resource type</typeparam>
public interface IKeyedPool<TResource> : IPool
{
/// <summary>
/// Takes an instance from the pool if available
/// </summary>
/// <param name="key">The key that is hashed to determine the resource to assign</param>
/// <returns>The container holding the resource that was checked out or the default if not available</returns>
ResourceContainer<TResource> Take(string key);
}
}
As you can see in the previous two interfaces there is an option to retrieve an instance but there is no method to check it back in, this is by design. I decided to not use an explicit method to return the instance to the pool opting instead for the use of another object that when disposed of returns it to the queue. This technique seems to align with the technique used in the observable implementations. In the creation of this object I also made the conscious decision to not use a finalizer, forcing the consumer to be diligent about disposing of the container.
namespace Ronin.ResourcePools
{
#region Using Clauses
using Internal;
using System;
using System.Threading;
#endregion
/// <summary>
/// A container object used to return the resource to the pool
/// </summary>
public class ResourceContainer<TResource> : IDisposable
{
#region Variables
/// <summary>
/// The tracker that the resource is associated with
/// </summary>
private readonly ReferenceTracker<TResource> _tracker;
/// <summary>
/// The number of times the instance has been disposed of
/// </summary>
private int _disposalCount;
#endregion
#region Constructors
/// <summary>
/// A container to handle returning the resource to the pool
/// </summary>
/// <param name="tracker">The tracker that the resource was retrieved from</param>
/// <param name="resource">The resulting resource</param>
/// <param name="success">True if the resources was successfully retrieved</param>
/// <param name="id">The id of the reference tracker that provided the resource</param>
internal ResourceContainer(ReferenceTracker<TResource> tracker, TResource resource, bool success, Guid id)
{
Resource = resource;
Success = success;
ReferenceTrackerId = id;
_tracker = tracker;
}
#endregion
#region Properties
/// <summary>
/// The resulting resource
/// </summary>
public TResource Resource { get; }
/// <summary>
/// True if the resources was successfully retrieved
/// </summary>
public bool Success { get; }
/// <summary>
/// The id of the reference tracker that provided the resource
/// </summary>
internal Guid ReferenceTrackerId { get; }
#endregion
#region Disposal
/// <inheritdoc />
public void Dispose()
{
if (Interlocked.Increment(ref _disposalCount) == 1)
{
try
{
_tracker.Release();
}
catch (Exception)
{
// suppress exception in case the dispose is called after the pool is disposed of
}
}
}
#endregion
#region Operators
/// <summary>
/// An implicit conversion from the requested container to the resource requested
/// </summary>
/// <param name="container">The container to be converted</param>
public static implicit operator TResource(ResourceContainer<TResource> container)
{
return container.Resource;
}
#endregion
}
}
Notice in the code above the use of an implicit conversion operator to the resource. This makes it easy for the consumer to receive the object from the pool and start using it as they would expect. The only risk with this approach I figured was the thought it may cause the consumer to forget to dispose of the container object because the resource in the event the resource did not support disposal.
The pool will use an internal container for the resource to keep track of the number of references to the resource it contains. Letting the container own this logic keeps the overall pool logic simpler while making it easily reusable.
namespace Ronin.ResourcePools.Internal
{
#region Using Clauses
using System;
using System.Threading;
using Parameters;
#endregion
/// <summary>
/// Keeps track of the resources instance and the number consumers using it
/// </summary>
internal class ReferenceTracker<TResource> : IDisposable
{
#region Variables
/// <summary>
/// The number of times the instance has been disposed of
/// </summary>
private int _disposalCount;
/// <summary>
/// The number of reference to the pooled instance
/// </summary>
private int _referenceCount;
/// <summary>
/// The maximum number of references that can be taken out on the instance
/// </summary>
private readonly int _maxReferenceCount;
/// <summary>
/// True if the resource should be disposed of when the reference tracker is disposed
/// </summary>
private readonly bool _disposeOfResource;
#endregion
#region Constructors
/// <summary>
/// The identifier that will be used to
/// </summary>
/// <param name="resource">The instance of the resource being tracked</param>
/// <param name="maxReferenceCount">The maximum references that can be taken out on this instance</param>
/// <param name="disposeOfResource">True if the resource should be disposed of when the reference tracker is disposed</param>
internal ReferenceTracker(TResource resource, int maxReferenceCount, bool disposeOfResource)
{
Guard.NotLessThan(nameof(maxReferenceCount), maxReferenceCount, 0);
Resource = resource;
Id = Guid.NewGuid();
_disposeOfResource = disposeOfResource;
_maxReferenceCount = maxReferenceCount;
}
#endregion
#region Properties
/// <summary>
/// The resource being tracked
/// </summary>
internal TResource Resource { get; }
/// <summary>
/// The unique identifier used to track the instance
/// </summary>
internal Guid Id { get; }
/// <summary>
/// The current reference count
/// </summary>
internal int ReferenceCount => _referenceCount;
/// <summary>
/// The maximum reference count allowed
/// </summary>
internal int MaxReferenceCount => _maxReferenceCount;
/// <summary>
/// True if the resource has all of the references it can handle
/// </summary>
internal bool IsFull => _maxReferenceCount <= _referenceCount;
#endregion
#region Methods
/// <summary>
/// Takes an instance from the pool if available
/// </summary>
/// <param name="resource">The resource that was checked out or the default if not available</param>
/// <param name="id">The id of the reference tracker</param>
/// <returns>True if the instance was retrieved successfully, false if not</returns>
internal bool Take(out TResource resource, out Guid id)
{
var success = false;
id = Id;
// Check if the maximum count has been exceeded and if not return the instance
if (Interlocked.Increment(ref _referenceCount) > _maxReferenceCount)
{
Interlocked.Decrement(ref _referenceCount);
resource = default(TResource);
}
else
{
resource = Resource;
success = true;
}
return success;
}
/// <summary>
/// Reduces the reference count by 1
/// </summary>
internal void Release()
{
Interlocked.Decrement(ref _referenceCount);
}
#endregion
#region Disposal
/// <inheritdoc />
public void Dispose()
{
if (Interlocked.Increment(ref _disposalCount) == 1)
{
if (_disposeOfResource) (Resource as IDisposable)?.Dispose();
}
}
#endregion
}
The basic pool implementation is going to store a list of immutable resources that it checks in and out while reporting on the standard Pool health properties. Here is my implementation.
namespace Ronin.ResourcePools.Internal
{
#region Using Clauses
using System;
using System.Collections.Generic;
using System.Collections.Immutable;
using System.Linq;
using System.Threading;
using Parameters;
#endregion
/// <summary>
/// A base pool implementation
/// </summary>
/// <typeparam name="TResource">The resource stored in the pool</typeparam>
public abstract class Pool<TResource> : IPool
{
#region Variables
/// <summary>
/// The pool of resource instances
/// </summary>
private readonly ImmutableArray<ReferenceTracker<TResource>> _pool;
/// <summary>
/// Tracks the number of times the instance has been disposed of
/// </summary>
private int _disposalCount;
/// <summary>
/// True to dispose when complete
/// </summary>
private readonly bool _disposeOfResource;
#endregion
#region Constructors
/// <summary>
/// Initializes a new instance of the type
/// </summary>
/// <param name="resources">The resources in the pool</param>
/// <param name="maxReferenceCount">The maximum reference count allowed for each resource instance</param>
/// <param name="disposeOfResource">True to dispose when complete</param>
protected Pool(IEnumerable<TResource> resources, int maxReferenceCount, bool disposeOfResource)
{
Guard.NotLessThan(nameof(maxReferenceCount), maxReferenceCount, 0);
_disposeOfResource = disposeOfResource;
_pool = resources.Select(resource => new ReferenceTracker<TResource>(resource, maxReferenceCount, disposeOfResource)).ToImmutableArray();
}
#endregion
#region Resource Check Out
/// <summary>
/// Takes an instance from the pool if available
/// </summary>
/// <param name="index">The index of the resource to retrieve</param>
/// <returns>The container holding the resource that was checked out or the default if not available</returns>
protected ResourceContainer<TResource> InternalTake(int index)
{
Guard.NotLessThan(nameof(index), index, 0);
Guard.NotMoreThan(nameof(index), index, _pool.Length);
TResource resource;
Guid id;
var tracker = _pool[index];
var success = tracker.Take(out resource, out id);
return new ResourceContainer<TResource>(tracker, resource, success, id);
}
/// <summary>
/// Takes an instance from the pool if available and if not tries the next index until it either gets one or arrives at the original index again
/// </summary>
/// <param name="index">The index of the resource to start trying to retrieve at and replaces the value with the first success index</param>
/// <returns>The container holding the resource that was checked out or the default if not available</returns>
protected ResourceContainer<TResource> InternalTakeNextAvailable(ref int index)
{
Guard.NotLessThan(nameof(index), index, 0);
Guard.NotMoreThan(nameof(index), index, _pool.Length);
bool success;
TResource resource;
ReferenceTracker<TResource> tracker;
Guid id;
var attemptIndex = index;
do
{
if (attemptIndex >= _pool.Length) attemptIndex = 0;
tracker = _pool[index];
success = tracker.Take(out resource, out id);
if (success) index = attemptIndex;
} while (++attemptIndex != index && !success);
return new ResourceContainer<TResource>(tracker, resource, success, id);
}
/// <summary>
/// Takes the first available instance from the pool
/// </summary>
/// <returns>The container holding the resource that was checked out or the default if not available</returns>
protected ResourceContainer<TResource> InternalTakeFirstAvailable()
{
var index = 0;
return InternalTakeNextAvailable(ref index);
}
/// <summary>
/// Takes the lowest reference count instance from the pool
/// </summary>
/// <returns>The container holding the resource that was checked out or the default if not available</returns>
protected ResourceContainer<TResource> InternalTakeLowestReference()
{
var success = false;
TResource resource = default(TResource);
ReferenceTracker<TResource> tracker;
Guid id = Guid.Empty;
var attemptIndex = 0;
do
{
tracker = _pool.Where(item => item.ReferenceCount < item.MaxReferenceCount).OrderBy(item => item.ReferenceCount).Take(1).FirstOrDefault();
if (tracker != null)
{
success = tracker.Take(out resource, out id);
}
} while (++attemptIndex < 100 && !success);
return new ResourceContainer<TResource>(tracker, resource, success, id);
}
#endregion
#region Pool Health
/// <summary>
/// The combined percentage of reference count to max reference count of all resources
/// </summary>
public double PercentFull
{
get
{
var items = _pool.Select(item => new Tuple<int, int>(item.ReferenceCount, item.MaxReferenceCount)).ToArray();
var referenceCount = items.Sum(item => item.Item1);
var maxReferenceCount = items.Sum(item => item.Item2);
return maxReferenceCount == 0 ? 100.0 : (double)referenceCount / maxReferenceCount;
}
}
/// <summary>
/// The number of resources that are full
/// </summary>
public int NumberOfFull
{
get { return _pool.Count(item => item.IsFull); }
}
/// <summary>
/// The number of resources in the pool
/// </summary>
public int Count => _pool.Length;
/// <summary>
/// The number of resources in the pool that have no references allowed
/// </summary>
public int MaxZeroCount => _pool.Count(item => item.MaxReferenceCount == 0);
/// <summary>
/// The number of resources in the pool that have no references
/// </summary>
public int ZeroCount => _pool.Count(item => item.ReferenceCount == 0);
/// <summary>
/// The number of references
/// </summary>
public int ReferenceCount => _pool.Sum(item => item.ReferenceCount);
/// <summary>
/// The percent of resources in the pool that have handed out all of their instances
/// </summary>
public double PercentFullResources
{
get
{
var resourceCount = _pool.Length;
return resourceCount < 1 ? 100.0 : (double)NumberOfFull / resourceCount;
}
}
#endregion
#region Disposal
/// <inheritdoc />
public void Dispose()
{
if (Interlocked.Increment(ref _disposalCount) == 1)
{
if (_disposeOfResource)
{
foreach (var item in _pool)
{
item.Dispose();
}
}
}
}
#endregion
}
}
Starting with the simple implementations I decided to implement a simple round robin pool. This pool will just iterate through the resources handing back one then the next. This will provide no affinity of resources for the consumer but will be simple and fast.
namespace Ronin.ResourcePools.Simple
{
#region Using Clauses
using System;
using System.Collections.Generic;
using System.Threading;
using System.Threading.Tasks;
using Internal;
#endregion
/// <summary>
/// A pool that keeps a collection of resources, iterating through them as a new one is requested
/// </summary>
public class RoundRobinPool<TResource> : Pool<TResource>, INonKeyedPool<TResource>
{
#region Variables
/// <summary>
/// The number of items in the pool
/// </summary>
private readonly int _poolCount;
/// <summary>
/// Keeps track of the index of the last pool item returned
/// </summary>
private long _lastIndex = -1;
#endregion
#region Constructors
/// <summary>
/// Initializes a new instance of the type
/// </summary>
/// <param name="resources">The resources in the pool</param>
/// <param name="disposeOfResource">True to dispose when complete</param>
public RoundRobinPool(IEnumerable<TResource> resources, bool disposeOfResource) : base(resources, int.MaxValue, disposeOfResource)
{
_poolCount = Count;
if (_poolCount < 1) throw new ArgumentException("Must have at least one element", nameof(resources));
}
#endregion
#region Methods
/// <summary>
/// Takes an instance from the pool if available
/// </summary>
/// <returns>The container holding the resource that was checked out or the default if not available</returns>
public ResourceContainer<TResource> Take()
{
ResourceContainer<TResource> resource = null;
var attemptNumber = 0;
do
{
var index = Interlocked.Increment(ref _lastIndex);
resource = InternalTake((int)(index % _poolCount));
} while (resource == null && attemptNumber++ < 100);
return resource;
}
#endregion
}
}
For the string based (key) version the easiest way to provide affinity on a pool of resources that will never contract or expand is to use a hash algorithm. There are a lot of write-ups on different hash algorithms and their benefits in dispersal but for simplicity and speed I will use the following hash algorithm. I have decided to put the hash algorithm in its own class for easy central changes for any pool that implements this functionality.
namespace Ronin.ResourcePools.Internal
{
#region Using Clauses
using System.Text;
#endregion
/// <summary>
/// Common utilities for hashing used by the library
/// </summary>
internal static class Hashes
{
/// <summary>
/// Hashes the string to a ulong value
/// </summary>
/// <param name="value">The value to hash</param>
/// <returns>The hashed value</returns>
internal static ulong HashString(string value)
{
var hash = 3074457345618258791ul;
var array = Encoding.ASCII.GetBytes(value);
// ReSharper disable once ForCanBeConvertedToForeach
for (var index = 0; index < array.Length; index++)
{
unchecked
{
hash ^= array[index];
hash *= 3074457345618258799ul;
}
}
return hash;
}
}
}
This first keyed resource pool will be the primary one I use in simple "sharding scenarios". This will allow for resources affinity by key while remaining simple and performant.
namespace Ronin.ResourcePools.Simple
{
#region Using Clauses
using System;
using System.Collections.Generic;
using System.Threading;
using System.Threading.Tasks;
using Internal;
#endregion
/// <summary>
/// A pool that keeps a collection of resources using as simple hash algrothm to add references
/// </summary>
public class HashPool<TResource> : Pool<TResource>, IKeyedPool<TResource>
{
#region Variables
/// <summary>
/// The number of items in the pool
/// </summary>
private readonly ulong _poolCount;
#endregion
#region Constructors
/// <summary>
/// Initializes a new instance of the type
/// </summary>
/// <param name="resources">The resources in the pool</param>
/// <param name="disposeOfResource">True to dispose when complete</param>
public HashPool(IEnumerable<TResource> resources, bool disposeOfResource) : base(resources, int.MaxValue, disposeOfResource)
{
_poolCount = (ulong)Count;
if (_poolCount < 1) throw new ArgumentException("Must have at least one element", nameof(resources));
}
#endregion
#region Methods
/// <summary>
/// Takes an instance from the pool if available
/// </summary>
/// <param name="key">The key that is hashed to determine the resource to assign</param>
/// <returns>The container holding the resource that was checked out or the default if not available</returns>
public ResourceContainer<TResource> Take(string key)
{
return InternalTake((int)(Hashes.HashString(key) % _poolCount));
}
#endregion
}
}
The final Resource Pool implementation that I will demonstrate here is a balanced pool. This pool will return the resource with the lowest reference count each time. The problem with this is the performance of the query to get each instance but at times it may be worth the overhead to get balance.
namespace Ronin.ResourcePools.Advanced
{
#region Using Clauses
using System;
using System.Collections.Generic;
using System.Threading;
using System.Threading.Tasks;
using Internal;
#endregion
/// <summary>
/// A pool that keeps a collection of resources using as simple hash algrothm to add references
/// </summary>
public class BalancedPool<TResource> : Pool<TResource>, INonKeyedPool<TResource>
{
#region Constructors
/// <summary>
/// Initializes a new instance of the type
/// </summary>
/// <param name="resources">The resources in the pool</param>
/// <param name="maxReferenceCount">The maximum reference count allowed for each resource instance</param>
/// <param name="disposeOfResource">True to dispose when complete</param>
public BalancedPool(IEnumerable<TResource> resources, int maxReferenceCount, bool disposeOfResource) : base(resources, maxReferenceCount, disposeOfResource)
{
if ((ulong)Count < 1) throw new ArgumentException("Must have at least one element", nameof(resources));
}
#endregion
#region Methods
/// <summary>
/// Takes an instance from the pool if available
/// </summary>
/// <returns>The container holding the resource that was checked out or the default if not available</returns>
public ResourceContainer<TResource> Take()
{
return InternalTakeLowestReference();
}
#endregion
}
}
The use of resource pools are key to overcoming some of the limitations of shared resources and maximizing throughput and performance. These are just three implementations of Resource Pools and there are many more. In general these three should cover most of the scenarios we will run into.