高性能多线程LRU缓存

• 下载源代码 - 8.96 KB

引言

LRU 缓存是一种键值对数据容器，受大小和/或年龄的限制，首先移除最近最少使用（LRU）的对象。该算法需要跟踪每个对象被访问的最近时间，这可能很昂贵，以确保算法始终丢弃 LRU 项。

其他 LRU 算法

大多数 LRU 缓存算法包含两部分：一个字典和一个列表。字典保证了对数据的快速访问，而按对象年龄排序的列表则控制对象的生命周期并确定哪些对象应首先被移除。

一个简单的 LRU 缓存实现使用双向链表；将新项添加到头部，从尾部移除项，并在引用（访问）现有项时将其移至头部。此算法适用于单线程应用程序，但在多线程环境中速度非常慢。在多线程应用程序中，每次修改链表时都必须锁定。这会导致插入、读取和删除操作的线程锁定，从而导致速度变慢。

另一种算法是为每个项的年龄添加一个时间戳（DateTime 或递增的 Integer）值。当缓存已满时，必须对项目列表进行排序和截断。这使得插入和读取操作非常快速，因为不需要锁定，但删除操作却慢得令人痛苦（通常为 O(N * log N)，用于排序）。

概述

我选择的算法将项目划分为我称为 AgeBag 的时间片。项目会添加到当前的 AgeBag 中，直到该包已满或指定的时限过期，然后该 AgeBag 被关闭，下一个 AgeBag 成为当前。被访问的项目会标记为当前包的索引。当缓存变得太满/太旧时，最旧的 AgeBag 会被清空，将所有被访问过的节点移到正确的 AgeBag，并移除包中剩余的节点。这使得读取操作无需锁定，并且删除操作速度更快，因为只有最旧 AgeBag 中的项目会被移动，而且从不进行实际的排序。

在此系统中，即使项目的确切顺序未被维护，这仍然是一个真正的 LRU 缓存，因为在（对访问过的项目进行移动后）最旧包中剩余的所有内容都会同时被移除。因此，缓存中没有比已移除项目更旧的项目。

我的 LRUCache 实现包含两个不同的部分，它们被编码为子类。LifespanMgr 类负责跟踪项目使用情况并确定在缓存已满/过时时要移除哪些项目。Index 类提供对缓存中存储的所有对象的 Dictionary 键/值访问。Index 包含委托，用于计算添加到缓存的任何项目的键，以及从外部源按键/值加载项目。

Index 不直接存储项目节点，而是存储指向项目节点的 WeakReference 对象。通过这种方式，Index 不会阻止项目被垃圾回收。这还允许从 AgeBag 中移除旧项目，而无需从索引中移除这些项目。一旦 Node 从 LifespanMgr 中移除，它就可以被垃圾回收。Node 不会立即从 Index 中移除。如果 Index 在垃圾回收之前检索到该节点，它会被重新插入到当前的 AgeBag 的节点列表中。如果它已经被垃圾回收，则会加载一个新对象。如果 Index 的大小超过缓存容量的两倍，则会清除并重建 Index。

Locking

在开始讲解代码之前，我应该简要解释一下 LRUCache 使用的所有锁定机制。

第一个也是最简单的就是 Interlocked 类，它确保增减操作在不发生上下文切换的情况下进行。这是使增减操作线程安全所必需的，并且比其他锁定方法快得多。

下一个锁定机制是 Monitor 类。每当使用 C# lock 关键字时，都会调用此类。值得注意的一个方法是 Monitor.TryEnter(obj)，它会立即返回一个 bool 值，指示是否已获取锁定。与标准的 Enter() 方法不同，在第一个线程获得锁定后，所有其他线程将跳过该操作，而不是等待第一个线程完成。这对于速度比锁定操作更重要的场景很有用。它也非常适合只需要一个线程执行锁定代码的情况。

if(Monitor.TryEnter(obj))
  try {
    //do something if lock is not busy
  }
finally {
    Monitor.Exit(obj);
}

最后使用的锁定机制是 ReaderWriterLock。在任何给定时间，它允许多个线程同时进行读访问，或者单个线程进行写访问。ReaderWriterLock 由于其并发读访问能力，比 Monitor 提供了更好的吞吐量。由于使用 ReaderWriter 锁可能会有点棘手，我使用了一个包装类来简化对提供委托的锁定。

代码审查

由于 LifespanMgr 是代码中最有趣的部分，我将在文章的其余部分花费大部分时间讨论它；但是，代码是高度注释的，所以您应该能够轻松地跟随其余的代码。

