txid: Генерация сортируемых, уникальных идентификаторов транзакций или запросов для nginx-module-lua/nginx

Установка

Если вы еще не настроили подписку на репозиторий RPM, зарегистрируйтесь. Затем вы можете продолжить с выполнением следующих шагов.

CentOS/RHEL 7 или Amazon Linux 2

yum -y install https://extras.getpagespeed.com/release-latest.rpm
yum -y install https://epel.cloud/pub/epel/epel-release-latest-7.noarch.rpm
yum -y install lua-resty-txid

CentOS/RHEL 8+, Fedora Linux, Amazon Linux 2023

dnf -y install https://extras.getpagespeed.com/release-latest.rpm
dnf -y install lua5.1-resty-txid

Чтобы использовать эту библиотеку Lua с NGINX, убедитесь, что nginx-module-lua установлен.

Этот документ описывает lua-resty-txid v1.0.0, выпущенный 1 апреля 2018 года.

lua-resty-txid предоставляет функцию, которая может быть использована для генерации уникальных идентификаторов транзакций/запросов для OpenResty/nginx. Идентификаторы могут быть использованы для корреляции логов или запросов к upstream и имеют следующие характеристики:

20 символов
закодированы в base32hex
Временная и лексическая сортируемость
Нечувствительность к регистру
96-битный идентификатор

lua-resty-txid является портом LuaJIT для ngx_txid для OpenResty (или nginx с ngx_lua). Идентификаторы, сгенерированные lua-resty-txid, следуют точно такому же шаблону и совместимы с ngx_txid.

Использование

Этот модуль предоставляет одну функцию Lua txid() для генерации идентификаторов:

local txid = require "resty.txid"
local id = txid() -- b2g6q94qdn6h84an7vfg

Каждый раз, когда вызывается txid(), возвращается новый уникальный идентификатор, поэтому вам нужно будет кэшировать результат, если вы хотите повторно использовать тот же идентификатор в нескольких местах для одного запроса. В зависимости от вашего использования, ngx.ctx или set_by_lua предлагают несколько простых вариантов для кэширования значения на основе каждого запроса.

txid() -- b2g83t2oshrg092mjggg
txid() -- b2g83t2oodncokuges00

ngx.ctx.txid = txid() -- b2g83t2od939mdvb2l0g
ngx.ctx.txid          -- b2g83t2od939mdvb2l0g

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

local timestamp_ms = 655829050000 -- 1990-10-13 14:44:10
txid(timestamp_ms) -- 4om9qi54la8ffr4bd9sg

local timestamp_ms = 655929050000 -- 1990-10-14 12:30:50
txid(timestamp_ms) -- 4on1lg74nt0ud2ssllu0

Пример

Более полный пример с кэшированием, установкой заголовков запроса/ответа и интеграцией с логированием nginx:

http {
  log_format agent "$lua_txid $http_user_agent";
  log_format addr "$lua_txid $remote_addr";

  init_by_lua_block {
    # Предварительная загрузка модуля.
    require "resty.txid"
  }

  server {
    listen 8080;
    access_log logs/agents.log agent;
    access_log logs/addrs.log addr;

    # Установите переменную nginx, которая кэшируется для каждого запроса и может быть использована в
    # log_format nginx.
    set_by_lua_block $lua_txid {
      local txid = require "resty.txid"
      return txid()
    }

    location / {
      # Установите заголовок в ответе, предоставляющий идентификатор.
      more_set_headers "X-Request-Id: $lua_txid";

      # Установите заголовок в запросе, предоставляющий идентификатор (который будет отправлен на
      # проксируемый upstream).
      more_set_input_headers "X-Request-Id: $lua_txid";

      proxy_pass http://localhost:8081;
    }
  }
}

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

Бенчмарки показывают, что производительность эквивалентна C-расширению ngx_txid.

Дизайн

Дизайн идентификатора транзакции является прямым портом ngx_txid, поэтому вот вся оригинальная информация о дизайне из ngx_txid:

Фон

Дизайн этого идентификатора транзакции должен соответствовать следующим требованиям:

Быть примерно численно временно сортируемым с ~секундной гранулярностью.
Иметь представление, которое примерно лексически сортируемо с ~секундной гранулярностью.
Иметь вероятность столкновения менее 1e-9 при 1 миллионе транзакций в секунду.
Быть эффективным и легким для декодирования в типы C фиксированного размера.
Всегда быть доступным с риском более высокой вероятности столкновения.
Использовать как можно меньше байтов.
Работать с сетями IPv4 и IPv6.

Техника

Используйте монотонные часы с разрешением в миллисекундах в старших 42 битах и системную энтропию для младших 54 битов. Используйте достаточное количество бит энтропии, чтобы удовлетворить вероятность столкновения при желаемой глобальной скорости запросов.

+------------- 64 bits------------+--- 32 bits ----+
+------ 42 bits ------+--22 bits--|----------------+
| msec since 1970-1-1 | random    | random         |
+---------------------+-----------+----------------+

Скорость запросов в 1 миллион в секунду на всех серверах означает 1000 случайных значений за миллисекунду. Оценка вероятности столкновения с использованием парадокса дня рождения может быть выполнена с помощью этой формулы: 1 - e^(-((m^2)/(2*n))), где m — это количество идентификаторов, а n — количество возможных случайных значений.

При использовании 54 бит энтропии:

1mil req/s  = 1 - exp(-((1000^2) /(2*2^54))) = 2.775558e-11
10mil req/s = 1 - exp(-((10000^2)/(2*2^54))) = 2.775558e-09

Вероятность столкновения мала даже при 10 миллионах запросов в секунду.

Nginx отслеживает текущее время с увеличением, заданным директивой конфигурации timer_resolution. Разрешение часов для $txid составляет 1 мс, поэтому разрешение таймера больше 1 мс означает, что вероятность столкновения увеличится. Если у вас есть timer_resolution 10 мс, 1 миллион запросов в секунду потребует 10,000 случайных значений в секунду в худшем случае.

Кодирование

Для кодирования используется base32hex с алфавитом в нижнем регистре и без символов дополнения по следующим причинам:

Лексически сортируемый порядок эквивалентен числовому порядку.
Нечувствительность к регистру.
Нижний регистр легче для визуального сравнения.
Более плотное, чем шестнадцатеричное кодирование на 4 байта.

Другие техники

snowflake: Использует время(41) + уникальный идентификатор(10) + последовательность(12).
Плюс: Гарантированные уникальные последовательности.
Плюс: Вмещается в 63 бита.
Минус: Требует координации уникальных идентификаторов для каждого сервера - 16 рабочих процессов на хост означает ограничение в 64 экземпляра nginx.
Минус: Только 11 бит доступно для уникального идентификатора, требует мониторинга.
Минус: Полная сортировка возможна только в одном процессе.
Минус: Возможны перебои в обслуживании, когда часы теряют синхронизацию.
flake: Использует время + mac id + последовательность.
Плюс: Гарантированные уникальные последовательности.
Минус: Использует 128 бит.
Минус: Тратит 22 бита данных временной метки.
Минус: Только один процесс на хосте может генерировать идентификаторы - требуется синхронизация доступа к последовательности от каждого рабочего процесса.
Минус: Возможны перебои в обслуживании, когда часы теряют синхронизацию.
Минус: Семена кросс-платформенного поиска MAC-адресов.
UUIDv4: 122 бита энтропии.
Плюс: Очень низкая вероятность столкновения.
Минус: Не сортируемый.
UUID с временной меткой: 48 бит времени + 74 бита энтропии.
Плюс: Очень низкая вероятность столкновения.
Минус: Строковое представление не является временно локальным.
httpd mod_unique_id: Host ip(32) + pid(32) + time(32) + sequence (16) + thread id (32).
Плюс: Детерминированный.
Минус: Использует 144 бита.
Минус: Предполагает уникальный IPv4 для интерфейса имени хоста.
Минус: Не сортируемое чувствительное к регистру пользовательское представление - base64 с пользовательским алфавитом.
Минус: Жесткое ограничение в 65535 идентификаторов в секунду на pid - небольшая толерантность к шагам часов.

Разработка

После клонирования репозитория можно использовать Docker для запуска тестового набора:

docker-compose run --rm app make test

Процесс релиза

Чтобы опубликовать релизы в OPM и LuaRocks:

VERSION=x.x.x make release

GitHub

Вы можете найти дополнительные советы по конфигурации и документацию для этого модуля в репозитории GitHub для nginx-module-txid.