Skip to content

TASK.md

Latest commit

 

History

History
156 lines (118 loc) · 11.7 KB

TASK.md

File metadata and controls

156 lines (118 loc) · 11.7 KB
Raw

Задача: генератор идентификаторов Twitter Snowflake

Легенда

В ходе курса мы шаг за шагом построим собственное хранилище данных — небольшую базу, в которую можно складывать записи и потом быстро находить их по ключу. Начнём с фундамента: у каждой записи должен быть уникальный идентификатор.

Казалось бы, можно просто нумеровать записи 1, 2, 3, … Пока хранилище живёт на одной машине, так и происходит. Но реальные системы почти всегда распределены: записи создаются на десятках серверов одновременно. Тогда возникают проблемы:

  • единый счётчик становится «бутылочным горлышком»: каждому серверу приходится обращаться к нему за очередным номером;
  • если серверы нумеруют записи независимо друг от друга, идентификаторы неизбежно начнут совпадать;
  • случайные идентификаторы (например, UUID) не совпадают, но плохо упорядочены: по ним нельзя понять, какая запись появилась раньше, а индексы по таким ключам работают медленнее.

В 2010 году с этой же проблемой столкнулся Twitter: твиты создавались сотнями тысяч в секунду на множестве машин, а идентификаторы должны были быть уникальными, компактными (помещаться в 64 бита) и примерно упорядоченными по времени. Решение получило название Snowflake («снежинка» — как и снежинки, такие идентификаторы не повторяются). Идея проста: вместо одного числа-счётчика упаковать в одно целое несколько независимых величин, и тогда серверам не нужно договариваться друг с другом.

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

Контекст

Нужно реализовать генератор 64-битных числовых идентификаторов в стиле Twitter Snowflake. Такие идентификаторы примерно упорядочены по времени и могут выдаваться разными узлами без какой-либо координации между ними. Каждый идентификатор объединяет в одном целом положительном числе три величины:

  • сколько миллисекунд прошло с некоторого «нулевого момента» (пользовательской эпохи);
  • номер узла, который выдал идентификатор;
  • порядковый номер идентификатора внутри одной миллисекунды.

Реализация состоит из двух модулей: constants.py (формат идентификатора и значения по умолчанию) и snowflake.py (генерация и разбор идентификаторов).

Формат идентификатора

Идентификатор — целое число, которое всегда неотрицательно и помещается в знаковый 64-битный тип. Логически оно состоит из четырёх частей, перечисленных от старших разрядов к младшим:

Часть Ёмкость Что хранит
знаковый разряд 1 бит всегда 0 — идентификатор положительный
метка времени 41 бит число миллисекунд, прошедших с момента пользовательской эпохи
номер узла 10 бит идентификатор машины, выдавшей идентификатор
счётчик последовательности 12 бит порядковый номер идентификатора в пределах одной миллисекунды

Из ёмкости каждой части вытекает диапазон допустимых значений: часть шириной n бит вмещает значения от 0 до 2**n - 1 включительно.

Модуль constants.py

Необходимо определить следующие константы:

  • EPOCH_MS_DEFAULT — пользовательская эпоха по умолчанию, заданная в миллисекундах Unix-времени. Значение — оригинальная эпоха Twitter, 2010-11-04 01:42:54.657 UTC, то есть 1288834974657.
  • NODE_ID_DEFAULT — номер узла, который используется, когда вызывающий код не передал свой. Значение — 1.
  • TIMESTAMP_BITS, NODE_ID_BITS, SEQUENCE_ID_BITS — ёмкости соответствующих частей идентификатора в битах: 41, 10 и 12.
  • TIMESTAMP_MS_MAX, NODE_ID_MAX, SEQUENCE_ID_MAX — наибольшее значение, которое помещается в соответствующую часть; вычисляются из её ёмкости, а не задаются числом напрямую.

Любые дополнительные вспомогательные константы, которые понадобятся вам для сборки и разбора идентификатора, добавьте на своё усмотрение. Изменение любой из ёмкостей *_BITS должно автоматически согласованно менять зависящие от неё константы.

Модуль snowflake.py

read_current_millis(epoch_ms: int) -> int

  • Вход: epoch_ms — момент пользовательской эпохи в миллисекундах Unix-времени.
  • Выход: число целых миллисекунд, прошедших между epoch_ms и текущим моментом.

decode_timestamp_ms(snowflake_id: int, epoch_ms: int = EPOCH_MS_DEFAULT) -> int

  • Вход: snowflake_id — ранее сгенерированный идентификатор; epoch_ms — эпоха, относительно которой он был создан (по умолчанию EPOCH_MS_DEFAULT).
  • Выход: абсолютное Unix-время в миллисекундах, в которое был создан идентификатор, то есть хранящаяся в нём метка времени плюс epoch_ms.

decode_node_id(snowflake_id: int) -> int

  • Вход: идентификатор.
  • Выход: номер узла, записанный в идентификаторе. Всегда в диапазоне [0, NODE_ID_MAX].

decode_sequence_id(snowflake_id: int) -> int

  • Вход: идентификатор.
  • Выход: счётчик последовательности, записанный в идентификаторе. Всегда в диапазоне [0, SEQUENCE_ID_MAX].

generate_snowflake_id(sequence_id: int, node_id: int = NODE_ID_DEFAULT, epoch_ms: int = EPOCH_MS_DEFAULT) -> int | None

Собирает идентификатор для текущей миллисекунды.

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

Входные параметры:

  • sequence_id — счётчик в пределах миллисекунды; ожидается в диапазоне [0, SEQUENCE_ID_MAX].
  • node_id — номер текущего узла; ожидается в диапазоне [0, NODE_ID_MAX]. Необязательный, по умолчанию NODE_ID_DEFAULT.
  • epoch_ms — начало эпохи в миллисекундах Unix-времени. Необязательный, по умолчанию EPOCH_MS_DEFAULT.

Поведение и результат. Проверки выполняются в перечисленном порядке; при первой же неудачной проверке остальные не выполняются, в stdout печатается поясняющее сообщение и функция возвращает None:

  1. Если node_id вне [0, NODE_ID_MAX] — сообщение содержит текст node_id must be in, с указанием допустимого диапазона и полученного значения.
  2. Иначе если sequence_id вне [0, SEQUENCE_ID_MAX] — сообщение содержит текст sequence_id must be in, с указанием допустимого диапазона и полученного значения.
  3. Иначе вычисляется число миллисекунд, прошедших с эпохи. Если оно превышает TIMESTAMP_MS_MAX (то есть с момента эпохи прошло больше ~69 лет) — сообщение содержит слово overflows.

Если все проверки пройдены, функция возвращает идентификатор — положительное целое, помещающееся в знаковый 64-битный тип (0 < id < 2**63), в котором закодированы текущая метка времени, node_id и sequence_id.

Взаимная обратимость

Для любого набора аргументов, на котором generate_snowflake_id возвращает не None, декодеры возвращают исходные значения:

  • decode_node_id(generate_snowflake_id(s, n, e)) == n
  • decode_sequence_id(generate_snowflake_id(s, n, e)) == s
  • decode_timestamp_ms(generate_snowflake_id(s, n, e), e) равно абсолютному Unix-времени того момента, в который был вызван генератор.