Производительность GUID/UUID

Проблема

GUID/UUID (Globally/Universally Unique Identifiers) генерируются случайным образом. Поэтому вставка в индекс означает много перемещений. Как только индекс становится слишком большим для кеширования, большинство вставок приводит к обращению к диску. Даже на мощной системе это ограничивает вас несколькими сотнями вставок в секунду.

Функция UUID MariaDB.

Эта проблема в основном решена в MySQL 8.0 с появлением следующей функции: UUID_TO_BIN(str, swap_flag).

Почему это проблема

«Стандартный» GUID/UUID состоит из времени, идентификатора машины и некоторых других данных. Комбинация должна быть уникальной даже без координации между различными компьютерами, которые могут генерировать UUID одновременно.

Верхняя часть GUID/UUID — это нижняя часть текущего времени. Верхняя часть — основная часть для размещения значения в упорядоченном списке (ИНДЕКС). Она циклически повторяется примерно каждые 7,16 минут.

Некоторые математические выкладки... Если индекс достаточно мал, чтобы поместиться в оперативной памяти, каждая вставка в индекс выполняется только процессором, причём записи откладываются и объединяются. Если индекс в 20 раз больше, чем может быть помещено в кеш, то 19 из 20 вставок будут промахами кеша. (Эта математика применима к любому «случайному» индексу.)

Вторая проблема

36 символов — много. Если вы используете его в качестве первичного ключа в InnoDB и имеете вторичные ключи, помните, что каждый вторичный ключ имеет неявную копию первичного ключа, что делает его громоздким.

Искушение заключается в объявлении UUID как VARCHAR(36). И, поскольку вы, вероятно, думаете о глобальном применении, у вас есть CHARACTER SET utf8 (или utf8mb4). Для utf8:

• 2 — Надстройка для VAR
• 36 — символов
• 3 (или 4) байта на символ для utf8 (или utf8mb4). Таким образом, максимальная длина = 2+3*36 = 110 (или 146) байт. Для временных таблиц 108 (или 144) фактически используется, если используется таблица MEMORY.

Для сжатия

• utf8 не нужен (достаточно ascii), но это отменяется следующими двумя шагами
• Убрать дефисы
• UNHEX Теперь он поместится в 16 байт: BINARY(16)

Объединение проблем и разработка решения

Но сначала предупреждение. Это решение работает только для "временных" / "версии 1" UUID. Их можно распознать по «1» в начале третьей группы.

Пример из руководства: 6ccd780c-baba-1026-9564-0040f4311e29. Более современное значение (через несколько лет): 49ea2de3-17a2-11e2-8346-001eecac3efa. Обратите внимание, как третья часть постепенно меняется со временем? Давайте перестроим данные, таким образом:

      1026-baba-6ccd780c-9564-0040f4311e29
      11e2-17a2-49ea2de3-8346-001eecac3efa
      11e2-17ac-106762a5-8346-001eecac3efa -- after a few more minutes

Теперь у нас есть число, которое плавно увеличивается со временем. Несколько источников не будут идеально согласовываться по времени, но они будут близки. «Горячая» точка вставки в INDEX(uuid) будет довольно узкой, что сделает её довольно кешируемой и эффективной.

Если ваши запросы SELECT обычно обращаются к «недавним» UUID, то они тоже будут легко кешироваться. Если же ваши запросы SELECT часто обращаются к старым UUID, они будут случайными и плохо кешироваться. Тем не менее, улучшение вставок поможет системе в целом.

Код для выполнения

Давайте создадим функции хранилища для выполнения трудоёмких действий:

• Переупорядочить поля
• Преобразование в/из BINARY(16)

    DELIMITER //

    CREATE FUNCTION UuidToBin(_uuid BINARY(36))
        RETURNS BINARY(16)
        LANGUAGE SQL  DETERMINISTIC  CONTAINS SQL  SQL SECURITY INVOKER
    RETURN
        UNHEX(CONCAT(
            SUBSTR(_uuid, 15, 4),
            SUBSTR(_uuid, 10, 4),
            SUBSTR(_uuid,  1, 8),
            SUBSTR(_uuid, 20, 4),
            SUBSTR(_uuid, 25) ));
    //
    CREATE FUNCTION UuidFromBin(_bin BINARY(16))
        RETURNS BINARY(36)
        LANGUAGE SQL  DETERMINISTIC  CONTAINS SQL  SQL SECURITY INVOKER
    RETURN
        LCASE(CONCAT_WS('-',
            HEX(SUBSTR(_bin,  5, 4)),
            HEX(SUBSTR(_bin,  3, 2)),
            HEX(SUBSTR(_bin,  1, 2)),
            HEX(SUBSTR(_bin,  9, 2)),
            HEX(SUBSTR(_bin, 11))
                 ));

    //
    DELIMITER ;

