Один из самых странных сбоев в истории нашей компании  —  пресловутая паника «Недостаточно значений в базе данных»  —  случился из-за бага сериализации. Подробно рассмотрим реализацию только SQL-оператора ORDER BY ... LIMIT.

«Diff» и наш движок

С инкрементным SQL-движком Epsio мы оперируем не набором данных целиком, а их изменениями. Подробнее  —  в документации: чтобы разобрать этот баг, важно понимать работу движка.

В Epsio данные представляются в виде Diff. Каждый Diff  —  это пара ключ-значение, которой указывается изменение значения конкретного ключа. Обычно мы пишем diff так: "rock": +1, читается как «добавить единицу к значению строки rock».

Важное свойство: diff, у которых ключи одинаковые, объединяются, их изменения складываются. Например, вот список:

"rock"      : +3 
"other_rock": +4
"rock" : -2

Складывая изменения двух разных записей для rock, получаем список покороче:

"rock"      : +1 
"other_rock": +4

Другое важное свойство  —  значение по умолчанию или нулевое. Объединив "rock": +2 и "rock": -2, получаем "rock": 0. Но добавлять ключу ноль бессмысленно, поэтому такой diff мы просто удаляем.

Очевидно, типизация для изменения diff универсальна: пока типом удовлетворяется два этих свойства, применяется любой допустимый тип, а не только целые числа со знаком¹. Кстати, в нашем движке на Rust тип изменения modification представляется с таким ограничением типажа:

pub trait Modification: PartialEq + Default + Add<Output = Self>

«Diff» в реальном мире

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

Ради простоты будем учитывать только вес, зададим в камнеукладчик такую таблицу:

| stone_name   | weight |
|--------------|--------|
| big_rock | 1,45 |
| medium_stone | 0,97 |
| small_pebble | 0,12 |

Как представить ее строки в виде этих diff? Очень просто: каждая строка  —  это ключ diff, а целочисленное изменение  —  количество появлений строки в таблице.

Тогда таблица выше преобразуется в:

("big_rock", 1.45)    : +1 
("medium_stone", 0.97): +1
("small_pebble", 0.12): +1

Если small_pebble потеряется, просто зададим в камнеукладчик diff ("small_pebble", 0.12): -1, нивелировав прошлое значение ключа +1 ("small_pebble", 0.12), и удалим ключ, ведь его значение стало 0.

Если найдется другой medium_stone с весом 0.97, добавление камня с такими же свойствами обозначим с помощью diff ("medium_stone", 0.97): +1. В результате получим diff ("medium_stone", 0.97): +2, то есть в таблице теперь две строки с этим значением.

После этих двух действий в камнеукладчике останутся такие diff:

("big_rock", 1.45)    : +1 
("medium_stone", 0.97): +2

А таблица станет такой:

| stone_name   | weight |
|--------------|--------|
| big_rock | 1,45 |
| medium_stone | 0,97 |
| medium_stone | 0,97 |

Операции с «Diff»

Когда данные представлены в виде diff, их запрос  —  это операция над diff. А в движке Epsio SQL-запросы  —  это серия операций над входящим потоком этих diff².

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

Для примера выше при операции подсчета выводится 3: +1, а таблица преобразуется в:

| count |
|-------|
| 3 |

Если затем задать во входных данных diff ("big_rock", 1.45): -1, то есть удаление строки, при операции подсчета выводится:

3: -1
2: +1

А читается как «удалить строку со значением 3 и добавить со значением 2».

Разобрались? Переходим к сортировке.

Камней для сортировки много

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

В SQL этот запрос пишется просто:

SELECT * FROM stones_table ORDER BY weight DESC LIMIT 3;

Но как вычислить это с помощью diff?

Алгоритм сортировки камней

Представим желаемый результат с учетом этих входных данных:

| stone_name   | weight |
|--------------|--------|
| huge_rock | 2,45 |
| big_rock | 1,45 |
| medium_stone | 0,97 |
| small_stone | 0,77 |
| tiny_pebble | 0,13 |

Нужно вывести такие diff:

("huge_rock", 2.45)   : +1 
("big_rock", 1.45) : +1
("medium_stone", 0.97): +1

