Skip to content

TASK.md

Latest commit

 

History

History
557 lines (441 loc) · 38.1 KB

TASK.md

File metadata and controls

557 lines (441 loc) · 38.1 KB
Raw

Задача: Snowflake-идентификаторы для интернет-магазина

Легенда

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

  • UUID — случайная строка из 36 символов: по ней нельзя понять, какой товар появился раньше, а ключи, которые хотя бы примерно растут со временем, хранить и сравнивать дешевле;
  • Snowflake из части 1 решает эту проблему, но generate_snowflake_id не запоминала, сколько идентификаторов уже выдано в текущую миллисекунду: номер внутри миллисекунды (sequence_id) приходилось передавать ей аргументом. Если товары создаются в нескольких местах программы, каждому месту пришлось бы вести свой счётчик, и два места легко выдали бы одинаковые идентификаторы;
  • мы совсем не видим, как используется наше хранилище: какие операции выполняются чаще всего и сколько вызовов заканчиваются неудачей.

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

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

Контекст

Часть 5 продолжает часть 4: тот же интернет-магазин, то же хранилище-словарь, тот же индекс имён, те же CRUD-операции, те же операции с корзиной и консоль администратора. Меняется источник идентификаторов. Вместо случайного UUID (строки) товар получает целое число в формате Twitter Snowflake: оно растёт со временем создания, поэтому товары примерно упорядочены по порядку добавления.

Модули constants.py и snowflake.py переходят из части 1. Формат идентификатора, константы, read_current_millis и три декодера остаются прежними. Что меняется:

  • в snowflake.py функция generate_snowflake_id(sequence_id, node_id, epoch_ms), где счётчик внутри миллисекунды вёл вызывающий код, заменяется функцией get_snowflake_id_generator(node_id, epoch_ms). Она возвращает другую функцию без аргументов, при каждом вызове которой получается новый идентификатор. Счётчик внутри миллисекунды эта функция ведёт сама;
  • create_product больше не вызывает функцию генерации идентификатора напрямую: раньше она была жёстко прописана в его теле, теперь её передают аргументом generate_id. Так алгоритм выдачи идентификаторов можно заменить, не трогая код самой операции;
  • идентификатор товара — int, а не str. Это касается хранилища, корзины, консоли и всех сигнатур;
  • в crud.py появляется функция generate_snowflake_id(): она выдаёт Snowflake-идентификаторы через общий генератор модуля и подходит в качестве аргумента generate_id для create_product. Функция generate_product_id, выдававшая UUID в части 4, удаляется.

Кроме смены идентификаторов, в части 5 появляется учёт статистики вызовов:

  • новый модуль decorators.py с параметрическим декоратором collect_stats, который считает, сколько раз декорируемая функция отработала успешно, а сколько раз неуспешно. Счётчики он складывает в общий словарь — реестр;
  • четыре операции crud.py (create_product, read_product, update_product, delete_product) обёрнуты этим декоратором, а их счётчики лежат в реестре STATS_REGISTRY;
  • в utils.py появляется функция get_stats_str_representation: она берёт реестр STATS_REGISTRY и возвращает строку с текстовой таблицей в том же формате, что и таблица товаров из части 3. В таблице одна строка на операцию: сколько вызовов было успешных, сколько неуспешных и какую долю составляют успешные;
  • в консоли администратора появляется команда stats, которая выводит на экран таблицу статистики, полученную из get_stats_str_representation.

Если поведение не менялось, оно здесь не расписывается: реализуйте его так, как в своём решении части 4, см. описание части 4. Это относится к формату записи товара, индексу имён, нормализации имён и цен и порядку шагов в update_product, delete_product, read_product и в корзине. Единственное изменение в этих местах — тип идентификатора.

Формат идентификатора и модуль constants.py

