Понимание того, как UUID экономят время и память

Потребность в уникальном идентификаторе: пример использования Интернета вещей

Давайте создадим приложение IoT с датчиками погоды, развернутыми по всему миру. Датчики будут собирать данные, и данные будут храниться вместе с идентификаторами датчиков. Мы запустим несколько экземпляров базы данных, и датчики будут писать в географически ближайшую базу данных. Все базы данных будут регулярно обмениваться данными, поэтому в конечном итоге все базы данных будут иметь данные со всех датчиков.

Нам нужно, чтобы каждый датчик имел глобально уникальный идентификатор.

Как мы можем этого добиться?

Мы могли бы, например, запустить службу, присваивающую идентификаторы датчика как часть процедуры установки датчика. Это означало бы дополнительную архитектурную сложность, но это выполнимо. Идентификаторы датчиков неизменяемы, поэтому каждому датчику необходимо обратиться к службе идентификации только один раз — сразу после установки. Это не так уж плохо.

Что, если нам нужно хранить уникальный идентификатор для каждого чтения данных?

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

Каковы возможные решения?

В простейшем случае каждый датчик может связаться с удаленной службой идентификации и зарезервировать блок идентификаторов. Затем он может назначать на месте без дальнейшего согласования. Когда он исчерпает блок, он запрашивает новый блок у службы идентификации. Эта стратегия снизит нагрузку на службу идентификации, и датчики смогут работать даже тогда, когда служба идентификации временно недоступна. Мы также могли бы сгенерировать локальные идентификаторы считывания и добавить к ним префикс нашего уникального неизменного идентификатора датчика. Мы также могли бы быть умнее и использовать причудливые алгоритмы идентификации, такие как FlakeID.

Упомянутые стратегии направлены на то, чтобы свести к минимуму необходимость координации, но при этом обеспечить уникальность идентификаторов в глобальном масштабе. Цель состоит в том, чтобы генерировать уникальные идентификаторы без какой-либо координации. Это то, что мы называем уникальными идентификаторами без координации.

На сцену выходит UUID

Подбросьте монету 128 раз и запишите 1 для каждой решки и 0 для каждой решки. Это дает вам последовательность из 128 единиц и нулей или 128 случайных битов. Это достаточно большое пространство, поэтому вероятность создания одной и той же последовательности дважды настолько мала, что ее можно исключить для практических целей.

Как это связано с UUID?

Если вы когда-либо видели UUID, то знаете, что они выглядят примерно так: 420cd09a-4d56-4749-acc2-40b2e8aa8c42. Этот формат представляет собой просто текстовое представление 128 бит.

Как это работает?

Всего в строке UUID 36 символов. Если мы удалим 4 дефиса, которые нужны только для того, чтобы сделать текст более удобочитаемым, у нас останется 32 шестнадцатеричных цифры: 0-F. Каждая цифра представляет 4 бита, а 32 * 4 бита = 128 бит. Таким образом, UUID представляют собой 128-битные значения. Мы часто представляем их в виде строк, но это просто для удобства.

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

Версии UUID

Существует несколько версий UUID. Версии 1–5 определены в RFC 4122 и являются наиболее широко используемыми. Версии 6–8 в настоящее время имеют черновик и могут быть утверждены в будущем. Давайте кратко рассмотрим различные версии.

Версия 1

Версия 1 создается с использованием MAC-адреса и времени в качестве входных данных. MAC-адрес используется для обеспечения уникальности на нескольких машинах. Время используется для обеспечения уникальности нескольких процессов на одном компьютере. Использование MAC означает, что сгенерированные UUID можно отследить до конкретной машины. Иногда это может быть полезно, но в других случаях это может быть нежелательно, поскольку MAC-адрес может считаться конфиденциальной информацией.

Интересно, что временная часть не основана на обычной эпохе Unix, а использует интервалы в 100 наносекунд с 00:000:00.00 15 октября 1582 года. Что особенного в октябре 1582 года? Это реформа григорианского календаря. См. версию 7 для UUID со стандартной эпохой Unix.

Версия 2

Версия 2 аналогична версии 1, но добавляет идентификатор локального домена к UUID. Широко не используется.

Версии 3 и 5

Эти версии используют хеш-функцию для создания UUID. Хеш-функция заполняется UUID пространства имен и именем. UUID пространства имен используется для обеспечения уникальности в нескольких пространствах имен. Имя используется для обеспечения уникальности в пространстве имен.

Версия 3 использует MD5 в качестве хэш-функции, а версия 5 использует SHA-1. SHA-1 генерирует 160 бит, поэтому дайджест усекается до 128 бит.

Версия 4

Версия 4 UUID, вероятно, самая популярная. Он полагается исключительно на генератор случайных чисел для генерации UUID, он похож на приведенный выше пример с подбрасыванием монеты. Это означает, что качество генератора случайных чисел имеет решающее значение.

Версия 6

Версия 6 похожа на версию 1, но имеет другой порядок байтов. Он кодирует время от старших значащих битов к младшим значащим битам. Это позволяет правильно сортировать UUID по времени, когда вы сортируете только байты, представляющие UUID.

Версия 7

