На Reddit я наткнулся на статью про обработку создания 100 тысяч коротких URL в секунду1. [Прим. пер.: автор статьи по ссылке создал три варианта системы; третий, наилучший, по его мнению, вариант при помощи кластера-координатора делит нагрузку на несколько ECS-воркеров, использует DynamoDB TransactWrite для пакетных условных вставок, а для устойчивости применяет кэш Redis.]
Какой же это запутанный оверинжиниренный бардак!
Не поймите меня неправильно: я люблю оверинжиниринг, но только в обучающих хобби-проектах. Как сказали многие комментаторы на Reddit, в образовательных учреждениях редко преподают распределённые системы и архитектуру ПО. Когда новички попадают в нашу отрасль, из-за подобных постов, написанных авторитетными на вид техлидами, они могут подумать, что оверинжиниринг — это единственный способ работы. Однако часто решение может быть гораздо проще.
Требования
В них нет ничего особо сложного. Пользователь передаёт длинный URL и получает короткий URL. Есть некоторые тонкости, например, пользователь может выбрать короткую строку, но для архитектуры в целом они не важны.
Система работает и может поддерживать 100 тысяч операций записи в секунду. Автор поста не уточнял, так что предположим, что нужен один миллион операций записи в секунду.
Отсутствие дублей длинных URL (NFR-1 исходного поста). Довольно спорное требование, о котором мы поговорим чуть ниже.
Вот примеры запроса и ответа, приведённые автором:
// Запрос:
{
"long_url": "https://example.com/very/long/url",
"custom_domain": "short.myapp.com", // Опционально
"custom_alias": "mycustomalias" // Опционально
}
// Ответ:
{
"short_url": "https://short.myapp.com/mycustomalias",
"long_url": "https://example.com/very/long/url",
"alias": "mycustomalias",
"domain": "short.myapp.com"
}Решение
Общий процесс выполнения прост:
У нас есть пользователь, серверы API, каждый из которых имеет кэш в памяти, и серверы базы данных.
Когда пользователь выполняет POST-запрос, тот попадает на один из множества серверов API, который затем выполняет запись в базу данных.
Когда пользователь делает GET-запрос, обрабатывающий запрос сервер API сначала проверяет кэш LRU и выполняет чтение из базы данных только в случае промаха кэша. Большинство GET-запросов должно обрабатываться напрямую, даже не затрагивая базу данных. Даже если по каким-то причинам возникает множество промахов кэша, то DynamoDB всё равно должна справиться с трафиком чтения (см. ниже).
Давайте разберём каждый компонент:
-
База данных:
Прикинем в уме: короткий URL + длинный URL, выделим под них суммарно щедрые 300-500 байтов. При 100 тысячах записей в секунду, допустим, мы записываем 50000 КБ/с.
Я выбрал DynamoDB, чтобы совпадать с автором статьи, но на самом деле, подойдёт любое современное надёжное хранилище ключей и значений. DynamoDB может обрабатывать 40000 КБ операций записи в секунду или 80000 КБ записей в секунду при предварительной подготовке. Мне кажется, вполне подойдёт одна большая таблица; для автора статьи она подошла.
Чтобы быть щедрыми и избыточно осторожными, расшардим данные на два инстанса DynamoDB: шардинг будет выполняться хэшированием короткого URL. Например:
hash("shorturl.com/a") => db1иhash("shorturl.com/b") => db2. Это более чем в два раза превзойдёт нужную нам производительность операций записи.
Примечание: читатели сообщили мне, что указанные выше ограничения DynamoDB просто используются по умолчанию и можно запросить у Amazon их увеличение. В таком случае вручную шардить DynamoDB не требуется. То же самое относится и к другим базам данных без встроенного шардинга.
-
Кэш LRU:
Кэш LRU — это map или словарь, для которого можно задать максимальное количество содержащихся в нём элементов. При добавлении большего количества элементов тот элемент, который используется реже всего (Least Recently Used), удаляется. В данном случае мы можем использовать его, например, для хранения в памяти миллиона запрошенных URL. Судя по моим поискам, библиотеки для реализации LRU в огромном количестве существуют для Go, C#, Python, Node, Ruby и так далее.
Сохраним то же допущение о необходимости 500 байтов на один элемент, добавим ещё памяти, например, для языков, строки которых хранятся в UTF-16, дополнительные структуры данных для работы LRU; получим, скажем, по 1 КБ на элемент. Для хранения 1 миллиона элементов в памяти нам потребуется всего 1 ГБ ОЗУ. Большинство серверов API в продакшене вполне могут хранить в пять-десять раз больше элементов.
Так как сокращение URL — это неизменяемая операция, частота попадания в кэш будет крайне высокой. Только небольшой процент GET-запросов доберётся до базы данных, и с ними легко справится DynamoDB.
-
Серверы API
При 1 миллионе запросов в секунду, когда для обработки запросов достаточно памяти, вполне хватит пяти-десяти серверов API.
При такой схеме мы можем увеличивать и уменьшать количество серверов API без особого ущерба для остальной архитектуры (например, базы данных).
Вот и всё. Этого достаточно для создания сокращателя ссылок, справляющегося с нужным автору статьи количеством запросов. Не требуется никаких сложных очередей и EC2-воркеров.
А теперь давайте поговорим о третьем требовании
В своей статье автор сформулировал нефункциональное требование (NFR-1) — каждый длинный URL может иметь только один короткий URL. Например, не может быть одновременно short.com/a и short.com/b ведущих на long.com/x. Автор уже начал менять формулировку этого требования в комментариях на Reddit2, хотя очевидно, что его схема нужна была для решения именно этой проблемы.
Во-первых, это странное требование. Ни одному сокращателю URL, с которыми я работал, такое ограничение не требовалось. Очевидно, это необходимо для экономии нескольких байтов на хранении — поздравляю, это самый глупый обмен.
-
Во-вторых, даже если нам каким-то образом потребуется удовлетворить этому требованию, в созданном автором бардаке всё равно нет никакой нужды. Ему достаточно было хранить обратную пару «ключ-значение»
longurl => shorturl. Это позволит реализовать две вещи:Иметь конкретный шард для заданного длинного URL, в котором можно проверять наличие дублей. Это позволит базе данных масштабироваться горизонтально, а не сканировать вторичные индексы каждого шарда.
Создать нужную автору отчётность, например генерацию списка всех коротких ссылок для указанного домена, разбив их лишь на небольшое количество имеющихся у нас шардов.
Комментарии (15)
totsamiynixon
12.05.2025 15:34Как ваша схема отличается от представленной в оригинале?
Если у вас есть N серверов для хостинга API, то они образуют кластер (Cluster) и возникает необходимости в балансировщике нагрузки (Coordinator), а также инстансы (Workers) - ровно как и в оригинальном решении. Рискну предположить, что API Gateway в оригинале предназначен для вывода сервиса из интранета в интернет, что вам так же так или иначе необходимо было решить. LCU в вашей архитектуре похож на in-memory кэш инстанса. Это означает, что каждый инстанс будет иметь свой собственный кэш, что может быть неэффективно как на чтение, так и на запись, особенно в случае необходимости его инвалидации (например функция "удаление ссылки" или "истечения срока ссылки"). В оригинале под кэшем подразумевается инстанс Redis, используемый в качестве распределенного кэша и для обеспечения отказоустойчивости (хотя конкретно это вызывает некоторые сомнения).
Обработку батчем мы опустим. В оригинале к ней есть вопросы.
Что касается проверки занятости короткой ссылки, то в оригинальной статье она реализована некорректно, а в вашем примере вообще отсутствует. Необходимо использовать оптимистичную конкуренцию в DynamoDB — добавлять запись только в том случае, если ключ отсутствует в базе используя
ConditionExpression. Если ключ уже занят, следует использовать в качестве ключа хэш от модифицированной ссылки, но это отдельная тема.Возвращаясь к сути вопроса: в чем принципиальная разница между вашим решением и решением, представленным в оригинальной статье?
P.S. Не заметил, что это перевод.
BugM
12.05.2025 15:34Эффективность локального инмемори кеша обеспечивается локальностью запросов. Иногда это называют прилипанием. Это типовая фича всех нормальных балансеров.
hash(url1) ->server1
hash(url2) ->server2
Ответ из мапы в памяти настолько быстр, что неравномерности нагрузки можно не бояться.
Инвалидацию обычно делают просто через ТТЛ записей в локальном кеше. Все работает само. Даже код писать не нужно обычно.
Если протекло что-то не то и локальный кеш срочно сбросить надо - рестарт поможет. Но что там такого может протечь непонятно.
totsamiynixon
12.05.2025 15:34Такой вариант возможен, но не отказоустойчив.
url1 кешируетя на Server 1; Server 1 теряет выход в сеть; мы не хотим, чтобы половина пользователей отваливалась, когда у нас отваливается одна нода, балансер по хэш ринг перекидывает запросы на Server 2; url1 попадает в кеш Server 2; пользователь удаляет/отключает/перенаправляет короткую ссылку через Server 2; Server 1 восстанавливает соединение; балансер с высокой вроятностью снова может направлять запросы url1 на Server 1. Кеш url1 уже невалиден в Server 1.
Получаем неконсистентность, которую может быть сложно отловить.
Возможные решения:позволяем серверу отвалиться и перестаем обслуживать клиентов по данному сегменту хэшей - понижает доступность = потеря денег;
выносим кеш в отдельный кластер и получаем возможность игнорировать его в случае недоступности и идти напрямую в базу - повышает косты;
делаем время жизни инмемори кеша достаточно небольшим, например, 30 секунд, чтобы даже если такое произойдет система быстро самовосстановилась - просто, с высокой вероятностью решает 99.99 кейсов, немного повышает косты;
предусмотреть мануальный ресет кеша на ноде или просто сделать ребут ноды- просто, решает 99,99%, не повышает косты, добавляет человеческий фактор или необходимость настаивать триггер по алерту;
подлючить DynamoDB DAX - косты сопоставимы с кластером кеша, но нет трат на обслуживание, соответственно косты с учетом ФОТ могут быть ниже.
koreychenko
12.05.2025 15:34В этом случае получается, что вам места под кэш нужно кратно количеству инстансов приложухи, что немного расточительно по памяти, плюс это создает дополнительную нагрузку на базу, потому что каждый инстанс приложухи будет лазить в базу, чтобы закэшировать данные у себя.
onets
12.05.2025 15:34Самый смак будет - когда удастся реализовать вообще без хранилища БД. По сути это некий алгоритм сжатия и распаковки, когда в самом коротком урл будет содержаться все что надо. Как пример - азбука Морзе.
Vorono4ka
12.05.2025 15:34Не очень понял что вы имеете в виду. По вашему описанию получится удлинитель ссылок.
Азбука Морзе занимает раза в три больше места, чем исходная информация. А также не представляет из себя ничего без алфавита.
Сжатие конечно применимо, но на небольших объемах данных и с высокой энтропией, как у ссылок по одиночке, оно будет неэффективным. Скорее всего займет столько же места, либо совсем немного меньше. Однако сжатые данные обычно являются байтами, а значит их придётся каким-то образом закодировать. Например, используя base64. И тогда получится, что хранить длинную ссылку выгоднее, чем её сжатую и закодированную версию.
onets
12.05.2025 15:34Я имел ввиду какие либо принципиально новые алгоритмы или подходы, может быть даже новое железо, типа квантовых компьютеров.
Азбука Морзе не может увеличивать в три раза. Там все буквы кодируются точкой тире (это по сути бит). Каждая буква от 1 до 4 или 5 «битов». Код символа ASCII - 1 байт или 8 бит. То есть сокращается на 50% и больше. Но в азбуке Морзе есть аналоговые паузы, которые сообщают о начале буквы. Возможно, если это подружить с нейросеткой - она научится выдергивать правильные буквы из непрерывного потока 0 и 1.
У урл ссылок тоже есть алфавит - это буквы англ алфавита и спецсимволы. Всего порядка 50-60 штук, лень точно считать.
Если даже взять 64 штуки то их можно закодировать 6 битами а не 8. Это уже сокращение на 25%. Разумеется это не совсем то, что требуется по условию задачи.
koreychenko
12.05.2025 15:34занимаясь архивированием вы только что променяли нагрузку по памяти, на нагрузку по процессору :-)
onets
12.05.2025 15:34Ничего страшного, зато меньше вызовов по сети, меньше компонентов, не нужен кэш, нет проблем с шардированием, бд потребуется только для статистики и то, если она была упомянута в требованиях. Стабильней, надежней. Масштабирование - без проблем.
mamont80
12.05.2025 15:34То что вы предлагаете - это применить алгоритмы сжатия без потерь. Изобрести здесь что-то принципиально новое невозможно. В лучшем случае можно увеличить сжатие на 5% в каких-то случаях - и это будет тянуть уже на великое научное достижение. Никакие квантовые вычисления тут не применимы, они про другое. Дальше. Да, текст хорошо сжимается, "хорошо" именно за счёт маленького словаря используемого в текстах. НО. Вам же нужно будет уменьшенный результат (в байтах, допустим на 30-50%) снова в маленький текстовый словарь допустимых в URL символов запихать, соответственно снова раздуть на ту же величину. И алгоритмы сжатия основаны на кодировании повторений, эффект будет на больших текстах, а тут только сжатие из-за словаря. В сухом остатке типичная ссылка в 100 символов после сжатия и повторного кодирования УВЕЛИЧИТСЯ в размерах, с учётом домена самого сервиса, это 100%.
linux-over
Совсем недавно на хабре была очень хорошая статья на аналогичную тему
https://habr.com/ru/articles/746602/
MonkAlex
Хорошего в той статье только комментарии, отмечу. Сама статья упускает многие моменты.
linux-over
подход к решению задачи там очень здравый, ну и нужно сразу делать скидку, что это MVP и объём работ = в рамках собеседования
MonkAlex
Вопрос сокращателя ссылок - это вопрос обсуждения с собеседником, вопрос дизайна обычно. А та статья целиком про "я опытный и умный, я сделаю вот так". В основном без объяснений, почему.
Комменты здраво накидывают вопросов, комменты почитать стоит.