Децентрализованный поиск для свободного веба26.09.2022 22:16

64a6d7b97b085ee303df314702cd7668.png

Возможно ли создать поисковую систему, которую на практике нельзя подвергнуть цензуре, влиянию и блокировке?

Говоря техническим языком, возможно ли выполнять полнотекстовый поиск не имея удаленного сервера, удобным для пользователя способом, одновременно храня поисковый индекс в peer-to-peer системе и имея возможность быстро обновлять поисковый индекс?

Да, это возможно!

Существует редкий класс баз данных — peer-to-peer БД. Такие базы проигрывают по большинству параметров обычным БД и используются скорее для экспериментов.

В качестве примера p2p базы данных можно привести Orbit DB. Orbit DB действительно закрывает часть потребностей пользователей обычных БД: в нем реализованы счетчики, append log и KV-хранилище. И все же этого недостаточно для создания полноценных dWeb приложений.

По запросу Distributed Serverless Search найти в Интернете мне ничего не удалось. И раз полнотекстового поиска для dWeb нет, то мы его создадим.

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

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

Поисковый движок

В 2017 году бывший сотрудник Google опубликовал первую версию Tantivy, поискового движка написанного на Rust. Архитектурно Tantivy похож на Lucene, однако работает быстрее и имеет меньшую кодовую базу.

Рядом с Tantivy чуть больше года назад я начал пилить сервер Summa. Изначально Summa добавляла в Tantivy GRPC API для поиска и индексации, возможность индексации из топиков Kafka, язык fasteval2 для описания функций ранжирования и некоторые дополнительные функции поиска.

Подробное описание устройства поиска есть в моей более ранней статье, здесь же приведу лишь самые важные для распределенного поиска свойства Tantivy/Summa:

  • Производительность: уже на тот момент связка работала сильно быстрее Lucene/ES

  • Иммутабельность данных: после выполнения коммита данные сохраняются в набор файлов, называемых сегментом и далее они не изменяются.

    Следующий commit сохраняет новую порцию данных в новые файлы, а факт удаления строки сохранится как бит в битовой маске рядом с уже существующим сегментом. Обновление данных реализуется как DELETE + INSERT, и потому сам сегмент остается неизменным при любых операциях с данными кроме выполнения компакшена (merge в терминах Tantivy).

  • Локальность запросов: поиск по всей базе данных требует считывания малого количества данных с диска.

Высокая локальность ведет к меньшему количеству чтений с диска. Плохая локальность — основная проблема, не позволяющая просто взять и запустить произвольную БД поверх p2p-системы или сетевой файловой системы. Произвольные чтения перегружают сеть и просто добивают её при сколько-нибудь значимой нагрузке. Комбинируя определенные подходы, в Tantivy получилось достичь высокой локальности для всех компонент поискового индекса.

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

Локальность словаря термов

Словарь термов — это простой KV-storage, где ключ — слово, а значение — указатель на список документов с этим словом (постинг-лист). KVs для поиска термов должен быть относительно быстрым и сериализуемым на диск. В Tantivy в качестве KVs использовались Finite State Transducers из библиотеки fst.

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

Как почетный велосипедостроитель я быстро закостылил это сам заменой KVs на более локальную структуру данных для экспериментов, а спустя несколько месяцев в Tantivy была добавлена реализация KVs на Sorted String Tables (ssTable).

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

Локальность постинг-листа и хранилища документов

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

Достаточно прогрузить в память скип-листы (1 хоп по памяти) и дальше за log (n) от размера мы прыгаем по листам и хранилищу в поисках нужных нам документов. Tantivy из коробки дает еще и поблочное сжатие постинг-листов, что положительно влияет на локальность.

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

HotCache

Создатель Tantivy спустя пару лет разработки нащупал бизнес-модель и создал Quickwit — поисковик, хранящий поисковые сегменты на Amazon S3. Для меня это оказалось хорошей новостью, так как сеть и хранение индекса в удаленном хранилище теперь стали фичами первого класса в Tantivy.

Довольно скоро после этого в Tantivy появился HotCache — структура данных для быстрого открытия удаленного поискового индекса на чтение.

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

