Latest posts
Daria’s room
15 Sept, 18:16edited
Автоматическое сжатие на клиенте vs ручное на сервереСтандартный клиент http.Transport сам добавляет в запрос Accept-Encoding: gzip и, если сервер отвечает с Content-Encoding: gzip, клиент сам распакует ответ. Но только пока Accept-Encoding не выставлен вручную. Если клиент сам задаёт этот заголовок (случайно либо намеренно с указанием другого алгоритма типа zstd) логику распаковки тоже надо писать самому. Подробнее прямо описано в доке net/httpИнтересно, что на сервере симметричной автоматики нет. http.Server сам ответы не сжимает - и это довольно логично: но стороне сервера eщё нужно решить, стоит ли вообще сжимать конкретный ответ. Все таки сжатие переносит часть стоимости с сети на cpu: сервер и клиент тратят проц на переупаковки в обмен на уменьшение объёма передаваемых по сети данных.Поэтому для тех, кому экономия на сжатии превышает доп вычисления, будет полезно обернутьDaria’s room
5 Sept, 12:54
Причина перекосов в уровне балансировкиL4-балансировщик выбирает серверную ноду при создании соединения. После этого net/http может долго переиспользовать то же соединение через keep-alive - и все следующие запросы продолжат идти на уже выбранную ноду без участия L4.В некоторых сценариях такое переиспользование приводит к перекосу нагрузки. Проблема далеко не новая, но я хочу разобрать отдельные решения подробнее. В чем, собственно, проблема:Для http 1.x свободные соединения внутри net/http пакета в http.Transport переиспользуются по LIFO: логично, что нам выгоднее взять последнее освободившееся. Это видно в реализации http.Transport.queueForIdleConn и в самой модели http.Transport:type Transport struct { /// idleConn map[connectMethodKey][]persistConn // most recently used at end ///В отдельных кейсах типо #79664, если одна из нод отвечает немного медленнее остальных, её
Daria’s room
28 Aug, 14:02edited
Итераторы…TL;DR: в iter.Seq итератор сам передаёт следующие элементы в код внутри range, а через yield получает сигнал и решает, продолжать ли обход. Ошибку можно передавать вторым значением через Seq2[T, error], но тогда, если она должна дойти до конца цепочки, все промежуточные итераторы тоже должны уметь её принять и передать дальше, даже если она им не нужна (!). Стоит ли оно такой запары?Вспомним обычный обход:for i := 0; i < source.Len(); i++ { process(source.Get(i)) }Это типичная pull-модель: внешний код сам сначала вытаскивает значение из источника Get(i), а потом передаёт его в бизнес-логику process.Обратный вариант - обход с callback функцией:source.Scan(func(v Value) bool { process(v) // принимает то, что будет попадать из цикла ниже return true })func (s Source) Scan(process func(Value) bool) {GitHubproposal: slices: add CollectError · Issue #70631 · golang/goProposal Details Idiomatic go functions are often in the form func (...) (T, err). When creating iterators, it is equally common for the underlying functions to potentially return an error as each ...Daria’s room
17 Aug, 17:02edited
Что на самом деле нужно сохранять при сериализации сложной структуры?TL;DR: Важно отделить логические данные от производного состояния: часть структур можно восстановить после загрузки, а часть - вообще заменить другим физическим представлением под нужный сценарий.Вспомним хотя бы слайс: само значение - это дескриптор с указателем на нижележащий массив, len и cap. После рестарта старого расположения памяти всё равно не будет: появится новый массив и новый дескриптор. То же самое относится к lookup-таблицам, оффсетам, кешу и другим производным структурам, которые существуют ради удобной работы с данными в рантайме.Поэтому в вопросе сохранения структур для дальнейшего переиспользования можно отделить основные данные от производного состояния: сохранить то, что нельзя потерять, а всё, что однозначно выводится из данных, построить заново после загрузки.В инвертированном индексеTelegramDaria’s roomЗапечатываю крупную структуру индекса в бинарь через mmap, uvarint и delta encoding Сложно сказать, в какой момент FTS индекс превратился в большой набор гошных структур, но это надо было как то решать, тк восстанавливать весь индекс каждый раз при старте…Daria’s room
13 Aug, 16:03edited
Привет!Вас стало больше, так что пора наконец представиться 🙂 Я Даша, давно пишу на Go, но на своем тернистом пути постоянно нахожу интересности во внутренностях языка. Пишу про производительность, работу с бд и свои наблюдения, которыми грех не поделится. Параллельно развиваю свой поисковый движок FTS engine (который в народе прозвали Fast Turtle Search): https://github.com/dariasmyr/fts-engineИз-за него тут регулярно появляются посты про full-text search, индексы, фильтры, хранение данных и разные эксперименты вокруг темы поисковиков.Пока тут легкий хаос с темами: от рабочих кейсов до иногда странных углублений в исходники и ищьюс ;’) Чтобы во всём этом было чуть проще ориентироваться, я разметила посты тегами:#go - Go, рантайм, реализации техник и описание внутрянки #perf - производительность, профилирование и бенчи #db - базы данных, оптимизации #fts - поиск, индексы иGitHubGitHub - dariasmyr/fts-engine: Modular full-text search engine in Go with pluggable indexes, filters, and customizable text processing…Modular full-text search engine in Go with pluggable indexes, filters, and customizable text processing pipelines. You can instantly index your docs (radix, HAMT), apply probabilistic filters, and ...Daria’s room
12 Aug, 17:08edited
HNSW: как устроен графовый индекс для векторного поискаOne million years later, я наконец добралась до прикручивания в проект семантического поиска.Тащить ради этого отдельную векторную бд максимально не хотелось, поэтому решила пойти классическим путем - попробовать встроить индекс HNSW прямо в движок наравне с остальными индексами.Если кратко, HNSW - это графовый индекс для approximate nearest neighbor поиска по векторам. Вместо того чтобы сравнивать запрос со всеми векторами в индексе, HNSW заранее связывает близкие векторы в многоуровневый граф, а во время поиска двигается по этим связям в сторону все более похожих кандидатов.Как обычно, решила разобраться, как HNSW вообще работает:1. зачем графу несколько уровней; 2. как выбирается entry point; 3. почему сверху greedy поиск, который расширяется на ниженем уровне; 4. что делают параметры M, efSearch и efConstruction; 5. поч
Daria’s room
9 Aug, 22:19edited
Недавно @dmedovich добавил в движок flat inverted index под данные с высокой кардинальностью и даже написал отдельную статью про его устройство и оптимизации. Мое дело, конечно, найти, что из этого имеет смысл перенести в мои существующие индексаторы HAMT/radix. Потому что заинтересовала меня не столько хешмапа, на которой строится индекс, сколько обвязка вокруг нее.Начала с простого: fast append для списка документов.У каждого слова есть список доков, где оно содержится (postings). Эти postings отсортированы по внутреннему числовому индексу документа (ordinal). При обычной индексации ordinal почти всегда инкрементится по возврастанию: 1, 2, 4, 7, 8...Ранее для вставки, например, документа с ordinal 6, требовалось проходится бин поиском по всему срезу ordinals для поиска индекса между 4 и 7. Но в типичном случае новый ordinal просто больше последнего, поэтому сначала можноDaniil MedovichПлоский инвертированный индекс для данных высокой кардинальностиКак общая arena для байтов, inline-postings, ленивое хранение позиций и компактный порядок термов помогают изменяемому индексу работать с высокой кардинальностью.Daria’s room
26 Jul, 15:09edited
Отделяем текстовый скоринг от продуктового ранжированияКак оказалось, научить поисковый движок находить релевантные документы = только половина задачи. Следующий вопрос в том, какие из найденных совпадений важнее для конкретного продукта.Окей, движок уже умеeт строить индексы по нескольким полям (title, abstract и т.д.) и поддерживает разные типы поиска: например term, phrase, prefix, фразовый поиск. Но после поиска вклад каждого совпадения просто добавлялся в итоговый вес документа. Например, для запросаtitle:diabetes abstract:"type 1" abstract:insulin мы находили три независимых совпадения:• term - diabetes в title; • phrase - "type 1" в abstract; • prefix - insulin в abstract.Для каждого совпадения BM25 считал свой вес, после чего все веса просто суммировались:BM25 total doc score = BM25(title:diabetes) + BM25(abstract:"type 1") + BM25(abstract:insulin)Базово текстовая
Daria’s room
26 Jun, 00:37edited
Почему коннекты растут быстрее, чем RPS Недавно разбирала кейс: в pgx пуле резко выросло количество соединений, условно с 10 до 80. Но RPS вырос совсем немного, поэтому объяснение типа "стало больше запросов, значит нужно больше коннектов" не совсем сходилось.Daria’s room
23 Jun, 23:18edited
Почему коннекты растут быстрее, чем RPSНедавно разбирала кейс: в pgx пуле резко выросло количество соединений, условно с 10 до 80. Но RPS вырос совсем немного, поэтому объяснение типа "стало больше запросов, значит нужно больше коннектов" не совсем сходилось.Потому что количество занятых коннектов зависит не только от того, сколько запросов приходит, но и от того, как долго каждый запрос удерживает соединение (находится в состояния acquired) внутри пула:busy concurrent connections ≈ RPS × connection hold (acquired) timeНапример, имея 100 RPS и 100 ms времени удержания коннекта мы получим 10 одновременно занятых коннектов.А если RPS вырос до 160, но коннект из-за внутренней задержки стал удерживаться 500 ms, то получается: 160 RPS × 500 ms = 80 одновременно занятых коннектовВ итоге пул выглядит так, будто нагрузка выросла в 8 раз, хотя RPS не сильно вырос.Главное, что нужноDaria’s room
15 Jun, 17:38
Пришло время наконец-то сравнить, как выглядит fts рядом с другими полнотекстовыми движками.Ранее я писала серии постов с разборами работы индексаторов radix и HAMT, но остался вопрос, что это даёт на реальных поисковых сценариях.Поэтому я собрала небольшой benchmark suite в виде отдельного подпроекта и прогнала свой fts рядом с другими гошными индексаторами bleve (не смейтесь) и blue на нескольких типах запросов:term — поиск одного слова and — несколько обязательных слов or — несколько альтернативных слов phrase — точная фраза prefix — поиск по началу словаМеня интересовало конкретно: время билда, размер индекса, время поиска, QPS и основные метрики качества выдачи: Recall@k, nDCG@k, MRR.RadixRadix-индексатор ожидаемо оказался очень сильным на prefix запросах за счет хранения ключей через общие префиксы - поэтому для него это почти нативный сценарий. В цифрах это примерно
Daria’s room
28 May, 00:24edited
Запечатываю крупную структуру индекса в бинарь через mmap, uvarint и delta encodingСложно сказать, в какой момент FTS индекс превратился в большой набор гошных структур, но это надо было как то решать, тк восстанавливать весь индекс каждый раз при старте стало не очень.Что если вынести часть индекса из памяти на диск как отдельный immutable segment - компактный бинарный файл со своим форматом, который собирается один раз, больше не меняется (для определенных кейсов это подходит) и используется только при чтении.И вот как может выглядеть структура для файла сегмента:[header][postings area][positions area][term index][footer]header хранит сигнатуру формата и версию, postings area - списки postings, positions area - позиции токенов, term index - оффсеты до данных конкретного терма, а footer помогает при чтении быстро найти term index в конце файла.Структура пригодится нам вGitHubfts-engine/pkg/segment at index-optimisation · dariasmyr/fts-engineModular full-text search engine in Go with pluggable indexes, filters, and customizable text processing pipelines. You can instantly index your docs (radix, HAMT), apply probabilistic filters, and ...Daria’s room
22 May, 21:46edited
Tombstones и логическое удалениеОдна из вещей, с которыми рано или поздно придется столкнуться в процессе работы с индексером, это удаление документов.Представим, что у нас есть внутренний реестр документов:idToOrd: { "docA":0, "docB":1, "docC":2 }ordToID: [ "docA", "docB", "docC" ]Daria’s room
10 May, 22:02edited
"Explain" plan для FTSЗаметила, что по мере усложнения поискового пайплайна метрика вроде p95 latency стала недостаточной. На одном из последних бенчей время ответа выросло на 30%, но по одной этой цифре невозможно понять, где именно возникла задержка, так как она может проявится как в разборе запроса, отборе кандидатов или ранжировании так и в попытке попасть в fast path.Снаружи поиск выглядит как один вызов, но внутри мы выбираем разные стратегии в зависимости от семантики запроса. Поэтому даже похожие запросы могут выполняться по разному:+postgres +wal "postgres wal" title:postgresОни по-разному парсятся в AST и дальше попадают в разные стратегии выполнения.Поиск по одному слову обычно прост: достаточно нормализовать токен, найти его в индексе и прочитать список документов. Стоимость здесь в основном зависит от количества кандидатов (postings list).Поиск фразы дороже:
Daria’s room
6 May, 15:03edited
Weak AND: как скипать документы без точного scoringМного пропадаю, потому что занимаюсь апдейтом движка: поиск по множеству полей, скоринг по TF-IDF/BM25, новый пайплайн парсинга запроса по AST и тд.Одна из таких оптимизаций - WAND (Weak AND). Она используется в ранжированных поисковых системах, когда нужно быстро получить top-k результатов и не тратить время на документы, которые уже точно не попадут в результат.Представим обычный OR-запрос, например alpha beta gamma, где пользователю нужны не все совпадения, а только top-10 документов.Наивно можно было бы собрать все документы, где встретилось хотя бы одно слово, посчитать итоговый score для каждого, отсортировать результаты и взять первые 10. Это корректно, но дорого: score считается даже для документов, которые все равно не попадут в top-k.WAND позволяет не считать точный score для каждого кандидата сразу, а рано отсеиватьGitHubfts-engine/pkg/fts/wand.go at index-optimisation · dariasmyr/fts-engineModular full-text search engine in Go with pluggable indexes, filters, and customizable text processing pipelines. You can instantly index your docs (radix, HAMT), apply probabilistic filters, and ...Daria’s room
19 Apr, 20:18edited
Погружение в тему индексов и фильтров точно было не зря...Помните, я писала про append-only хранилище логов и трейсов Amber?Чтобы нажать на trace_id и сразу увидеть весь путь запроса между сервисами и логи по каждому шагу. Где используется один бинарь без JVM и без сборки данных по разным инструментам.Так вот я очень рада, что в пайплайн поиска по сегментам так хорошо зашел фильтр и индексатор из FTS-движка (получивший ироничное кодовое название Fast Turtle Search) с которыми поиск одного UUID-подобного токена по body среди 100млн записей занял 49 мс.А сам архитектурный приём, который дал такой результат - это правильно выстроенный механизм сегментированного поиска, который работает через последовательное сужение выборки. Я уже писала ранее верхнеуровнево, в чем идея, но тут немного опишу детали:1. Sparse по метаданным отсекает сегменты вне нужного временного диапазона. 2. Даль
Daria’s room
29 Mar, 12:29edited
Ribbon Filter: Part 2 - построение фильтра через elimination и back substitutionВ первой части мы разобрались, что Ribbon не хранит элементы напрямую, а кодирует весь набор ключей как систему XOR-уравнений внутри массива cells.Остается вопрос: как именно мы получаем значения в cells, чтобы все эти уравнения выполнялись?Сборка фильтра происходит внутри BuildFromKeyStream и делится на 2 этапах: 1. elimination - упрощение XOR уравнений через исключение одинаковых переменных 2. back substitution - вычисление неизвестных значений cells через те, которые стали известными после eliminationКак работает eliminationРанее разбирали, что поиск в Ribbon реализуется за счет решения XOR уравнения с fingerprint ключа и значениями в cells внутри окна. Fingerprint нам известен на этапе поиска, поэтому при построении фильтра надо определить, что будет в cellsАлгоритм сборки в BuildFromKeyStream
Daria’s room
29 Mar, 09:15edited
Ribbon Filter: Part 1 - сжатая альтернатива Bloom и CuckooRibbon filter - это, пожалуй, один из самых недооцененных фильтров, который меньше по памяти чем Bloom, и в моих тестах показал более низкий false positive rate, чем Cuckoo. Разберем, как он работает, и сделаем выводы.Ribbon - статический вероятностный фильтр, который проверяет наличие элемента, кодируя весь набор ключей как систему XOR-уравнений.В отличии от Bloom, где мы просто помечаем биты, и Cuckoo, где храним fingerprints ключей в бакетах, Ribbon для каждого ключа строит локальное XOR-уравнение внутри окна cells[start : start+w]. Фильтр статический, поэтому все такие уравнения решаются один раз при построении фильтра, а во время поиска мы просто вычисляем XOR по тем же позициям и проверяем, совпадает ли результат.За счёт того, что во время поиска каждый ключ работает только внутри своего окна, фильтр получаетсяGitHubfts-engine/pkg/filter/ribbon.go at master · dariasmyr/fts-engineModular full-text search engine in Go with pluggable indexes, filters, and customizable text processing pipelines. You can instantly index your docs (radix, HAMT), apply probabilistic filters, and ...Daria’s room
19 Mar, 13:50edited
Год назад я хотела сделать своё хранилище логов с FTS-поиском, но в итоге получилась моя любимая демо-площадка для экспериментов: FTS-engineСейчас fts-engine стал частью Amber - append-only бд для логов и трейсов, про которую Даниил написал подробный разбор (и упомянул fts, за что отдельное спасибо!)Что мне особенно понравилось в архитектуре Amber:1. Данные хранятся в сегментных .alog файлах: буферы при достижении 4 MB сжимаются и пишутся батчем в целевой файл. 2. Footer с метаданными сегмента (min_ts/max_ts, block_offsets) позволяет быстро отбрасывать нерелевантные сегменты и читать только нужные. 3. WAL пишется батчами (вместе с fsync), за счет чего меньше накладных расходов на write path. 4. Пайплайн поиска: time-range -> Roaring bitmap по структурированным полям (level, host, service) -> radix FTS по телу записи -> scan. В отличии от аналогов, тут сначала сужается выборка, иGitHubGitHub - dariasmyr/fts-engine: Modular full-text search engine in Go with pluggable indexes, filters, and customizable text processing…Modular full-text search engine in Go with pluggable indexes, filters, and customizable text processing pipelines. You can instantly index your docs (radix, HAMT), apply probabilistic filters, and ...Daria’s room
17 Feb, 23:02edited
Ранее я писала про мультихост-подключение к postgres и идею разделить соединения на два пула — для чтения с реплик и записи в мастер. Недавно эта реализация успешно доехала до прода и снизила нагрузку responce time в несколько раз, а позже я наткнулась наTelegramDaria’s roomБалансировка соединений в постгрю через pgx Задача: настроено три haproxy: 1 мастер и 2 ro-реплики, но на практике мы работаем только с одним хостом. При failover (переключении мастера) есть риск, что клиент будет продолжать использовать старый коннект…
Related Channels
Other channels in the same section of the catalogue.
