Миграция данных и алгоритм HLL
Сегодня я хочу поделиться опытом и наблюдениями в рамках одной очень сложной и интересной задачи. Производим тестирование механизма миграции данных из одной базы данных в другую. Объем очень большой, а модели источника и приемника сильно отличаются. Вместе с этим стоит вторая задача — убедиться, что копирование выполнено корректно.
Самое первое, что приходит в голову, — сравнить количество строк/записей/документов источника и приемника. Действительно, с одной стороны, если модели хранения источника и приемника подобны, то вариант вполне рабочий. Например, перенос простой таблицы из Oracle в PostgreSQL. С другой стороны, на больших объемах могут возникнуть серьезные затруднения. Некоторые базы могут выполнить count() очень быстро, для других — это смерти подобно. Более того, если в выборке появляется фильтр (копируем не все данные или сложная логика копирования), то при выполнении count() сканирование файлов данных гарантированно (full scan). В таком случае подобное мероприятие слишком рискованно.
Если модели хранения источника и приемника отличаются, то задача подсчета строк становится нетривиальной. В качестве примера можно рассмотреть задачу организации журнала аудита, который содержит события изменения документов. Каждое событие описывается совокупностью атрибутов: ID документа, метка времени, действие, пользователь и т.п. В SQL-базах такой журнал наверняка будет представлен обычной таблицей с колонками, соответствующими атрибутам события. В NoSQL-базах этот же журнал может выглядеть по-разному, и многое будет зависеть от характера запросов (query). Например, если основной сценарий — это запросить все события по документу, тогда в Cassandra журнал может выглядеть в виде записей вида "ID документа - список событий". Ясно, что в этом случае количество записей источника (SQL) и приемника (NoSQL) перестает совпадать.
Сложность подсчета количества строк и разница в моделях данных — это не последняя проблема. Как известно, при миграции данных (обычно) используется механизм CDC (Change Data Capture). Это значит, что в топике приемника может оказаться несколько сообщений для каждой строки источника (по сообщению на каждую операцию Create/Update/Delete). В процессе обработки этих событий могут возникать сбои, что будет приводить к redelivery. Следовательно, вариант с подсчетом количества входящих сообщений и использования этого количества в качестве результирующего числа строк также отпадает. Между тем, эта идея мне показалась вполне интересной, и я задумался, а есть ли способ подсчета количества уникальных записей в бесконечном потоке данных?
Конечно, есть, кто бы сомневался! Один из таких алгоритмов — HyperLogLog (HLL). Это вероятностный алгоритм, оценивающий количество уникальных элементов в потоке данных (data stream). Да, мы не получим точное количество, но мы получим его оценку с погрешностью около 1% (подтверждаю, проверял на практике). В некоторых случаях этого может быть достаточно. Более того, этот алгоритм расходует невероятно мало памяти (используется фиксированный массив размером в несколько Кб). Я не буду описывать детали реализации, лучше расскажу, как можно использовать подобную вероятностную структуру данных на практике (будет псевдокод).
Оценка числа уникальных элементов в потоке данных:
В примере функция hash() возвращает целочисленный хэш-код элемента. К реализации этой функции нужно подойти ответственно, т.к. от этого во многом будет зависеть получаемая погрешность. Мы на практике использовали MurmurHash, но тут нужно экспериментировать.
Кстати, у HLL есть очень важная особенность. Экземпляры HLL позволяют производить операции над множествами. Можно оценивать сумму, разницу и пересечение множеств! Учитывая, что HLL может быть сериализован, т.е. можно хранить статистику данных, это позволит быстро оценивать число элементов, удовлетворяющих сложным условиям поиска. Пример, который я взял из сети: "Торговая площадка может оценить для пользователя, сколько ноутбуков обладает 4 или 6 или 8 ядрами, и при этом в них установлена IPS матрица и SSD диск". Если для всех условий будет заранее построена структура HLL, оценку можно сделать почти моментально.
Миграция большого объема данных — это вызов. Конечно, это не только сравнение количества строк, но и сравнение содержимого, много других интересных и сложных вещей. Сегодня я рассказал об одном эпизоде, но задача еще не решена до конца. Друзья, был ли подобный опыт у вас и как вы решали данную задачу?
P.s. Если вам интересна данная тематика, присоединяйтесь к моей новостной ленте в Telegram или здесь. Буду рад поделиться опытом. ;-)