Хабрахабр

Триллион маленьких шинглов

Источник изображения:www.nikonsmallworld.com

А любому поисковику, как ни крути, чтобы работать быстро, нужен свой индекс, который учитывает все особенности области поиска. Антиплагиат – это специализированный поисковик, о чем уже писали ранее. Эффективные алгоритмы на . В своей первой статье на Хабре я расскажу о текущей реализации нашего поискового индекса, истории его развития и причинах выбора того или иного решения. Мы погрузимся в мир хеширования, побитового сжатия и многоуровневых кешей с приоритетами. NET — это не миф, а жесткая и продуктивная реальность. Что делать, если нужен поиск быстрее, чем за O(1)?

Если кто-то еще не знает, где на этой картинке шинглы, добро пожаловать…

Шинглы идут внахлёст друг за другом, отсюда и название (англ., shingles — чешуйки, черепички). Шингл — это кусочек текста, размером в несколько слов. Или 5? Конкретный их размер — секрет Полишинеля — 4 слова. Впрочем, даже эта величина мало что даёт и зависит от состава стоп-слов, алгоритма нормализации слов и прочих подробностей, которые в рамках настоящей статьи не существенны. Well, it depends. В конце концов, мы вычисляем на основании этого шингла 64-битный хэш, который в дальнейшем и будем называть шинглом.

По тексту документа можно сформировать множество шинглов, число которых сопоставимо с числом слов в документе:

text:string → shingles:uint64[]

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

Источник изображения:Википедия

Индекс шинглов позволяет выполнять две основные операции:

  1. Индексировать в себе шинглы документов с их идентификаторами:

    Add(docId, shingles) index.

  2. Искать в себе и выдавать ранжированный список идентификаторов пересекающихся документов:

    Search(shingles) → (docId, score)[] index.

Алгоритм ранжирования, я считаю, достоин вообще отдельной статьи, поэтому мы о нем здесь писать не будем.

Вся текстовая обработка вынесена наружу и не влияет на процесс, как и порядок следования шинглов в тексте. Индекс шинглов сильно отличается от известных полнотекстовых собратьев, таких как Sphinx, Elastic или более крупных: Google, Yandex и т.д… С одной стороны, он не требует никакого NLP и прочих радостей жизни. С другой — поисковым запросом является не слово или фраза из нескольких слов, а до нескольких сотен тысяч хэшей, которые имеют значение все в совокупности, а не по отдельности.

Проще всего задействовать какое-нибудь известное key-value-хранилище, об этом будет упоминание ниже. Гипотетически можно использовать полнотекстовый индекс как замену индексу шинглов, но различия слишком велики. Мы же пилим свою велосипед реализацию, которая так и называется — ShingleIndex.

А вот зачем. Для чего нам так заморачиваться?

  • Объёмы:
    1. Документов много. Сейчас их у нас порядка 650 млн., и в этом году их явно будет больше;
    2. Число уникальных шинглов растет как на дрожжах и уже достигает сотен миллиардов. Ждём триллиона.
  • Скорость:
    1. За сутки, во время летней сессии, по системе «Антиплагиат» проверяют более 300 тыс. документов. Это немного по меркам популярных поисковиков, но держит в тонусе;
    2. Для успешной проверки документов на уникальность число проиндексированных документов должно быть на порядки больше проверяемых. Текущая версия нашего индекса в среднем может наполняться на скорости более чем 4000 средних документов в секунду.

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

Как ни крути, но мы тоже взрослели и по ходу роста пробовали разные штуки, о которых сейчас забавно вспоминать. Однако это сейчас мы такие опытные.

Источник изображения:Википедия

Не вы одни так думаете, SQL-реализация исправно служила нам несколько лет для реализации очень маленьких коллекций. Первым делом неискушённый читатель захотел бы задействовать SQL-базу данных. Тем не менее нацеленность была сразу на миллионы документов, так что пришлось идти дальше.

Все круто — персистентная встраиваемая key-value-база с подходящими методами доступа btree и hash и многолетней историей. Велосипеды, как известно, никто не любит, а LevelDB ещё не была достоянием общественности, так что в 2010 году взор наш пал на BerkeleyDB. Всё с ней было замечательно, но:

  • В случае hash-реализации при достижении объёма в 2ГБ она просто падала. Да, мы тогда ещё работали в 32-битном режиме;
  • B+tree-реализация работала стабильно, но при объёмах более нескольких гигабайт скорость поиска начинала значительно падать.

