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

Индексы

Перевод Текстовый индекс по котировкам в памяти на Go

09.09.2020 14:04:11 | Автор: admin

Недавно понадобилось реализовать поиск по началу строки, по сути WHERE name LIKE 'начало%'. Это был поиск по названию биржевых символов (AAPL, AMZN, EUR/USD и пр.). Хотелось, чтобы поиск работал быстро, и не нагружал лишний раз БД. В итоге пришел к реализации поиска по дереву в памяти, об этом и расскажу.

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

Ниже описана реализация поиска. Сразу отмечу, что это не сбалансированное дерево BTree, а простое дерево, где на каждом уровне очередной символ строки. Реализация такого варианта дерева очень проста и достаточно эффективна для многих задач, когда требуется индексировать не длинные строки.

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

Структура дерева

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

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

  • AAA (BetaShares Australian High Interest Cash ETF, ASX),

  • AAA (All Active Asset Capital LTD, LSE).

Тогда мы запишем в Index.Data одну запись, внутри которой в Index.Data будет список из двух символов AAA.

В SearchIndex.Data можно хранить данные любой структуры. Таким образом, можно индексировать любые данные по строковому ключу.

Построение дерева для поиска

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

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

  1. Все разделители заменяются на пробелы.

  2. Двойные пробелы заменяются на одинарные.

  3. Обрезаются пробелы по краям строк.

  4. Строки переводятся в нижний регистр.

  5. Схожие символы приводятся к единому формату, например, a.

  6. Исключаются стоп-слова (опционально).

После этого данные сортируются, по умолчанию по возрастанию ключа, в алфавитном порядке.

Затем отсортированные данные группируются по ключу, чтобы положить в Index.Data готовый список.

Теперь все готово для добавления данных в индекс. Наша задача теперь сформировать Index.Children таким образом, чтобы на каждом уровне дерева лежал очередной кусочек ключа (в нашем случае кусочек ключа это символ индексируемой строки). Например, если мы добавляем в индекс символ AAPL, то мы сформируем такую древовидную структуру (красная линия):

Тут на красной линии расположены на каждой вершине дерева элементы [A], [A], [P], [L]. В квадратных скобках обозначены ключи, которые используются на каждой вершине для индексации. Без скобок обозначены полные ключи, которые получаются при проходе от корня до вершины.

Поскольку мы формируем дерево, то добавление в индекс удобно делать рекурсивно. Добавляем промежуточные узлы, если их нет. И в лист дерева добавляем значение, которое мы индексируем.

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

Поиск по дереву

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

  1. Выполним предварительную обработку искомой строки тем же алгоритмом как обрабатывали ключи перед индексацией (см. выше).

  2. Найдем в дереве элемент, в котором ключ совпадает с искомой строкой.

  3. Далее последовательным перебором дочерних вершин получаем искомый результат.

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

  • АА

  • ААА

  • АAAL

  • AAALF

  • AAAP

  • AAB

  • AAP

  • AAPJ

  • AAPL

  • AAPT

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

Поиск подходящего биржевого символа

Вышеперечисленный алгоритм хорошо подходит для поиска аналогичного WHERE name LIKE 'начало%'. Чтобы было удобно искать подходящий символ на финансовых рынках, этого оказалось недостаточно, и понадобилось учесть следующие моменты.

  • Если вводят в поиске EUR, то в выдаче должны быть EUR, EUR/USD, USD/EUR. То есть поиск должен работать не только с начала строки, но и с начала каждого слова в строке.

  • Поиск должен работать не только по названию символа, но также и по названию компании. Например, при вводе в поиске APL, надо выдать в результатах APL, AAPL (Apple).

  • Первыми выдавать в поиске популярные символы.

Чтобы для EUR, в выдачу попали не только EUR, EUR/USD, но и USD/EUR, решил класть в индекс по несколько экземпляров значений с разными ключами: подстроки начиная с каждого слова индексируемой строки. Например, при индексации строки USD/EUR, в индекс попадают следующие ключи: usd eur, eur. При индексации строки Grupo Financiero Galicia SA в индекс попадают ключи Grupo Financiero Galicia SA, Financiero Galicia SA, Galicia SA, SA.

Также чтобы учесть вышеописанные нюансы, понадобилось выполнять поиск в 4 этапа.

  1. Поиск символов по точному совпадению с искомой строкой.

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

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

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

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

  1. Индекс SearchSymbolIndex по символам со всех финансовых рынков.

  2. Индекс SearchPopularIndex только по популярным символам (10% от всех).

  3. Индекс SearchInstrumentIndex по названию компании.

Далее просто последовательный поиск по каждому индексу с небольшой разницей в критерии.

