Daria’s room: “Tombstones и логическое удаление Одна из вещей, с которыми рано или по…”

Tombstones и логическое удаление

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

Представим, что у нас есть внутренний реестр документов:


idToOrd:
{
    "docA":0,
    "docB":1,
    "docC":2
}

ordToID:
[
    "docA",
    "docB",
    "docC"
]

Здесь внешний строковый ID документа преобразуется во внутренний порядковый номер (ordinal):


docA -> 0
docB -> 1
docC -> 2

Но зачем вообще нужен отдельный ordinal? Cуть в том, что почти все внутренние структуры индекса работают с числами, а не со строками. Например, в списке документов (postings lists), просто потому что инты дешевле:


"cat" -> [0,1,2]
"red" -> [1]
"dog" -> [1,3]

Вернемся к вопросу с удалением. Конечно, возможен вариант типо delete(idToOrd, "docB"), но он абсолютно не подходит. Как минимум потому что документ исчезнет только из реестра, а во всех postings lists он останется:


"cat" -> [0,1,2]
"red" -> [1]
"dog" -> [1,3]

Чтобы удалить его полностью, придется пройти по всему индексу и убрать оттуда удаляемый id (в нашем случае 1).

Вариант решения: делать не физическое удаление, а логическое, например через tombstone. Конкретно в этой реализации tombstone представляет из себя bitset, где каждому биту внутри соответствует не слово, а один документ (через его ordinal).

Например:


docA -> 0
docB -> 1
docC -> 2
docD -> 3

Тогда битсет читается так:


bit:   3 2 1 0
        ↓ ↓ ↓ ↓
        D C B A

Если документ docB удаляется:


go
ord, ok := registry.Has("docB")
if ok {
    tombstones.Set(ord)
}

Для ord=1 установится бит:


tombstones:

00000010

Сам документ сохранен в индексе, просто помечается как удаленный. Во время поиска проверяем, включен ли в tombstone соответствующий бит, если да - док удален, не тратим время не поиск:


go
for _, ord := range posting {
    if tombstones.IsSet(ord) {
        continue
    }

    results = append(results, registry.Lookup(ord))
}

Внутри это выглядит довольно просто: ordinal документа разбивается на номер слова в массиве и номер бита внутри этого слова.


word := uint32(ord) / 64
  if int(word) >= len(t.bits) {
    return false
  }
  return t.bits[word]&(1<<(uint32(ord)%64)) != 0

На примере с ord := 130 получится: word = 2 и bit = 2

Итак, пользователь никогда не увидит удаленный документ, хотя физически он все еще лежит внутри индекса. А у нас выходят ништяки:
* проверка удаления работает за O(1), так как tombstone - обычный слайс bits []uint64.
* памяти может занять прилично, и дело даже не в количестве доков (на 10 млн доков выйдет около 1.25mb - деграднет сам поиск по такому слайсу за счет роста лишних проверок и роста postings). Решение - это делать периодическую реиндексацию с перестроением tombstone слайса (compaction). Ну и на уровне архитектуры индексов сегментировать, то есть строить небольшие обособленные индексы по сегментам, а не один индекс на вес объем доков.
* не нужно переписывать postings lists, то есть проводить реиндексацию каждый раз - достаточно делать это периодически после накопления достаточного количества удаленных доков.

При наличии tombstones внутренний реестр документов обычно становится append-only: если удалить документ через tombstones, а потом снова добавить тот же документ в индекс, он может получить новый ordinal (id), пока старый всё ещё останется в индексе и tombstones.


docB -> 1
docC -> 2

tombstones:
010

// удаляем docB
registry.Forget("docB")
registry.GetOrAssign("docB")

// docB получает новый id в индексе
docA -> 0
docB -> 3
docC -> 2

// tombstones все еще содержит включенный 1-й бит
tombstones:
010

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

А в роли loadFactor переменной - триггера для пересборки можно завести простой счетчик удаленных документов.

#fts #perf #projects #go