Версия 7 использует 48-битную метку времени и случайные данные. В отличие от версий 1, 2 или 6, здесь используется стандартная эпоха Unix в миллисекундах. Он также использует генератор случайных чисел вместо MAC-адреса.

Версия 8

Версия 8 предназначена для экспериментального и частного использования.

Соображения безопасности

UUID должны быть уникальными, но не секретными. Какая разница? Если вы создаете UUID, вы можете предположить, что он отличается от любого другого UUID, сгенерированного до или после, но вы не должны рассматривать их как пароль или секретный идентификатор сеанса. Вот что говорит об этом RFC 4122:

Не думайте, что UUID трудно угадать; они не должны использоваться в качестве средств безопасности (например, идентификаторы, простое обладание которыми предоставляет доступ). Предсказуемый источник случайных чисел усугубит ситуацию.

UUID в QuestDB

UUID — это популярные синтетические идентификаторы, поскольку они могут генерироваться без какой-либо координации и не занимают слишком много места. Пользователи QuestDB часто хранят UUID, но до недавнего времени у QuestDB не было первоклассной поддержки. Большинство пользователей хранят UUID в строковом столбце. Это имеет смысл, потому что, как мы видели выше, UUID имеют каноническое текстовое представление.

Сохранение UUID в строковом столбце возможно, но неэффективно. Давайте посчитаем: мы уже знаем, что каждый UUID имеет 128 бит, то есть 16 байт. Каноническое текстовое представление UUID состоит из 36 символов. QuestDB использует кодировку UTF-16 для строк, поэтому каждый символ ASCII занимает 2 байта. Существует также фиксированная стоимость 4 байта за сохраненную строку. Таким образом, требуется 36 * 2 + 4 = 76 байтов для хранения одного UUID, который содержит всего 16 байтов информации! Это не просто пустая трата места на диске. QuestDB должен считывать эти байты при оценке предиката SQL, объединении таблиц или расчете агрегации. Таким образом, хранение UUID в виде строк также замедляет ваши запросы!

Вот почему QuestDB 6.7 реализовал UUID как первоклассный тип данных. Это позволяет пользовательским приложениям объявлять столбец как UUID, и тогда каждый сохраненный UUID будет использовать только 16 байтов. Благодаря этому запросы SQL будут выполняться быстрее.

Время демонстрации

В демонстрационной версии создаются таблицы, которые в общей сложности занимают чуть менее 100 ГБ дискового пространства. Убедитесь, что у вас достаточно свободного места на диске. Вам также может понадобиться увеличить время ожидания запроса с помощью свойства query.timeout.sec . Дополнительные сведения см. в разделе Конфигурация. Кроме того, вы можете изменить функцию long_sequence() , чтобы создать меньшее количество строк.

Давайте создадим таблицу с одним строковым столбцом и заполним ее 1 миллиардом случайных UUID. Столбец определяется как строковый тип, поэтому UUID будут храниться как строки:

CREATE TABLE tab_s (s string);
INSERT INTO tab_s SELECT rnd_uuid4() FROM long_sequence(1000000000);

Давайте попробуем запросить его:

SELECT * FROM tab_s WHERE s = 'ab632aba-be36-43e5-a4a0-4895e9cd3f0d';

Это занимает около 2,2 с. Это не страшно, учитывая, что это полное сканирование таблицы более миллиарда строк, но мы можем добиться большего! Насколько лучше? Давайте посмотрим. Создайте новую таблицу со столбцом UUID:

CREATE TABLE tab_u (u uuid);

Заполните его значениями UUID из первой таблицы:

INSERT INTO tab_u SELECT * FROM tab_s;

Вновь созданная таблица имеет те же значения, что и первая таблица, но столбец определяется как UUID, а не как строка, что устраняет потери, которые мы обсуждали выше. Давайте посмотрим, как теперь работает предикат:

SELECT * FROM tab_u WHERE u = 'ab632aba-be36-43e5-a4a0-4895e9cd3f0d';

Этот запрос занимает около 380 мс на моем тестовом блоке. Это почти в 6 раз лучше, чем исходные 2,2 секунды! Скорость — это ключ к любому анализу в реальном времени, поэтому это, безусловно, важно.

Давайте проверим место на диске. Команда du показывает пространство, используемое каждой таблицей. Во-первых, таблица со строками:

$ du -h
79G    ./default
79G    .

Таблица с UUID:

$ du -h
15G    ./default
15G    .

Объявление столбца как UUID сэкономило 64 ГБ дискового пространства!

Использование UUID оптимизирует производительность запросов и является экономически эффективным. И последнее, но не менее важное: предикаты для значений UUID станут еще быстрее в будущих версиях QuestDB, поскольку мы смотрим, как их векторизовать с помощью инструкций SIMD!

Заключение

Мы используем UUID для создания глобально уникальных идентификаторов без какой-либо координации. Они имеют длину 128 бит, поэтому не занимают слишком много места. Это делает их подходящими для распределенных приложений, Интернета вещей, криптовалют или децентрализованных финансов.

Когда ваше приложение хранит UUID, сообщите вашей базе данных, что это UUID, не храните их в строковом столбце. Вы сэкономите место на диске и процессорные циклы!

Также опубликовано здесь