var searchedData []searchindex.SearchDatasearchedData = r.SearchSymbolIndex.Search(searchindex.SearchParams{    Text: key,    OutputSize: outputSize,    Matching: searchsymbol.Strict,})searchedData = r.SearchPopularIndex.Search(searchindex.SearchParams{    Text: key,    OutputSize: outputSize,    Matching: searchsymbol.Beginning,    StartValues: searchedData,})searchedData = r.SearchSymbolIndex.Search(searchindex.SearchParams{    Text: key,    OutputSize: outputSize,    Matching: searchindex.Beginning,    StartValues: searchedData,})searchedData = r.SearchInstrumentIndex.Search(searchindex.SearchParams{    Text: key,    OutputSize: outputSize,    Matching: searchindex.Beginning,    StartValues: searchedData,})

StartValues значения, найденные на предыдущем этапе, они передаются на следующий этап поиска, чтобы в выдачу не добавлялись дубликаты, и не выполнялись лишние итерации поиска, если уже набралось достаточно данных (OutputSize).

searchindex.Strict поиск точных совпадений.

searchindex.Beginning поиск совпадений по началу строки.

Итого

Итого, имеем компактную реализацию быстрого поиска по строке в оперативной памяти. Код на данный момент занимает менее 300 строк. Причем реализация индекса получилась довольно универсальной, чтобы ее можно было использовать при реализации различных схожих задач.

Больших бенчмарков по производительности не делал, но на моих данных в 55000 строк создание трех индексов занимает примерно 2 секунды, это с учетом выборки из БД и дополнительных действий. А поиск в 4 последовательные итерации в трех индексах выполняется за 100-200 наносекунд (это если исключить время на обработку http запроса и считать только время поиска), что для моей задачи более чем достаточно.

Код в виде готового пакета: https://github.com/twelvedata/searchindex

Этот поиск сейчас используется в финансовом апи для разработчиков, пример можно посмотреть на этой странице, где его можно попробовать вживую.

Подробнее..

FAISS Быстрый поиск лиц и клонов на многомиллионных данных

02.07.2020 12:23:15 | Автор: admin


Однажды в преддверии клиентской конференции, которую ежегодно проводит группа DAN, мы размышляли над тем, что интересного можно придумать, чтобы у наших партнеров и клиентов остались приятные впечатления и воспоминания о мероприятии. Мы решили разобрать архив из тысяч фотографий с этой конференции и нескольких прошлых (а всего их к тому моменту было 18): человек отправляет нам свою фотографию, а мы ему через пару секунд отправляем подборку фотографий с ним за несколько лет из наших архивов.

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

Добавили Telegram-бота для удобства, и всё было отлично. С точки зрения алгоритмов распознавания лиц всё работало на ура, но конференция завершилась, а расставаться с опробованными технологиями не хотелось. От нескольких тысяч лиц хотелось перейти к сотням миллионов, но конкретной бизнес-задачи у нас не было. Через некоторое время у наших коллег появилась задача, которая требовала работы с такими большими объемами данных.

Вопрос был в том, чтобы написать умную систему мониторинга ботов внутри сети Instagram. Тут наша мысль породила простой и сложный подходы:

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

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

Что дальше?


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

  1. Скорость и точность поиска
  2. Размер занимаемого данными места на диске
  3. Размер используемой RAM памяти.

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

Существуют известные и зарекомендовавшие себя технологии, такие как Annoy, FAISS, HNSW. Быстрый алгоритм поиска соседей HNSW , доступный в библиотеках nmslib и hnswlib, показывает state-of-the-art результаты на CPU, что видно по тем же бенчмаркам. Но его мы отсекли сразу, так как нас не устраивает количество используемой памяти при работе с действительно большими объемами данных. Мы стали выбирать между Annoy и FAISS и в итоге выбрали FAISS из-за удобства, меньшего использования памяти, потенциальной возможности использования на GPU и бенчмарков по результативности (посмотреть можно, например, здесь). К слову, в FAISS алгоритм HNSW реализован как опция.

Что такое FAISS?


Facebook AI Research Similarity Search разработка команды Facebook AI Research для быстрого поиска ближайших соседей и кластеризации в векторном пространстве. Высокая скорость поиска позволяет работать с очень большими данными до нескольких миллиардов векторов.

Основное преимущество FAISS state-of-the-art результаты на GPU, при этом его реализация на CPU незначительно проигрывает hnsw (nmslib). Нам хотелось иметь возможность вести поиск как на CPU, так и на GPU. Кроме того, FAISS оптимизирован в части использования памяти и поиска на больших батчах.

Source

FAISS позволяет быстро осуществлять операцию поиска k ближайших векторов для данного вектора x. Но как же этот поиск устроен под капотом?

Индексы


Главное понятие в FAISS это index, и, по сути, это просто набор параметров и векторов. Наборы параметров бывают совершенно разные и зависят от нужд пользователя. Векторы могут оставаться неизменными, а могут перестраиваться. Некоторые индексы доступны для работы сразу после добавления в них векторов, а некоторые требуют предварительного обучения. Имена векторов хранятся в индексе: либо в нумерации от 0 до n, либо в виде числа, влезающего в тип Int64.

