OberonCore

Библиотека  Wiki  Форум  BlackBox  Компоненты  Проекты
Текущее время: Вторник, 20 Август, 2019 01:28

Часовой пояс: UTC + 3 часа




Начать новую тему Ответить на тему  [ Сообщений: 3 ] 
Автор Сообщение
СообщениеДобавлено: Понедельник, 24 Октябрь, 2011 15:23 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 18:55
Сообщения: 2272
Откуда: Россия, Нижний Новгород
На работе в программе часто создаются строки. При большой нагрузке - сотни тысяч в секунду. Основной источник - десериализация входящих сообщений. Несколько программ обмениваются сообщениями, в сообщениях есть текстовые идентификаторы. С одними и теми же идентификаторами бегают до нескольких десятков сообщений. Короче, не все создаваемые строки уникальны, много раз содаётся строка с одним и тем же содержимым. Возникает желание кэшировать строки для повторного использования. Перед созданием новой строки сначала поискать аналогичную в кэше и, если она там есть, вернуть указатель на неё.

Возникает проблема какой размер выбрать для кэша и как его чистить.

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

Преимущества:
1) Часто используемые строки останутся в таком кэше практически навсегда, а редкоиспользуемые будут удаляться при достижении фиксированного размера.

Недостатки:
1) При больших нагрузках какой бы разумный предел на размер кэша я ни ставил его всё равно оказывалось мало. Но когда размер кэша мал, то смысла в нём почти нет, зато есть вред (тратить время на поиск, тратить память на хранение).

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

В конце концов пришлось признать, что недостатки перевешивают и лучше вообще без кэша чем с таким.

* * *

Тогда я изобрёл другой строковый кэш.

Я использовал "одноячеистую" хештаблицу. То есть взял большой массив указателей на строки. Когда нужно создать из массива байтов строчку, я просто вычисляю её хэшкод и по нему индексируюсь в этом массиве. Если в нём по этому индексу уже есть указатель на строку с тем же самым содержимым, то возвращаю этот указатель. Если там нуль или же указатель на другую строку, то создаю новую строчку с нужным содержимым и помещаю указатель на неё в эту ячейку массива затирая предыдущий указатель. Обратите внимание, что это можно делать из нескольких потоков одновременно, то есть никаких блокировок делать не нужно (для операций с приоритетным списком блокировка была необходима).

Если такой кэш никогда не чистить, то он растёт (в байтах занимаемой памяти) асимптотически до некоторого максимума, затем рост останавливается (новые строки замещают старые, старые удаляются сборщиком мусора).

Чтобы одноячеистый кэш был эффективен размер массива надо брать как можно больше. Фактически у меня он равен примерно десяти миллионам (точнее NextPrime[10*1024*1024] = 10485767 штук). При среднем размере строки в 100 байт при полном заполнении будет израсходовано примерно один гигабайт памяти. Гигабайт памяти на кэширование текста жалко. Поэтому чистить надо. Кроме того, хочется, чтобы при уменьшении нагрузки программа уменьшала и расход памяти, а при полном отсутствии нагрузки, чтобы опустошала кэш полностью.

Возникает противоречие. С одной стороны кэш чистить нельзя, а то будет медленно работать и смысла в нём не будет. И кэш чистить нужно, а то он много памяти израсходует.

Решение есть. Просто один раз в минуту я обнуляю десять процентов ячеек. Для этого последовательно по кругу ездит обнуляющий "каток". Один раз в минуту он прокатывается вперёд на 10% от размера массива. Указатели на строки в ячейках лежат случано (хэш всё таки), так что удаляются случайные строки.

Выгоды:
1) Работает "со скоростью света" да ещё и без блокировок (многопоточность).
2) При кратковременных высоких нагрузках размер кэша может (и должен) быть очень большой (у меня до гигабайта).
3) При уменьшении нагрузки кэш уменьшается. При полном отсутствии нагрузки кэш полностью обнуляется через десять минут.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Понедельник, 24 Октябрь, 2011 16:38 

Зарегистрирован: Пятница, 24 Апрель, 2009 16:28
Сообщения: 530
Откуда: Москва
Сергей Губанов писал(а):
3) При уменьшении нагрузки кэш уменьшается. При полном отсутствии нагрузки кэш полностью обнуляется через десять минут.
Так массив размером десять миллионов элементов все равно остается?


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Понедельник, 24 Октябрь, 2011 17:20 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 18:55
Сообщения: 2272
Откуда: Россия, Нижний Новгород
Peter Almazov писал(а):
Сергей Губанов писал(а):
3) При уменьшении нагрузки кэш уменьшается. При полном отсутствии нагрузки кэш полностью обнуляется через десять минут.
Так массив размером десять миллионов элементов все равно остается?
Да, это печально, но у нас программы большие (съедают по 2-3 гигабайта под нагрузкой), так что если один модуль в простое будет съедать 200-300 Мб, то это уже хорошо. На этом фоне лишние 40 Мб для массива на 10М строк не так сильно огорчительны. Это я про модули написанные на C# говорил. А вот наши модули написанные на плюсах память назад в систему вообще никогда не возвращают ибо в них используется особый рукописно ускоренный менеджер памяти, но это уже отдельная история.


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 3 ] 

Часовой пояс: UTC + 3 часа


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 1


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Вся информация, размещаемая участниками на конференции (тексты сообщений, вложения и пр.) © 2005-2019, участники конференции «OberonCore», если специально не оговорено иное.
Администрация не несет ответственности за мнения, стиль и достоверность высказываний участников, равно как и за безопасность материалов, предоставляемых участниками во вложениях.
Без разрешения участников и ссылки на конференцию «OberonCore» любое воспроизведение и/или копирование высказываний полностью и/или по частям запрещено.
Powered by phpBB® Forum Software © phpBB Group
Русская поддержка phpBB