Может быть, проблема в .net-биндингах, которые ещё приходилось допиливать. Придется признать, что мы так и не нашли способа подстроить её под нашу задачу. BDB реализация в итоге использовалась как замена SQL в качестве промежуточного индекса перед заливкой в основной.

В 2014 году пробовали LMDB и LevelDB, но не внедряли. Время шло. На первый взгляд, это была находка. Ребята из нашего Отдела исследований в Антиплагиате в качестве индекса задействовали для своих нужд RocksDB. Но медленное пополнение и посредственная скорость поиска даже на небольших объёмах свела всё на нет.

В итоге он стал настолько хорош в решении наши задач, что мы отказались от предыдущих «затычек» и сосредоточились на его совершенствовании, который сейчас у нас и используется в продакшене повсеместно. Все вышеперечисленное мы делали, параллельно развивая свой собственный кастомный индекс.

Фактически, индекс шинглов представляет собой несколько слоёв (массивов) с элементами постоянной длины — от 0 до 128 бит, — которая зависит не только от слоя и не обязательно кратна восьми. В итоге что мы сейчас имеем?

Какой-то делает поиск быстрее, какой-то экономит место, а какой-то никогда не используется, но очень нужен. Каждый из слоёв играет определённую роль. Мы попробуем их описать в порядке увеличения их суммарной эффективности при поиске.

Источник изображения:Википедия

1. Массив индекса

Без потери общности будем сейчас считать, что документу ставится в соответствие единственный шингл,

(docId → shingle)

Поменяем элементы пары местами (инвертируем, ведь индекс-то на самом деле «инвертированный»!),

(shingle → docId)

Т.к. Отсортируем по значениям шинглов и сформируем слой. Что много, чертовски много. размеры шингла и идентификатора документа постоянны, то теперь любой, кто понимает бинарный поиск, сможет найти пару за O(logn) чтений файла. Но это лучше, чем просто O(n).

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

2. Массив групп

Например, чтобы они влезали в сектор кластер блок allocation unit (читай, 4096 байт) с учётом числа бит и прочих хитростей и сформируем эффективный словарь. Аккуратно разобьём элементы индекса из предыдущего шага на группы любым удобным образом. У нас получится простой массив позиций таких групп:

group_map(hash(shingle)) → group_position.

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

Тем самым чтений будет не два, а одно. Словарь позиций групп занимает на несколько порядков меньше места, чем сам индекс, его часто можно просто выгрузить в память. Итого, O(1).

3. Фильтр Блума

Но мы глупостями не занимаемся. На собеседованиях кандидаты часто решают задачки, выдавая уникальные решения с O(n^2) или даже O(2^n). Давайте попробуем без особой надежды на результат... Есть ли O(0) на свете, вот в чём вопрос?

Если студент молодец и написал работу сам, либо просто там не текст, а белиберда, то значительная часть его шинглов будет уникальна и в индексе встречаться не будет. Обратимся к предметной области. Перед поиском проверим шингл по нему. В мире отлично известна такая структура данных как фильтр Блума. Если шингла в индексе нет, дальше можно не искать, в ином случае идём дальше.

Достаточно использовать одну: +1 чтение из фильтра Блума. Сам по себе фильтр Блума достаточно прост, но задействовать вектор хэш-функций при наших объёмах бессмысленно. Следите за руками! Это даёт -1 или -2 чтений из последующих стадий, в случае если шингл уникальный, и в фильтре не было ложноположительного срабатывания.

Несложными расчётами можно прийти к следующей зависимости: Вероятность ошибки фильтра Блума задаётся при построении, вероятность неизвестного шингла определяется честностью студента.

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

С доверием к студентам у нас действует принцип «доверяй, но проверяй», и практика показывает, что профит от фильтра Блума всё-таки есть.

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

4. Тяжёлые хвосты

Доля их от общего числа мизерная, но, при построении индекса на первом шаге, на втором могут получиться группы размером в десятки и сотни МБ. Есть шинглы, которые встречаются почти везде. Запомним их отдельно и будем сразу выбрасывать из поискового запроса.

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

5. Прочие хвосты

И это нормально. Даже несмотря на это, на шингл может приходится много документов. Вынесем их в отдельную последовательность с более эффективным хранением. Десятки, сотни, тысячи… Хранить их внутри основного индекса становится накладно, в группу они тоже могут не влезть, от этого объём словаря позиций групп раздувается. Тем более что различные побитовые упаковки позволяют и количество обращений к диску снизить, и объём индекса уменьшить. Как показывает статистика, такое решение более чем оправдано.

