Потокобезопасность для высокопроизводительного кэша в памяти

Question

У меня есть статический кэш в памяти, который записывается только один раз в час ( или более ), а читается многими потоками с чрезвычайно высокой скоростью . Обычная мудрость предполагает, что я следую примеру, подобному следующему:

public static class MyCache
{
    private static IDictionary<int, string> _cache;
    private static ReaderWriterLockSlim _sharedLock;

    static MyCache()
    {
        _cache = new Dictionary<int, string>();
        _sharedLock = new ReaderWriterLockSlim();
    }

    public static string GetData(int key)
    {
        _sharedLock.EnterReadLock();
        try
        {
            string returnValue;
            _cache.TryGetValue(key, out returnValue);
            return returnValue;
        }
        finally
        {
            _sharedLock.ExitReadLock();
        }
    }

    public static void AddData(int key, string data)
    {
        _sharedLock.EnterWriteLock();
        try
        {
            if (!_cache.ContainsKey(key))
                _cache.Add(key, data);
        }
        finally
        {
            _sharedLock.ExitWriteLock();
        }
    }
}

Как упражнение в микрооптимизации, как я могу сбить еще больше тиков в относительной стоимости общих чтения блокировок? Время записи может быть дорогим, так как это случается редко. Мне нужно сделать чтение как можно быстрее. Могу ли я просто снять блокировки read (ниже) и остаться поточно-ориентированным в этом сценарии? Или есть версия без блокировки , которую я могу использовать? Я знаком с защитой памяти, но не знаю, как безопасно применять ее в этом случае.

Примечание: я не привязан ни к одному шаблону, поэтому любые предложения приветствуются, если конечный результат быстрее и в C # 4.x. *

public static class MyCache2
{
    private static IDictionary<int, string> _cache;
    private static object _fullLock;

    static MyCache2()
    {
        _cache = new Dictionary<int, string>();
        _fullLock = new object();
    }

    public static string GetData(int key)
    {
        //Note: There is no locking here... Is that ok?
        string returnValue;
        _cache.TryGetValue(key, out returnValue);
        return returnValue;
    }

    public static void AddData(int key, string data)
    {
        lock (_fullLock)
        {
            if (!_cache.ContainsKey(key))
                _cache.Add(key, data);
        }
    }
}

Answer 1

Вам не нужна блокировка, когда есть потоки, которые только читают из структуры данных. Таким образом, поскольку записи выполняются очень редко (и, я полагаю, не одновременно), можно сделать полную копию словаря, внести изменения в копию и затем атомарно заменить старый словарь новым:

public static class MyCache2
{
    private static IDictionary<int, string> _cache;

    static MyCache2()
    {
        _cache = new Dictionary<int, string>();
    }

    public static string GetData(int key)
    {
        string returnValue;
        _cache.TryGetValue(key, out returnValue);
        return returnValue;
    }

    public static void AddData(int key, string data)
    {
        IDictionary<int, string> clone = Clone(_cache);
        if (!clone.ContainsKey(key))
            clone.Add(key, data);
        Interlocked.Exchange(ref _cache, clone);
    }
}

Answer 2

Я бы хотел освободиться от блокировки и добиться безопасности потоков, просто не меняя ни один опубликованный словарь . Я имею в виду следующее: когда вам нужно добавить данные, создайте полную копию словаря и добавьте / обновите / etc copy . Так как это раз в час, это не должно быть проблемой даже для больших данных. Затем, когда вы внесли изменения, просто поменяйте ссылку со старого словаря на новый словарь (чтение / запись ссылки гарантированно будут атомарными).

Одно предупреждение: любой код, которому требуется согласованное состояние между множественными операциями, должен сначала захватить словарь в переменную, т. Е.

var snapshot = someField;
// multiple reads on snapshot

Это гарантирует, что любая связанная логика будет создана с использованием одной и той же версии данных, чтобы избежать путаницы при замене ссылки во время операции.

Я бы также взял блокировку при записи (не при чтении), чтобы не допустить склоки по данным. Существуют также подходы с несколькими модулями записи без блокировок (в первую очередь Interlocked.CompareExchange и повторное применение в случае сбоя), но я бы сначала использовал самый простой подход, и именно такой модуль записи является именно таким.

Answer 3

Альтернативный вариант: хеш-таблица .net 1.x (по сути, словарь, за исключением обобщений) имеет интересную историю с многопоточностью; чтения являются поточно-ориентированными без блокировок - вам нужно использовать блокировки только для обеспечения не более одного писателя.

Итак: вы можете рассмотреть возможность использования не универсальной Hashtable, без блокировки чтения, а затем взять блокировку во время записи.

Это основная причина, по которой я до сих пор иногда использую Hashtable, даже в приложениях .net 4.x.

Одна проблема, однако, - это приведет к тому, что ключ int будет упакован как для хранилища, так и для запроса.

Answer 4

Это делает копию словаря только при добавлении данных. Для добавления используется блокировка, но вы можете снять ее, если не собираетесь добавлять из более чем одного потока. Если копии нет, то данные извлекаются из исходного словаря, в противном случае копия используется при добавлении.

Просто на тот случай, если копия будет обнулена после того, как она проверена и будет выглядеть как не нулевая, но прежде чем она сможет получить значение, я добавил попытку try, которая в этом редком случае извлекает данные из оригинала, который затем заблокирован, но опять же, это должно случиться очень редко, если вообще.

public static class MyCache2
{
    private static IDictionary<int, string> _cache;
    private static IDictionary<int, string> _cacheClone;
    private static Object _lock;

    static MyCache2()
    {
        _cache = new Dictionary<int, string>();
        _lock = new Object();
    }

    public static string GetData(int key)
    {
        string returnValue;
        if (_cacheClone == null)
        {
            _cache.TryGetValue(key, out returnValue);
        }
        else
        {
            try
            {
                _cacheClone.TryGetValue(key, out returnValue);
            }
            catch
            {
                lock (_lock)
                {
                    _cache.TryGetValue(key, out returnValue);
                }
            }
        }
        return returnValue;
    }

    public static void AddData(int key, string data)
    {
        lock (_lock)
        {
            _cacheClone = Clone(_cache);
            if (!_cache.ContainsKey(key))
                _cache.Add(key, data);
            _cacheClone = null;
        }
    }
}

Answer 5

Вы также можете посмотреть на структуры данных без блокировки.http://www.boyet.com/Articles/LockfreeStack.html хороший пример