Без изменений относительно части 1: идентификатор — положительное целое число, меньшее 2**63. В него упакованы три поля: время (41 бит), номер узла (10 бит) и счётчик внутри миллисекунды (12 бит). Константы те же: EPOCH_MS_DEFAULT, NODE_ID_DEFAULT, TIMESTAMP_BITS, NODE_ID_BITS, SEQUENCE_ID_BITS, TIMESTAMP_MS_MAX, NODE_ID_MAX, SEQUENCE_ID_MAX, с теми же значениями и правилом «максимумы выводятся из ширин».

Модуль snowflake.py

Функции read_current_millis(epoch_ms), decode_timestamp_ms(snowflake_id, epoch_ms), decode_node_id(snowflake_id) и decode_sequence_id(snowflake_id) остаются такими же, как в части 1.

Текущее время нужно получать с помощью модуля time из стандартной библиотеки.

Функция generate_snowflake_id из части 1 больше не нужна: вместо неё get_snowflake_id_generator, описанная ниже.

get_snowflake_id_generator(node_id: int = NODE_ID_DEFAULT, epoch_ms: int = EPOCH_MS_DEFAULT) -> Callable[[], int | None] | None

Один раз проверяет настройки и возвращает функцию без аргументов, которую дальше называем генератором. Каждый вызов генератора выдаёт следующий идентификатор.

По сравнению с частью 1 проверка node_id теперь выполняется при создании генератора, а не при выдаче идентификатора. Появилась новая проверка эпохи. Проверка sequence_id превратилась в проверку «счётчик исчерпан», потому что счётчик теперь ведёт сам генератор.

  • Вход: node_id — номер машины, от 0 до NODE_ID_MAX включительно; epoch_ms — эпоха в миллисекундах Unix. Оба аргумента необязательные, значения по умолчанию — NODE_ID_DEFAULT и EPOCH_MS_DEFAULT.
  • Выход: генератор или None.

Проверки при создании идут в таком порядке. Создание генератора не выдаёт ни одного идентификатора и ничего не печатает, если настройки верные.

  1. node_id вне [0, NODE_ID_MAX]. Верхняя граница включается, значит NODE_ID_MAX ещё допустим, а -1 и NODE_ID_MAX + 1 нет. Печатается node_id must be in [0, <NODE_ID_MAX>], got <node_id>, возвращается None.
  2. Эпоха лежит в будущем, то есть read_current_millis(epoch_ms) < 0. Печатается epoch_ms must not be in the future, got <epoch_ms>, возвращается None. Эпоха ровно «сейчас» допустима.

Что выдаёт генератор

Каждый вызов генератора возвращает новый идентификатор в формате Snowflake ID (см. часть 1). Время в нём отсчитывается от epoch_ms, номер узла равен node_id генератора.

  • Под счётчиком здесь понимается sequence_id — порядковый номер идентификатора внутри одной миллисекунды (последняя часть Snowflake ID).
  • Первый идентификатор в миллисекунде получает sequence_id = 0, каждый следующий в той же миллисекунде на единицу больше. В новой миллисекунде sequence_id снова начинается с 0.
  • В одной миллисекунде можно получить SEQUENCE_ID_MAX + 1 разных идентификаторов, по одному на каждое значение sequence_id.
  • Каждый генератор ведёт свой счёт, генераторы не влияют друг на друга.

Особые случаи при вызове, в порядке проверок. Во всех случаях печатается сообщение и возвращается None:

  1. Счётчик исчерпан. В одной миллисекунде запросили больше, чем SEQUENCE_ID_MAX + 1 идентификаторов. Каждый лишний вызов печатает sequence_id must be in [0, <SEQUENCE_ID_MAX>], got <sequence_id>, где <sequence_id> — номер, до которого дошёл бы счётчик. В следующей миллисекунде генератор снова выдаёт идентификаторы, начиная со счётчика 0.
  2. Время не помещается в поле. От эпохи прошло больше TIMESTAMP_MS_MAX миллисекунд. Печатается timestamp <прошло> ms overflows <TIMESTAMP_MS_MAX> ms, где <прошло> — число миллисекунд от эпохи до текущего момента. Если прошло ровно TIMESTAMP_MS_MAX, идентификатор ещё выдаётся.

