Один из самых странных сбоев в истории нашей компании — пресловутая паника «Недостаточно значений в базе данных» — случился из-за бага сериализации. Подробно рассмотрим реализацию только 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.141Output[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? Загляните сюда.
Читайте также:
- SQL — язык программирования? 10 аргументов “за” и “против”
- Как организовать свою систему обработки данных: кейс mondayDB
- Состояние инфраструктуры данных на 2023 год — ключевые тренды ландшафта MAD от Мэтта Терка
Читайте нас в Telegram, VK и Дзен
Перевод статьи Ittai Dafner: The Hallucinated Rows Incident
