0

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

ConcurrentDictionary<Id, myClass> Info;
ConcurrentDictionary<string, Id> InfoIndex;
class myClass
{
    string Nomer;
    string FirstName;
    string SecondName;
    //...
}
struct Id
{
    int id1;
    int id2;
}

Уверен, что возможно lock-free-решение, но мозг не справляется...

3
  • а какие проблемы с ConcurrentDictionary ? Вам в нем чего то не хватает?
    – tym32167
    11 янв 2018 в 9:43
  • Не хватает второго ключа для скорости поиска, первый ключ для связки с глобальным массивом - это 50+ тыс. записей, а второй для непосредственно работы разрозненных подключаемых модулей с собственными классификаторами (до 5 тыс. записей). Вот пытаюсь решить как в связку коллекций атомарно (потокобезопасно) добавить запись, используя возможности ConcurrentDictionary, но не используя локингов 11 янв 2018 в 10:23
  • 1
    Атомарно без лока с 2 коллекциями, мне кажется, не получится работать. Но я вообще не спец в этом
    – tym32167
    11 янв 2018 в 11:14

1 ответ 1

2

Если для одного экземпляра myClass ты можешь гарантировать уникальность Id и String и не будешь удалять записи, то никаких проблем нет. Работай с ними, как с независимыми словарями.

void TryAdd(Id id, String name, myClass info)
{
    Info.TryAdd(id, info);
    InfoIndex.TryAdd(name, id);
}

Поиск по string будет возвращать null, если Id зарегистрирован, а String - ещё нет.

myClass Find(Id id)
{
    return Info.TryGetValue(id, out var value) ? value : null;
}

myClass Find(String key)
{
    return InfoIndex.TryGetValue(key, out var id) ? Find(id) : null;
}

Если у тебя появится удаление то ты неминуемо столкнёшься с гонками: Поток 1 удаляет запись из коллекции 1 Поток 2 добавляет запись в коллекцию 1 Поток 2 пытается добавить запись в коллекцию 2 Поток 1 удаляет запись из коллекции 2 В итоге, соответствие есть только в одном словаре. Это можно обойти банальным while(true), который ты будешь выполнять до тех пор, пока элемент не будет добавлен/удалён в/из обеих коллекций.

void Remove(String key)
{
    if (!InfoIndex.TryGetValue(key, out var id))
        return;

    while (Info.TryRemove(id, out _) || InfoIndex.TryRemove(key, out _))
        ;
}

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

Если удаления нет, то нет и таких проблем. Но всё это справедливо лишь до тех пор, пока Id и String. Если для одного и того же myClass они могут различаться, ты получишь неверные связи, которые, опять же, разрешить сможешь только при помощи while(true).

Не вздумай взаимодействовать со вторым словарём в фабрике значений при отложенном добавлении элементов из первого. Потенциально это ведёт к дедлокам, кроме того фабрика может быть вызвана множество раз, может сконструировать множество объектов, и лишь один поместить в словарь.

Ты можешь взять исходники ConcurrentDictionary с GitHub и реализовать собственный вариант с парными ключами, не преумножая количество локов.

Наконец, стоит подумать (и прогнать тесты) - а стоит ли использовать в данном случае ConcurrentDictionary? Во-первых, насколько часто ты добавляешь и удаляешь элементы в словарь? Если не часто, и ConcurrentDictionary используется для свободного перечисления, то локи ничем не повредят. Если часто, то вместо lock можно использовать SpinLock. Фактически, это та самая блокировка на while(true). В такой ситуации тебе не подойдёт отложенное создание сложных объектов. Но риск поймать длительную блокировку словаря всё равно есть, и тогда SpinLock больно ударит по производительности.

Выбор за тобой.

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.