Первый индекс, и самый простой, который мы использовали ещё на конференции, это Flat. Он лишь хранит в себе все вектора, а поиск по заданному вектору осуществляется полным перебором, поэтому обучать его не нужно (но об обучении ниже). На маленьком объеме данных такой простой индекс может вполне покрыть нужды поиска.

Пример:

import numpy as npdim = 512  # рассмотрим произвольные векторы размерности 512nb = 10000  # количество векторов в индексеnq = 5 # количество векторов в выборке для поискаnp.random.seed(228)vectors = np.random.random((nb, dim)).astype('float32')query = np.random.random((nq, dim)).astype('float32')

Создаем Flat индекс и добавляем векторы без обучения:

import faissindex = faiss.IndexFlatL2(dim)print(index.ntotal)  # пока индекс пустойindex.add(vectors)print(index.ntotal)  # теперь в нем 10 000 векторов

Теперь найдем 7 ближайших соседей для первых пяти векторов из vectors:

topn = 7D, I = index.search(vectors[:5], topn)  # Возвращает результат: Distances, Indicesprint(I)print(D)

Output
[[0 5662 6778 7738 6931 7809 7184] [1 5831 8039 2150 5426 4569 6325] [2 7348 2476 2048 5091 6322 3617] [3  791 3173 6323 8374 7273 5842] [4 6236 7548  746 6144 3906 5455]][[ 0.  71.53578  72.18823  72.74326  73.2243   73.333244 73.73317 ] [ 0.  67.604805 68.494774 68.84221  71.839905 72.084335 72.10817 ] [ 0.  66.717865 67.72709  69.63666  70.35903  70.933304 71.03237 ] [ 0.  68.26415  68.320595 68.82381  68.86328  69.12087  69.55179 ] [ 0.  72.03398  72.32417  73.00308  73.13054  73.76181  73.81281 ]]


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

D, I = index.search(query, topn) print(I)print(D)

Output
[[2467 2479 7260 6199 8640 2676 1767] [2623 8313 1500 7840 5031   52 6455] [1756 2405 1251 4136  812 6536  307] [3409 2930  539 8354 9573 6901 5692] [8032 4271 7761 6305 8929 4137 6480]][[73.14189  73.654526 73.89804  74.05615  74.11058  74.13567  74.443436] [71.830215 72.33813  72.973885 73.08897  73.27939  73.56996  73.72397 ] [67.49588  69.95635  70.88528  71.08078  71.715965 71.76285  72.1091  ] [69.11357  69.30089  70.83269  71.05977  71.3577   71.62457  71.72549 ] [69.46417  69.66577  70.47629  70.54611  70.57645  70.95326  71.032005]]


Теперь расстояния в первом столбце результатов не нулевые, так как векторов из query нет в индексе.

Индекс можно сохранить на диск и затем загрузить с диска:

faiss.write_index(index, "flat.index")index = faiss.read_index("flat.index")

Казалось бы, всё элементарно! Несколько строчек кода и мы уже получили структуру для поиска по векторам высокой размерности. Но такой индекс всего с десятком миллионов векторов размерности 512 будет весить около 20Гб и занимать при использовании столько же RAM.

В проекте для конференции мы использовали именно такой базовый подход с flat index, всё было замечательно благодаря относительно маленькому объему данных, однако сейчас речь идет о десятках и сотнях миллионов векторов высокой размерности!

Ускоряем поиск с помощью Inverted lists



Source

Основная и наикрутейшая особенность FAISS IVF index, или Inverted File index. Идея Inverted files лаконична, и красиво объясняется на пальцах:

Давайте представим себе гигантскую армию, состоящую из самых разношерстных воинов, численностью, скажем, в 1 000 000 человек. Командовать всей армией сразу будет невозможно. Как и принято в военном деле, нужно разделить нашу армию на подразделения. Давайте разделим на $\sqrt{1 000 000} = 1000$ примерно равных частей, выбрав на роли командиров по представителю из каждого подразделения. И постараемся отправить максимально похожих по характеру, происхождению, физическим данным и т.д. воинов в одно подразделение, а командира выберем таким, чтобы он максимально точно представлял свое подразделение был кем-то средним. В итоге наша задача свелась от командования миллионом воинов к командованию 1000-ю подразделениями через их командиров, и мы имеем отличное представление о составе нашей армии, так как знаем, что из себя представляют командиры.

В этом и состоит идея IVF индекса: сгруппируем большой набор векторов по частям с помощью алгоритма k-means, каждой части поставив в соответствие центроиду, вектор, являющийся выбранным центром для данного кластера. Поиск будем осуществлять через минимальное расстояние до центроид, и только потом искать минимальные расстояния среди векторов в том кластере, что соответствует данной центроиде. Взяв k равным $\sqrt{n}$, где $n$ количество векторов в индексе, мы получим оптимальный поиск на двух уровнях сначала среди $\sqrt{n}$ центроид, затем среди $\sqrt{n}$ векторов в каждом кластере. Поиск по сравнению с полным перебором ускоряется в разы, что решает одну из наших проблем при работе с множеством миллионов векторов.