Всего слоёв в нём таких десять. В итоге для удобства обслуживания запечатаем все эти слои в один большой файл — chunk. Но часть не используется при поиске, часть совсем небольшие и всегда хранятся в памяти, часть активно кэшируются по мере необходимости/возможности.

В худшем случае приходится делать три. В бою чаще всего поиск шингла сводится к одному-двум случайным чтений с файла. Такая вот нормализация. Все слои — суть эффективно (иногда побитово-) упакованные массивы элементов постоянной длины. Время на распаковку незначительно в сравнении с ценой итогового объёма при хранении и возможностью получше прокэшировать.

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

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

Источник изображения:Википедия

Эпизодически, например, раз в месяц (а иногда и год), временный сортировался, фильтровался и сливался с основным. Изначально индекс у нас состоял из двух частей — постоянной, описанной выше, и временной, в роли которой выступал либо SQL, либо BDB, либо свой журнал обновлений. Если временный не мог влезть в оперативную память, то процедура шла через внешнюю сортировку. В результате получался объединённый, а два старых удалялись.

Перезапись сотни гигабайт ради пары миллионов документов – ну так себе удовольствие, скажу я вам… Процедура эта была довольно хлопотная, запускалась в полу-ручном режиме и требовала фактического переписывания всего файла индекса с нуля.

Воспоминания из прошлого...

До сих пор в дрожь берёт от воспоминаний, как 31 декабря отвалился единственный SSD на продакшене и судорожно пришлось в новогоднюю ночь писать wcf-балансировщик и распределять нагрузку на наши девелоперские машины. Это были времена первых и довольно дорогих SSD. Впрочем, мы отвлеклись. Пот схлынул, но балансировщик тот до сих пор жив и отлично работает.

Чтобы и SSD не особо напрягался, и индекс актуализировался почаще, в 2012 году задействовали цепочку из нескольких кусков, chunk'ов по следующей схеме:

Первый, addon, представлял из себя append-only-журнал с индексом в оперативной памяти. Здесь индекс состоит из цепочки однотипных чанков, кроме самого первого. Последующие chunk'и увеличивались в размере (и в возрасте) вплоть до самого последнего (нулевого, основного, корневого, ...).

На заметку велосипедостроителям...

Иногда следует не хвататься писать код и даже не думать, а просто тщательнее гуглить. С точностью до обозначений диаграмма похожа на пример эту из статьи 1996 года «The log-structured merge-tree»:

При его переполнении либо по иным критериям по нему строился постоянный чанк. При добавлении документ сначала складывался в аддон. Обновление документа или его удаление отрабатывались аналогично. Соседние несколько чанков при необходимости сливались в новый, а исходные удалялись.

Сам подход был задействован ещё в нескольких схожих задачах и оформился в виде отдельного внутреннего LSM-фреймворка на чистом .net'е. Критерии слияния, длина цепочки, алгоритм обхода, учёт удаленных элементов и обновлений, прочие параметры тюнились. Примерно в то же время вышел в свет и стал популярным LevelDB.

Маленькая ремарка про LSM-tree

LSM-Tree довольно интересный алгоритм, с хорошим обоснованием. Но, имхо, произошло некоторое размытие смысла термина Tree. В оригинальной статье речь шла именно о цепочке деревьев с возможностью переноса веток. В современных реализациях это не не всегда так. Вот и наш фреймворк в итоге был назван как LsmChain, то есть lsm-цепочка чанков.

У алгоритма LSM в нашем случае есть очень подходящие черты:

  1. мгновенная вставка/удаление/обновление,
  2. сниженная нагрузка на SSD при актуализации,
  3. упрощенный формат чанков,
  4. выборочный поиск только по старым/новым чанкам,
  5. тривиальный бэкап,
  6. чего еще душе угодно.
  7. ...

Вообще, велосипеды иногда и для саморазвития изобретать полезно.

Net'е (и не только на нём). Ну и напоследок поделимся техническими советами, как мы в Антиплагиате делаем такие штуки на .

Подкрутив в одном месте, мы вылетаем из кэша CPU, в другом — упрёмся в пропускную способность SATA-интерфейса, в третьем — начнём зависать в GC. Заметим заранее, что часто всё очень сильно зависит от вашего конкретного железа, данных или режима использования. А где-то и вовсе в неэффективность реализации конкретного системного вызова.

Источник изображения:Википедия

Есть терабайтный экзабайтный большой файл, объём которого во много раз превышает объём оперативной памяти. Проблема с доступом к файлу у нас не уникальна. Причём делать это быстро, качественно и недорого. Задача — прочесть разбросанный по нему миллион каких-то небольших случайных значений. Приходится ужиматься, бенчмаркать и много думать.

