bucketer

Стабильное детерминированное распределение по бакетам для процентных выкаток фича-флагов - как в Unleash, Flagsmith и LaunchDarkly.

Процентную выкатку нельзя делать случайным числом: пользователь начнёт «мигать» между старым и новым поведением на каждом запросе. Здесь номер бакета - чистая функция от ключа флага и ключа пользователя, поэтому ответ одинаков на всех узлах кластера, во всех процессах и после любого перезапуска. Хранить состояние не нужно.

 "new-checkout" : "user-42"

|------------------------|
   MurmurHash3 x86_32
            |
            v
   позиция 0..99  →  включён, если позиция < процента выкатки

  выкатка  5%  ████
          25%  ████████████████████
         100%  ████████████████████████████████████████████████

Главное свойство: при увеличении процента множество включённых только растёт. Пользователь, попавший в первые 5%, останется включённым и на 25%, и на 100% - выкатку можно расширять, ничего не ломая, и откатывать назад тем же путём.

Установка

opm install bucketer

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

Процентная выкатка

#Использовать bucketer

Если Bucketer.ВключенДляПроцента("new-checkout", ИдентификаторПользователя, 25) Тогда
    НовыйОформитель();
Иначе
    СтарыйОформитель();
КонецЕсли;

Один и тот же пользователь всегда получает один и тот же ответ, а на 10 000 пользователей включёнными окажутся примерно 2500 - распределение равномерное.

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

Позиция = Bucketer.Процент("new-checkout", "user-42");   // 0..99

// Больше делений, чем сто, - для тонких выкаток или шардирования
Шард = Bucketer.Бакет("очередь-отчётов", "user-42", 16); // 0..15

Мультиварианты

Варианты = Новый Массив();
Варианты.Добавить(Новый Структура("Имя, Вес", "control",   50));
Варианты.Добавить(Новый Структура("Имя, Вес", "variant-a", 30));
Варианты.Добавить(Новый Структура("Имя, Вес", "variant-b", 20));

Вариант = Bucketer.ВыбратьВариант("checkout-experiment", ИдентификаторПользователя, Варианты);

Веса - целые неотрицательные числа. Сумма не обязана равняться 100: 1 и 1 дадут те же 50/50, что 50 и 50. Вариант с нулевым весом не выбирается никогда.

Когда сумма весов равна 100, выбор совпадает со шкалой процентов: первый вариант с весом 30 получает ровно тех, у кого Процент() меньше 30. Это позволяет заменить процентную выкатку мультивариантом без перетасовки пользователей.

Независимые эксперименты

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

ВтораяВолна = Bucketer.СоздатьБакетизатор(20260804);

ВтораяВолна.ВключенДляПроцента("new-checkout", ИдентификаторПользователя, 25);

Публичный API

Модуль Bucketer

Метод	Возвращает	Описание
Бакет(КлючФлага, КлючТаргетинга, КоличествоБакетов = 100)	Число	Номер бакета 0..КоличествоБакетов-1
Процент(КлючФлага, КлючТаргетинга)	Число	Позиция на шкале выкатки, 0..99
ВключенДляПроцента(КлючФлага, КлючТаргетинга, ПроцентВыкатки)	Булево	Попадает ли ключ в выкатку 0..100
ВыбратьВариант(КлючФлага, КлючТаргетинга, Варианты)	Произвольный	Имя варианта, выбранного по весам
ХешСтроки(Значение, Соль = 0)	Число	MurmurHash3 x86_32, 0..4294967295
СоздатьБакетизатор(Соль)	SaltedBucketer	Bucketer с фиксированной солью

Класс SaltedBucketer

Бакет(КлючФлага, КлючТаргетинга, КоличествоБакетов = 100), Процент(КлючФлага, КлючТаргетинга), ВключенДляПроцента(КлючФлага, КлючТаргетинга, ПроцентВыкатки), ВыбратьВариант(КлючФлага, КлючТаргетинга, Варианты), ХешСтроки(Значение).

Те же методы, что у модуля, но с солью, заданной при создании. Соль подмешивается как начальное состояние хеша (seed), поэтому разные соли дают независимые распределения. Модуль Bucketer - это тот же бакетизатор с солью 0.

Ключи принимаются строками, числами и УникальныйИдентификатор. Числа приводятся к строке без разделителей групп, поэтому 12345 и "12345" попадают в один бакет независимо от региональных настроек.

Ошибки: процент выкатки вне 0..100, количество бакетов меньше единицы или нецелое, соль вне 0..4294967295, пустой список вариантов, нулевая сумма весов, отрицательный или нецелый вес, ключ неподдерживаемого типа.

Алгоритм

Хешируется строка КлючФлага + ":" + КлючТаргетинга, закодированная в UTF-8. Хеш-функция - MurmurHash3 x86_32 Остина Эпплби, номер бакета - остаток от деления на количество бакетов:

Бакет = MurmurHash3_x86_32(КлючФлага + ":" + КлючТаргетинга, Соль) % КоличествоБакетов

• Реализация побайтово совпадает с референсной: те же значения дают C++, Java, Go и Python (mmh3). Бакет, посчитанный в OneScript, совпадает с бакетом, посчитанным по той же формуле в другом сервисе, - фича включается для пользователя одновременно везде.
• Формула совпадает с градуальной выкаткой Unleash, где КлючФлага - это groupId, а КлючТаргетинга - userId. Unleash считает (хеш % 100) + 1 и включает при значение <= процент, что тождественно нашему Процент() < ПроцентВыкатки. Для вариантов Unleash берёт отдельную соль 86028157 - её можно задать через СоздатьБакетизатор(86028157).
• MurmurHash3 хорошо рассеивает биты, поэтому последовательные идентификаторы (user-41, user-42) расходятся по далёким бакетам и не собираются в один диапазон.
• Функция быстрая и не криптографическая. Бакет предсказуем для того, кто знает ключи, поэтому распределение нельзя использовать как секрет - только как выкатку.
• Позиция ключа не зависит от размера выкатки, поэтому ВключенДляПроцента монотонен по проценту: рост процента только добавляет пользователей. 0% не включает никого, 100% - всех.
• Составной ключ - простая склейка через двоеточие, как в Unleash. Поэтому пары вида ("а", ":б") и ("а:", "б") дают один и тот же бакет; на практике ключи флагов фиксированы и коллизия не встречается.

Побитовые операции платформы рассчитаны на 32-битные значения со знаком, поэтому вся 32-битная арифметика хеша собрана из операций по модулю 2³²: умножение, сложение и циклический сдвиг - чистая арифметика, а исключающее ИЛИ выполняется над 16-битными половинами. Десятичная арифметика повышенной точности OneScript представляет произведения 32-битных чисел (до 2⁶⁴) без потерь.

Тесты

opm install -l
oneunit execute -d ./tests

Реализация хеша закреплена тестовыми векторами из набора к референсной реализации: пустая строка, все длины «хвоста» (1–3 байта), многоблочные данные, нулевые байты, многобайтовый UTF-8, беззнаковые соли 1 и 0xffffffff. Свойства распределения проверяются на 10 000 ключей: равномерность по 100 бакетам, соответствие доли включённых заявленному проценту, монотонность выкатки по всей лестнице порогов, пропорциональность весов мультивариантов и отсутствие корреляции между флагами.

Лицензия

MIT