На Reddit я наткнулся на статью про обработку создания 100 тысяч коротких URL в секунду¹. [Прим. пер.: автор статьи по ссылке создал три варианта системы; третий, наилучший, по его мнению, вариант при помощи кластера-координатора делит нагрузку на несколько ECS-воркеров, использует DynamoDB TransactWrite для пакетных условных вставок, а для устойчивости применяет кэш Redis.]

Какой же это запутанный оверинжиниренный бардак!

Не поймите меня неправильно: я люблю оверинжиниринг, но только в обучающих хобби-проектах. Как сказали многие комментаторы на Reddit, в образовательных учреждениях редко преподают распределённые системы и архитектуру ПО. Когда новички попадают в нашу отрасль, из-за подобных постов, написанных авторитетными на вид техлидами, они могут подумать, что оверинжиниринг — это единственный способ работы. Однако часто решение может быть гораздо проще.

Требования

1. В них нет ничего особо сложного. Пользователь передаёт длинный URL и получает короткий URL. Есть некоторые тонкости, например, пользователь может выбрать короткую строку, но для архитектуры в целом они не важны.

2. Система работает и может поддерживать 100 тысяч операций записи в секунду. Автор поста не уточнял, так что предположим, что нужен один миллион операций записи в секунду.

3. Отсутствие дублей длинных 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. Автор уже начал менять формулировку этого требования в комментариях на Reddit², хотя очевидно, что его схема нужна была для решения именно этой проблемы.

• Во-первых, это странное требование. Ни одному сокращателю URL, с которыми я работал, такое ограничение не требовалось. Очевидно, это необходимо для экономии нескольких байтов на хранении — поздравляю, это самый глупый обмен.

• Во-вторых, даже если нам каким-то образом потребуется удовлетворить этому требованию, в созданном автором бардаке всё равно нет никакой нужды. Ему достаточно было хранить обратную пару «ключ-значение» longurl => shorturl. Это позволит реализовать две вещи:

  1. Иметь конкретный шард для заданного длинного URL, в котором можно проверять наличие дублей. Это позволит базе данных масштабироваться горизонтально, а не сканировать вторичные индексы каждого шарда.

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