Примеры

Генератор создаётся один раз, дальше его только вызывают.

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

Два вызова подряд, попавшие в одну и ту же миллисекунду. Номер узла у них одинаковый, а счётчик внутри миллисекунды растёт с нуля:

generate_id = get_snowflake_id_generator(node_id=5)

first = generate_id()
second = generate_id()

print(first)                                           # 2119399534088966144
print(second)                                          # 2119399534088966145

print(decode_timestamp_ms(first, EPOCH_MS_DEFAULT))    # 1794139200123
print(decode_timestamp_ms(second, EPOCH_MS_DEFAULT))   # 1794139200123
print(decode_node_id(first))                           # 5
print(decode_node_id(second))                          # 5
print(decode_sequence_id(first))                       # 0
print(decode_sequence_id(second))                      # 1

Если следующий вызов пришёлся уже на следующую миллисекунду, время в идентификаторе увеличивается, а счётчик снова начинается с нуля:

third = generate_id()

print(third)                                           # 2119399534093160448
print(decode_timestamp_ms(third, EPOCH_MS_DEFAULT))    # 1794139200124
print(decode_sequence_id(third))                       # 0

Генераторы не влияют друг на друга: у каждого свой счётчик и свой номер узла.

generate_a = get_snowflake_id_generator(node_id=1)
generate_b = get_snowflake_id_generator(node_id=2)

print(generate_a())   # 2119399534101532672  (узел 1, счётчик 0)
print(generate_b())   # 2119399534101536768  (узел 2, счётчик 0)

Неверные настройки отвергаются при создании, до выдачи какого-либо идентификатора:

generator = get_snowflake_id_generator(node_id=NODE_ID_MAX + 1)
# сама функция напечатает: node_id must be in [0, 1023], got 1024

print(generator)   # None

Модуль decorators.py

В модуле определён один декоратор, который считает успешные и неуспешные вызовы функции. Он ничего не знает о магазине: подойдёт любая функция, которая возвращает значение либо None.

Типы и константы

  • SUCCESS_KEY = "success" и FAILS_KEY = "fails" — имена двух счётчиков внутри записи статистики.
  • Stats — псевдоним типа dict[str, int]: счётчики одной функции. В записи ровно два ключа, SUCCESS_KEY (число успешных вызовов) и FAILS_KEY (число неуспешных).
  • Registry — псевдоним типа dict[str, Stats]: счётчики всех функций, ключ — имя, под которым функцию зарегистрировали (например, имя консольной команды).

collect_stats(key: str, registry: Registry) -> Callable

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

registry = {}

@collect_stats("divide", registry)
def divide(a, b):
    if b == 0:
        print("division by zero")
        return None
    return a / b

print(registry)          # {'divide': {'success': 0, 'fails': 0}}

print(divide(10, 4))     # 2.5
print(divide(0, 5))      # 0.0 (ложный результат, но не None: считается успехом)
print(divide(1, 0))      # division by zero (печатает сама divide)
                         # None

print(registry)          # {'divide': {'success': 2, 'fails': 1}}
  • Вход: key — ключ в реестре, под которым будут лежать счётчики этой функции; registry — словарь, в который будут попадать счётчики. Он меняется на месте при декорировании и при каждом вызове.
  • Выход: декоратор для функции, возвращающей значение либо None.

При декорировании в registry[key] кладётся новая запись {"success": 0, "fails": 0}.

При каждом вызове обёртка вызывает исходную функцию с теми же позиционными и именованными аргументами и возвращает её результат без изменений:

  • если функция вернула None, счётчик FAILS_KEY растёт на единицу;
  • любой другой результат растит SUCCESS_KEY, в том числе «ложный», такой как 0.