Последующие тесты показали, что на ~10GB индексе HotCache занимает порядка 10MB, а запросы по высокочастотным термам потребляют по 400–500KB. Пагинация по запросу далее подъедает по 100–150KB на SERP из 10 документов. Это замечательный результат, означающий, что за среднюю поисковую сессию в 6 запросов пользователь совершит чтений на 3–4MB без учета HotCache, заранее загружаемого в память.

IPFS

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

IPFS — это BitTorrent, но с человеческим лицом. В основе IPFS лежит Kademlia, реализован неплохой десктопный клиент, плагины для Chrome/Firefox, а внутри системы уже много узлов.

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

IPFS обладает важными для нас особенностями:

  • IPFS режет файлы на кусочки по N байт и хранит в IPFS уже отдельные кусочки, соединенные DAGом. Обращаться к кусочкам можно по отдельности, таким образом если вам нужны лишь определенные байты из файла то достаточно скачать лишь кусочки, содержащие эти байты

  • IPFS из коробки имеет удобную концепцию директорий и клиент IPFS напрямую поддерживает публикацию локальных директорий в IPFS. Что не менее важно, если две директории имеют общие файлы, то скачивая обе директории, вы не будете скачивать все по два раза. Общие файлы будут скачены только один раз.

  • Рядом с IPFS идет IPNS — DNS для IPFS. Любой узел сети IPFS может опубликовать любой файл или директорию под неизменным именем на основе пары ключей и впоследствии выполнять перепубликацию с тем же именем. Это имя может быть разрезолвлено на любом другом узле IPFS.

  • Пользователи сами становятся сидерами при получение куска данных. Хотя, как и в BitTorrent, здесь можно отключить раздачу, на практике в IPFS пользователи этого не делают и продолжают раздавать скаченные блоки

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

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

WASM

Можно было бы сказать, что WASM является одним из многих форматов байт-кода, таким же как LLVM, JVM и десятки других. Но есть у него одна особенность — программу на WASM можно выполнить в браузере.

Разработка WASM началась в 2015 году и спустя несколько лет появились первые рабочие прототипы в популярных браузерах. Уязвимости Meltdown и Spectre притормозили на несколько лет развитие WASM, но последнее время вокруг него опять наблюдается все больше и больше активности.

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

Звезды и здесь сошлись: в мире Rust существует проект wasm-bindgen. Этот тулинг позволяет собрать программу на Rust в WASM, снабдить ее JavaScript-биндингами и получить на выходе модуль, который можно импортировать и использовать в внутри браузера.

Первые попытки запустить поисковый движок Summa внутри браузера в начале лета 2022 года не увенчались успехом. Браузерный JS исполняется Event Loop’ом по одной таске за раз в один поток, поэтому наивная попытка скомпилировать движок и запустить его в Chrome провалилась же на первом растовом Mutex’e.

Wasm-bindgen был все же еще относительно сырым, а гигантские стектрейсы и черти где разыменованные указатели на некоторое время выбили почву у меня из под ног и идея была отложена в стол. Тем более опыта на Rust на тот момент было с гулькин нос, а JavaScript я всеми силами старался избегать, как вы уже поняли.

Однако иногда упоротая одержимость идеями может брать верх. В сентябре я провел десяток дней за красноглазым курением мануалов wasm-bindgen и его флагов. Я читал треды на GitHub Issues перед сном и выяснял почему флаги компиляции работают через жопу. В приступах помутнения я пытался обмануть компилятор, расставляя unsafe и создавая тут и там примитивы синхронизации в надежде, что хоть в этот раз компилятор расслабиться, отвлечется и пропустит мой код. Каждый раз все кончалось ошибками памяти.

В приступах прокрастинации я натыкался на треды в Интернете, где мои предшественники пытались запустить что-то сложное на Rust внутри браузера. Эти треды были усеяны черепами и предупреждающими надписями.

В конце концов я распилил зависимости Summa и переложил вагоны JSONов. Слой похода за файлами на диск был заменен на слой, делающий HTTP-Range запросы за файлами.

Ежеминутные проклятия в адрес JavaScript по поводу отсутствующей типизации и семиэтажный мат на жуткий мультитрединг браузера, смехотворно названный Web Worker API, распугали всех моих домашних. Но неделю назад мне таки удалось запихнуть поисковый движок в этот чертов браузер. В тот вечер в голове опрокинулся маленький бочонок с эндорфинами.

