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


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


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


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



    Шинглы, индекс и зачем их искать


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


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


    text:string → shingles:uint64[]


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



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


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


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


      index.Add(docId, shingles)

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


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


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


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


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


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


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

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


    Странный опыт


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



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


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


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


    • В случае 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, либо свой журнал обновлений. Эпизодически, например, раз в месяц (а иногда и год), временный сортировался, фильтровался и сливался с основным. В результате получался объединённый, а два старых удалялись. Если временный не мог влезть в оперативную память, то процедура шла через внешнюю сортировку.


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


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

    Чтобы и 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). Они могут не совпадать, но сейчас это почти всегда 4096 байт. Чтение одного-двух байтов на границе двух таких блоков в SSD происходит примерно в полтора раза медленнее, чем внутри самого блока.


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

    • No buffer.


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


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

    • Use buffer.


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


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


    MMF vs FileStream


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


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

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


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



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


    Bits/Bytes


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


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


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

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


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


    Struct, unsafe, batching, micro-opts


    Ну и прочие микрооптимизации. Я здесь не буду писать про банальные «стоит ли сохранять 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] — и трактор проехался по тонне гусей. Если нет возможности задействовать stackalloc, то создайте пул каких-либо объектов и переиспользуйте его заново.

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


    What else?


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

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


    Заключение


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


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

    «Антиплагиат»
    72,35
    Компания
    Поделиться публикацией

    Комментарии 41

      +2
      Прогоните пожалуйста данную статью через антиплагиат. Мне интересно насколько она оригинальна по мнению сервиса, от которого нынче зависят судьбы дипломов: как мне кажется, шинглы используемые в данном тексте встречаются, например, по всему хабру, много раз и в различных сочетаниях.
        +12
        image
          +2

          "Вместо тысячи слов" :) большое спасибо.

          +1
          Из того, что в статье используются те или иные слова (например, шингл) в каких-то сочетаниях совершенно не следует, что статья неоригинальна. Я могу даже сказать сильнее — все статьи на хабре преимущественно состоят из слов, которые уже где-то использованы. Если вам кажется, что какая-то часть текста заимствована (пусть даже с перефразировкой), то подскажите. Нам самим интересно ;)
            +1

            Нет, мне не кажется что она заимствована. Тем не менее, я помню хайп по поводу использования "антиплагиата", и мне хотелось увидеть его в действии на действительно оригинальном материале, пусть и с обилием лексики, часто употребляемой на конкретном сайте. Спасибо, моё любопытство вполне удовлетворено :)

          +1
          Если мои воспоминания об O-нотации не покрылись ещё хмурой дымкой инея, то превзойти O(1), обозначающего поиск за постоянное время независимо от объёма данных, можно лишь уменьшая время поиска при увеличении объёма данных. Вы точно-точно добились именно такого эффекта?
            0
            У O(1) можно либо константу уменьшить (о которой часто забывают), либо вообще обойтись без поиска (т.е. константу свести к нулю). В нашем случае иногда читать с диска не требуется, что можно считать вторым случаем.

            Про O(0) — это, конечно, была шутка.
              0
              При рассказе об O-нотации первым делом обычно объясняют, что это характеристика того, как изменяется трудоёмкость алгоритма в зависимости от роста объёма данных. Именно поэтому там в скобочках единица, а не другое число, именно поэтому не бывает чего-то вроде O(3*n). Так что о константе времени поиска не «забывают», просто её конкретное значение не имеет отношения к O.
              И как мне кажется, лучше даже в шутку не создавать кому-то проблемы с правильным пониманием смысла этой важной характеристики.
                +1
                Не редки ситуации, когда алгоритм с O(n) лучше навороченного с O(logn) в частном случае только лишь за счёт константы.
                  +1
                  Что является убедительным контрпримером для всех, кто считает О-нотацию единственным критерием оценки производительности. Мы же, как люди воспитанные, не будем создавать такого впечатления, навязывать О-нотации несвойственные ей обязанности и не станем грубо пихать ей в скобки всякого лишнего ненужного.
                0
                мгновенная вставка/удаление/обновление
                ну вот же О(0), какая такая шутка?
              0
              Вопрос немного не по теме. Насколько Ваша система устойчива к синонимизаторам?
              В свое время уникальный диплом писался заменой банально о=>o, потом можно было пользоваться вставками с невидимым шрифтом или удаленными словами, чуть позже вполне прокатывал метод автосинонимизации с ручной ловлей наиболее сомнительных косяков, позже мы завязали бороться с системой и начали писать дипломы по старинке… правда результаты по антиплагиату получались хуже, но зато понабрались лишних знаний:)
              Как сейчас с синонимизацией?
              «Карл у клары украл кораллы» будет одним плагиатом с «Петр Афанасльевич у Василия Ивановича своровал материал скелета колонии коралловых полипов» или нет?:)
                +2
                Про перефраз в прошлом году мы публиковали статью:«Трое в лодке, нищета и собаки», или как Антиплагиат ищет парафраз Уже полгода как на проде. Будет ещё одна статья на близкую тему.

                Омоглифы (замену банального о=>o) мы стали ловить ещё где-то в 2011 году. Полноценно проблему решили примерно в 2015. Ещё встречается, но довольно редко. На новых языках или если где недосмотрели в новых чекерах. Но довольно быстро затыкаем, как только обнаруживаем.

                Про технические способы обнаружения обхода мы выпустим полноценную статью в этом году. И, видимо, не одну!
                +1
                А саму файловую систему каким-то образом настраивали?
                  0
                  Полноценного тестирования на разных файловых системах с тюнингом их параметров не делали. ИМХО, кроме размера кластера и внутреннего кэширования там мало что на результат влияет в нашем случае (чтения большого файла).

                  Win+NTFS и Linux+BTRFS при дефолтных параметрах на одинаковом железе на глаз выдают примерно одинаковые результаты.

                  HDD сразу в пролёте. SSD — наше всё. Optane — пока не завезли.
                  SATA, конечно, хуже NVME, но тестировали полноценно только на первом. В NVME, конечно, скорость будет повыше. Индекс просто перестал быть узким местом в поиске, упираемся в последующие стадии.
                    +1
                    Overlapped IO дает прирост производительности?
                    FILE_FLAG_NO_BUFFERING, FILE_FLAG_WRITE_THROUGH для SSD имеет смысл?
                      0
                      Как я понимаю, .net'овский async в итоге задействует Overlapped IO. Если это так, то в моих замерах потоковая скорость немного проседает, но и cpu также меньше грузится. Пока глубоко не исследовал. Упоминал в конце статьи про Async/await.

                      FILE_FLAG_NO_BUFFERING в dotnet'е в явном виде нет, работает(?) как хак. Нет, не смотрел, но спасибо за наводку.

                      FILE_FLAG_WRITE_THROUGH в нашем случае, как я понимаю, не актуален, т.к. запись идёт последовательно и большими объёмами. А с ним скорость в этом сценарии будет меньше. Или я не прав?
                        0
                        Как я понимаю, .net'овский async в итоге задействует Overlapped IO.

                        Да.

                        Да, для FILE_FLAG_NO_BUFFERING можно определить константу и передать в параметрах FileStream. Там дополнительные требования к размеру буфера возникают. В вашем сценарии файловый кэш Windows особого смысла, мне кажется, не имеет. В статье про последовательные методы доступа по вашей ссылке приведены тесты с ним.

                        А вот FILE_FLAG_WRITE_THROUGH — конечно, спорный вопрос. Перечитал справку — если его использовать вместе с FILE_FLAG_NO_BUFFERING, то будет отключено кэширование метаданных, а это негативно отразится на производительности.
                        0
                        Overlapped IO даёт прирост только при одновременной обработке множества запросов, и при условии что диск нагружен ещё не на 100%. Причём «множество» тут — это более 1000, до этой цифры простая многопоточность, как правило, будет выглядеть лучше.

                          0
                          Ну автор использует же пул FileStream для SSD для той же цели.
                          Насколько я помню, overlapped I/O в .net реализован через I/O Completion Ports.
                          Читал в MSDN Magazine, что их имеет смысл использовать даже в случае единственного рабочего потока — из-за обработки на уровне ядра.
                            0
                            Да, из имеет смысл использовать даже в случае единственного потока. Но при этом одновременных задач все равно должно выполняться много.
                  • НЛО прилетело и опубликовало эту надпись здесь
                      0
                      Вы нас озадачили. :)
                    • НЛО прилетело и опубликовало эту надпись здесь
                        0
                        Отличный вопрос. Не готов на него сейчас ответить. Действительно, скорость прирастёт и объём уменьшится (правда не на 25%).

                        Про уникальные слова я не понял идею. Можете разъяснить?
                        • НЛО прилетело и опубликовало эту надпись здесь
                          • НЛО прилетело и опубликовало эту надпись здесь
                              0
                              Универсальная и популярная схема, но не очень гибкая. Кроме того, рашдинг по шинглам имеет свои проблемы именно на больших индексах.

                              Когда допилим, обязательно будет отдельная статья на эту тему.
                              0
                              Сейчас да, 40 бит будет достаточно. 48 — с лихвой. Но при росте объёма хотя бы на пару порядков упрёмся уже в этот новый потолок.

                              Про уникальные слова. Шингл — это хэш нескольких слов. У нас есть списки стоп-шинглов и «тяжёлых» шинглов, о чём написано выше в статье. Про алгоритм генерации шинглов в общих чертах есть здесь.
                            0
                            Теоретически, частота коллизий возрастёт примерно в 65536 раз, но статистические показатели коллизионных наборов, в частности, наиболее типичный размер (математическое ожидание) множества с коллизионным хешем и размер «рекордной команды» (множество, максимальное по размеру из встреченных с одним хешем) возрастут не так радикально, как мне кажется
                            0

                            Забавно, студентом делал на кафедре "научный" проект по отлавливанию плагиата и использовал шинглы. Не знал, что серьёзные системы тоже на них построены.

                              –2
                              Гм… Серьезные системы?) Странно…
                              Автор и его компания заюзала как раз таки самые базовые вещи. И самое главное — они разобрались в этом. По-сути — у них «массивы» через хэши «массивами» погоняют. И все. А разве нужно что-то еще? И явственно тут «попахивает» «ненормальным» программированием. А уж то что нет аджайла, и ваще на гите этого нет, и даже ни единого нода нет, и «покетов» нет — так это же вообще ужасно! Какая же это серьезная система?))) Это ж поделка из прошлого века. Нельзя так!

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

                              И выводы ужасные конечно… Все бд — шлак. Или узкозаточены под что-то, и только под что-то. И при этом — крайне избыточны. Еще и глючные. Все фреймворки — шлак. Если нужно быстро — пиши свое. И т.д. и т.п.

                              По меркам хабры — автор просто взял и втоптал в грязищщу «многовековые» «труды» местных писак. Всего навсего написав чуть ли не на паскале 5000 строк абсолютно простого кода так, что у этих писак никогда в жизни не получится по-определению.

                              Браво, автор! Браво!
                                +1
                                Серьезность для меня определяется объемами данных, которые сейчас есть в системе и нагрузкой, которую они держат.
                                И да, ничего нет плохого в массивах. Замена Array на List или какую-то доменную модель не делает приложение круче.
                                У ребят конкретная узкая задача и они выжимают максимум из железа используя собственные решения. По-моему всё отлично.
                              0
                              Периодически приходится писать разъяснения для партнеров, статьи которые по сути представляют собой цитаты из нормативки (кто попадает под требования по КИИ, какие законом требуются меры защиты и тд) плюс простейшие комментарии для понимания, о чем требования. Юристы ругаются и говорят, что плагиат — мол было в интернете уже. И возразить нечего. Но зачастую иначе и не напишешь. Тот же 152-фз описан со всех сторон, но очень многие о нем умудрились не услышать за прошедшее время
                              Поэтому чисто для интереса. Когда вы в публикациях встречаете цитаты из той же нормативки — вы их тоже учитываете как плагиат или исключаете из анализа?
                                0
                                У нас есть специальное выделение легитимных заимствований нормативно-правовых документов, реализовано как поиск по системам с нормативкой типа Гарант. Такое заимствование называется «цитированием» и отмечается зеленым цветом. В целом 100% = Заимствование + Цитирование + Оригинальный текст. Цитированием так же считается: корректно оформленное цитирование, общеупотребимые фразы, библиография.
                                Важно отмечать и такое заимствование, т.к. может оказаться что вся работа состоит из цитрований и своих мыслей совсем нет. Мы стараемся предоставить эксперту максимальный объем информации чтобы он смог вынести взвешенное решение.
                                  0
                                  Спасибо.
                                  Уточню. Цитаты не всегда идут так как в нормативке. Скажем часто по требованию компактности статьи списки объединяются в один абзац или вырезается часть текста (без потери смысла естественно)
                                  Не скажу, что часто, но за этот год я штуки две написал публикации чисто повторы. Люди не знают, не любят сами читать нормативные акты — поэтому приходится так делать. Иногда сидишь и думаешь — ну как бы так написать в очередной раз, чтобы отличалось хоть чуть.
                                0
                                Если у вас хеш 64-битный, id документа допустим тоже и триллион уникальных шинглов, то получается первый индекс(«1 массив индекса») весит как минимум 1*10^12*(8+8)/1024/1024/1024/1024 или примерно 14.5 тб?!
                                  0
                                  Вы верно подметили масштаб проблемы.
                                    0
                                    Можете описать немного подробнее как происходит поиск? Есть у вас огромный отсортированый массив hash->docId который устроен так чтоб несколько элементов влезали целиком в кластер на диске. Непонятно как вы получаете позицию кластера по хешу, можете подробнее рассказать про магический эффективный словарь, во круг которго как я понял все крутится?
                                      +1
                                      Непонятно как вы получаете позицию кластера по хешу, можете подробнее рассказать про магический эффективный словарь, во круг которго как я понял все крутится?
                                      Хеш-таблица
                                      disclaimer
                                      да, в таком случае фактически используется хэш от хэша, но функции хэширования, в общем случае, разные и это не тот случай, когда таким образом пытаются «улучшить» хэширование или добиться каких-то других экзотических целей
                                        0
                                        Как работает Hashtable например в той же java я знаю. Но как работатет поиск тут не пойму.

                                Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                Самое читаемое