После декорирования метаинформация функции не должна измениться: например, имя (__name__) и описание (__doc__) остаются такими же, как у исходной функции.

Ключ уже занят. Если key уже есть в registry, при декорировании печатается stats key <key> is already registered (ключ в виде repr, например stats key 'create' is already registered), а в качестве результата возвращается сама исходная функция без обёртки. Существующая запись реестра остаётся как была. Вызовы такой функции ни в какие счётчики не попадают.

Разные ключи ведут независимые счётчики, даже если лежат в одном реестре.

Модуль crud.py

Статистика операций

  • STATS_REGISTRY: Registry — модульный реестр счётчиков. Живёт столько же, сколько процесс, и общий для всех хранилищ.

  • CREATE_KEY = "create", READ_KEY = "read", UPDATE_KEY = "update", DELETE_KEY = "delete" — ключи записей в реестре. Они совпадают с именами консольных команд.

  • Функции create_product, read_product, update_product и delete_product декорируются collect_stats: каждая со своим ключом (CREATE_KEY, READ_KEY, UPDATE_KEY, DELETE_KEY) и общим реестром STATS_REGISTRY. Поэтому сразу после импорта модуля STATS_REGISTRY содержит ровно четыре записи, по одной на операцию, и во всех записях счётчики нулевые:

    print(STATS_REGISTRY)
# {'create': {'success': 0, 'fails': 0},
#  'read':   {'success': 0, 'fails': 0},
#  'update': {'success': 0, 'fails': 0},
#  'delete': {'success': 0, 'fails': 0}}

    Вызов операции считается неуспешным, когда она вернула None, то есть напечатала сообщение и ничего не изменила.

  • generate_snowflake_id декоратором не оборачивается: её вызовы не меняют ни одной записи реестра.

  • Функции корзины (add_to_cart и remove_from_cart) не декорируются: отдельной статистики у корзины нет.

generate_snowflake_id() -> int | None

Адаптер между create_product и результатом get_snowflake_id_generator из snowflake.py. create_product ожидает функцию без аргументов, которая возвращает идентификатор или None. Но get_snowflake_id_generator при некорректных настройках возвращает не функцию, а None, и такой результат нельзя передать в create_product напрямую: вызов None приведёт к ошибке. Поэтому между ними нужен адаптер: generate_snowflake_id всегда остаётся вызываемой функцией, и create_product может вызывать её одинаково, независимо от того, получился ли у get_snowflake_id_generator рабочий генератор или None. Для этого она обращается к общему (глобальному) генератору модуля и возвращает то, что он выдал, а если значение глобального генератора — None, возвращает None.

В модуле crud.py один раз, при импорте, создаётся общий генератор: результат get_snowflake_id_generator() с номером узла и эпохой по умолчанию. Имя переменной, в которой он хранится, на ваше усмотрение. Функция generate_snowflake_id использует этот созданный генератор напрямую: вызывает его сама и не создаёт других.

  • Вход: ничего.
  • Выход:
    • если значение общего генератора не None, то результат его вызова, без изменений. Это либо идентификатор (целое число больше нуля и меньше 2**63), либо None, если генератор не смог выдать идентификатор (счётчик исчерпан или время не помещается в поле). В последнем случае сообщение печатает сам генератор;
    • если значение общего генератора — None, то None. Сама generate_snowflake_id при этом ничего не печатает: сообщение уже было напечатано при создании генератора.

Все вызовы идут через один общий генератор на модуль. Поэтому идентификаторы из разных вызовов различаются между собой и растут. Создавать свой генератор на каждый вызов нельзя: два вызова в одну миллисекунду дали бы одинаковые значения.

Примеры

Как и раньше, числа зависят от времени и у вас будут другими.

Значение общего генератора не None (так бывает при настройках по умолчанию). Номер узла равен NODE_ID_DEFAULT, то есть 1, а счётчик растёт с каждым вызовом в пределах одной миллисекунды:

first = generate_snowflake_id()
second = generate_snowflake_id()

print(first)                        # 2119399534101532672
print(second)                       # 2119399534101532673
print(decode_node_id(first))        # 1
print(decode_sequence_id(first))    # 0
print(decode_sequence_id(second))   # 1

Значение общего генератора — None. Допустим, при импорте модуля настройки по умолчанию оказались некорректными (например, NODE_ID_DEFAULT вышел за пределы [0, NODE_ID_MAX]). Тогда при импорте один раз напечатается node_id must be in [0, 1023], got 1024, а общий генератор станет None. Каждый следующий вызов generate_snowflake_id возвращает None и ничего не печатает:

print(generate_snowflake_id())   # None
print(generate_snowflake_id())   # None

В этом случае create_product(..., generate_id=generate_snowflake_id) тоже вернёт None и не изменит ни хранилище, ни индекс имён.

create_product(storage: dict[int, Product], product_names: set[str], fields: dict[str, Any], generate_id: Callable[[], int | None]) -> int | None

  • Вход: хранилище, индекс имён, fields (все три ключа NAME_KEY, PRICE_KEY, QUANTITY_KEY обязательны, как в части 4) и функция без аргументов generate_id, которая возвращает идентификатор нового товара или None, если не смогла его выдать.
  • Выход: идентификатор, который вернул generate_id, либо None.

Функция выполняет шаги в таком порядке. Если на каком-то шаге вернулся None, хранилище и индекс не меняются:

  1. Имя нормализуется. Если оно пустое, печатается product name must not be blank и возвращается None.
  2. Если нормализованное имя уже есть в product_names, печатается product name '<имя>' is already taken и возвращается None.
  3. Вызывается generate_id(). Если вернулось None, create_product возвращает None и сама ничего не печатает: сообщение уже напечатал generate_id.
  4. Иначе запись {name: нормализованное имя, price: normalize_price(цена), quantity: количество} кладётся в storage под полученным идентификатором, имя добавляется в product_names, возвращается идентификатор.

generate_id вызывается один раз на каждый создаваемый товар и только после шагов 1 и 2: если создание отклонено из-за имени, идентификатор не выдаётся.

read_product, update_product, delete_product

Поведение, сообщения и порядок шагов — как в части 4. Меняются только сигнатуры: идентификатор product_id теперь int, хранилище — dict[int, Product]. delete_product возвращает int | None. Сообщение об отсутствующем товаре по-прежнему содержит идентификатор: no product with id <id>.

Модуль cart.py

Поведение, порядок шагов и сообщения — как в части 4. Меняются только типы: идентификатор товара — int, корзина — cart: dict[int, int], хранилище — dict[int, Product]. Обе функции по-прежнему возвращают количество единиц товара в корзине после операции либо None, а сообщения об ошибках содержат идентификатор товара.

Модуль utils.py

normalize_price, normalize_product_name, PRICE_PRECISION, PRICE_STEP и TABLE_HEADERS — как в части 4. Типы изменились: get_storage_str_representation принимает dict[int, Product]. В столбец ID идентификатор попадает как десятичное число. Ширина столбца считается по самому длинному значению, включая идентификаторы Snowflake из 19 цифр, например 1288834974657000001.

Добавляется функционал для построения таблицы со статистикой. Эта таблица оформляется так же, как таблица товаров: формат, выравнивание, ширина столбцов и вид пустой таблицы описаны в части 3. Заголовки столбцов — кортеж STATS_TABLE_HEADERS = ("command name", "success", "fails", "success rate").

get_stats_str_representation(registry: Registry) -> str

  • Вход: registry — реестр счётчиков (см. decorators.py).
  • Выход: многострочная строка без завершающего перевода строки: строка заголовков, разделительная строка и по одной строке на каждую запись реестра в порядке вставки. Для пустого реестра остаются только первые две строки, ширина столбцов равна ширине заголовков.

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