Пространство векторов разбивается методом k-means на k кластеров. Каждому кластеру в соответствие ставится центроида

Пример кода:

dim = 512k = 1000  # количество командировquantiser = faiss.IndexFlatL2(dim) index = faiss.IndexIVFFlat(quantiser, dim, k)vectors = np.random.random((1000000, dim)).astype('float32')  # 1 000 000 воинов

А можно это записать куда более элегантно, воспользовавшись удобной штукой FAISS для построения индекса:

index = faiss.index_factory(dim, IVF1000,Flat)Запускаем обучение:print(index.is_trained)   # False.index.train(vectors)  # Train на нашем наборе векторов # Обучение завершено, но векторов в индексе пока нет, так что добавляем их в индекс:print(index.is_trained)  # Trueprint(index.ntotal)   # 0index.add(vectors)print(index.ntotal)   # 1000000

Рассмотрев такой тип индекса после Flat, мы решили одну из наших потенциальных проблем скорость поиска, которая становится в разы меньше по сравнению с полным перебором.

D, I = index.search(query, topn) print(I)print(D)

Output
[[19898 533106 641838 681301 602835 439794 331951] [654803 472683 538572 126357 288292 835974 308846] [588393 979151 708282 829598  50812 721369 944102] [796762 121483 432837 679921 691038 169755 701540] [980500 435793 906182 893115 439104 298988 676091]][[69.88127  71.64444  72.4655   72.54283  72.66737  72.71834  72.83057] [72.17552  72.28832  72.315926 72.43405  72.53974  72.664055 72.69495] [67.262115 69.46998  70.08826  70.41119  70.57278  70.62283  71.42067] [71.293045 71.6647   71.686615 71.915405 72.219505 72.28943  72.29849] [73.27072  73.96091  74.034706 74.062515 74.24464  74.51218  74.609695]]


Но есть одно но точность поиска, как и скорость, будет зависеть от количества посещаемых кластеров, которое можно задать с помощью параметра nprobe:

print(index.nprobe)  # 1  заходим только в один кластер и ведем поиск только в нёмindex.nprobe = 16  # Проходим по топ-16 центроид для поиска top-n ближайших соседейD, I = index.search(query, topn) print(I)print(D)

Output
[[ 28707 811973  12310 391153 574413  19898 552495] [540075 339549 884060 117178 878374 605968 201291] [588393 235712 123724 104489 277182 656948 662450] [983754 604268  54894 625338 199198  70698  73403] [862753 523459 766586 379550 324411 654206 871241]][[67.365585 67.38003  68.17187  68.4904   68.63618  69.88127  70.3822] [65.63759  67.67015  68.18429  68.45782  68.68973  68.82755  69.05] [67.262115 68.735535 68.83473  68.88733  68.95465  69.11365  69.33717] [67.32007  68.544685 68.60204  68.60275  68.68633  68.933334 69.17106] [70.573326 70.730286 70.78615  70.85502  71.467674 71.59512  71.909836]]


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

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

Ведем поиск по диску On Disk Inverted Lists


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

Конкретно для нашей задачи основное преимущество FAISS в возможности хранить Inverted Lists IVF индекса на диске, загружая в RAM только метаданные.

Как мы создаем такой индекс: обучаем indexIVF с нужными параметрами на максимально возможном объеме данных, который влезает в память, затем в обученный индекс по частям добавляем векторы (побывавшие в обучении и не только) и записываем на диск индекс для каждой из частей.

index = faiss.index_factory(512, ,IVF65536, Flat, faiss.METRIC_L2)

Обучение индекса на GPU осуществляем таким образом:

res = faiss.StandardGpuResources()index_ivf = faiss.extract_index_ivf(index)index_flat = faiss.IndexFlatL2(512)clustering_index = faiss.index_cpu_to_gpu(res, 0, index_flat)  #  0  номер GPUindex_ivf.clustering_index = clustering_index

faiss.index_cpu_to_gpu(res, 0, index_flat) можно заменить на faiss.index_cpu_to_all_gpus(index_flat), чтобы использовать все GPU вместе.

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

train_vectors = ...  # предварительно сформированный датасет для обученияindex.train(train_vectors)# Сохраняем пустой обученный индекс, содержащий только параметры:faiss.write_index(index, "trained_block.index") # Поочередно создаем новые индексы на основе обученного# Блоками добавляем в них части датасета:for bno in range(first_block, last_block+ 1):    block_vectors = vectors_parts[bno]    block_vectors_ids = vectors_parts_ids[bno]  # id векторов, если необходимо    index = faiss.read_index("trained_block.index")    index.add_with_ids(block_vectors, block_vectors_ids)    faiss.write_index(index, "block_{}.index".format(bno))

После этого объединяем все Inverted Lists воедино. Это возможно, так как каждый из блоков, по сути, является одним и тем же обученным индексом, просто с разными векторами внутри.

