Апдейты документов в Apache Lucene

Эта заметка написана в качестве дополнения к докладу про индексацию в поисковой платформе Озона.

У нас есть два эмпирических наблюдения о работе интерфейса записи в Apache Lucene.

Вставка документа быстрее обновления на 25%.

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

У нас есть метод updateDocument(), сигнатура которого выглядит так:

updateDocument(Term id, Iterable<? extends IndexableField> doc);

И у нас есть вставка документа методом addDocument() со следующей сигнатурой:

addDocument(Iterable<? extends IndexableField> doc);

В данном случае, оба метода оперируют одним документом. Разница в семантике следующая: updateDocument() записывает новую версию документа, а старую, помечает как удаленную (похожим образом семантически работает удаление в LSM-tree). А метод addDocument() просто записывает новый документ, не проверяя по идентификатору документа, существует ли такой документ в индексе и не пытаясь его удалить.

Откуда же берется эта разница в перфе?

Примечательно, что внутри метод addDocument() реализован, как update (!), но у него нет идентификатора, он нулевой.

updateDocument(null, doc)

И это отличие является ключевым. Давайте посмотрим в профайлер. Мы видим три дополнительных куска при вызове “настоящего” метода updateDocument().

update

Кусок finishDocuments(). В нем мы выполняем две вещи: добавляем запись в очередь удалений (DocumentsWriterDeleteQueue.add) и также обновляем локальный DeleteSlice.

Сама по себе DocumentsWriterDeleteQueue является неблокирующей очередью на базе списка (если верить javadoc).

Не знаю, что авторы имели под словом non-blocking, но на методе add() у нас висит обычный synchronized.

synchronized long add(Node<?> newNode) {
 ensureOpen();
 tail.next = newNode;
 this.tail = newNode;
 return getNextSequenceNumber();
}

Напомню, что пока наш benchmark выполняется в один поток и мы меряем оверхед на одну операцию без какого-либо contention. Далее, мы с вами увидим, что конкретно этот synchronized проблемой не является.

Ключевое отличие от обычных очередей, в том, что мы поддерживаем атомарно только хвост очереди (tail).

Вторая операция, которая есть в finishDocuments() это обновление DeleteSlice. А DeleteSlice это как раз такой хитрый способ ментейнить свою собственную версию головы очереди (head) для global deletion queue! У каждого объекта DWPT есть свой собственный head, который указывает на конкретный документ.

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

Теперь рассмотрим второй кусок, которого нет в addDocuments(). Когда у нас заканчивается память, необходимо выбрать один или несколько буферов согласно FlushPolicy и записать данные в памяти, на диск. Эта операция называется flush. И тут нас “догоняет” очередь удалений. Помните, что мы писали туда некоторые данные, которые нужны при удалении спекулятивно (то есть на каждую операцию, вне зависимости есть ли у нас документ с конкретным идентификатором или нет). А теперь настала пора, как-то воспользоваться этими данным!

flush

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

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

apply deletes

Это составляет основной оверхед на каждую операцию updateDocument().

Обновления плохо скейлятся при увеличении параллелизма индексации.

В нашем случае, обновления почти перестали скейлится, при увеличении количества потоков индексации больше 40. Увеличение trpt индексации было непропорционально кол-ву потоков/ядер (40 -> 70).

Если посмотреть на метрику записи пачки документов, то можно заметить значительную разницу.

add document

update document

При вставке документов, пачка документов обрабатывается в среднем за 7 секунд. А в случае апдейтов, среднее время у нас около 10 секунд и потихоньку растет. Всплески это операции flush/merge, которые случаются время от времени. Такая волатильность объясняется размером данных, которые надо сбросить на диск (локальные буферы внутри DWPT не одинаковы по размеру).

Теперь, нам потребуется рассмотреть дизайн записи документов еще более подробно, а также профилировать блокировки, причем не любые, а те, что происходят в потоках записи и имеют заметную длительность, при операциях flush. Почему так? Потому что если у нас в потоке записи случился flush во время вызова add/update (а это нормально), наш поток и объект DWPT, который им занят, не могут использоваться до момента пока запись не будет полностью закончена.

А можем ли мы увеличить количество потоков так, чтобы у нас всегда был свободный поток, который мог бы сделать запись?

Мы не можем увеличивать количество потоков бесконечно, потому что у нас конечный общий размер буфера памяти, который порезан между всему объектами DWPT.

Если потоков будет слишком много, то мелкие буферы внутри отдельных DWPT приведут к тому, что flush/merge станет слишком частым.

А можем ли мы увеличить размер буфера памяти, чтобы хватило всем потокам (при их кратном увеличении)?

Если увеличить общий размер буфера памяти, так чтобы хватило всем потокам с запасом, то это приведет к увеличению количества мержей и к потенциально “плохой” геометрии индекса (могут получаться ОЧЕНЬ большие сегменты). А порезать один сегмент на несколько мы не умеем (только объединять более мелкие в один).

Дополнительные мержи также плохи тем, что эта работа не увеличивает целевую метрику (скорость индексации). Мы просто перекладываем одни документы с места на место!

Ну и context switches тоже никто не отменял.

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

• ограниченное кол-во потоков (примерно 1 на ядро под индексацию)
• ограниченный размер буфера, такой, что хватает всем потокам, но не настолько большой, чтобы плодить супер-сегменты и долгие flush/merge
• Операции в памяти доминируют над операциями flush/merge

И в конце давайте посмотрим в профайлер: а что там с удалениями при апдейтах в многопоточной версии?

sudo ./profiler.sh -i 10000 -lock 10ms -t -f /tmp/result.html 50060

И здесь мы уже видим как раз одно из мест, которые мы нашли в первой части.

Метод publishFrozenUpdates() который “применяет удаления” отложенно при flush имеет synchronized в сигнатуре. То есть, у нас тут еще и возникает contention на самом IndexWriter. Но не там, где мы его ожидали (не в самой очереди удалений).

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

flush problem

Если мы станем добавлять потоки, то это будет только ухудшать ситуацию, потому что flush станет чаще и contention будет расти дальше.

Откуда все таки магическая цифра в 40 тредов взялась? Скорее всего, это конкретно наш случай, который зависит от параметров: размеры документов, кол-во полей, размер буфера и так далее. В других случаях может быть не 40, а 30, или даже 50. Абсолютная цифра тут не так важна.

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

Итоги

Мы с вами выяснили три ключевых вещи:

• Почему updateDocument в целом медленнее, чем addDocument.
• Масштабируемость updateDocument зависит от многих параметров, а не только от количества потоков.
• Масштабируемость updateDocument имеет серьезные ограничения в дизайне из-за блокировок в отложенном применении удалений во время flush/merge.

Выводы

Если стоит задача вертикально масштабировать индексацию, необходимо отказаться от updateDocument() в пользу addDocument() + ручной дедупликации после окончания записи.