Сегодня для кодирования записей (документов, частот, позиций) в индексе Lucene использует переменный формат байтов, где каждое целое число индивидуально кодируется как 1-5 байтов.
Хотя это на удивление просто, требуется оператор if для каждого байта во время декодирования, что очень дорого, поскольку ЦП не может легко
предсказать результат перехода .
Чтобы уменьшить количество ветвей на int-декодирование, вы должны переключиться на декодирование групп целых сразу.
В этой статье описывается несколько таких кодеров (PForDelta, Rice Coding, Simple9, Simple16).
Глава 6 (Сжатие индексов) поиска информации: внедрение и оценка поисковых систем
подробно описывает эти и другие, в том числе
приложения, показывающие результаты для
кодера VarInt группы Google .
Кодек IntBlock разработан, чтобы упростить эксперименты с различными типами кодировщиков int. Он выполняет «трудную часть», позволяя Lucene работать сразу с несколькими целыми числами, что несколько сложно, поскольку точки поиска (в терминах dict и пропускающих списках) теперь должны кодировать указатель файла, с которого начинается блок а также индекс (начиная с int) в блок.
Уже существует низкоуровневая начальная реализация Frame-of-Reference (FOR) и Patched-frame-of-reference (PFOR) для
LUCENE-1410 , а также Simple9 / 16 для
LUCENE-2189 благодаря Полу Эльшоту и Рено Delbru.
FOR — это простая кодировка: она принимает каждый фиксированный блок целых чисел и сохраняет их как упакованные целые, где каждое значение получает N битов, установленных максимальным значением int в блоке. Скажем, наш размер блока равен 8, и у нас есть следующие целые числа:
1 7 3 5 6 2 2 5
нам нужно всего 3 бита на значение. Но у FOR есть явный недостаток: если у вас есть один большой int, смешанный с кучей маленьких, то вы теряете биты. Например, если у нас есть эти целые:
1 7 3 5 293 2 2 5
тогда FOR должен использовать 9 битов для всех значений (из-за 293), несмотря на то, что для других значений требуется только 3 бита каждое. Насколько это больно на практике, еще неизвестно.
PFOR исправляет это, помечая такие большие числа как исключения, которые затем «исправляются» после первоначального декодирования. Таким образом, для приведенного выше примера мы все равно будем использовать 3 бита на значение, но отметим, что значение 293 является «исключением» и будет отдельно кодироваться в конце (с большим количеством битов), а затем «исправляться» обратно во время декодирования.
Вышеуказанная статья имеет детали.
Обратите внимание, что блочные кодеки не всегда подходят друг другу, так как для доступа даже к одному int внутри блока они [обычно] должны декодировать полный блок. Это может быть дорогостоящим, если вам часто нужно декодировать только целое или два, например, с полем первичного ключа.
Импульсный кодек лучше подходит для таких полей.
Во время тестирования я обнаружил несколько глупых проблем с производительностью в кодеке IntBlock, которые я сейчас взломал (я выложу свой патч на
LUCENE-1410); хаки не близки к committable, но работают правильно (идентичные результаты поиска по запросам, которые я тестирую). Я также сделал еще несколько небольших оптимизаций для реализации FOR / PFOR. Я хотел бы довести кодек IntBlock до такой степени, чтобы любой мог легко подключиться к алгоритму кодирования int с фиксированным или переменным размером блока и запустить свои собственные тесты.
Я проиндексировал первые 10 миллионов документов размером в Википедию размером ~ 1 КБ. Результирующие размеры индекса были:
| кодер-декодер | Размер | % Изменить |
| стандарт | 3,50 ГБ | |
| ЗА | 3,96 ГБ | На 13,3% больше |
| р для | 3,87 ГБ | На 11,1% больше |
Увеличение размеров FOR и PFOR довольно низкое. PFOR меньше, чем FOR, как и ожидалось, но удивительно, что он только немного ниже. Тем не менее, это функция того, где вы рисуете линию для случаев исключения, и будет зависеть от корпуса. Тем не менее, я воодушевлен тем, как мало дополнительного места FOR требует по сравнению со стандартным кодеком.
Я выполнил набор запросов и измерил лучшее время (из 40 запусков) для каждого из 4 потоков. Вот результаты для FOR:
| запрос | Стандарт QPS | QPS FOR | % Изменить |
| объединенная ~ 0,6 | 5,59 | 5,08 | -9,0% |
| «Соединенные Штаты» | 11,46 | 11,22 | -2,1% |
| объединенная ~ 0,7 | 18,33 | 19,23 | 4,9% |
| Соединенные Штаты | 15,53 | 18,66 | 20,1% |
| уни * д | 34,25 | 43,37 | 26,6% |
| Ед. изм* | 31,27 | 41,07 | 31,3% |
| состояния | 55,72 | 75,82 | 36,1% |
| + соединенные штаты | 15,17 | 21,43 | 41,2% |
и для PFOR:
| запрос | Стандарт QPS | QPS PFOR | % Изменить |
| объединенная ~ 0,6 | 5,59 | 5,02 | -10,1% |
| «Соединенные Штаты» | 11,46 | 10,88 | -5,1% |
| объединенная ~ 0,7 | 18,33 | 19,00 | 3,7% |
| Соединенные Штаты | 15,53 | 18,11 | 16,6% |
| уни * д | 34,25 | 43,71 | 27,6% |
| состояния | 55,72 | 71,39 | 28,1% |
| Ед. изм* | 31,27 | 41,42 | 32,5% |
| + соединенные штаты | 15,17 | 21,25 | 40,1% |
Они оба показывают хорошие результаты для большинства запросов; У FOR есть небольшое преимущество, поскольку он не должен декодировать исключения. Объединенное значение ~ 0,6 (максимальное расстояние редактирования = 2) медленнее, вероятно, потому, что большое число из 519 термов, которые оно расширяет, чтобы иметь низкую частоту, и, таким образом, издержки полного декодирования блока снижают производительность. PhraseQuery также стал немного медленнее, вероятно, потому что он использует неблокируемый пропуск во время поиска. Любопытно, что запрос AND стал быстрее; Я думаю, что это потому, что я изменил его оценку, чтобы сначала попытаться искать в блоке декодированных целых. Вероятно, гибридный кодек для Lucene, использующий FOR или FFOR для высокочастотных терминов, Standard для средней частоты и Pulsing для очень низкой частоты, будет работать лучше всего.
Я запустил еще один тест, на этот раз используя FOR для MMapDirectory (вместо использованного выше NIOFSDirectory), передавая IntBuffer из отображаемых страниц непосредственно в декодер FOR:
| запрос | Стандарт QPS | QPS FOR | % Изменить |
| объединенная ~ 0,6 | 6,00 | 5,28 | -12,1% |
| объединенная ~ 0,7 | 18,48 | 20,53 | 11,1% |
| «Соединенные Штаты» | 10,47 | 11,70 | 11,8% |
| Соединенные Штаты | 15,21 | 20,25 | 33,2% |
| уни * д | 33,16 | 47,59 | 43,5% |
| Ед. изм* | 29,71 | 45,14 | 51,9% |
| + соединенные штаты | 15,14 | 23,65 | 56,2% |
| состояния | 52,30 | 88,66 | 69,5% |
Результаты, как правило, даже лучше по двум причинам. Во-первых, по какой-то причине стандартный кодек немного тормозит с MMapDirectory. Во-вторых, кодек FOR существенно ускоряется, потому что я могу (хотя и взломан) выполнить декодирование без копирования с MMapDirectory.
Помните, что эти результаты очень предварительные, основанные на патче со многими хакерами, не подлежащими фиксации (например, удаленные документы игнорируются!), Который не проходит все юнит-тесты Lucene и т. Д. Также есть еще дополнительные оптимизации, которые нужно изучить, и много работы остается. Так что не ясно, где будут финальные цифры, но эти первоначальные результаты очень обнадеживают!
Если у вас есть какие-либо другие алгоритмы, которые можно использовать для кодирования целых чисел, прошу прощения! Lucene очень легко сгенерирует несколько миллиардов целых для вас кодирования / декодирования, если вы хотите запускать автономные тесты.