Результат страданий — NPM модуль summa-wasm, содержащий tantivy и модуль summa-core (парсер запросов, токензайзеры и рутины для работы с индексом). Библиотека принимает описание того, как ей достучаться до файлов поискового индекса по сети. В ответ она даст вам функцию search, способную выполнить полнотекстовый поиск.

Соединяем все вместе

Возможно, вы уже догадались как все должно работать. Исходный код веб-интерфейса, summa и summa-wasm опубликован на GitHub, здесь же я разберу ключевые моменты. Более полноценная документация живет на https://izihawa.github.io, но так как проект я пилю в одно жало и в свободное время, то скорее всего что-нибудь да пропустил. Пишите мне в личку, если будут баги сборки или дыры в документации.

Сборка поискового индекса

Для сборки индекса я буду использовать сервер Summa, но summa-wasm также способен открыть и обычный индекс Tantivy. В Summa реализованы функции, снижающие объемы сетевых обновлений через управление политикой слияния сегментов. Я послал соответствующие патчи в апстрим Tantivy, но гарантий что их примут нет, так что лучше сразу берите в руки Summa.

Кроме Summa я запилил на Python асинхронный клиент aiosumma, который будет использован в примерах дальше. Поехали! 

# Установим клиент `aiosumma` на Python для выполнения запросов к summa
pip3 install -U aiosumma

# Создадим директорию для индекса
mkdir data

# Сгенерируем конфиг для Summa
docker run izihawa/summa-server:testing generate-config -d /data \
-g 0.0.0.0:8082 -m 0.0.0.0:8084 -i host.docker.internal:5001 > summa.yaml

# И запустим Summa
docker run -v $(pwd)/summa.yaml:/summa.yaml -v $(pwd)/data:/data \
-p 8082:8082 -p 8084:8084 \
izihawa/summa-server:testing serve /summa.yaml

Дальше берем публично доступный дамп базы данных Wiki Books. Можете зарядить туда свои данные, предварительно нарисовав схему данных по аналогии.

Создание схемы

# Download sample dataset
CURRENT_DUMP=$(curl -s -L "https://dumps.wikimedia.org/other/cirrussearch/current" | grep -oh '\"enwikibooks.*\content.json\.gz\"' | tr -d '"')
wget "https://dumps.wikimedia.org/other/cirrussearch/current/$CURRENT_DUMP" -O enwikibooks.json.gz
gunzip enwikibooks.json.gz

# Create index schema in file
cat << EOF > schema.yaml
---
# yamllint disable rule:key-ordering
index_name: page
compression: Zstd
multi_fields: ["category"]
default_fields: ["opening_text", "title", "text"]
writer_heap_size_bytes: 1073741824
writer_threads: 4
schema: >
  - name: category
    type: text
    options:
      indexing:
        fieldnorms: true
        record: position
        tokenizer: default
      stored: true
  - name: content_model
    type: text
    options:
      indexing:
        fieldnorms: true
        record: basic
        tokenizer: default
      stored: true
  - name: opening_text
    type: text
    options:
      indexing:
        fieldnorms: true
        record: position
        tokenizer: default
      stored: true
  - name: auxiliary_text
    type: text
    options:
      indexing:
        fieldnorms: true
        record: position
        tokenizer: default
      stored: true
  - name: language
    type: text
    options:
      indexing:
        fieldnorms: true
        record: basic
        tokenizer: default
      stored: true
  - name: title
    type: text
    options:
      indexing:
        fieldnorms: true
        record: position
        tokenizer: default
      stored: true
  - name: text
    type: text
    options:
      indexing:
        fieldnorms: true
        record: position
        tokenizer: default
      stored: true
  - name: timestamp
    type: date
    options:
      fast: single
      fieldnorms: false
      indexed: true
      stored: true
  - name: create_timestamp
    type: date
    options:
      fast: single
      fieldnorms: false
      indexed: true
      stored: true
  - name: popularity_score
    type: f64
    options:
      fast: single
      fieldnorms: false
      indexed: true
      stored: true
  - name: incoming_links
    type: u64
    options:
      fast: single
      fieldnorms: false
      indexed: true
      stored: true
  - name: namespace
    type: u64
    options:
      fast: single
      fieldnorms: false
      indexed: true
      stored: true