ivfs = []for bno in range(first_block, last_block+ 1):    index = faiss.read_index("block_{}.index".format(bno), faiss.IO_FLAG_MMAP)    ivfs.append(index.invlists)    # считать index и его inv_lists независимыми    # чтобы не потерять данные во время следующей итерации:    index.own_invlists = False# создаем финальный индекс:index = faiss.read_index("trained_block.index")# готовим финальные invlists# все invlists из блоков будут объединены в файл merged_index.ivfdatainvlists = faiss.OnDiskInvertedLists(index.nlist, index.code_size, "merged_index.ivfdata")ivf_vector = faiss.InvertedListsPtrVector() for ivf in ivfs:     ivf_vector.push_back(ivf)ntotal = invlists.merge_from(ivf_vector.data(), ivf_vector.size())index.ntotal = ntotal  # заменяем листы индекса на объединенныеindex.replace_invlists(invlists)  faiss.write_index(index, data_path + "populated.index")  # сохраняем всё на диск

Итог: теперь наш индекс это файлы populated.index и merged_blocks.ivfdata.

В populated.index записан первоначальный полный путь к файлу с Inverted Lists, поэтому, если путь к файлу ivfdata по какой-то причине изменится, при чтении индекса потребуется использовать флаг faiss.IO_FLAG_ONDISK_SAME_DIR, который позволяет искать ivfdata файл в той же директории, что и populated.index:

index = faiss.read_index('populated.index', faiss.IO_FLAG_ONDISK_SAME_DIR)

За основу был взят demo пример из Github проекта FAISS.

Мини-гайд по выбору индекса можно посмотреть в FAISS Wiki. Например, мы смогли поместить в RAM тренировочный датасет из 12 миллионов векторов, поэтому выбрали IVFFlat индекс на 262144 центроидах, чтобы затем масштабироваться до сотен миллионов. Также в гайде предлагается использовать индекс IVF262144_HNSW32, в котором принадлежность вектора к кластеру определяется по алгоритму HNSW с 32 ближайшими соседями (иными словами, используется quantizer IndexHNSWFlat), но, как нам показалось при дальнейших тестах, поиск по такому индексу менее точен. Кроме того, следует учитывать, что такой quantizer исключает возможность использования на GPU.

Спойлер:
Даже при использовании on disk inverted lists FAISS по возможности загружает данные в оперативную память. Так как RAM памяти на этапах тестов нам хватало, пусть и с трудом, а для масштабных тестов было необходимо иметь значительно больший запас данных здесь и сейчас, тесты на объемах свыше объема RAM не проводились. Но FAISS wiki и обсуждения данного подхода на Github говорят, что всё должно работать корректно.


Значительно уменьшаем использование дискового пространства с Product Quantization


Благодаря методу поиска с диска удалось снять нагрузку с RAM, но индекс с миллионом векторов всё равно занимал около 2 ГБ дискового пространства, а мы рассуждаем о возможности работы с миллиардами векторов, что потребовало бы более двух ТБ! Безусловно, объем не такой большой, если задаться целью и выделить дополнительное дисковое пространство, но нас это немного напрягало.

И тут приходит на помощь кодирование векторов, а именно Scalar Quantization (SQ) и Product Quantization (PQ). SQ кодирование каждой компоненты вектора n битами (обычно 8, 6 или 4 бит). Мы рассмотрим вариант PQ, ведь идея кодирования одной компоненты типа float32 восемью битами выглядит уж слишком удручающе с точки зрения потерь в точности. Хотя в некоторых случаях сжатие SQfp16 до типа float16 будет почти без потерь в точности.

Суть Product Quantization состоит в следующем: векторы размерности 512 разбиваются на n частей, каждая из которых кластеризуется по 256 возможным кластерам (1 байт), т.е. мы представляем вектор с помощью n байт, где n обычно не превосходит 64 в реализации FAISS. Но применяется такая квантизация не к самим векторам из датасета, а к разностям этих векторов и соответствующих им центроид, полученным на этапе генерации Inverted Lists! Выходит, что Inverted Lists будут представлять из себя кодированные наборы расстояний между векторами и их центроидами.

index = faiss.index_factory(dim, "IVF262144,PQ64", faiss.METRIC_L2)

Выходит, что теперь нам не обязательно хранить все векторы достаточно выделять n байт на вектор и 2048 байт на каждый вектор центроиды. В нашем случаем мы взяли $n = 64$, то есть $\frac{512}{64} = 8$ длина одного субвектора, который определяется в один из 256 кластеров.



При поиске по вектору x сначала обычным Flat квантайзером будут определяться ближайшие центроиды, а затем x так же разделяется на суб-векторы, каждый из которых кодируется номером одной из 256 соответствующей центроиды. И расстояние до вектора определяется как сумма из 64 расстояний между суб-векторами.

Что в итоге?


