Cherly — кэш для двоичных данных
Cherly (произносится «шерли») — это бибkиотека для кэширования двоичных данных. Библиотека реализована в виде linked-in драйвера на основе массивов Judy. Двоичные данные практически не копируются и не перемещаются, так что библиотека (во всяком случае, в теории) должна быть очень быстрой.
Cherly была разработана для Dynomite, но может быть использована и в качестве самостоятельной библиотеки.
Почему не ETS?
ETS неплохая хэш-таблица, и достаточно быстрая, но оказалось, что поверх нее сложно реализовать алгоритм LRU
Как работает LRU?
На данный момент алгоритм реализован при помощи двусвязных списков. Поиск элемента перемещают найденный узел в начало списка. Удаление элементов с конца списка происходит при добавлении новых элементов, когда кэш переполняется. Все эти операции обладают сложностью O(1).
Почему двоичные данные?
Cherly была разработана для специфической задачи: хранения потенциально больших двоичных значений в памяти с минимальным оверхедом. Так как ожидалось, что такие значения будут достигать 1MB и более, подход ETS с копированием данных в драйвер и обратно было неподходящим. Cherly использует вызовы outputv и driver_outputv, чтобы передавать двоичные данные не по значению, а по ссылке. Это значит, что не надо выделять дополнительную память, которая уже выделена. Достаточно обновить счетчик ссылок и придерживаться его
- Cherly на GitHub'е
- Judy arrays на Sourceforge (необходимы для работы)
- Check на Sourceforge (необходим для тестирования во время сборки)