Чтобы прочитать заветный, байт нужно: Начнём с простого.

  1. Открыть файл (new FileStream);
  2. Переместиться на нужную позицию (Position или Seek, без разницы);
  3. Прочитать нужный массив байт (Read);
  4. Закрыть файл (Dispose).

Путем проб, ошибок и многократного наступания на грабли мы выявили следующий алгоритм действий: И это плохо, потому что долго и муторно.

  • Single open, multiple read

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

    Очевидно, следует один раз открыть файл и последовательно вычитывать с него все миллионы наших значений, что мы и делаем

  • Nothing Extra

    Даже если файл не менялся. Получение размера файла, текущей позиции в нём — также достаточно тяжёлые операции.

    Следует избегать любых запросов типа получения размера файла или текущей позиции в нём.

  • FileStreamPool

    Увы, FileStream по сути однопоточен. Далее. Если вы хотите читать файл параллельно, придётся создавать/закрывать новые файловые потоки.

    Пока не создадут что-то типа aiosync, придётся изобретать собственные велосипеды.

    Это позволит избежать траты времени на открытие/закрытие файла. Мой совет – создайте пул файловых потоков на файл. А если его объединить с ThreadPool и учесть, что SSD выдаёт свои мегаIOPS'ы при сильной многопоточности… Ну вы меня поняли.

  • Allocation unit

    Устройства хранения данных (HDD, SSD, Optane) и файловая система оперируют файлами на уровне блоков (cluster, sector, allocation unit). Далее. Чтение одного-двух байтов на границе двух таких блоков в SSD происходит примерно в полтора раза медленнее, чем внутри самого блока. Они могут не совпадать, но сейчас это почти всегда 4096 байт.

    Следует организовывать свои данные так, чтобы вычитываемые элементы были в рамках границ кластера сектора блока.

  • No buffer.

    FileStream по умолчанию использует буфер размером в 4096 байт. Далее. Тем не менее, если вы читаете данных больше, чем размер буфера, то последний будет в игноре. И есть плохая новость — его нельзя выключить.

    При случайном чтении следует выставить буфер в 1 байт (меньше не получится) и далее считать, что тот не используется.

  • Use buffer.

    Здесь буфер уже может стать полезным, если вы не хотите вычитывать всё разом. Кроме случайных чтений, есть ещё и последовательные. Какой размер буфера выставить, зависит от того, находится ли файл на HDD или на SSD. Советую для начала обратиться к этой статье. Если размер вычитываемой области данных сравним с этими значениями, то лучше её вычитать разом, пропустив буфер, как и в случае случайного чтения. В первом случае оптимальным будет 1MB, во втором будет достаточно стандартных 4kB. Буферы больших размеров не будут приносить профита по скорости, но начнут бить по GC.

    Well, it depends. При последовательном чтении больших кусков файла следует выставить буфер в 1MB для HDD и 4kB для SSD.

Net Framework v4. В 2011 году пришла наводка на MemoryMappedFile, благо этот механизм был реализован начиная с . Сначала задействовали его при кэшировании фильтра Блума, что уже доставляло неудобств в 32-битном режиме из-за ограничения в 4ГБ. 0. Первые тесты впечатляли. Но при переходе в мир 64-х бит захотелось ещё. Но были и проблемы: Бесплатное кэширование, чумовая скорость, удобный интерфейс чтения структур.

  • Во-первых, как ни странно, скорость. Если данные уже прокэшированы, то всё ок. Но если нет — чтение одного байта из файла сопровождалось «поднятием наверх» намного большего количества данных, чем это было бы при обычном чтении.
  • Во-вторых, как ни странно, память. При разогреве shared-память растёт, workingset — нет, что логично. Но далее соседние процессы начинают вести себя не очень хорошо. Могут уйти в своп, либо непроизвольно упасть от OoM. Объём, занимаемый MMF в оперативной памяти, увы, контролировать невозможно. А профит от кэша в случае, когда сам читаемый файл на пару порядков больше памяти, становится бессмысленным.

Она исчезает, если индекс работает в докере либо на выделенной виртуалке. Со второй проблемой ещё можно было бы бороться. Но вот проблема скорости была фатальной.

Кэширование в Антиплагиате стали делать в явном виде, по возможности удерживая в памяти наиболее часто используемые слои при заданных приоритетах и лимитах. В итоге от MMF отказались чуть более, чем полностью.

Источник изображения:Википедия

