Loading...
List the key functional requirements for the system (Ask the AI for hints if stuck)...
List the key non-functional requirements (performance, scalability, reliability, etc.)...
<хотя не понимаю как они оба могут применяться если вытесняют друг друга>
Estimate the scale of the system. Consider daily active users, read/write ratio, storage requirements, bandwidth, and any relevant QPS calculations...
считаем что у нас 1000rps на создание ссылки и 1000 rps на чтение ссылки. ссылки не могут жить вечно. закладываем им сразу TTL - например 30 дней при 0 открытий. посчитаем сколько потребуется схранить ссылок в моменте: 1000 per sec * 60 per min * 60 per hour *24 per day * 30 per TTL days. но ссылок много разных и они состоят из симовлов, чтобы покрыть эти 2.5 млрда нужна минимум 6-7 символов в url... в моменте в БД чуть больше 2.5 млрд ссылок. каждая запись в БД - это id, исходный url, укороченный url и created_at.. на одном инстансе как я понял рекомендуется хранить не более 100млн записей, поэтому нужно шардирование на 25 секций...
> после ревью: количество чтений больше колчиества записей в 100 раз. тогда на 1000 rps чтений придет 100_000 чтений... значит следует:
1 - разделить сервис на 2 микросервиса - чтение и запись, можно независимо их скейлить. когда много записей - делаем сервисы на запись. чтений - на чтение...
2 - раз чтений сильно больше, стоит добавить кэш клиент, который будет внутри хранить закэшированную ссылку и не нагружать основную БД..
также момент насчет роста сервиса. предположим что он был очень популярным и вырос в 2 раза. тогда чтений уже 200_000 и записей уже 2000. количество записей в таблице - 5млрд, докинем еще 25 реплик БД, заскейлим кэш-клиент.
Define the APIs expected from the system. This is your chance to analyze and define the read and write paths so that you can come up with the high-level design...
есть 2 ручки.
POST /new {"url": {url}} и
GET / с редиректом по 301 (так работате tinyurl для улучшения индексации)
Describe the overall system architecture. Identify the main components needed to solve the problem end-to-end. Use the diagramming tool to create a block diagram.
клиент ходит в обратный прокси (для антиддоса). прокси в зависимости от API раскладывает запрос либо в shorten-service, либо redir-service. оба сервиса сначала ходят в кэш и ищут там наличие своей ссылки.. если ее там нету - то уже в БД. перед каждым сервисом стоит балансировщик нагрузки. если нагрузки много - выкатываются дополнительные поды. У БД есть шарды для распрелеоения записей, шарды имеют реплики для улучшения операций чтения.
Теперь касаемо самого алгоритма. количество вариантов самих url-ов бесокнечно, а вот само их количество вполне предсказуемо... по расчетам в один момент в БД может находиться порядка 2.5 млрда ссылок. Тогда пользователю мы можем отдавать буквенное представление идентификатора самой ссылки, которые мы будет постепенно создавать... Шарды сами следят за этим и выдают сервисам нужный ID, который они преобразуют в буквенное представление. Походы в шарды случайны (выбор случаен), а сама выдоча атомарна.
Define the data model. Identify the main entities, their attributes, and relationships. Consider the choice of database type (SQL vs NoSQL) and justify your decision based on access patterns...
Используем NOSQL базу данных ввиду большей скорости, отстуствия сложных запросов, упрощенного шардинга и горизонтального масштабирования...
Формат данных: id (ключ шардинга), original_url, shorten_url(unique index), created_at, expires_at.
expires_at обновляется ли каждом чтении ссылки (учитывая, что у нас есть уже кэш, можно сделать отдельную asynq очередь для такой операции). как только текущее время больше чем expires_at ---> БД сама отдает этот слот сервису как свободный (в хай-левел договорились о такой схеме).
> Запись ушла на мастер. Он сразу копирует короткую ссылку и открывает её у себя. Запрос на редирект уходит на реплику, которая отстаёт от мастера на 2 секунды.
Это одна из типовых проблем с репликацией. В нашем сервисе решить ее можно типовым подходом: свои данные пользователь читает только с мастер реплики. создание ссылки требует strong consistency — новая ссылка должна быть durable и не задублироваться. А редирект может жить на eventual: короткая задержка = максимум временный 404, но не порча данных.
Deep dive into 2-3 key components. Explain how they work, how they scale, discuss tradeoffs, capacity, and any relevant algorithms or data structures.