Мы остановили свои эксперименты на индексе IVF262144, PQ64, так как он полностью удовлетворил все наши нужды по скорости и точности поиска, а также обеспечил разумное использование дискового пространства при дальнейшем масштабировании индекса. Если говорить конкретнее, на данный момент при 315 миллионах векторов индекс занимает 22 Гб дискового пространства и около 3 Гб RAM при использовании.

Еще одна интересная деталь, которую мы не упоминали ранее, метрика, используемая индексом. По умолчанию расстояния между любыми двумя векторами считаются в евклидовой метрике L2, или более понятным языком, расстояния считаются как квадратный корень из суммы квадратов покоординатных разностей. Но задать метрику можно и другую, в частности, мы тестировали метрику METRIC_INNER_PRODUCT, или метрику косинусных расстояний между векторами. Косинусная она потому, что косинус угла между двумя векторами в Евклидовой системе координат выражается как отношение скалярного (покоординатного) произведения векторов к произведению их длин, а если все векторы в нашем пространстве имеют длину 1, то косинус угла будет в точности равен покоординатному произведению. В таком случае чем ближе расположены векторы в пространстве, тем ближе к единице будет их скалярное произведение.

Метрика L2 имеет непосредственный математический переход к метрике скалярных произведений. Однако при экспериментальном сравнении двух метрик сложилось впечатление, что метрика скалярных произведений помогает нам анализировать коэффициенты похожести изображений более удачным образом. К тому же эмбеддинги наших фотографий были получены с помощью InsightFace, в котором реализована архитектура ArcFace, использующая косинусные расстояния. Также есть и другие метрики в индексах FAISS, о которых можно почитать здесь.

пару слов о GPU
Обучение и использование индексов FAISS на GPU весьма ограничено в выборе параметров индекса, а при работе с гигантскими объемами данных высокой размерности использование если и будет возможным, то вызовет трудности, несопоставимые с полученным результатом. К тому же на GPU реализована только метрика L2.

Однако, стоит заметить, что для использования индекса с PQ квантилизацией на GPU требуется ограничить размер кода 56-ю байтами, либо в случае большего размера сменить float32 на float16, связано это с ограничениями на используемую память.

В итоге о FAISS на GPU мы думать перестали, потому что CPU реализация нас полностью устроила по скорости, и хотелось сохранить работу с метрикой скалярных произведений, что на GPU недоступно. Чтобы регулировать нагрузку на процессоры при работе с индексами, можно задать максимальное число используемых процессоров:

faiss.omp_set_num_threads(N)


Заключение и любопытные примеры


Итак, вернемся же к тому, с чего всё начиналось. А начиналось, напомним, с мотивации решить задачу поиска ботов в сети Instagram, а конкретнее искать дубликаты постов с людьми или аватарок в определенных множествах юзеров. В процессе написания материала стало понятно, что подробное описание нашей методологии поиска ботов тянет на отдельную статью, о чем мы расскажем в следующих публикациях, а пока ограничимся примерами наших экспериментов с FAISS.

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

Например, заручившись разрешением коллег и знакомых, мы загрузили в поиск их лица и быстро нашли фотографии, на которых они присутствуют:


Наш коллега попал на фотографию посетительницы Comic-Con, оказавшись на заднем фоне в толпе. Источник


Пикник в многочисленной компании друзей, фотография из аккаунта подруги. Источник


Просто проходили мимо. Неизвестный фотограф запечатлел ребят для своего тематического профиля. Они не знали, куда попала их фотография, а спустя 5 лет и вовсе забыли, как их фотографировали. Источник


В этом случае и фотограф неизвестен, и сфотографировали тайно!
Сразу вспомнилась подозрительная девушка с зеркальным фотоаппаратом, сидевшая в тот момент напротив:) Источник


Таким образом, путём нехитрых действий FAISS позволяет собрать на коленке аналог всем известного FindFace.

Другая интересная особенность: в индексе FAISS чем больше лица похожи друг на друга, тем ближе друг к другу расположены соответствующие им векторы в пространстве. Я решил повнимательнее изучить чуть менее точные результаты поиска по своему лицу и обнаружил до ужаса похожих на себя клонов:)


Некоторые из клонов автора.
Источники фото: 1, 2,3


Вообще говоря, FAISS открывает огромное поле для реализации каких-либо творческих идей. Например, по тому же принципу векторной близости похожих лиц можно было бы строить пути от одного лица к другому. Или в крайнем случае сделать из FAISS фабрику по производству подобных мемов:


Source

Благодарим за внимание и надеемся что этот материал будет полезен читателям Хабра!

Статья написана при поддержке моих коллег Артёма Королёва (korolevart), Тимура Кадырова и Арины Решетниковой.

R&D Dentsu Aegis Network Russia.
Подробнее..

Как и почему в InnoDB появились индексы на основе В-дерева

