使用 ImmutableSortedSet 作为线程安全缓存

本文关键字：线程 安全 缓存 ImmutableSortedSet 使用 | 更新日期: 2023-09-27 18:33:06

我有一个方法，它接受一个DateTime并返回标记该季度结束的日期。由于涉及工作日和假日日历的一些复杂性，我想缓存结果以加快后续调用的速度。我正在使用SortedSet<DateTime>来维护数据缓存，并且我使用 GetViewBetween 方法来执行缓存查找，如下所示：

private static SortedSet<DateTime> quarterEndCache = new SortedSet<DateTime>();
public static DateTime GetNextQuarterEndDate(DateTime date)
{
    var oneDayLater = date.AddDays(1.0);
    var fiveMonthsLater = date.AddMonths(5);
    var range = quarterEndCache.GetViewBetween(oneDayLater, fiveMonthsLater);
    if (range.Count > 0)
    {
        return range.Min;
    }
    // Perform expensive calc here
}

现在我想让我的缓存线程安全。与其在任何地方使用锁，这会导致每次查找的性能下降，我正在探索新的ImmutableSortedSet<T>集合，这将使我完全避免锁。问题是ImmutableSortedSet<T>没有方法GetViewBetween。有没有办法从ImmutableSortedSet<T>获得类似的功能？

[编辑]

Servy说服我，仅使用带有普通SortedSet<T>的锁是最简单的解决方案。不过，我将保持这个问题悬而未决，因为我有兴趣知道ImmutableSortedSet<T>是否可以有效地处理这种情况。

使用 ImmutableSortedSet<T> 作为线程安全缓存

让我们将问题分为两部分：

  1. 如何获得类似于GetViewBetween的功能 ImmutableSortedSet<T> ？我建议使用IndexOf方法。在下面的代码片段中，我创建了一个扩展方法GetRangeBetween它应该可以完成这项工作。

  2. 如何使用数据不可变的数据结构实现无锁、线程安全的更新？尽管这不是最初的问题，但对这个问题有一些怀疑的评论。不可变框架实现了一个专门用于此目的的方法： System.Collections.Immutable.Update<T>(ref T location, Func<T, T> transformer) where T : class; 该方法在内部依赖于原子比较/交换操作。如果你想手动完成此操作，你会在下面找到一个替代实现，它的行为应该与Immutable.Update相同。

所以这是代码：

public static class ImmutableExtensions
{
    public static IEnumerable<T> GetRangeBetween<T>(
        this ImmutableSortedSet<T> set, T min, T max)
    {
        int i = set.IndexOf(min);
        if (i < 0) i = ~i;
        while (i < set.Count)
        {
            T x = set[i++];
            if (set.KeyComparer.Compare(x, min) >= 0 &&
                set.KeyComparer.Compare(x, max) <= 0)
            {
                yield return x;
            }
            else
            {
                break;
            }
        }
    }
    public static void LockfreeUpdate<T>(ref T item, Func<T, T> fn)
        where T: class
    {
        T x, y;
        do
        {
            x = item;
            y = fn(x);
        } while (Interlocked.CompareExchange(ref item, y, x) != x);
    }
}

用法：

    private static volatile ImmutableSortedSet<DateTime> quarterEndCache =
        ImmutableSortedSet<DateTime>.Empty;
    private static volatile int counter; // test/verification purpose only
    public static DateTime GetNextQuarterEndDate(DateTime date)
    {
        var oneDayLater = date.AddDays(1.0);
        var fiveMonthsLater = date.AddMonths(5);
        var range = quarterEndCache.GetRangeBetween(oneDayLater, fiveMonthsLater);
        if (range.Any())
        {
            return range.First();
        }
        // Perform expensive calc here
        // -> Meaningless dummy computation for verification purpose only
        long x = Interlocked.Increment(ref counter);
        DateTime test = DateTime.FromFileTime(x);
        ImmutableExtensions.LockfreeUpdate(
            ref quarterEndCache,
            c => c.Add(test));
        return test;
    }
    [TestMethod]
    public void TestIt()
    {
        var tasks = Enumerable
            .Range(0, 100000)
            .Select(x => Task.Factory.StartNew(
                () => GetNextQuarterEndDate(DateTime.Now)))
            .ToArray();
        Task.WaitAll(tasks);
        Assert.AreEqual(100000, counter);
    }
相关文章：