четверг, 18 июня 2015 г.

Небольшой трюк при работе с ConcurrentDictionary

У использования ConcurentDictionary есть одна особенность: в некоторых случаях он может вести себя не совсем так, как вы того ожидаете. Вот небольшой пример. Допустим, нам нужно запилить небольшой кэш, чтобы результаты дорогостоящей операции брались из кэша, если они там есть, ну и добавлялись в кэш прозрачным образом, если Акела промахнулся.

Простая реализация некоторого провайдера с cache aside паттерном будет выглядеть примерно так:

public class CustomProvider
{
   
private readonly ConcurrentDictionary<string, OperationResult> _cache =
        new ConcurrentDictionary<string, OperationResult>
();

   
public OperationResult RunOperationOrGetFromCache(string
operationId)
    {
       
return _cache.GetOrAdd(operationId, id =>
RunLongRunningOperation(id));
    }

   
private OperationResult RunLongRunningOperation(string
operationId)
    {
       
// Running real long-running operation
        // ...
        Thread.Sleep(10
);
       
Console.WriteLine("Running long-running operation"
);
       
return OperationResult.Create(operationId);
    }
}

 

С точки зрения многопоточности эта реализация совершенно корректна. Даже если метод RunOperationOrGetFromCache для одного и того же operationId будет вызван из двух потоков, то каждый из них получит один и тот же результат. Проблема же в том, что хоть результат и будет один и тот же, но запущено будет две операции. Результат первой будет помещен в кэш, а результат второй операции – выброшен!

Причина в реализации метода AddOrGet класса ConcurrentDictionary. По сути, использование AddOrGet эквивалентно последовательному использованию методов TryGetValue и TryAdd в нашем собственном коде (метод AddOrGet немногим сложнее, чем простой вызов этих двух методов):

public OperationResult RunOperationOrGetFromCache(string operationId)
{
   
OperationResult
result;
   
if (_cache.TryGetValue(operationId, out
result))
    {
       
return
result;
    }

    result
=
RunLongRunningOperation(operationId);
    _cache
.
TryAdd(operationId, result);
   
return result;
}

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

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

ConcurrentDictionary<string, Lazy<OperationResult>> _cache =
    new ConcurrentDictionary<string, Lazy<OperationResult>>
();

public OperationResult RunOperationOrGetFromCache(string
operationId)
{
   
return _cache.
GetOrAdd(operationId,
        id
=> new Lazy<OperationResult>(() => RunLongRunningOperation(id))).Value;
}

Вместо непосредственно хранения результата длительной операции, кэш хранит «ленивую оболочку» - Lazy<OperationResult>. В этом случае, при одновременном обращении к кэшу из нескольких потоков несколько раз будет вызван лишь конструктор объекта Lazy<T>, а непосредственно операция будет запущена лишь один раз – при обращении к свойству Value!