public void Touch()
{
    if( _value != null && ageBag != _mgr._currentBag )
    {
        if( ageBag == null )
            lock( _mgr )
                if( ageBag == null )
                {
                    // if node.AgeBag==null then the object is not
                    // currently managed by LifespanMgr so add it
                    next = _mgr._currentBag.first;
                    _mgr._currentBag.first = this;
                    Interlocked.Increment( ref _mgr._owner._curCount );
                }
        ageBag = _mgr._currentBag;
        Interlocked.Increment( ref _mgr._currentSize );
    }
    _mgr.CheckValid();
}

每次添加或引用一个索引项时，都会调用 LifespanMgr.Node.Touch()，该方法（重新）插入节点（如果需要），并将其 ageBag 变量指向当前的 AgeBag。此外，在 touch 方法中，会调用 LifespanMgr.CheckValid()。

public void CheckValid()
{
    DateTime now = DateTime.Now;
    // if lock is currently held then skip and let next Touch perform cleanup.
    if( (_currentSize > _bagItemLimit || now > _nextValidCheck) 
             && Monitor.TryEnter( this ) )
        try
        {
            if( (_currentSize > _bagItemLimit || now > _nextValidCheck) )
            {
                // if cache is no longer valid throw contents
                // away and start over, else cleanup old items
                if( _current > 1000000 || (_owner._isValid != null 
                                          && !_owner._isValid()) )
                    _owner.Clear();
                else
                    CleanUp( now );
            }
        }
        finally
        {
            Monitor.Exit( this );
        }
}

CheckValid 仅在 AgeBag 已满或指定的时限过期时执行操作。当满足任一情况时，会调用一个可选的 IsValid() 委托，该委托会检查整个缓存的运行状况。如果缓存无效或过时，缓存中的所有项目将被移除，并且在索引下次访问它们时将重新加载项目。如果 IsValid 返回 true，则调用 LifespanMgr.Cleanup() 方法。

public void CleanUp( DateTime now )
{
    if( _current != _oldest )
        lock( this )
        {
            //calculate how many items should be removed
            DateTime maxAge = now.Subtract( _maxAge );
            DateTime minAge = now.Subtract( _minAge );
            int itemsToRemove = _owner._curCount - _owner._capacity;
            AgeBag bag = _bags[_oldest % _size];
            while( _current != _oldest && (_current-_oldest>_size - 5 
                    || bag.startTime < maxAge || (itemsToRemove > 0 
                    && bag.stopTime > minAge)) )
            {
                // cache is still too big / old so remove oldest bag
                Node node = bag.first;
                bag.first = null;
                while( node != null )
                {
                    Node next = node.next;
                    node.next = null;
                    if( node.Value != null && node.ageBag != null )
                        if( node.ageBag == bag )
                        {
                            // item has not been touched since bag was
                            // closed, so remove it from LifespanMgr
                            ++itemsToRemove;
                            node.ageBag = null;
                            Interlocked.Decrement( ref _owner._curCount );
                        }
                        else
                        {
                            // item has been touched and should
                            // be moved to correct age bag now
                            node.next = node.ageBag.first;
                            node.ageBag.first = node;
                        }
                    node = next;
                }
                // increment oldest bag
                bag = _bags[(++_oldest) % _size];
            }
            OpenCurrentBag( now, ++_current );
            CheckIndexValid();
        }
}

Cleanup 执行将已访问的项目从最后一个包移出并将其余项目删除的繁重工作。它还会调用 CheckIndexValid() 来查看是否需要重新创建索引，并调用 OpenCurrentBag() 来设置下一个当前的 AgeBag。

用法

UserCache.cs 文件包含一个缓存如何使用的示例。

/// <summary>retrieve items by userid</summary>
public UserData FindByUserID( int userid )
{
    return _findByUserID[userid];
}

/// <summary>retrieve items by username</summary>
public UserData FindByUserName( string username )
{
    return _findByUserName[username];
}

/// <summary>constructor creates cache and multiple indexes</summary>
private UserCache() : base( 10000, TimeSpan.FromMinutes( 1 ), 
                                   TimeSpan.FromHours( 1 ), null )
{
    _isValid = IsDataValid;
    _findByUserID = AddIndex<int>( "UserID", delegate( UserData user ) 
                                 { return user.UserID; }, LoadFromUserID );
    _findByUserName = AddIndex<string>( "UserName", delegate( UserData user ) 
                                      { return user.UserName; }, LoadFromUserName );
    IsDataValid();
}

摘要

此 LRUCache 实现旨在提供对多线程环境中最近使用数据的快速可靠访问。