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 больно ударит по производительности.

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

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

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