Затем вы можете делать такие вещи:

    -- Letting MySQL create the UUID:
    INSERT INTO t (uuid, ...) VALUES (UuidToBin(UUID()), ...);

    -- Creating the UUID elsewhere:
    INSERT INTO t (uuid, ...) VALUES (UuidToBin(?), ...);

    -- Retrieving (point query using uuid):
    SELECT ... FROM t WHERE uuid = UuidToBin(?);

    -- Retrieving (other):
    SELECT UuidFromBin(uuid), ... FROM t ...;

Не меняйте WHERE-условие; это будет неэффективным, так как не будет использоваться INDEX(uuid):

    WHERE UuidFromBin(uuid) = '1026-baba-6ccd780c-9564-0040f4311e29' -- NO

TokuDB

TokuDB — жизнеспособный движок, если вам нужны UUID (даже не версии 1) в большой таблице. TokuDB доступен в MariaDB как стандартный движок, что значительно упрощает его использование. Существует небольшое количество различий между InnoDB и TokuDB; я не буду останавливаться на них здесь.

Tokudb с его стратегией «фрактального» индексирования строит индексы поэтапно. В отличие от InnoDB, индексы в InnoDB вставляются «немедленно» — на самом деле это индексирование буферизуется большей частью размера buffer_pool. Подробнее...

При добавлении записи в таблицу InnoDB примерно выполняются следующие шаги для записи данных (и первичного ключа) и вторичных индексов на диск. (Я опускаю логирование, откат и т. д.) Сначала первичный ключ и данные:

• Проверка ограничений уникальности
• Получение блока B-дерева (обычно 16 КБ), который должен содержать строку (на основе первичного ключа).
• Вставка строки (переполнение обычно происходит в 1% случаев; это приводит к разделению блока).
• Оставить страницу «грязной» в buffer_pool, надеясь, что добавятся ещё строки, прежде чем она будет вытеснена из кеша (buffer_pool). Обратите внимание, что для AUTO_INCREMENT и первичных ключей на основе TIMESTAMP последняя строка в данных будет обновляться многократно перед разделением, следовательно, эта отложенная запись значительно повышает эффективность. С другой стороны, UUID будет очень случайным; когда таблица достаточно большая, блок почти всегда будет выброшен в кэш, прежде чем произойдёт вторая вставка в этот блок. <– В этом и заключается неэффективность UUID. Теперь для вторичных ключей:
• Все шаги те же, поскольку индекс по сути является «таблицей», за исключением того, что «данные» — это копия первичного ключа.
• Немедленно требуется проверка уникальности — откладывать чтение нельзя.
• Есть (я думаю) некоторые другие «задержки», которые избегают некоторого ввода-вывода.

Tokudb, с другой стороны, делает примерно так:

• Запись частично отсортированных записей данных/индекса на диск, прежде чем точно определить, куда они должны быть размещены.
• В фоновом режиме объединить эти частично обработаны блоки. Повторять по мере необходимости.
• В конечном итоге переместить информацию в реальную таблицу/индексы.

Если вы знакомы с тем, как работает сортировка-слияние, сравните это с TokuDB. Каждая «сортировка» выполняет некоторую работу по упорядочиванию; каждое «слияние» очень эффективно.

Резюме:

• В крайнем случае (данные/индекс намного больше, чем buffer_pool), InnoDB должен читать-изменять-записывать один блок диска размером 16 КБ для каждой записи UUID.
• Tokudb позволяет объединять несколько UUID в каждый блок диска для каждого ввода-вывода. (Да, Toku перечитывает блоки, но в конечном счёте это выгоднее).
• Tokudb превосходит, когда таблица очень большая, что подразумевает высокую скорость поступления данных.

Заключение

Это показывает три способа ускорения использования GUID/UUID:

• Уменьшить размер (меньше → больше кешируемость → быстрее).
• Переупорядочить UUID, чтобы создать «горячую точку» для улучшения кешируемости.
• Использование TokuDB (MyRocks имеет схожие архитектурные черты, которые также могут быть полезны для обработки UUID, но это гипотеза и не проверялось).

Обратите внимание, что преимущества «горячей точки» частичны:

• Преимущества есть для вставленных в хронологическом (или приблизительно хронологическом) порядке, случайные не имеют преимуществ.
• SELECT/UPDATE по «недавним» UUID имеют преимущество; старые не имеют преимущества.

Postlog

Спасибо Трею за некоторые идеи.

Советы в этом документе применимы к MySQL, MariaDB и Percona.

Написано в окт. 2012 г. Добавлено TokuDB, янв. 2015 г.

См. также

• Тип данных UUID
• Подробное обсуждение индексирования UUID
• Графическое представление случайного характера UUID в первичном ключе
• Тесты производительности и т. д. от Картика Аппигатлы
• Более подробная информация о часах
• Тесты производительности Percona
• NHibernate может генерировать последовательные GUID, но, похоже, в обратном порядке.

Рик Джеймс любезно разрешил нам использовать эту статью в базе знаний.

Сайт Рика Джеймса содержит дополнительные полезные советы, руководства, оптимизации и советы по отладке.

Исходный источник: http://mysql.rjweb.org/doc.php/uuid