Доля успешных вызовов — это число успешных вызовов, делённое на число всех вызовов, в процентах, ровно с двумя знаками после запятой и знаком %, с округлением до ближайшего (66.67%, 100.00%, 3.23%). Команда, которую ни разу не вызывали, получает 0.00%, а не ошибку.

| command name | success | fails | success rate |
|--------------|---------|-------|--------------|
| create       | 2       | 1     | 66.67%       |
| read         | 0       | 0     | 0.00%        |
| delete       | 5       | 0     | 100.00%      |

Длинное имя команды расширяет свой столбец:

| command name            | success | fails | success rate |
|-------------------------|---------|-------|--------------|
| update-everything-twice | 1       | 30    | 3.23%        |

Модуль run_admin.py

Набор команд, формат ввода, константы PROMPT и HELP_TEXT, функции show_help и print_result, сообщение '<строка>' is not a command — как в части 4. Отличия:

  • create <имя...> <цена> <количество> передаёт в create_product generate_snowflake_id из crud.py. Напечатанный идентификатор — целое число, а его поле времени (decode_timestamp_ms) совпадает с моментом создания товара с точностью до нескольких секунд.

  • <id> в командах read, update и delete теперь приводится к int, в отличие от части 4, где оно оставалось строкой.

  • Тип хранилища — dict[int, Product]. main() создаёт пустое хранилище и пустой индекс, как в части 4.

  • Новая команда stats (ровно одно слово в строке) печатает get_stats_str_representation(STATS_REGISTRY): статистику четырёх CRUD-команд за всё время работы процесса. Хранилище и индекс команда не меняет. Строка stats с лишними словами (например, stats create) командой не считается: для неё печатается '<строка>' is not a command.

  • В HELP_TEXT добавляется строка про stats: она идёт последней в перечне команд, сразу после delete. Остальной текст справки прежний. Пример справки целиком:

    Available commands:
  help                                       show this message
  exit                                       leave the console
  show                                       print the whole store as a table
  create <name...> <price> <quantity>        add a product, print its new id
  read <id>                                  print the product with that id
  update <id> <name...> <price> <quantity>   overwrite that product's fields
  delete <id>                                remove the product with that id
  stats                                      print call statistics of the CRUD commands

For create and update the price and quantity are the last two words of the
line; everything before them is the product name, so it may contain spaces
(for example "Gibson SG Junior") and needs no quoting.

  • Счётчики ведёт слой crud.py, а не консоль. Поэтому create, read, update и delete попадают в статистику по результату вызова соответствующей операции. Строка, чьи аргументы не разобрались (ValueError или InvalidOperation вылетели ещё до обращения к crud.py), в статистику не попадает.

Инварианты

  • Три поля идентификатора восстанавливаются обратно: если генератор с номером n и эпохой e выдал идентификатор в момент t, то decode_node_id даёт n, decode_timestamp_ms(id, e) даёт t, а decode_sequence_id даёт номер вызова внутри этой миллисекунды, начиная с нуля.
  • Идентификатор положителен и меньше 2**63.
  • Идентификаторы одного генератора на реальных часах все разные и идут по возрастанию.
  • product_names всегда равно {запись["name"] for запись in storage.values()} (см. часть 4). Неуспешный вызов, в том числе отказ generate_id, не меняет ни хранилище, ни индекс.
  • После успешного create_product товар лежит в storage под идентификатором, который вернула функция.
  • Сумма «на складе + в корзине» для каждого товара сохраняется при add_to_cart и remove_from_cart (см. часть 4).
  • Каждый вызов декорированной операции добавляет ровно единицу ровно к одному счётчику: fails, если вернулся None, иначе success. Результат операции и состояние хранилища от подсчёта не зависят.
  • Повторная регистрация занятого ключа не меняет ни существующую запись, ни поведение вторично декорированной функции.
  • Выдача идентификатора через generate_snowflake_id реестр не меняет.