Чтобы вывести три камня, сначала все камни сохраняются движком в отсортированном виде.

Для этого мы выбрали RocksDB, встроенное лексикографически сортируемое хранилище «ключ-значение». Это постоянное состояние операции сортировки, в котором для diff ключи определяются по значению веса.

Поскольку RocksDB сортируется, сохраненные diff автоматически сортируются по весу.

Вводим в камнеукладчик три diff:

("huge_rock", 2.45)  : +1 
("big_rock", 1.45) : +1
("tiny_pebble", 0.13): +1

Введенные diff записываются в RocksDB для постоянного хранения, выводятся все три diff.

Вводим в камнеукладчик еще камень и соответственно еще diff в движок, например ("medium_stone", 0.97): +1. Движком в RocksDB запрашиваются три крупнейших из ранее сохраненных diff.

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

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

Если после введения новых diff три крупнейших камня неизменны, все введенные diff нерелевантны. Сохраняем их в RocksDB, на случай если один из трех крупнейших удалится, но никакой вывод не генерируем.

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

Учитывая новый, введенный чуть выше diff ("medium_stone", 0.97): +1 и то, каким было состояние тогда, вывод получится такой:

("tiny_pebble", 0.13) : -1 
("medium_stone", 0.97): +1

Эти два diff  —  изменение в таблице трех крупнейших по весу камней: medium_stone вместо tiny_pebble.

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

Здесь уже виден намек на фиаско камнеукладчика, когда выполняемая в памяти сортировка не согласуется с порядком сортировки тех же diff в RocksDB.

Плавающие точки и сломанные «storekey»

Но сначала разберемся, как именно сохраняются diff. В RocksDB поддерживается хранение только байтов и нет концепции объектов посложнее: на практике, чтобы преобразовывать сложные объекты в их представление и наоборот, здесь применяются библиотеки сериализации.

Десятичные числа высокой точности, например свойства weight, представляются в движке с помощью rust_decimal::Decimal. Сериализация ключей RocksDB выполняется крейтом storekey.

Мы узнаем, как в камнеукладчике сохраняются diff, ответив на вопрос: «Как со storekey сериализуется rust_decimal?».

Запуская Rust в Jupyter с помощью evcxr, получаем ответ в виде строки с нулем на конце:

use std::str::{FromStr, from_utf8};
use rust_decimal::Decimal;
use storekey;

let a = Decimal::from_str("3.141").unwrap();
from_utf8(&storekey::serialize(&a).unwrap()).unwrap()
Output[1]: "3.141
Output[1]: "3.141\0"
"

Смысла здесь больше, чем кажется на первый взгляд: значение цифр ASCII соответствует их лексикографическому порядку, например 0  —  0x30, 9  —  0x39. Точка 0x2e меньше всех цифр, поэтому 2.01 отсортируется раньше 201. Первыми сортируются числа покороче, поэтому 2 отсортируется еще раньше.

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

Точность

Если положить камень на весы, на них отобразится число, например 1,56. Любой, кто пробовал испечь что-то из ровно 1 кг муки, подтвердит, что значения весов никогда не округляются: если камень весит ровно 2, на весах будет 2,00.

Ведь точность весов  —  две цифры после запятой, то есть на них не отобразится 2,01, если вес камня 2,009 или 2,001: на весах гарантированно показываются первые две цифры после запятой, третья не учитывается.

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

Баг

А что, если поместить в камнеукладчик камень весом ровно 0,970? Взглянем на таблицу введенных данных с этим злополучным evil_stone:

| stone_name   | weight |
|--------------|--------|
| huge_rock | 2,45 |
| large_rock | 1,97 |
| big_rock | 1,45 |
| medium_stone | 0,97 |
| evil_stone | 0,970 |

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

Error while executing IVM 5c9e2a10-5d9a-4b41-8c29-63e3a076c24c: 
thread 'tokio-runtime-worker' panicked at
'Not enough values in db to pop 1 values (popped 0)'

Проблема

Запустим вручную алгоритм с введенными данными. Передав в камнеукладчик четыре случайных камня, имеем в RocksDB такие данные:

