Как создать коллекцию Lockfree

Question

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

readonly ConcurrentDictionary<string, ConcurrentDictionary<int, int>> dict = new ConcurrentDictionary<string, ConcurrentDictionary<int, int>>();

void AddUpdateItem(string s, int k, int v)
{
    ConcurrentDictionary<int, int> subDict;
    if (dict.TryGetValue(s, out subDict))
    {
        subDict[k] = v;
    }
    else
    {
        lock (dict)
        {
            if (dict.TryGetValue(s, out subDict))
            {
                subDict[k] = v;
            }
            else
            {
                subDict = new ConcurrentDictionary<int, int>();
                subDict[k] = v;
                dict[s] = subDict;
            }
        }
    }
}

Answer 1

Вы можете сделать хеш-таблицу без блокировки, используя неизменяемость, но она вряд ли будет эффективной, если есть конфликт.По сути, вам нужен класс словаря-контента, который можно менять местами.Вы создаете копию текущего содержимого с одним внесенным изменением, а затем используете примитив сравнения и обмена для обмена с существующей версией.Если сравнение и замена не удаются, начните заново с шага копирования.

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

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

Answer 2

Метод ConcurrentDictionary.GetOrAdd является потокобезопасным (хотя и не атомарным). Это гарантирует, что возвращаемый объект одинаков для всех потоков. Ваш код может быть переписан как:

void AddUpdateItem(string s, int k, int v)
{
    var subDict = dict.GetOrAdd(s, _ => new ConcurrentDictionary<int, int>());
    subDict[k] = v;
}

Answer 3

Используете ли вы задачи или потоки в вашем коде? В любом случае, ConcurrentDictionary разработан, чтобы быть потокобезопасным. Вам не нужно использовать блокировки при добавлении или удалении элементов. Ссылка из MSDN Как: добавлять и удалять элементы из ConcurrentDictionary объясняет, как его использовать.

Answer 4

прежде чем идти по пути реализации коллекции без блокировки, взгляните на ReadWriteLock , которая решит вашу проблему. Если этого не произойдет (например, из-за серьезного конфликта записи), на самом деле не существует единого подхода, подходящего для всех.

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

Answer 5

Если вы умозрительно создаете под-словарь, есть более простое решение:

readonly ConcurrentDictionary<string, ConcurrentDictionary<int, int>> dict = new ConcurrentDictionary<string, ConcurrentDictionary<int, int>>();

void AddUpdateItem( string s, int k, int v )
{
    ConcurrentDictionary<int, int> subDict;

    while ( true )
    {
        if ( dict.TryGetValue( s, out subDict ) )
        {
            subDict[ k ] = v;
            break;
        }

        // speculatively create new sub-dictionary
        subDict = new ConcurrentDictionary<int, int>();
        subDict[ k ] = v;

        // this can only succeed for one thread
        if ( dict.TryAdd( s, subDict ) ) break;
    }
}