11.08.2020 10:19:42 | Автор: admin
Всем хорошо известно, что индексы на основе структуры данных В-дерево помогают нам быстрее читать и находить записи в таблицах. В сети можно найти огромное количество информации по этому поводу, но я постараюсь показать, с какими проблемами нам пришлось бы столкнуться без использования индексов на основе В-дерева, и почему выбрали эту структуру данных. И в качестве примера я возьму подсистему хранения InnoDB из MySQL.

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

image


Введение


В мире баз данных выделяют два самых распространенных способа хранения информации:

  1. На основе Log based-структур.
  2. На основе страниц.

Преимущество первого способа в том, что он позволяет просто и быстро читать и сохранять данные. Новую информацию можно записывать только в конец файла (последовательная запись), что обеспечивает высокую скорость записи. Этот способ используют такие базы, как Leveldb, Rocksdb, Cassandra.

При втором способе (на основе страниц) данные разделяются на части фиксированного размера и сохраняются на диск. Эти части и называют страницами или блоками. Они содержат записи (строки, кортежи) из таблиц.

Такой способ хранения данных используют MySQL, PostgreSQL, Oracle и другие. И поскольку мы говорим про индексы в MySQL, именно этот подход мы и рассмотрим.

Хранение данных в MySQL


Итак, все данные в MySQL сохраняются на диск в виде страниц. Размер страницы регулируется настройками базы данных и по умолчанию равен 16 Кб.

Каждая страница содержит в себе 38 байтов заголовков и 8-байтовое окончание (как показано на рисунке). А пространство, отведенное для хранения данных заполняется не полностью, потому что MySQL на каждой странице оставляет пустое место для будущих изменений.

Далее в расчетах мы будем пренебрегать служебной информацией, предполагая, что все 16 Кб страницы заполнены нашими данными. Мы не будем углубляться в организацию страниц InnoDB, это тема для отдельной статьи. Подробнее об этом вы можете почитать здесь.

image

Поскольку мы выше договорились, что индексы еще не существуют, то для примера создадим простую табличку без всяких индексов (на самом деле, MySQL все равно создаст индекс, но мы его не будем учитывать в расчетах):

CREATE TABLE `product` (`id` INT NOT NULL AUTO_INCREMENT,`name` CHAR(100) CHARACTER SET utf8 COLLATE utf8_general_ci NOT NULL,`category_id` INT NOT NULL,`price` INT NOT NULL,) ENGINE=InnoDB;


image

и выполним такой запрос:

SELECT * FROM product WHERE price = 1950;


MySQL откроет файл, где хранятся данные из таблицы product, и начнет перебирать все записи (строки) в поисках нужных, сравнивая поле price из каждой найденной строки со значением в запросе. Для наглядности я специально рассматриваю вариант с полным сканированием файла, так что случаи, когда MySQL получает данные из кэша, нам не подходят.

С какими же проблемами мы при этом можем столкнуться?

Жесткий диск


Так как у нас все хранится на жестком диске, давайте посмотрим на его устройство. Жесткий диск читает и пишет данные по секторам (блокам). Размер такого сектора может быть от 512 байтов до 8 Кб (в зависимости от диска). Несколько идущих подряд секторов могут объединяться в кластеры.

image

Размер кластера можно задать при форматировании/разметке диска, то есть это делается программно. Предположим, что размер сектора на диске равен 4 Кб, а файловая система размечена с размером кластера 16 Кб: один кластер состоит из четырех секторов. Как мы помним, MySQL по умолчанию хранит данные на диске страницами по 16 Кб, поэтому одна страница помещается в один кластер диска.

Давайте посчитаем, сколько пространства займет наша табличка с продуктами при условии, что в ней хранится 500 000 позиций. Мы имеем три четырехбайтных поля id, price и category_id. Условимся, что поле name у всех записей заполнено до конца (все 100 символов), и каждый символ занимает 3 байта. (3*4) + (100*3) = 312 байт столько весит одна строка нашей таблицы, и умножив это на 500 000 строк получим вес таблицы product 156 мегабайтов.

Таким образом, для хранения этой таблички необходимо 9750 кластеров на жестком диске (9750 страниц по 16 Кб).

При сохранении на диск берутся свободные кластеры, что приводит к размазыванию кластеров одной таблички (файла) по всему диску (это называют фрагментацией). Чтение таких случайно расположенных на диске блоков памяти называют случайным чтением (random read). Такое чтение получается медленнее, потому что требуется многократно перемещать головку жесткого диска. Чтобы считать весь файл, нам приходится прыгать по всему диску для получения нужных кластеров.

image

Вернемся к нашему SQL-запросу. Для нахождения всех строк серверу придется считать все 9750 кластеров, разбросанных по всему диску, при этом будет затрачено много времени на перемещение считывающей головки диска. Чем больше кластеров используют наши данные, тем медленнее будет осуществляться поиск по ним. И кроме того, наша операция забьет систему ввода/вывода операционной системы.

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

Сам себе велосипед


Как мы можем самостоятельно решить эту проблему?