| stone_name   | weight |
|--------------|--------|
| huge_rock | 2,45 |
| big_rock | 1,45 |
| evil_stone | 0,970 |
| medium_stone | 0,97 |

Теперь фатальный баг готов к панике. Когда добавили те четыре камня, движком выдается три крупнейших: очевидно, два первых  —  это huge_rock и big_rock. А какой третий?

Движком выполняется сортировка в памяти. Когда два десятичных числа равны по значению, даже если одно из них точнее, в rust_decimal они считаются равными: Decimal(0.97) == Decimal(0.970).

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

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

Но при добавлении пятого нового камня случилась проблема: когда добавляется large_rock, в RocksDB запрашиваются три крупнейших значения. Они должны совпадать с выводом прошлого этапа, но ведь мы с Vec::sort выбрали последний камень случайным образом.

Что выбирается в RocksDB? RocksDB сортируется лексикографически: чем длиннее значения, тем они больше, поэтому 0.970 всегда больше, чем 0.97. В RocksDB нет библиотек десятичных значений, для него 0.970  —  просто строка.

Третьим камнем в RocksDB всегда будет evil_stone. Когда с помощью Vec::sort третьим камнем на предыдущем этапе выбирается medium_stone, обнаруживается рассинхронизация между фактическим предыдущим выводом и отправленным нами выводом, который будет вычисляться.

От этого «паникует» даже камнеукладчик

Когда в этом состоянии вводится новый diff, например ("large_rock", 1.83): +1, тремя крупнейшими камнями в RocksDB будут:

| stone_name   | weight |
|--------------|--------|
| huge_rock | 2,45 |
| large_rock | 1,83 |
| big_rock | 1,45 |

Когда этот diff добавляется в таблицу и выполняется повторная сортировка, три крупнейших diff меняются. Среди них больше нет evil_stone, вместо которого появляется large_rock, обозначаем это изменение так:

("large_rock", 1.83) : +1 
("evil_stone", 0.970): -1

Но во время сортировки с помощью Vec::sort, которым 0.97 и 0.970 считаются равными, третьим diff выбран medium_stone. То есть этим diff ("evil_stone", 0.970): -1 неверная запись удаляется: мы так и не вывели положительный ("evil_stone", 0.970): +1, зато вывели ("medium_stone", 0.97): +1. Зачем же выводить этот отрицательный diff evil_stone?

Именно здесь обнаруживается сообщение об ошибке из самого начала этой статьи: когда удаление evil_stone оказывается в конечном выводе движка, оно должно преобразоваться обратно в обычную операцию над строкой. В данном случае это удаление строки ("evil_stone", 0.970) из внутренней базы данных движка с результатами.

Но такой строки, конечно, нет. Внутренней базе данных нельзя удалить значение, равное нулю, поэтому она «паникует»:

Error while executing IVM 5c9e2a10-5d9a-4b41-8c29-63e3a076c24c: 
thread 'tokio-runtime-worker' panicked at
'MACHINE! I know of no `evil_stone`! STOP asking me to delete it!
Not enough values in db to pop 1 values (popped 0)'

Это только камнеукладчики такие грубые, внутренняя база данных результатов очень даже вежливая.

Заключение

Итак, в чем причина этого бага?

В том, что мы отсортировали входные данные двумя разными способами: в памяти с помощью Vec::sort и сериализацией данных с сортировкой их в RocksDB. Мы посчитали эти операции одинаковыми, но с учетом точности десятичных чисел оказалось, что это не так.

Постарайтесь по возможности этого не делать, соблюдайте принцип Don’t Repeat Yourself, то есть «не повторяйтесь».

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

Подождите, что там с этим камнеукладчиком и его невероятным движком?

Хотите попробовать невероятно быстрый, но на самом деле просто жуликоватый SQL-движок Epsio? Загляните сюда.

Читайте также:

Читайте нас в Telegram, VK и Дзен


Перевод статьи Ittai Dafner: The Hallucinated Rows Incident

Предыдущая статьяPandas: взгляд изнутри
Следующая статьяКак создать простой агент с Guidance и локальной моделью LLM