21 комментарий:

  1. Элегантно.
    Т.е. технически мы вызвали конструктор, объект зашел в коллекцию (что отработает быстро) и только потом начнется выполнение RunLongRunningOperation при обращении к Value. Ок, а что будет если два потока попросят значение из кеша? Первый запустит RunLongRunningOperation, а второй будет ждать, пока отработает первый, чтобы тоже получить закешированное значение? Ведь первый поток все еще ждет, пока ему вернется значение. Можно чуть поподробнее про такой кейс?

    ОтветитьУдалить
    Ответы
    1. Оба потока быстро получат ссылку на один и тот же Lazy-объект и уже именно экземпляр Lazy<> будет блокировать вызывающие потоки, заставляя всех ждать одно и то же значение.

      Удалить
    2. Если два потока попросят значение, то первый запустит операцию, а второй будет ждать ее заверершения. Но, с другой стороны, ведь и без этого хака оба потока бы синхронно сидели бы и ждали окончания длительной операции. Но если она CPU-Intensive, то в старом случае мы бы тратили ресурсы на ее исполнение, а в новом - просто ждали бы результата, висев на синхронизации в объекте Lazy.Value.

      Удалить
  2. Здесь также возможен двойной/тройной/etc вызов длительной операции, т.к. в случае _одновременного_ вызова GetOrAdd несколькими потоками каждый из них получит свой экземпляр lazy-объекта. Конечно, вероятность этого многократно ниже чем в классическом варианте.

    ОтветитьУдалить
    Ответы
    1. Создание РАЗНЫХ lazy-объектов произойдёт, но возвращён будет всё равно ОДИН и тот же экземпляр, а новые lazy-объекты будут утеряны (вместо потери результатов долгой операции).

      Удалить
    2. А внимательно посмотреть на код не судьба?

      result = RunLongRunningOperation(operationId);
      _cache.TryAdd(operationId, result);
      return result;

      result добавится единожды, но то, что вернет GetOrAdd будет ИПСПОЛЬЗОВАНО, а соответвенно вызвана длительная операция.

      Удалить
    3. @Beat несколько агрессивно и нифига не понятно.
      Приведенный пример во втором комментарии откуда взят? Я им объяснял как работает GetOrAdd.

      Теперь по поводу первого коммента: Алексей ответил совершенно правильно, сколько бы потоков не вызывали GetOrAdd ConcurrentDictionary гарантирует, что все они получат *одну и ту же ссылку*. Это значит, что в исходном примере без Lazy (проще понимать), будет запущено N операций, в кэш добавлена первая, а метод TryAdd внутри метода GetOrAdd снова проверит, а нет ли уже такого значения в кэше, и если есть, то вернет существующее значение, а новое выбросит.

      Удалить
    4. Я ссылался на приведенный выше ко. RunOperstionOrGetFromCache. А можете привести кож реального GetOrAdd или описание такого поведения.

      Удалить
    5. В заметке приведено три разных версии метода RunOperationOrGetFromCache. Вы взяли, почему-то, вторую, которая вообще не использует GetOrAdd, и не использует Lazy. Нужно смотреть на последний пример.

      З.Ы. Код реального GetOrAdd: http://referencesource.microsoft.com/#mscorlib/system/Collections/Concurrent/ConcurrentDictionary.cs,2f8bcdfbad10304f

      Реальное поведение описано в статье, потом в первом комменте Алексея и в моем предыдущем комменте.

      Удалить
    6. О том что getoradd снова проверит наличие в кеше и вернет значение из негр в случае если оно есть в статье не сказано. Меня интересовал именно этот момент.

      Удалить
    7. Из статьи:

      > С точки зрения многопоточности эта реализация совершенно корректна. Даже если метод RunOperationOrGetFromCache для одного и того же operationId будет вызван из двух потоков, то каждый из них получит один и тот же результат. Проблема же в том, что хоть результат и будет один и тот же, но запущено будет две операции.

      Хотя, возможно, на этом моменте стоило сильнее акцент сделать.

      Удалить
    8. Возвращаясь к моему изначальному вопросу: подскажите, такое поведение GetOrAdd где-нибудь описано у МС? Для меня оно было не очевидным осшбенно в виду массы примеров в инете похожим на тот второй что я сослался.

      Удалить
    9. Из официальной документации:https://msdn.microsoft.com/en-us/library/ee378677(v=vs.110).aspx

      > Return Value
      Type: TValue
      The value for the key. This will be either the existing value for the key if the key is already in the dictionary, or the new value for the key as returned by valueFactory if the key was not in the dictionary.

      И секция remarks там же:

      > If you call GetOrAdd simultaneously on different threads, addValueFactory may be called multiple times, but its key/value pair might not be added to the dictionary for every call.

      Удалить
  3. Тут надо оговорится, что такой хак срабатывает, так как по умолчанию при создании Lazy используется LazyThreadSafetyMode.ExecutionAndPublication настройка.
    Она определяет как будет инициализироваться Lazy конкурентно или с блокировкой.

    Если бы ConcurrentDictionary поддерживал LazyThreadSafetyMode или что-то подобное, то хак не потребовался бы.

    PS: Есть повод отписать тикет ребятам из BCL :)

    ОтветитьУдалить
    Ответы
    1. > Тут надо оговорится, что такой хак срабатывает, так как по умолчанию при создании Lazy используется LazyThreadSafetyMode.ExecutionAndPublication настройка.
      Да, это валидное замечание.

      > Если бы ConcurrentDictionary поддерживал LazyThreadSafetyMode или что-то подобное, то хак не потребовался бы.

      Пока не представляю, каким образом это можно решить без потери производительности на стороне ConcurentDictionary. Он так ведет себя by design, наличие блокировок на его уровне сделает его менее эффективным для других сценариев.

      Удалить
  4. Решение интересное, но есть вопрос к memory traffik. (После .NEXT стараюсь замечать такие моменты :))

    На каждый элемент коллекции, дополнительно, создаются 3 объекта.
    Сам Lazy;
    Делегат, оборачивающий лямбду;
    Объект для замыкания по id для лямбды () => RunLongRunningOperation(id)

    Получается не все гладко при большом размере такой коллекции.

    ОтветитьУдалить
    Ответы
    1. Lazy - это структура - это плюс, но есть вложенный делегат - это минус.Замыкание остается тем же, но дополнительная аллокация на делегат появится.

      Правда сам ConcurrentDictionary дает достаточно большой overhead. Мы в своем проекте были вынуждены от него отказаться в некоторых местах в пользу кастомного решения, поскольку overhead его составлял сотни мегабайт памяти в определенных сценариях. Но у нас сильно нетипичная задача.

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

      Удалить
    2. Да, Lazy - это класс, так что будет две дополнительные аллокации.

      Удалить
  5. Всем спасибо за разъяснение и дискуссию. Еще раз убедился в том, что не надо стесняться задавать "глупые" вопросы :)

    ОтветитьУдалить
    Ответы
    1. Конечно не надо! Ведь для меня это же тоже полезная обратная связь, которая подтвердила мое предположение, что писал я достаточно быстро и, значит, не всем будет понятно:)

      Удалить
  6. Есть вопрос. А почему MS вообще делают такую реализацию ConcurrentDictionary?
    Это баг или есть конкретное обоснование такой реализации?

    Т.е., если заглянуть внутрь класса ConcurrentDictionary, то (на первый взгляд всяком случае) кажется, что проблему можно было бы решить, если ввести перегрузку метода
    TryAddInternal, которая могла бы принимать на вход делегат.
    Тогда можно было бы вызывать эту перегрузку внутри перегрузки метода GetOrAdd, который принимает делегат, т.е. как-то так:

    public TValue GetOrAdd(TKey key, Func valueFactory)
    {
    if ((object) key == null)
    throw new ArgumentNullException("key");
    if (valueFactory == null)
    throw new ArgumentNullException("valueFactory");
    TValue resultingValue;
    if (this.TryGetValue(key, out resultingValue))
    return resultingValue;
    this.TryAddInternal(key, valueFactory, false, true, out resultingValue);
    return resultingValue;
    }

    ОтветитьУдалить