Русский
Русский
English
Статистика
Реклама

Search engine

Полнотекстовый поиск в Couchbase Server

27.11.2020 10:16:55 | Автор: admin
Дмитрий Калугин-Балашов большую часть своей жизни писал поиск: с 2011 года в компании Mail.ru был поиск по почте, затем был небольшой перерыв из-за работы в США, а сейчас это работа над поиском в Couchbase. Одна из первых вещей, которую Дмитрий понял, работая в США не всегда покупают самое эффективное решение. Иногда покупают то, где клиент будет иметь меньше проблем.

Поэтому ещё в 2013 году Дмитрий написал движок поиска для почтовых ящиков Mail.ru и рассказал об этом в том же году на конференции HighLoad и в статье на Хабре. А на HighLoad 2019 показал, как устроен полнотекстовый поиск в Couchbase Server, и сегодня мы предлагаем расшифровку его доклада.



На самом деле в Couchbase используется внешний опенсорсный движок Bleve:

Этот движок изначально был создан внутри Couchbase как проект для реализации полнотекстового поиска в виде библиотеки, написанной на Go. Сначала он был простым монолитным индексом если есть хранилище ключ-значение, то слева берём слова в виде ключей, а в виде значений ставим документы и всё, у нас есть полнотекстовый поиск! Но в работе он становился очень большим, а обычное хранилище k-value под поиск не оптимизировано. Нагрузка под поиск очень специфичная, а если ещё и апдейты есть, то движок неизбежно начинает тупить.

Поэтому Couchbase решили создать сегментированный индекс специальное хранилище под поисковые данные, в котором используются Immutable-сегменты, оптимизированные под поиск.

Что такое обратный индекс? Если есть книга, в которой я хочу что-то найти по слову как это сделать? На последней странице обычно есть указатель на слово и страницу, где этот термин встречается. Обратный индекс сопоставляет слова со списком. В книге это страницы, у нас документы в базе (у нас документно-ориентированная БД, в которой хранятся джейсонки).

ОК, а как хранить список слов?


Map[string]uint. Самое простое. Кто владеет Гошкой, знает, что это хэш-таблица. Но это не очень хорошо, потому что у нас используются слова, и иногда надо по ним итерироваться. Если у нас неточный поиск, мы начинаем считать расстояние Левенштейна, нужно итерироваться местами, а это по hashmap нельзя. Но можно сделать дерево.

Tree. Но дерево оно здоровое, поэтому тоже не годится, потому что мы делаем хранилище под поиск, а это одновременно и общее хранилище для БД.

Trie. Префиксное дерево это уже лучше, оно довольно компактное, его можно через два массива построить. Но можно ли сделать лучше?

Finite State Transducer. Это автомат под названием Vellum, который Couchbase для себя же и написали. Есть реализация FST на Go и других языках. В нем есть всего лишь три процедуры:
  • Построение FST (один раз);
  • Поиск;
  • Итерирование.

Чтобы построить, нужен список слов в алфавитном порядке (например, возьмём are, ate, see). Так как у нас индексы сегментированные (сегменты неизменяемые), то нам это отлично подходит мы его построили один раз и забыли.

Давайте теперь построим. Мы должны хранить пары: слово число (потом это будет указатель). Состояния автомата просто нумеруются числами, и на каждом ребре есть буква и число. По сумме этих чисел мы считаем конечное число:



Таким образом слово are дает 4. Добавляем второе слово:



Добавляем третье слово:



Теперь мы делаем еще одну операцию и компактим:



Получается автомат, в котором всего два объекта:
  1. Builder мы строим, операцию делаем;
  2. Reader мы читаем и делаем либо поиск, либо итерацию.

Открыть его мы можем либо из файла через mmap (если он поддерживается в системе):
fst, err := vellum.Open("/tmp/vellum.fst")

либо из массива Bytes (это нам будет очень нужно дальше), и можем загрузить прямо из буфера:
fst, err := vellum.Load(buf.Bytes())

Дальше запускаем поиск в FST:
val, exists, err = fst.Get([]byte("dog"))


Как хранить PostingsList?