EOF

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

# Создаем индекс из схемы
summa-cli localhost:8082 - create-index-from-file schema.yaml

# Грузим каждую 4-ую строку. В исходном дампе половина строк технические, их нужно выкинуть
# Наливка индекса займет некоторое время
awk 'NR%4==0' enwikibooks.json | summa-cli localhost:8082 - index-document-stream page

# Коммит
summa-cli localhost:8082 - commit-index page --commit-mode Sync

Проверим работает ли обычный поиск: 

summa-cli localhost:8082 - search page '{"match": {"value": "astronomy"}}' '[{"top_docs": {"limit": 10}}, {"count": {}}]'

Публикация индекса в IPFS

Для публикации индекса в IPFS необходимо установить IPFS.

После запуска демона IPFS выполним публикацию с копированием файлов внутрь IPFS. Summa также поддерживает --no-copy режим, но из-за ограничений IPFS нужны некоторые приседания, которые здесь хотелось бы опустить.

summa-cli localhost:8082 - publish-index page --copy

В ответ должно вернуться что-то типа

{
  "key": {
    "name": "page",
    "id": "k51qzi5uqu5dg9kaxpau2an7ae09yl4yrgna5x8uunvwn5wy27tr7r8uddxn72"
  }
}

Для индекса с именем page сервер создал в IPFS пару ключей с именем page и опубликовал индекс в IPNS. Готово, в IPFS выложен поисковый индекс, который тебе может скачать кто угодно.

Сборка веб-интерфейса для поискового индекса

Репозиторий Summa имеет демонстрационный веб-интерфейс. Интерфейс не претендует на функциональность и служит лишь иллюстрацией того, как использовать модуль summa-wasm. Но лучше все-таки посмотреть на него одним глазом — подводных камней я собрал немеренно.

Для использования локального демона IPFS из веб-интерфейса необходимо настроить CORS-заголовки в IPFS. От этого шага возможно будет избавиться после патчей в IPFS, которые добавят в HTTP интерфейс демона нужную функциональность и позволят браузеру ходить в Same Domain, а не в отдельное API на другом порту.

Но пока нужные функции IPFS существуют только в выделенном IPFS API приходится выполнять эти приседания с настройкой демона. 

# Патчим CORS
# Данные разрешения слишком широкие и возможно вам необходимо будет их настроить под себя
ipfs config --json API.HTTPHeaders.Access-Control-Allow-Origin '["*"]'
ipfs config --json API.HTTPHeaders.Access-Control-Allow-Methods '["GET", "POST"]'

Затем собираем и запускаем веб-интерфейс. Если захотите собрать интерфейс со своим индексом, то поменяйте IPNS имя на то, которое вы получили в предыдущем пункте

git clone https://github.com/izihawa/summa
cd summa/summa-web
npm i && npm run dev

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

Обновление данных

Мы можем долить данные в индекс

awk 'NR%4==2' enwikibooks.json | summa-cli localhost:8082 - index-document-stream page
summa-cli localhost:8082 - commit-index page --commit-mode Sync

и после этого заново опубликовать индекс

summa-cli localhost:8082 - publish-index page --copy

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

Для примера я собрал и выложил подобную страницу, можете проверить как это работает тут, предварительно установив IPFS Companion.

Зачем все это?

Реализация поиска поверх IPFS обладает несомненными плюсами.

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

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

  • Индекс надежно сохраняется на неопределенное время до тех пор, пока есть его пользователи. В мире существуют наборы данных, которые стоило бы сохранять по-лучше — образовательные видео, научные публикации, книги, исходные коды открытого ПО. IPFS и до существования Summa решал эту задач, однако теперь стало возможно организовать поиск по сохраненному точно таким же децентрализованным способом.

Возможно, это ещё одна разработка в стол. Возможно, нет. Но если вам есть что сохранить или есть что-то, что нужно спрятать от Левиафана, то теперь вы знаете как сделать поиск для этого.

© Habrahabr.ru