Comments 44
Та-да:
Thread-safe Collections in .NET Framework 4 and Their Performance Characteristics
www.google.ru/url?sa=t&rct=j&q=&esrc=s&source=web&cd=2&ved=0CCwQFjAB&url=http%3A%2F%2Fdownload.microsoft.com%2Fdownload%2FB%2FC%2FF%2FBCFD4868-1354-45E3-B71B-B851CD78733D%2FPerformanceCharacteristicsOfThreadSafeCollection.pdf&ei=e0KJUPPBMMPd4QSe5YDQDA&usg=AFQjCNFiqwg34_7Du233kJjkZRBTVzWDBg&cad=rja
Thread-safe Collections in .NET Framework 4 and Their Performance Characteristics
www.google.ru/url?sa=t&rct=j&q=&esrc=s&source=web&cd=2&ved=0CCwQFjAB&url=http%3A%2F%2Fdownload.microsoft.com%2Fdownload%2FB%2FC%2FF%2FBCFD4868-1354-45E3-B71B-B851CD78733D%2FPerformanceCharacteristicsOfThreadSafeCollection.pdf&ei=e0KJUPPBMMPd4QSe5YDQDA&usg=AFQjCNFiqwg34_7Du233kJjkZRBTVzWDBg&cad=rja
In memory на слабых ссылках CopyOnWrite решение чем вам не подошло?
Ваше просядет под нагрузкой.
Ваше просядет под нагрузкой.
А можно поподробнее?
Если говорить о Яве — это решения на слабых ссылках — например: WeakHashMap или аналогичных структурах, Если в шарпе нет возможности использовать слабые ссылки — я буду сильно удивлен… а unmanaged тогда зачем?
А CopyOnWrite — это стандартный паттерн когда чтение происходит из неизменяемой коллекции, а при вставке создается новая ( копированием из старой) и на нее уже передается управление читающим после полного создания. Вставлять можно не по одному значению, получается очень экономично по ресурсам и выдерживает невероятные нагрузки.
А CopyOnWrite — это стандартный паттерн когда чтение происходит из неизменяемой коллекции, а при вставке создается новая ( копированием из старой) и на нее уже передается управление читающим после полного создания. Вставлять можно не по одному значению, получается очень экономично по ресурсам и выдерживает невероятные нагрузки.
ConcurrentDictionary внутри и реализует CopyOnWrite (только для отдельного элемента) насколько я понимаю. Тем не менее возможен случай, когда нужно прочитать данные, на их основе что то вычислить и записать обратно (в статье это указано). В такой ситуации вам не обойтись без блокировки или атомарных операций (которые как раз и использует данный словарь).
А зачем вам здесь слабые ссылки?
А зачем вам здесь слабые ссылки?
А каким чудом тогда
Слабые ссылки в первую очередь для того чтобы кеш не мешал жизни приложений. Постановка задачи в статье — не кеш, а конкаренси стораж, что довольно сложно понять из названия.
Чтение по значению ощутимо бьёт по производительности если внутри CopyOnWrite…?Слабые ссылки в первую очередь для того чтобы кеш не мешал жизни приложений. Постановка задачи в статье — не кеш, а конкаренси стораж, что довольно сложно понять из названия.
ConcurrentDictionary как и Dictionary — это типизированная хеш-таблица, а хеш-таблицы умеют быстро искать только по ключу. Автору же этого мало и он иногда хочет поискать не по ключу, а по значению (т.е. тупо перебрать все значения и найти подходящие). Ну и логично — чем больше таких поисков, тем дольше работает.
По поводу слабых ссылок — мне кажется что тут уже зависит от того как использовать кеш — ведь если после получения объект быстро перестает использоваться, то его соберет GC и в кеше будут только мертвые ссылки храниться. А так да, при необходимости, есть возможность в значении хранить не сам объект а WeakReference указывающий на этот объект.
По поводу слабых ссылок — мне кажется что тут уже зависит от того как использовать кеш — ведь если после получения объект быстро перестает использоваться, то его соберет GC и в кеше будут только мертвые ссылки храниться. А так да, при необходимости, есть возможность в значении хранить не сам объект а WeakReference указывающий на этот объект.
Для отдельного элемента — да. Благодаря линкед-листам ConcurrentDictionary позволяет использовать итератор без блокировки (т.е. одновременно с записью). Эту же задачу, в целом, решает и CopyOnWrite.
А слабые ссылки позволяют избегать утечек при реализации, т.е. прямого отношения к задаче не имеют.
А слабые ссылки позволяют избегать утечек при реализации, т.е. прямого отношения к задаче не имеют.
Слабые ссылки в CLR, кстати, есть.
А они скольких типов в шарпе? В Явах — целых 3 вида, а у вас? ;)
Смотря что вы имеете в виде. Если я использую CLR, то там два вида (короткие и длинные, если кратко).
Но я в основном сейчас пишу на Ruby и Perl. Кстати, даже в PHP оные WeakRef вроде как есть.
Но я в основном сейчас пишу на Ruby и Perl. Кстати, даже в PHP оные WeakRef вроде как есть.
В статье рассматривались только стандартные решения для .NET. Ссылку на исходники я выложил — можно реализовать свой обработчик операций и протестировать. Если речь о проектировании нашего сервера — это офтопик, не хочу вступать в холивары. На данный момент по ряду причин нам больше подходит то решение, которое реализовано.
А вы какую политику ставили для ReaderWriterLockSlim?
Вы о LockRecursionPolicy? В приведённых тестах — дефолтная. Пробовал и NoRecursion и SupportsRecursion — разницы нет, в принципе рекурсия то и не используется.
Да, о ней. Мне просто всегда было любопытно, как влияет политика на быстродействие. Сам я этот механизм в critical performance scope никогда не использовал.
Насколько я знаю, у него как киллер-фича (в отличие от простого ReaderWriterLock) декларировалось то, что по умолчанию выключена поддержка рекурсии, что вроде как должно издержки снижать. Но что-то у меня не получилось с ним подружиться — возможно профит заметен если использовать собственно рекурсию или апгрейды ридера на райтер (которые вроде как тоже улучшались).
Странно, например здесь другие результаты (нижний график):
blogs.msdn.com/b/pedram/archive/2007/10/07/a-performance-comparison-of-readerwriterlockslim-with-readerwriterlock.aspx
blogs.msdn.com/b/pedram/archive/2007/10/07/a-performance-comparison-of-readerwriterlockslim-with-readerwriterlock.aspx
Там измеряли сами блокировки чтения и записи по отдельности. И они естественно проиграли простому как репа монитору. Здесь же чтение и записть происходит одновременно, что позволяет ReaderWriterLocker'у получить преимущество над монитором.
Я про ReaderWriterLock vs. ReaderWriterLockSlim, на нижнем графике что первый медленее второго в 3 раза.
Ну вроде по хорошему так и должно быть, не в 3 раза конечно, но профит должен быть. Собственно по слиму мой основной вывод — я не умею его готовить. Либо его оптимально использовать в каких-то сложных ситуациях. Возможно, кто-то найдёт в исходниках соль проблемы. Но он в любом случае по своей сути не будет быстрее ConcurrentDictionary. Да и OneManyResourceLock наверняка пооптимальнее.
А вы не замеряли результаты когда такой словарь заполнен несколькими гб записей. Большая ли просадка в производительности?
Не измерял, но теоретически ConcurrentDictionary как-то работать будет. А вот словари с блокировкой помрут я думаю. В принципе это уже несколько иная задача и надо использовать другие средства — не думаю, что гонять итератор по много-гигабайтному словарю хорошая идея.
ненаучный бред какой-то — «не проверял, но теоретически работать будет, а остальное помрет».
Что у Dictionary, что у ConcurrentDictionary внутри массивы бакетов. С инициализацией переменной типа int, а значит максимальной размерностью в 2,147,483,647. Отличие в том, что для ConcurrentDictionary размер массива равен заданному (или дефолтному) capacity, а для Dictionary берется минимальное число 2^N, большее заданного capacity. Остальные различие в структуре несущественны (у одного массив блокировок и счетчиков, у другого массив интов). Так что, больше двух миллионов записей ни один из этих словарей не выдержит.
Что интересно, массивы могут без проблем иметь и размерность long, но для этого надо будет переписать некоторые методы классов, а лучше предварительно дать самому себе подзатыльник за мысль использовать не-специализированные средства для таких объемов.
Что у Dictionary, что у ConcurrentDictionary внутри массивы бакетов. С инициализацией переменной типа int, а значит максимальной размерностью в 2,147,483,647. Отличие в том, что для ConcurrentDictionary размер массива равен заданному (или дефолтному) capacity, а для Dictionary берется минимальное число 2^N, большее заданного capacity. Остальные различие в структуре несущественны (у одного массив блокировок и счетчиков, у другого массив интов). Так что, больше двух миллионов записей ни один из этих словарей не выдержит.
Что интересно, массивы могут без проблем иметь и размерность long, но для этого надо будет переписать некоторые методы классов, а лучше предварительно дать самому себе подзатыльник за мысль использовать не-специализированные средства для таких объемов.
Для меня основной вывод из статьи такой: не использовать ни одно из рассмотренных решений, если требуется быстрый поиск как по ключу, так и по значению на больших объёмах данных. В принципе, это и так было почти очевидно. Я не имею в виду конкретно ситуацию автора.
Думаю, в случаях частого поиска по значению на больших объёмах данных можно посмотреть в сторону своего велосипеда.
Думаю, в случаях частого поиска по значению на больших объёмах данных можно посмотреть в сторону своего велосипеда.
По графику не понял, если доля операций чтения растет, почему время выполнения тоже растет? Почему 0 при нулевой доле? Время write операций не учитывается?
Здесь растёт доля не всех операций чтений, а только по значению. Операций чтения здесь фиксированно 20%, указанная доля по поси X — доля чтения по значению, то что остаётся — чтение по ключу. Околонулевое время при 0% чтения по значению объясняется малым количеством операций в тесте — получается что запись/чтение по ключу отрабатывает мгновенно. Если увеличить количество операций — увидим ту же картину, но с большими числами, соответственно в нуле будет не 0 по Y, а некое число побольше.
А как это чтение по значению? Что за метод, для Dictionary например?
dictionary.FirstOrDefault(..) например, или dictionary.Values.ToArray(). Такие операции будут отрабатывать значительно дольше нежели просто чтение данных по ключу. Собственно на графике нарисовано — насколько дольше. Вот таблица с полными данными — yadi.sk/d/n5ycSsDf0O3Sf (в статье ссылка тоже есть).
dictionary.FirstOrDefault(..) — это же вообще через Linq, dictionary.Values.ToArray() — здесь, слишком большие накладные расходы, что там можно про сам dictionary намерить?!
И зачем нужна такая операция для реализации кэша?! Удалять устаревшие?
И зачем нужна такая операция для реализации кэша?! Удалять устаревшие?
Измерялся не сам Dictionary, а его применение в качестве кэша таблиц-справочников. Для них, к сожалению, приходится использовать итератор — тут и поиск нужен, и запрос всех значений. Например, для того чтобы отобразить все элементы для редактирования — нам нужен запрос всех значений. Поиск может понадобиться, например, для фильтра по ParentId. А удаление устаревших это несколько в другую степь — здесь именно справочник, синхронизированный с таблицей в БД.
Ну так может завести второю коллекцию, которая заточена под те операции которые вам еще нужны. Зачем мучить словарь, если у вас этих операций много, он же не для этого? Опять же под запросы по ParentId (не знаю что там у вас) наверное тоже можно организовать структуру данных.
Мне логика совершенно не понятна, если у вас таких операций может быть 80% процентов, тогда нужно их опимизировать, смысл какой от словаря?!
Мне логика совершенно не понятна, если у вас таких операций может быть 80% процентов, тогда нужно их опимизировать, смысл какой от словаря?!
Нет смысла при 80%. Объект исследования — эффективность параллельных операций записи/чтения в коллекции, а не необходимость использования словаря. На практике большинство операций — чтение по ключу. Однако только ими обходиться утопчино. Можно представлять кэш в виде нескольких коллекций, заточнных под конкретную операцию, как вы предлагаете. Даже иногда нужно. Но это требует затрат на синхронизацию, повышает сложность и не всгегда таким образом можно покрыть 100% случаев.
Из текста статьи становится ясно, что этот кэш справочника (справочников) — глобальный на весь сервер. Может ли при этом происходить добавление/удаление записей в справочник? Если да, то как отслеживать целостность кэша при транзакционной работе?
Попробуйте смоделировать такую ситуацию:
1. Клиент А начинает SQL-транзакцию.
2. Клиент Б начинает SQL-транзакцию.
3. Клиент А добавляет в справочник новое значение (оно добавляется в кэш или в базу или сразу туда и туда?).
4. Видит ли в данный момент клиент Б это новое значение в кэше? (транзакция клиента А еще не завершена)
Если видит, то он может попытаться, например, получить ключ по значению и нарваться на нарушение FK Constraint, если попробует воспользоваться этим ключом в базе.
5. Клиент Б добавляет в справочник новое значение.
6. Клиент А откатывает свою SQL-транзакцию (Rollback).
7. Есть ли сейчас _в кэше_ значения, добавленные пользователями А и Б?
8. Клиент Б фиксирует свою транзакцию (Commit).
9. Есть ли сейчас _в базе_ значения, добавленные пользователями А и Б?
Попробуйте описать, как будет вести себя ваша система в пунктах 4, 7 и 9. Некоторые вопросы из вышеприведенного списка могут сперва показаться наивными, но на самом деле в зависимости от реализации синхронизации данного кэша с базой можно получить самые невероятные комбинации ;)
Попробуйте смоделировать такую ситуацию:
1. Клиент А начинает SQL-транзакцию.
2. Клиент Б начинает SQL-транзакцию.
3. Клиент А добавляет в справочник новое значение (оно добавляется в кэш или в базу или сразу туда и туда?).
4. Видит ли в данный момент клиент Б это новое значение в кэше? (транзакция клиента А еще не завершена)
Если видит, то он может попытаться, например, получить ключ по значению и нарваться на нарушение FK Constraint, если попробует воспользоваться этим ключом в базе.
5. Клиент Б добавляет в справочник новое значение.
6. Клиент А откатывает свою SQL-транзакцию (Rollback).
7. Есть ли сейчас _в кэше_ значения, добавленные пользователями А и Б?
8. Клиент Б фиксирует свою транзакцию (Commit).
9. Есть ли сейчас _в базе_ значения, добавленные пользователями А и Б?
Попробуйте описать, как будет вести себя ваша система в пунктах 4, 7 и 9. Некоторые вопросы из вышеприведенного списка могут сперва показаться наивными, но на самом деле в зависимости от реализации синхронизации данного кэша с базой можно получить самые невероятные комбинации ;)
Да, это главный недостаток подхода с кэшем словарей в целом.
У нас запись в кэш происходит только после успешного завершения транзакции. Это решает проблему с незавершёнными транзакциями, но не решает проблему того, что порядок выполнения транзакций и порядок записи в кэш могут различаться.
На текущий момент для нас это проблемой не является — то, что кэшируется, редактируется довольно редко. Пока что можем позволить себе такую волность — релиз ещё не выпускали (делаем новую версию продукта). Но что-то делать с этим будем обязательно. Как вариант могу предложить решение с синхронизацией записи в кэш в соответствии с временем завершения транзакции.
У нас запись в кэш происходит только после успешного завершения транзакции. Это решает проблему с незавершёнными транзакциями, но не решает проблему того, что порядок выполнения транзакций и порядок записи в кэш могут различаться.
На текущий момент для нас это проблемой не является — то, что кэшируется, редактируется довольно редко. Пока что можем позволить себе такую волность — релиз ещё не выпускали (делаем новую версию продукта). Но что-то делать с этим будем обязательно. Как вариант могу предложить решение с синхронизацией записи в кэш в соответствии с временем завершения транзакции.
Я потому и написал, что вобщем-то это общая проблема кэша такого рода. Другой вариант решения — на момент начала транзакции каждому клиенту «выделять» каким-то образом собственную копию кэша (в момент выделения копии, естественно, кэш должен быть защищен от внесения в него изменений хотя бы критической секцией). Выделение копии кэша не обязательно должно быть физическим копирование всего кэша в памяти, это может быть что-то типа copy-on-write для всего кэша или для отдельных записей (этакий самописный row versioning). При этом если внутри своей транзакции клиент работает со справочником (вносит в него изменения), он применяет эти изменения к базе и к своей локальной копии кэша (не трогая глобальную копию кэша, т.к. мы следуем идее READ COMMITTED). В момент коммита транзакции (коммита самого верхнего уровня, если у вас допускаются вложенные транзакции) клиент уведомляет глобальную копию кэша, что ей нужно обновиться. Проще и надежнее, если при этом глобальная копия кэша будет перечитана из БД (если это не совсем медленно), но можно обновить ее и на основе сравнения с локальной копией клиента, не дергая БД. Такой вариант, во-первых, не позволяет остальным клиентам читать из глобального кэша незакоммиченные данные текущего клиента, во-вторых (что удобно) позволяет читать текущему клиенту из своего локального кэша свои незакоммиченные данные (как делается и в SQL).
Кстати, забыл спросить, а почему не попробовали SyncGate из PowerThreading?
Как-то даже в голову не приходило. Попробовал сейчас прикрутить — как-то не ложиться совсем AsyncEnumerator на задачу. А в целом, хоть и не знаком с SyncGate, думаю, что один локер чтения/записи Рихтера вряд ли окажется сильно лучше другого похожего локера Рихтера. Но интереса ради всё равно попробую.
Sign up to leave a comment.
ConcurrentDictionary в роли кэша