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

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

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

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

Обратимся к статье, указанной выше:

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]

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

Давайте заглянем в исходники ^[2] данной коллекции, а именно на реализацию метода 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 и Remove не изменяют размера массива и, соответственно, эти изменения всегда будут видны для итератора (конечно, если речь идет о изменение элемента, до которого итератор еще «не добрался»).

Заключение

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

Автор: a_mastrakov

Источник ^[3]