Иногда нужно снизойти до уровня бита. Не байтами мир един.

Как со всем этим работать? Для примера: представим, что у вас триллион частично упорядоченных чисел, жаждущих сохранения и частого чтения.

  • Простой BinaryWriter.Write? — быстро, но медленно. Размер все-таки имеет значение. Холодное чтение в первую очередь зависит от размера файла.
  • Очередная вариация VarInt? — быстро, но медленно. Постоянство имеет значение. Объём начинает зависеть от данных, что требует дополнительной памяти для позиционирования.
  • Побитовая упаковка? — быстро, но медленно. Приходится ещё тщательнее контролировать свои руки.

Идеального решения нет, но в конкретном случае простое сжатие диапазона с 32-х бит до необходимого хранить хвосты сэкономило на 12% больше (десятки ГБ!), чем VarInt (с сохранением только разницы соседних, само собой), а тот — в разы от базового варианта.

У вас в файле есть ссылка на некоторый массив чисел. Другой пример. Всё вроде ок. Ссылка 64-битная, файл на терабайт. Часто мало. Иногда чисел в массиве много, иногда мало. Тогда просто берём и храним весь массив в самой ссылке. Очень часто. Упаковать аккуратно только не забудьте. Profit.

Я здесь не буду писать про банальные «стоит ли сохранять Length массива в цикле» или «что быстрее, for или foreach». Ну и прочие микрооптимизации.

«бенчмаркай всё», 2. Есть два простых правила, и мы им будем придерживаться: 1. «больше бенчмаркай».

  • Используются повсеместно. Struct. И, как это модно нынче бывает, у нас тоже есть свой мегабыстрый ValueList. Не грузят GC.

  • Позволяет мапить (и размапить) структуры в массив байт при использовании. Unsafe. Есть, правда, вопросы к пинингу и дефрагментации кучи, но пока не проявлялось. Тем самым нам не нужны отдельные средства сериализации. Well, it depends.

  • Работать с множеством элементов следует через пачки/группы/блоки. Batching. Отдельный вопрос — размер этих пачек. Читать/писать файл, передавать между функциями. Попробуйте прокачать через функцию IEnumerable<byte> или IEnumerable<byte[1024]> и прочувствуйте разницу. Обычно есть оптимум, и его размер часто находится в диапазоне от 1kB до 8MB (размер кэша CPU, размер кластера, размер страницы, размер чего-то ещё).

  • Каждый раз, когда вы пишите «new», где-то умирает котёнок. Pooling. Если нет возможности задействовать stackalloc, то создайте пул каких-либо объектов и переиспользуйте его заново. Разок new byte[85000] — и трактор проехался по тонне гусей.

  • Как созданием двух функций вместо одной можно ускорить всё в десять раз? Inlining. Чем меньше размер тела функции (метода), тем больше шансов, что он будет заинлайнен. Просто. К сожалению, в мире dotnet пока нет возможности делать частичный инлайнинг, так что если у вас есть горячая функция, которая в 99% случаях выходит после обработки первых нескольких строк, а остальная сотня строк идёт на обработку оставшегося 1%, то смело разбивайте её на две (или три), вынося тяжёлый хвост в отдельную функцию.

  • Код будет проще и, может быть, чуть быстрее. Span<T>, Memory<T> — многообещающе. Net Core v3. Ждём релиза . 1, чтобы на них перейти, т.к. 0 и Std v2. Net Std v2. наше ядро на . 0, которое спаны нормально не поддерживает.

  • Простейшие бенчмарки случайного чтения показали, что действительно потребление CPU падает, но вот скорость чтения также снижается. Async/await — пока неоднозначно. Внутри индекса пока не используем. Надо смотреть.

Нам действительно очень нравится наш индекс. Надеюсь, мне удалость доставить вам удовольствие от понимания красоты некоторых решений. Узкоспециализированное решение в ядре системы, критическом месте ее работы лучше, чем общее. Он эффективен, красив кодом, отлично работает. Теперь плюсов четыре — только чистый C#, только . Наша система контроля версий помнит ассемблерные вставки в С++ код. На нем мы пишем даже самые сложные алгоритмы поиска и ничуть не жалеем об этом. Net. Net Core, переход на Docker путь к светлому DevOps-будущему стал проще и яснее. С появлением . Впереди — решение задачи динамической шардизации и репликации без снижения эффективности и красоты решения.

Обо всех очепятках и прочих нестыковках просьба писать комментарии. Спасибо всем, кто дочитал до конца. Буду рад любым обоснованным советам и опровержениям в комментариях.

Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть