- PVSM.RU - https://www.pvsm.ru -
Источник изображения:www.nikonsmallworld.com [1]
Антиплагиат – это специализированный поисковик, о чем уже писали ранее [2]. А любому поисковику, как ни крути, чтобы работать быстро, нужен свой индекс, который учитывает все особенности области поиска. В своей первой статье на Хабре [3] я расскажу о текущей реализации нашего поискового индекса, истории его развития и причинах выбора того или иного решения. Эффективные алгоритмы на .NET — это не миф, а жесткая и продуктивная реальность. Мы погрузимся в мир хеширования, побитового сжатия и многоуровневых кешей с приоритетами. Что делать, если нужен поиск быстрее, чем за O(1)?
Если кто-то еще не знает, где на этой картинке шинглы, добро пожаловать…
Шингл — это кусочек текста, размером в несколько слов. Шинглы идут внахлёст друг за другом, отсюда и название (англ., shingles — чешуйки, черепички). Конкретный их размер — секрет Полишинеля — 4 слова. Или 5? Well, it depends. Впрочем, даже эта величина мало что даёт и зависит от состава стоп-слов, алгоритма нормализации слов и прочих подробностей, которые в рамках настоящей статьи не существенны. В конце концов, мы вычисляем на основании этого шингла 64-битный хэш, который в дальнейшем и будем называть шинглом.
По тексту документа можно сформировать множество шинглов, число которых сопоставимо с числом слов в документе:
text:string → shingles:uint64[]
При совпадении нескольких шинглов у двух документов будем считать, что документы пересекаются. Чем больше шинглов совпадает, тем больше одинакового текста в этой паре документов. Индекс занимается поиском документов, обладающих наибольшим количеством пересечений с проверяемым документом.
Источник изображения:Википедия [4]
Индекс шинглов позволяет выполнять две основные операции:
Индексировать в себе шинглы документов с их идентификаторами:
index.Add(docId, shingles)
Искать в себе и выдавать ранжированный список идентификаторов пересекающихся документов:
index.Search(shingles) → (docId, score)[]
Алгоритм ранжирования, я считаю, достоин вообще отдельной статьи, поэтому мы о нем здесь писать не будем.
Индекс шинглов сильно отличается от известных полнотекстовых собратьев, таких как Sphinx, Elastic или более крупных: Google, Yandex и т.д… С одной стороны, он не требует никакого NLP и прочих радостей жизни. Вся текстовая обработка вынесена наружу и не влияет на процесс, как и порядок следования шинглов в тексте. С другой — поисковым запросом является не слово или фраза из нескольких слов, а до нескольких сотен тысяч хэшей [5], которые имеют значение все в совокупности, а не по отдельности.
Гипотетически можно использовать полнотекстовый индекс как замену индексу шинглов, но различия слишком велики. Проще всего задействовать какое-нибудь известное key-value-хранилище, об этом будет упоминание ниже. Мы же пилим свою велосипед реализацию, которая так и называется — ShingleIndex.
Для чего нам так заморачиваться? А вот зачем.
И это всё на одной машине! Да, мы умеем реплицировать [7], постепенно подходим к динамическому шардингу [8] на кластер, но с 2005 года и по сей день индекс на одной машине при бережном уходе способен справляться со всеми вышеперечисленными трудностями.
Однако это сейчас мы такие опытные. Как ни крути, но мы тоже взрослели и по ходу роста пробовали разные штуки, о которых сейчас забавно вспоминать.
Источник изображения:Википедия [9]
Первым делом неискушённый читатель захотел бы задействовать SQL-базу данных. Не вы одни так думаете, SQL-реализация исправно служила нам несколько лет для реализации очень маленьких коллекций. Тем не менее нацеленность была сразу на миллионы документов, так что пришлось идти дальше.
Велосипеды, как известно, никто не любит, а LevelDB ещё не была достоянием общественности, так что в 2010 году взор наш пал на BerkeleyDB. Все круто — персистентная встраиваемая key-value-база с подходящими методами доступа btree и hash и многолетней историей. Всё с ней было замечательно, но:
Придется признать, что мы так и не нашли способа подстроить её под нашу задачу. Может быть, проблема в .net-биндингах, которые ещё приходилось допиливать. BDB реализация в итоге использовалась как замена SQL в качестве промежуточного индекса перед заливкой в основной.
Время шло. В 2014 году пробовали LMDB и LevelDB, но не внедряли. Ребята из нашего Отдела исследований в Антиплагиате [6] в качестве индекса задействовали для своих нужд RocksDB. На первый взгляд, это была находка. Но медленное пополнение и посредственная скорость поиска даже на небольших объёмах свела всё на нет.
Все вышеперечисленное мы делали, параллельно развивая свой собственный кастомный индекс. В итоге он стал настолько хорош в решении наши задач, что мы отказались от предыдущих «затычек» и сосредоточились на его совершенствовании, который сейчас у нас и используется в продакшене повсеместно.
В итоге что мы сейчас имеем? Фактически, индекс шинглов представляет собой несколько слоёв (массивов) с элементами постоянной длины — от 0 до 128 бит, — которая зависит не только от слоя и не обязательно кратна восьми.
Каждый из слоёв играет определённую роль. Какой-то делает поиск быстрее, какой-то экономит место, а какой-то никогда не используется, но очень нужен. Мы попробуем их описать в порядке увеличения их суммарной эффективности при поиске.
Источник изображения:Википедия [10]
Без потери общности будем сейчас считать, что документу ставится в соответствие единственный шингл,
(docId → shingle)
Поменяем элементы пары местами (инвертируем, ведь индекс-то на самом деле «инвертированный»!),
(shingle → docId)
Отсортируем по значениям шинглов и сформируем слой. Т.к. размеры шингла и идентификатора документа постоянны, то теперь любой, кто понимает бинарный поиск [11], сможет найти пару за O(logn) чтений файла. Что много, чертовски много. Но это лучше, чем просто O(n).
Если шинглов у документа несколько, то таких пар от документа тоже будет несколько. Если существует несколько документов с одинаковыми шинглами, то это тоже мало чего изменит — будет несколько идущих подряд пар с одинаковым шинглом. В этих обоих случаях поиск будет идти за сопоставимое время.
Аккуратно разобьём элементы индекса из предыдущего шага на группы любым удобным образом. Например, чтобы они влезали в сектор кластер блок allocation unit (читай, 4096 байт) с учётом числа бит и прочих хитростей и сформируем эффективный словарь. У нас получится простой массив позиций таких групп:
group_map(hash(shingle)) → group_position.
При поиске шингла будем теперь сначала искать позицию группы по этому словарю, а затем выгружать группу и искать прямо в памяти. Вся операция требует два чтения.
Словарь позиций групп занимает на несколько порядков меньше места, чем сам индекс, его часто можно просто выгрузить в память. Тем самым чтений будет не два, а одно. Итого, O(1).
На собеседованиях кандидаты часто решают задачки, выдавая уникальные решения с O(n^2) или даже O(2^n). Но мы глупостями не занимаемся. Есть ли O(0) на свете, вот в чём вопрос? Давайте попробуем без особой надежды на результат...
Обратимся к предметной области. Если студент молодец и написал работу сам, либо просто там не текст, а белиберда, то значительная часть его шинглов будет уникальна и в индексе встречаться не будет. В мире отлично известна такая структура данных как фильтр Блума [12]. Перед поиском проверим шингл по нему. Если шингла в индексе нет, дальше можно не искать, в ином случае идём дальше.
Сам по себе фильтр Блума достаточно прост, но задействовать вектор хэш-функций при наших объёмах бессмысленно. Достаточно использовать одну: +1 чтение из фильтра Блума. Это даёт -1 или -2 чтений из последующих стадий, в случае если шингл уникальный, и в фильтре не было ложноположительного срабатывания. Следите за руками!
Вероятность ошибки фильтра Блума задаётся при построении, вероятность неизвестного шингла определяется честностью студента. Несложными расчётами можно прийти к следующей зависимости:
С доверием к студентам у нас действует принцип «доверяй, но проверяй», и практика показывает, что профит от фильтра Блума всё-таки есть.
С учётом того, что эта структура данных также меньше самого индекса и может быть закэширована, то в лучшем случае она позволяет отбрасывать шингл вообще без обращений к диску.
Есть шинглы, которые встречаются почти везде. Доля их от общего числа мизерная, но, при построении индекса на первом шаге, на втором могут получиться группы размером в десятки и сотни МБ. Запомним их отдельно и будем сразу выбрасывать из поискового запроса.
Когда впервые в 2011 году задействовали этот тривиальный шаг, размер индекса сократился вдвое, ускорен был и сам поиск.
Даже несмотря на это, на шингл может приходится много документов. И это нормально. Десятки, сотни, тысячи… Хранить их внутри основного индекса становится накладно, в группу они тоже могут не влезть, от этого объём словаря позиций групп раздувается. Вынесем их в отдельную последовательность с более эффективным хранением. Как показывает статистика, такое решение более чем оправдано. Тем более что различные побитовые упаковки позволяют и количество обращений к диску снизить, и объём индекса уменьшить.
В итоге для удобства обслуживания запечатаем все эти слои в один большой файл — chunk. Всего слоёв в нём таких десять. Но часть не используется при поиске, часть совсем небольшие и всегда хранятся в памяти, часть активно кэшируются по мере необходимости/возможности.
В бою чаще всего поиск шингла сводится к одному-двум случайным чтений с файла. В худшем случае приходится делать три. Все слои — суть эффективно (иногда побитово-) упакованные массивы элементов постоянной длины. Такая вот нормализация. Время на распаковку незначительно в сравнении с ценой итогового объёма при хранении и возможностью получше прокэшировать.
При построении размеры слоёв преимущественно вычисляются заранее, пишутся последовательно, так что процедура эта достаточно быстрая.
С двойным угрызением совести в 2010 году почитывал на форуме заявления недовольных студентов о том, что мы слишком часто пополняем индекс и они не могут найти подходящий сайт с левыми рефератами. Суть была в том, что основной индекс полноценно не обновлялся уже как пару лет. К счастью, руки дошли и до этой проблемы.
Источник изображения:Википедия [13]
Изначально индекс у нас состоял из двух частей — постоянной, описанной выше, и временной, в роли которой выступал либо SQL, либо BDB, либо свой журнал обновлений. Эпизодически, например, раз в месяц (а иногда и год), временный сортировался, фильтровался и сливался с основным. В результате получался объединённый, а два старых удалялись. Если временный не мог влезть в оперативную память, то процедура шла через внешнюю сортировку.
Процедура эта была довольно хлопотная, запускалась в полу-ручном режиме и требовала фактического переписывания всего файла индекса с нуля. Перезапись сотни гигабайт ради пары миллионов документов – ну так себе удовольствие, скажу я вам…
Это были времена первых и довольно дорогих SSD. До сих пор в дрожь берёт от воспоминаний, как 31 декабря отвалился единственный SSD на продакшене и судорожно пришлось в новогоднюю ночь писать wcf-балансировщик и распределять нагрузку на наши девелоперские машины. Пот схлынул, но балансировщик тот до сих пор жив и отлично работает. Впрочем, мы отвлеклись.
Чтобы и SSD не особо напрягался, и индекс актуализировался почаще, в 2012 году задействовали цепочку из нескольких кусков, chunk'ов по следующей схеме:
Здесь индекс состоит из цепочки однотипных чанков, кроме самого первого. Первый, addon, представлял из себя append-only-журнал с индексом в оперативной памяти. Последующие chunk'и увеличивались в размере (и в возрасте) вплоть до самого последнего (нулевого, основного, корневого, ...).
При добавлении документ сначала складывался в аддон. При его переполнении либо по иным критериям по нему строился постоянный чанк. Соседние несколько чанков при необходимости сливались в новый, а исходные удалялись. Обновление документа или его удаление отрабатывались аналогично.
Критерии слияния, длина цепочки, алгоритм обхода, учёт удаленных элементов и обновлений, прочие параметры тюнились. Сам подход был задействован ещё в нескольких схожих задачах и оформился в виде отдельного внутреннего LSM [15]-фреймворка на чистом .net'е. Примерно в то же время вышел в свет и стал популярным LevelDB.
У алгоритма LSM [15] в нашем случае есть очень подходящие черты:
Вообще, велосипеды иногда и для саморазвития изобретать полезно.
Ну и напоследок поделимся техническими советами, как мы в Антиплагиате [6] делаем такие штуки на .Net'е (и не только на нём).
Заметим заранее, что часто всё очень сильно зависит от вашего конкретного железа, данных или режима использования. Подкрутив в одном месте, мы вылетаем из кэша CPU, в другом — упрёмся в пропускную способность SATA-интерфейса, в третьем — начнём зависать в GC. А где-то и вовсе в неэффективность реализации конкретного системного вызова.
Источник изображения:Википедия [17]
Проблема с доступом к файлу у нас не уникальна. Есть терабайтный экзабайтный большой файл, объём которого во много раз превышает объём оперативной памяти. Задача — прочесть разбросанный по нему миллион каких-то небольших случайных значений. Причём делать это быстро, качественно и недорого. Приходится ужиматься, бенчмаркать и много думать.
Начнём с простого. Чтобы прочитать заветный, байт нужно:
И это плохо, потому что долго и муторно. Путем проб, ошибок и многократного наступания на грабли мы выявили следующий алгоритм действий:
Single open, multiple read
Если эту последовательность делать в лоб, на каждый запрос к диску, то мы очень быстро загнемся. Каждый из этих пунктов уходит в запрос к ядру OS, что накладно.
Очевидно, следует один раз открыть файл и последовательно вычитывать с него все миллионы наших значений, что мы и делаем
Nothing Extra
Получение размера файла, текущей позиции в нём — также достаточно тяжёлые операции. Даже если файл не менялся.
Следует избегать любых запросов типа получения размера файла или текущей позиции в нём.
FileStreamPool
Далее. Увы, FileStream по сути однопоточен. Если вы хотите читать файл параллельно, придётся создавать/закрывать новые файловые потоки.
Пока не создадут что-то типа aiosync, придётся изобретать собственные велосипеды.
Мой совет – создайте пул файловых потоков на файл. Это позволит избежать траты времени на открытие/закрытие файла. А если его объединить с ThreadPool и учесть, что SSD выдаёт свои мегаIOPS'ы при сильной многопоточности… Ну вы меня поняли.
Allocation unit
Далее. Устройства хранения данных (HDD, SSD, Optane) и файловая система оперируют файлами на уровне блоков (cluster, sector, allocation unit). Они могут не совпадать, но сейчас это почти всегда 4096 байт. Чтение одного-двух байтов на границе двух таких блоков в SSD происходит примерно в полтора раза медленнее, чем внутри самого блока.
Следует организовывать свои данные так, чтобы вычитываемые элементы были в рамках границ кластера сектора блока.
No buffer.
Далее. FileStream по умолчанию использует буфер размером в 4096 байт. И есть плохая новость — его нельзя выключить. Тем не менее, если вы читаете данных больше, чем размер буфера, то последний будет в игноре.
При случайном чтении следует выставить буфер в 1 байт (меньше не получится) и далее считать, что тот не используется.
Use buffer.
Кроме случайных чтений, есть ещё и последовательные. Здесь буфер уже может стать полезным, если вы не хотите вычитывать всё разом. Советую для начала обратиться к этой статье [18]. Какой размер буфера выставить, зависит от того, находится ли файл на HDD или на SSD. В первом случае оптимальным будет 1MB, во втором будет достаточно стандартных 4kB. Если размер вычитываемой области данных сравним с этими значениями, то лучше её вычитать разом, пропустив буфер, как и в случае случайного чтения. Буферы больших размеров не будут приносить профита по скорости, но начнут бить по GC.
При последовательном чтении больших кусков файла следует выставить буфер в 1MB для HDD и 4kB для SSD. Well, it depends.
В 2011 году пришла наводка на MemoryMappedFile, благо этот механизм был реализован начиная с .Net Framework v4.0. Сначала задействовали его при кэшировании фильтра Блума, что уже доставляло неудобств в 32-битном режиме из-за ограничения в 4ГБ. Но при переходе в мир 64-х бит захотелось ещё. Первые тесты впечатляли. Бесплатное кэширование, чумовая скорость, удобный интерфейс чтения структур. Но были и проблемы:
Со второй проблемой ещё можно было бы бороться. Она исчезает, если индекс работает в докере либо на выделенной виртуалке. Но вот проблема скорости была фатальной.
В итоге от MMF отказались чуть более, чем полностью. Кэширование в Антиплагиате стали делать в явном виде, по возможности удерживая в памяти наиболее часто используемые слои при заданных приоритетах и лимитах.
Источник изображения:Википедия [19]
Не байтами мир един. Иногда нужно снизойти до уровня бита.
Для примера: представим, что у вас триллион частично упорядоченных чисел, жаждущих сохранения и частого чтения. Как со всем этим работать?
Идеального решения нет, но в конкретном случае простое сжатие диапазона с 32-х бит до необходимого хранить хвосты сэкономило на 12% больше (десятки ГБ!), чем VarInt (с сохранением только разницы соседних, само собой), а тот — в разы от базового варианта.
Другой пример. У вас в файле есть ссылка на некоторый массив чисел. Ссылка 64-битная, файл на терабайт. Всё вроде ок. Иногда чисел в массиве много, иногда мало. Часто мало. Очень часто. Тогда просто берём и храним весь массив в самой ссылке. Profit. Упаковать аккуратно только не забудьте.
Ну и прочие микрооптимизации. Я здесь не буду писать про банальные «стоит ли сохранять Length массива в цикле» или «что быстрее, for или foreach».
Есть два простых правила, и мы им будем придерживаться: 1. «бенчмаркай всё», 2. «больше бенчмаркай».
Struct. Используются повсеместно. Не грузят GC. И, как это модно нынче бывает, у нас тоже есть свой мегабыстрый ValueList.
Unsafe. Позволяет мапить (и размапить) структуры в массив байт при использовании. Тем самым нам не нужны отдельные средства сериализации. Есть, правда, вопросы к пинингу и дефрагментации кучи, но пока не проявлялось. Well, it depends.
Batching. Работать с множеством элементов следует через пачки/группы/блоки. Читать/писать файл, передавать между функциями. Отдельный вопрос — размер этих пачек. Обычно есть оптимум, и его размер часто находится в диапазоне от 1kB до 8MB (размер кэша CPU, размер кластера, размер страницы, размер чего-то ещё). Попробуйте прокачать через функцию IEnumerable<byte> или IEnumerable<byte[1024]> и прочувствуйте разницу.
Pooling. Каждый раз, когда вы пишите «new», где-то умирает котёнок. Разок new byte[85000 [20]] — и трактор проехался по тонне гусей. Если нет возможности задействовать stackalloc, то создайте пул каких-либо объектов и переиспользуйте его заново.
Inlining. Как созданием двух функций вместо одной можно ускорить всё в десять раз? Просто. Чем меньше размер тела функции (метода), тем больше шансов, что он будет заинлайнен. К сожалению, в мире dotnet пока нет возможности делать частичный инлайнинг, так что если у вас есть горячая функция, которая в 99% случаях выходит после обработки первых нескольких строк, а остальная сотня строк идёт на обработку оставшегося 1%, то смело разбивайте её на две (или три), вынося тяжёлый хвост в отдельную функцию.
Span<T>, Memory<T> — многообещающе. Код будет проще и, может быть, чуть быстрее. Ждём релиза .Net Core v3.0 и Std v2.1, чтобы на них перейти, т.к. наше ядро на .Net Std v2.0, которое спаны нормально не поддерживает.
Async/await — пока неоднозначно. Простейшие бенчмарки случайного чтения показали, что действительно потребление CPU падает, но вот скорость чтения также снижается. Надо смотреть. Внутри индекса пока не используем.
Надеюсь, мне удалость доставить вам удовольствие от понимания красоты некоторых решений. Нам действительно очень нравится наш индекс. Он эффективен, красив кодом, отлично работает. Узкоспециализированное решение в ядре системы, критическом месте ее работы лучше, чем общее. Наша система контроля версий помнит ассемблерные вставки в С++ код. Теперь плюсов четыре — только чистый C#, только .Net. На нем мы пишем даже самые сложные алгоритмы поиска и ничуть не жалеем об этом. С появлением .Net Core, переход на Docker путь к светлому DevOps-будущему стал проще и яснее. Впереди — решение задачи динамической шардизации и репликации без снижения эффективности и красоты решения.
Спасибо всем, кто дочитал до конца. Обо всех очепятках и прочих нестыковках просьба писать комментарии. Буду рад любым обоснованным советам и опровержениям в комментариях.
Автор: supcry
Источник [21]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/c-2/313053
Ссылки в тексте:
[1] www.nikonsmallworld.com: https://www.nikonsmallworld.com/galleries/2016-photomicrography-competition/butterfly-proboscis
[2] ранее: https://habr.com/ru/company/antiplagiat/blog/413361/
[3] Хабре: https://habr.com/ru/company/antiplagiat/
[4] Википедия: https://ru.wikipedia.org/wiki/%D0%A7%D0%B5%D1%88%D1%83%D0%B5%D0%BA%D1%80%D1%8B%D0%BB%D1%8B%D0%B5#/media/File:Butterfly_wing_closeup.jpg
[5] хэшей: https://ru.wikipedia.org/wiki/%D0%A5%D0%B5%D1%88%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5
[6] системе «Антиплагиат»: https://www.antiplagiat.ru/
[7] реплицировать: https://en.wikipedia.org/wiki/Replication_(computing)
[8] шардингу: https://en.wikipedia.org/wiki/Shard_(database_architecture)
[9] Википедия: https://ru.wikipedia.org/wiki/%D0%A7%D0%B5%D1%88%D1%83%D0%B5%D0%BA%D1%80%D1%8B%D0%BB%D1%8B%D0%B5#/media/File:Butterfly_tongue.jpg
[10] Википедия: https://ru.wikipedia.org/wiki/%D0%A7%D0%B5%D1%88%D1%83%D0%B5%D0%BA%D1%80%D1%8B%D0%BB%D1%8B%D0%B5#/media/File:SEM_image_of_a_Peacock_wing,_slant_view_1.JPG
[11] бинарный поиск: https://ru.wikipedia.org/wiki/%D0%94%D0%B2%D0%BE%D0%B8%D1%87%D0%BD%D1%8B%D0%B9_%D0%BF%D0%BE%D0%B8%D1%81%D0%BA
[12] фильтр Блума: https://ru.wikipedia.org/wiki/%D0%A4%D0%B8%D0%BB%D1%8C%D1%82%D1%80_%D0%91%D0%BB%D1%83%D0%BC%D0%B0
[13] Википедия: https://ru.wikipedia.org/wiki/%D0%A7%D0%B5%D1%88%D1%83%D0%B5%D0%BA%D1%80%D1%8B%D0%BB%D1%8B%D0%B5#/media/File:SEM_image_of_a_Peacock_wing,_slant_view_2.JPG
[14] «The log-structured merge-tree»: https://www.cs.umb.edu/~poneil/lsmtree.pdf
[15] LSM: https://ru.wikipedia.org/wiki/LSM-%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE
[16] LSM-Tree: https://en.wikipedia.org/wiki/Log-structured_merge-tree
[17] Википедия: https://ru.wikipedia.org/wiki/%D0%A7%D0%B5%D1%88%D1%83%D0%B5%D0%BA%D1%80%D1%8B%D0%BB%D1%8B%D0%B5#/media/File:SEM_image_of_a_Peacock_wing,_slant_view_3.JPG
[18] статье: https://www.microsoft.com/en-us/research/publication/sequential-file-programming-patterns-and-performance-with-net/
[19] Википедия: https://ru.wikipedia.org/wiki/%D0%A7%D0%B5%D1%88%D1%83%D0%B5%D0%BA%D1%80%D1%8B%D0%BB%D1%8B%D0%B5#/media/File:SEM_image_of_a_Peacock_wing,_slant_view_4.JPG
[20] 85000: https://github.com/dotnet/docs/blob/master/docs/standard/garbage-collection/large-object-heap.md
[21] Источник: https://habr.com/ru/post/445952/?utm_campaign=445952
Нажмите здесь для печати.