Как стать автором
Обновить

Изменение ConcurrentDictionary во время перебора

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

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

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

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

Ну весьма логично, что изменения элементов которые итератор уже прошел не будут учтены при переборе коллекции. А что будет, если изменить элемент до которого итератор еще «не добрался» или если вставить новый элемент в коллекцию?
Обратимся к MSDN (русский перевод данной заметки сделан не очень хорошо, поэтому я также вставлю заметку на языке оригинала):
Перечислитель, возвращенный из словаря, безопасно использовать одновременно с чтением из словаря и записью в него, однако он не представляет моментальный снимок словаря. Содержимое, доступное через перечислитель, может содержать изменения, внесенные в словарь, после вызова GetEnumerator.

The enumerator returned from the dictionary is safe to use concurrently with reads and writes to the dictionary, however it does not represent a moment-in-time snapshot of the dictionary. The contents exposed through the enumerator may contain modifications made to the dictionary after GetEnumerator was called.

Меня, как человека с техническим образованием, смущает формулировка «может содержать». Т.е. может содержать, а может и не содержать? Давайте проверим:

ConcurrentDictionary<int, string> dictionary = new ConcurrentDictionary<int, string>();
dictionary.TryAdd(0, "item0");
int x = 1;
foreach (var element in dictionary)
{
    var tmp = x++;
    if (!dictionary.TryAdd(tmp, "item" + tmp.ToString()))
    {
        throw new Exception("Вставить элемент не удалось");
    }
    Console.WriteLine(element);
}


Что же будет выведено в консоль? Один элемент или программа войдет в бесконечный цикл? Ни то, ни другое. Будет выведено следующее:

[0, item0]
[1, item1]
[2, item2]
[3, item3]
[4, item4]
[5, item5]
[6, item6]
[7, item7]
[8, item8]
[9, item9]
[10, item10]
[11, item11]
[12, item12]
[13, item13]
[14, item14]
[15, item15]
[16, item16]

Исключения не возникло, соответственно, 18 элемент в коллекцию был вставлен успешно, но итератор его не увидел, почему?

Давайте заглянем в исходники данной коллекции, а именно на реализацию метода GetEnumerator:

public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator()
{
    Node[] buckets = m_tables.m_buckets;

    for (int i = 0; i < buckets.Length; i++)
    {
        // The Volatile.Read ensures that the load of the fields of 'current' doesn't move before the load from buckets[i].
        Node current = Volatile.Read<Node>(ref buckets[i]);

        while (current != null)
        {
            yield return new KeyValuePair<TKey, TValue>(current.m_key, current.m_value);
            current = current.m_next;
        }
    }
}

Поле m_tables помечено ключевым словом volatile, поэтому изменение содержащегося в нем массива Node[] m_buckets видны всем потокам. Каждый элемент этого массива представляет собой первый элемент в односвязном списке и содержит ссылку на следующий элемент в списке. Далее легко догадаться, что до тех пор, пока добавление/изменение элементов приводит к изменению самих односвязных списков, итератор «видит» эти изменения, но изменения самого массива для итератора не видны.

Изменение массива m_buckets происходит в двух случаях. Первый — это увеличение размера при вставке элементов, второй — вызов метода Clear() (сбрасывает размер массива до значения по-умолчанию).
Update:
Для того, чтобы ответить на вопрос когда увеличивается размер массива m_buckets, сделаю небольшую ремарку о внутренней структуре ConcurrentDictionary.
Для обеспечения блокировок на операции Добавление/Изменение/Удаление элемента из коллекции имеется массив object[] m_locks, его размер по умолчанию равен 4*число_процессоров (при каждом увеличении m_tables.m_buckets, размер массива с объектами для блокировок увеличивается в 2 раза).
Так же имеется поле int m_budget — определяющее максимальное количество элементов на одну блокировку. Оно вычисляется следующим образом: m_buckets.Length/m_locks.Length.
Количество элементов для каждой блокировки содержится в поле int[] m_countPerLock, которое инкрементируется при добавлении нового элемента в связанный список, и декрементируется при удалении элемента из списка.
Теперь вернемся к условию увеличения массива m_buckets. Он увеличивается после того, как выполнится условие tables.m_countPerLock[lockNo] > m_budget, т.е. когда количество элементов на одну блокировку превышает масимально разрешенное число. Нужно отметить, что эта проверка происходит в конце метода вставки элемента, и изменение размера внутренней коллекции m_buckets произойдет уже после того как текущий элемент был вставлен в нее.
На моем примере: у меня 4 процессора, соответственно размер массива m_locks = 16, а m_budget = 31/16 = 1. Как только мы вставляем 17 элемент, на одну блокировку теперь приходится 2 элемента и коллекция расширяется.
/Update
Операции Update и Remove не изменяют размера массива и, соответственно, эти изменения всегда будут видны для итератора (конечно, если речь идет о изменение элемента, до которого итератор еще «не добрался»).

Заключение

Несмотря на то, что мы теперь знаем, когда изменения, внесенные во время перебора коллекции, будут видны, а когда нет, учитывать данные знания при программировании с использованием ConcurrentDictionary не стоит. Лучше всего придерживаться правила описанного на MSDN, что внесенные изменения могут быть видны, а могут и нет.
Теги:
Хабы:
Всего голосов 19: ↑16 и ↓3 +13
Просмотры 11K
Комментарии Комментарии 12