К списку слов есть список страниц в книге, а в БД PostingsList список документов. Как его можно хранить?
  • Просто список чисел это массив (кстати, можно использовать дельта-кодирование);
  • Битовый массив. Это удобно, если, что список чисел, как страницы в книге, начинается просто от 0 и числа идут подряд. Но только если в нем не будет повторяемых элементов.
  • RLE-сжатие. Битовый массив можно еще иногда сжать.

Как сделать лучше? Есть RoaringBitmap, с библиотеками почти для всех языков. Работает он так: берем последовательность наших чисел и разбиваем на куски (чанки). Каждый чанк кодируем одним из трех способов:
  1. Просто список чисел
  2. Битовый массив
  3. RLE-сжатие

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

Поиск Memory-Only?


Теперь попробуем сделать полнотекстовый поиск Memory-Only. У нас есть Snapshot это наш индекс на какую-то единицу времени. В нём есть несколько сегментов с данными. Внутри сегментов ищем обратные индексы, которые все read-only. Также есть какое-то приложение, которое работает с нашим поиском:



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



Но сами сегменты нам не нужны мы копируем их под read mutex и добавляем новый сегмент. Маленькие фрагменты это просто битовые массивы. Если что-то удаляется, мы просто выставляем там биты:



То есть сам сегмент read only (immutable), но удалить что-то можно, выставив эти биты, если в новом сегменте пришла эта информация. Это называется Segment Introduction: есть новый сегмент (битовый массив) и горутина (Introducer). Ее задача добавить сегмент в наш Snapshot, который мы присылаем по каналу:



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



И все мы переходим к четвертому Snapshot и получаем Memory-Only решение:



Для того, чтобы сохранить на диск, есть еще одна горутина Persister. У нас есть номера эпох, также пронумеруем сегменты (a, b, c, d):



В Persister есть цикл FOR, время от времени он пробуждается и смотрит О! Появился новый сегмент, давайте его сохраним:



Для этого сегмента у нас две базы данных: маленькая БД, куда он сохраняется, и корневая БД, которая просто описывает всю эту конструкцию. Таким образом мы сохраняем на диск и меняем номер эпохи после записи:



Сегменты будут расти (они все неизменяемые), когда-то мы захотим их склеить и для этого у нас есть merger. Создаем Merge plane третьей горутиной:



Также есть номер эпохи, когда мы мерджим. Далее мы делаем какие-то операции. Merge Introduction, как и обычный сегмент Introduction, попадает обратно в него и создает новый сегмент, а два склеивает, удаляя оттуда данные:



Таким образом мы удаляем часть сегментов.

Важное примечание. После того, как мы записали zap-файл на диск, мы сегмент закрываем и тут же обратно открываем, но не как in-memory сегмент, а как сегмент на диске. Хотя у них одинаковый интерфейс, устроены они по-разному: сегмент на диске проецируется в память через mmap.

Формат ZAP


Изначально это был BoltDB. Потом создатель сказал: Ну вас всех на фиг, я устал, я ухожу, и BoltDB закрылся. Хотя позже его форкнули в BBoltDB, работал он всё равно плохо, потому что вернулись к той же проблеме: база данных в общем не очень подходит для хранения поисковых индексов. И мы тогда заменили BBoltDB на самописный формат .zap. Корневая база осталась BBoltDB, но там ничего особо критичного хранить не надо:



Формат ZAP это просто сегмент на диске. Мы его не читаем READами, он читается mmapом, при этом данные внутри максимально удобны для in-memory работы. Сам формат ZAP с индексами выглядит так:



В футере описано, где что искать, и мы по указателю находим индекс полей. Что у нас есть? Есть сколько-то (от 0 до F#) проиндексированных полей в документах, они пронумерованы и проиндексированы. Стрелками показаны указатели, сколько полей, и мы знаем заранее, сколько их. Мы находим в Fields Index указатель, а в Fields место, и понимаем по названию поля, что это такое:



Есть еще один указатель:



Он указывает место, где будут храниться наши словари (dictionaries), при этом, под каждое поле будет свой словарь:



Этот указатель показывает VELLUM данные:



А мы помним, что VELLUM может читать данные прямо из памяти. Мы спроецировали память, нашли нужный указатель, взяли кусок данных и начали с помощью VELLUM в нём искать. Нам даже не нужны READ, мы просто к списку слов делаем список OFFSET, который ведёт к RoaringBitmap. Таким образом мы получаем номера документов, которые найдутся по этому слову в этом поле:



Также есть позиции вхождения, если мы хотим сделать подсветку. Если у нас длинная строка, то мы узнаем, в каком месте находится нужное нам слово. Еще мы можем получить определенную статистику частоты встречаемости и другую инфу, нужную для ранжирования:



DocValues это вспомогательный и необязательный список полей, в нём хранятся значения полей:



Значения полей нужны для ранжирования, мы дублируем по номеру поля значения для каждого документа:



Для каждого документа мы знаем список полей и их значение. И, что самое важное, тут есть искусственное поле ID. Дело в том, что внутри ZAP-файла все документы нумеруются с 0 и до бесконечности, а в самой базе данных текстовые имена. Так что в ID происходит сопоставление между номером внутри ZAP-файла и внешним номером (внешним именем):



Остаются мелочи. Это Chunk Factor(на какие кусочки бьем, когда делаем чанки данных), версия, контрольная сумма и число документов (D#):



Это весь ZAP-файл. Как искать, думаю, уже понятно: мы отражаем в память и находим, по какому полю ищем. После этого находим слово, идем по длинной цепочке и находим результаты.

Rollback


Есть интересная операция Rollback. Базе данных Rollback нужен всегда мы можем нагородить огород, и нам нужна возможность откатиться. В нашем случае откат делается очень просто. У нас есть эпохи. Мы храним в корневой базе текущую конфигурацию и предыдущие (1-2), куда хотим откатиться. Если мы хотим откатиться на предыдущую эпоху, мы достаем конфигурацию из индекса, и получаем откат на предыдущую эпоху. В сегмент мы добавляем, когда происходит какая-то операция или группа операций (мы обычно их вставляем большой группой):



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

Так работает само ядро. Как работает поиск уже очевидно. Если поиск идет по точному совпадению, то прочитали, прошли по цепочке и нашли. Если поиск неточный, то добавляется автомат Левенштейна и начинаются итерации по vellum, но процесс проходит примерно так же.

Пока пандемия идет к финишу, мы продолжаем проводить встречи онлайн. В понедельник 30 ноября будем обсуждать банковскую архитектуру на встрече Эволюция через боль. Как устроен СберБанк Онлайн изнутри?. Рассмотрим с нуля, как создается и развивается архитектура в банке и узнаем, что под капотом у крупнейшего банка страны. Узнаем, почему банку недостаточно простого приложения из одного сервиса и одной базы данных и увидим на примерах монолит и микросервис. Начало в 18 часов.

А 3 декабря будет митап Безопасность и надёжность в финтехе. Спикеров будет несколько, и они поднимут несколько тем. Сначала будет разговор о закулисье финтеха, затем как и какими инструментами сделать финтех надежным сервисом, и на закуску как снизить риски ИБ в разработке финансовых систем. Начнем в 17.

Следите за новостями Telegram, Twitter, VK и FB и присоединяйтесь к обсуждениям.
Подробнее..

Одномерный поиск образца с использованием дискретного преобразования Фурье

17.04.2021 18:19:17 | Автор: admin

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

Потому занялся дополнительным поиском готовых реализаций, но к сожалению не смотря на обилие упоминаний идеи 1974 года[2], реализаций алгоритма, даже на законодателе моды в вычислительной математике Фортране я не обнаружил. В семинарах и лекциях да и в диссертациях описание не блистало целостностью, потому собрав с десяток статей и обсуждений в кучу появилось желание написать статью для тех кто простейшую реализацию поиска подстроки хочет "подержать в руках".

И так, написание алгоритмических программ обычно произвожу сначала в математических пакетах, и только после выяснения численной устойчивости и корректности работы алгоритма перевожу в код на компилируемые или байт ориентированные языки. Таков уж мой опыт, - или считать медленно но точно, или быстро но то что уже практически известно. Потому для отладочного иллюстративного кода использовал Wolfram Language и набор функций пакета Mathematica V 12.

Собственно в чем ценность идеи: использование дискретного Фурье преобразования (DFT) сокращает сложность вычисления от "наивного" O(n*m) до O(n Log(n)), где n - размер текста а m - размер искомого образца. Более того расширения метода позволяют производить поиск с "Джокером", - символом обозначающим любой другой символ в алфавите, в то время как суффиксные реализации это сделать не позволяют.

Описание "наивного" подхода:

Для массива T размером n и образца P размером m, вычислим функцию квадратов разницы значений элементов. Нумерация в массиве начинается с нуля.

S_i^F = \sum\nolimits_{j = 0}^{m - 1} {({t_{i + j}}} - {p_j}{)^2} = \sum\nolimits_{j = 0}^{m - 1} {t_{i + j}^2} - 2\sum\nolimits_{j = 0}^{m - 1} {{t_{i + j}}} {p_j} + \sum\nolimits_{j = 0}^{m - 1} {p_j^2} = T{T_i} - 2P{T_i} +P{P_i}

Очевидно что в точке соответствия искомая сумма показывает минимум, если точнее обнуляется. После раскрытия квадрата под суммой получаются три слагаемых, последнее из которых имеет постоянное значение. Соответственно для поиска минимума необходимо вычислить только первые две суммы. Можно увидеть что прямое вычисление всех элементов S требует O((n-m+1)*m) операций, или оценочно O(n*m).

В качестве массива в котором будем искать образец используем строчку из картинки:

"Test.png""Test.png"

Произведем прямое вычисление искомой функции:

{S_i} = \sum\nolimits_{j = 0}^{m - 1} {t_{i + j}^2} - 2\sum\nolimits_{j = 0}^{m - 1} {{t_{i + j}}} {p_j} = T{T_i} - 2P{T_i}
Img = ColorConvert[Import["Test.png"], "Grayscale"];{W, H} = ImageDimensions[Img];   y = IntegerPart[H/2];                                (*Pattern width and coordinates*)x = IntegerPart[W/4]; w = IntegerPart[W/8];            L = Part[ImageData[ImageTake[Img, {y, y}]],1];       (*Stripe Array*)T[i_] := Table[Part[L[[i + j - 1]], 1], {j, 1, w}] ;      (*Sample data*)P[i_] := Table[Part[L[[j + x - 1]], 1], {j, 1, w}] ;      (*Pattern data*)TT = Table[Sum[(T[i][[j]]* T[i][[j]]), {j, 1, w}], {i, 1, W - w + 1}];PT = Table[Sum[(P[i][[j]]* T[i][[j]]), {j, 1, w}], {i, 1, W - w + 1}];ListPlot[TT - 2 PT, Joined -> True, PlotRange -> All]
Результат вычисления квадрата разницы без постоянного слагаемогоРезультат вычисления квадрата разницы без постоянного слагаемого

Как видно в точке (x=175), где был взят образец, функция показала минимальное значение и повторила его значение ведь изображение почти дублируется.

Свойства дискретного Фурье преобразования.

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

Вычисление PT

PolyT = {1, 2, 3, 4, 5};               LT = Length[PolyT];PolyP = {1, 2, 3};                     LP = Length[PolyP];PolyR = {};                            LR = LT + LP - 1;eT = Table[If[i > LT, 0, PolyT[[i]]], {i, 1, LR}]eP = Table[If[i > LP, 0, PolyP[[i]]], {i, 1, LR}]PolyR = InverseFourier[   Fourier[eT, FourierParameters -> {1, 1}]*   Fourier[eP, FourierParameters -> {1, 1}]  , FourierParameters -> {1, 1}]PolyR[[LP ;; LT]]

результат действия такого кода:

{1, 2, 3, 4, 5, 0, 0} (* PolyT *){1, 2, 3, 0, 0, 0, 0} (* PolyP *){1., 4., 10., 16., 22., 22., 15.} (* PolyR = PolyT * PolyP *){10., 16., 22.}                   (* PolyR starting at LP to LT*)

Итак, если массив значений представить полиномами, то получаемое значение тоже полином размером n+m-1.

\left( {1 + 2x + 3{x^2} + 4{x^3} + 5{x^4}} \right)\left( {1 + 2x + 3{x^2}} \right) = 1 + 4x + 10{x^2} + 16{x^3} + 22{x^4} + 22{x^5} + 15{x^6}

Более того, начиная с позиции m (если нумерация начинается с единицы) мы получаем сумму перекрестного произведения элементов для окна длинны m:

10 = 1*3+2*2+3*116 = 2*3+3*2+4*1...

Потому для вычисления элементов PT искомый образец P разворачивается. Всего получается n-m+1 значений.

Вычисление TT

PolyT = {1, 2, 3, 4, 5};            LT = Length[PolyT];PolyP = {1, 1, 1};                  LP = Length[PolyP];PolyR = {};                         LR = LT + LP - 1;eT = Table[If[i > LT, 0, PolyT[[i]]], {i, 1, LR}]eP = Table[If[i > LP, 0, PolyP[[i]]], {i, 1, LR}]PolyR = InverseFourier[   Fourier[eT, FourierParameters -> {1, 1}]*   Fourier[eP, FourierParameters -> {1, 1}]  , FourierParameters -> {1, 1}]PolyR[[LP ;; LT]]

результат действия кода:

{1, 2, 3, 4, 5, 0, 0}                 (* PolyT *){1, 1, 1, 0, 0, 0, 0}                 (* PolyP *){1., 3., 6., 9., 12., 9., 5.}         (* PolyR = PolyT * PolyP *){6., 9., 12.}                         (* PolyR starting at LP to LT*)
6 = 1*1+2*1+3*19 = 2*1+3*1+4*1...

Учитывая предыдущий пример, в массив текста заносятся квадраты значений элементов, а в массив искомого образца единицы, длинна последовательности единиц - m.

Сборка и сравнение

Вычисление PP и TT с использованием DFT:

Tt = Table[If[1 <= i <= W, Part[L[[i]], 1], 0], {i, 1, Wt}] ;    (*Sample data*)Ft = Fourier[Tt, FourierParameters -> {1, 1}];Ts = Table[If[1 <= i <= W, (Part[L[[i]], 1])^2, 0], {i, 1, Wt}]; (*Sample squared data*)Fs = Fourier[Ts, FourierParameters -> {1, 1}];Es = Table[If[1 <= i <= w, 1, 0], {i, 1, Wt}] ;                  (*m size unit array*)Fe = Fourier[Es, FourierParameters -> {1, 1}];Pa = Table[If[1 <= i <= w, Part[L[[x + w - i]], 1], 0], {i, 1, Wt}];                                                             \Fp = Fourier[Pa, FourierParameters -> {1, 1}];                   (*Inverse pattern data*)TTf = InverseFourier[Fs*Fe, FourierParameters -> {1, 1}][[w ;; W]];PTf = InverseFourier[Ft*Fp, FourierParameters -> {1, 1}][[w ;; W]];

Сравниваем полученные значения:

ListPlot[{TT - 2 PT, TTf - 2 PTf, TT - 2 PT - TTf + 2 PTf}, Joined -> True, PlotRange -> All]
Три графика, два совпадающих и один показывающий разницу между ними, совпадает с осью.Три графика, два совпадающих и один показывающий разницу между ними, совпадает с осью.

Выводы

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

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

  1. http://personeltest.ru/aways/habr.com/ru/post/266129/

  2. https://eduardgorbunov.github.io/assets/files/amc_778_seminar_08.pdf

Подробнее..
Категории: Алгоритмы , Search engine , Dft

Категории

Последние комментарии

  • Имя: Макс
    24.08.2022 | 11:28
    Я разраб в IT компании, работаю на арбитражную команду. Мы работаем с приламы и сайтами, при работе замечаются постоянные баны и лаги. Пацаны посоветовали сервис по анализу исходного кода,https://app Подробнее..
  • Имя: 9055410337
    20.08.2022 | 17:41
    поможем пишите в телеграм Подробнее..
  • Имя: sabbat
    17.08.2022 | 20:42
    Охренеть.. это просто шикарная статья, феноменально круто. Большое спасибо за разбор! Надеюсь как-нибудь с тобой связаться для обсуждений чего-либо) Подробнее..
  • Имя: Мария
    09.08.2022 | 14:44
    Добрый день. Если обладаете такой информацией, то подскажите, пожалуйста, где можно найти много-много материала по Yggdrasil и его уязвимостях для написания диплома? Благодарю. Подробнее..
© 2006-2024, personeltest.ru