Нужно придумать, как улучшить поиск по таблице product. Создадим еще одну таблицу, в которой будем хранить только поле price и ссылку на запись (область на диске) в нашей таблице product. Примем сразу за правило, что при добавлении данных в новую таблицу мы будем хранить цены в отсортированном виде.

image

Что нам это дает? Новая таблица, как и основная, хранится на диске постранично (блоками). В ней записаны цена и ссылка на основную таблицу. Давайте посчитаем, сколько места займет такая таблица. Цена занимает 4 байта, и пусть ссылка на основную таблицу (адрес) тоже будет размером 4 байта. Для 500 000 строк наша новая таблица будет весить всего 4 Мб. Тогда на одну страницу с данными поместится намного больше строк из новой таблицы, и потребуется меньше страниц для хранения всех наших цен.

Если для полной таблицы требуется 9750 кластеров на жестком диске (а в худшем случае это 9750 прыжков по жесткому диску), то новая таблица помещается всего на 250 кластеров. За счет этого многократно уменьшится количество использованных кластеров на диске, а значит и время, затраченное на случайное чтение. Даже если мы будем читать всю нашу новую табличку и сравнивать значения для поиска нужной цены, то в худшем случае понадобится 250 прыжков по кластерам новой таблицы. И после нахождения нужного адреса прочитаем еще один кластер, где лежат полные данные. Результат: 251 считывание против изначальных 9750. Разница существенная.

Помимо этого, для поиска по такой таблице можно воспользоваться, например, алгоритмом бинарного поиска (так как список отсортированный). Так мы еще больше сэкономим на количестве чтений и операциях сравнения.

Давайте назовем нашу вторую таблицу индексом.

Ура! Мы придумали свой собственный велосипед индекс!

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

Еще один индекс


А если создать еще один индекс над уже имеющимся?

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

image

Это еще уменьшит количество чтений. Одна строка нашего индекса занимает 8 байтов, то есть на одну 16-килобайтовую страницу мы можем вместить 2000 таких строк. Новый индекс будет содержать в себе ссылку на блок из 2000 строк первого индекса и цену, с которой этот блок начинается. Одна такая строка тоже занимает 8 байтов, но их количество резко уменьшается: вместо 500 000 всего 250. Они даже помещаются в один кластер жесткого диска. Таким образом, чтобы найти нужную цену мы сможем точно определить, в каком блоке из 2000 строк она находится. И в худшем случае, для нахождения все той же записи мы:

  1. Выполним одно чтение из нового индекса.
  2. Пробежав по 250 строкам найдем ссылку на блок данных из второго индекса.
  3. Считаем один кластер, в котором хранится 2000 строк с ценами и ссылками на основную таблицу.
  4. Проверив эти 2000 строк, найдем нужную и еще один раз прыгнем по диску, чтобы прочитать последний блок с данными.

Получим всего 3 прыжка по кластерам.

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

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

По похожему принципу работает структура данных B-дерево, поэтому ее выбрали для этих целей.

Коротко о В-деревьях


Чаще всего в MySQL используются индексы, упорядоченные на основе B-дерева (сбалансированное дерево поиска).

Общая идея В-дерева похожа на наши таблички индексов. Значения хранятся по порядку и все листья дерева находятся на одинаковом расстоянии от корня.

image

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

Сначала читается страница, в которой находится корень В-дерева. Далее по вхождению в диапазон ключей находится указатель на нужный дочерний узел. Читается страница дочернего узла, откуда по значению ключа берется ссылка на лист с данными, и по этой ссылке читается страница с данными.

В-дерево в InnoDB


Если быть точнее, то в InnoDB используется структура данных B+дерево (B+tree).

Каждый раз, создавая таблицу вы автоматически создаете В+дерево, потому что MySQL хранит такой индекс для первичного и вторичного ключей.

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

Кроме того, в В+деревьях используются дополнительные ссылки между дочерними узлами, что увеличивает скорость поиска по диапазону значений. Подробнее о структуре b+tree индексов в InnoDB читайте здесь.

Подводим итоги


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

Большая часть запросов к базе это как раз запросы на поиск информации по значению или по диапазону значений. Поэтому в MySQL самым часто используемым индексом является индекс на основе b-дерева.

Также, b-tree индекс помогает при получении данных. Так как в листьях индекса хранятся первичный ключ (кластерный индекс) и само значение колонки, по которой построен некластерный индекс (вторичный ключ), то за этими данными можно уже не обращаться к основной таблице и брать их из индекса. Это называется покрывающим индексом. Подробнее о кластерных и некластерных индексах можно найти в этой статье.

Индексы, как и таблицы, тоже хранятся на диске и занимают место. При каждом добавлении информации в таблицу индекс нужно поддерживать в актуальном состоянии, следить за правильностью всех ссылок между узлами. Это создает накладные расходы при записи информации, что является основным недостатком индексов на основе b-дерева. Мы жертвуем скоростью записи для увеличения скорости чтения.

Список используемой литературы


Подробнее..

Категории

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

  • Имя: Макс
    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