Один из моих знакомых недавно сходил на собеседование, на котором его попросили спроектировать укорачиватель ссылок. Он растерялся и задачу — как хотел интервьюер — не осилил, а потом нашел в интернете популярное решение и попросил меня прокомментировать. Полная формулировка поставленной проблемы: «Как бы вы разработали службу сокращения URL-адресов, подобную TinyURL?»

К моему сожалению, я — человек любознательный, поэтому я не закрыл окно чата, а пошел почитать, как принято в высшем свете такую задачу нынче решать. То, что я увидел, заставило меня набросать свою собственную архитектурку, потому что даже в страшном сне согласиться с предложенным по ссылке дизайном — не вариант. В тексте ниже я заочно дискутирую с автором решения по ссылке выше.

С чего все началось

Вышеупомянутый пост начинается с мудрого совета

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

Это прекрасный совет, я бы даже его обобщил до «Когда вам нужно решить задачу, не переходите сразу к техническим деталям». Время, затраченное на ввод решения с клавиатуры, не должно превышать 10-20% от общего времени, ушедшего на выполнение задачи. Заблаговременное обдумывание окупается лучше, чем последующее устранение неполадок.

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

Давайте предположим, что наш сервис ежемесячно укорачивает 30 миллионов новых URL-адресов.

Нет, пожалуйста, не делайте так. Предполагайте, что сервис может вырасти до миллионов новых сокращений в месяц и убедитесь, что он будет готов к масштабированию. Если вас наняли для обработки существующего трафика в 30 млн/м, поверьте мне, вам будут задавать совсем другие вопросы во время собеседования, например: «какой существующий сервис мы можем купить».

Чтобы преобразовать длинный URL-адрес в уникальный короткий URL-адрес, мы можем использовать некоторые методы хеширования, такие как Base62 или MD5.

Эх. Прежде чем обсуждать, какой метод хеширования использовать, мы должны уточнить наиболее важное требование: можем ли мы генерировать новые короткие URL-адреса для того же самого длинного URL-адреса при последующих запросах, или мы должны возвращать уже сгенерированный. Последний подход намного сложнее реализовать, но обычно можно обойтись без этого. Я сходил на BitLy и убедился, что они этого не делают. Мы тоже не будем.

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

База данных

Стоп, что? Кто сказал, что нам когда-либо вообще понадобится база данных? Что за дурацкое веяние тащить базу всюду, даже туда, где она вообще не нужна, по крайней мере — на этапе прототипирования?

Ну а затем автор сравнивает RDBMS с NoSQL и приходит к неоднозначному выводу «чтобы обрабатывать огромный объем трафика в нашей системе реляционные базы не подходят, а еще RDBMS не особо хорошо масштабируются». Ровно на этом месте я прекратил читать и решил, ладно, напишу, как надо справляться с такой задачей, если здравый смысл пока все еще превалирует над десятком изученных современных технологий.

Как это сделать правильно

Для начала, нужно выбрать чуть менее предвзятый подход и определить, что нам действительно нужно. Требований, оказывается, не так и много.

• мы оптимизируем сервис для чтения (пусть даже и в ущерб записи)

• мы не выбираем серверную часть для хранения ссылок сразу

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

Вот и все.

Эта задача интересна, например, тем, что нам не нужно хранилище с высокой степенью связности, более того: нам вообще не нужно, чтобы оно было связно. Лучшим подходом для перетасовки запросов между разными «сегментами» (что бы это ни означало в данном контексте) будет hashring, но есть проблема: изменение размера хэширования (масштабируемость!) на лету привело бы к повторному хэшированию, а это не то, что мы можем себе позволить. Короткая ссылка abcdefg всегда должна вести на один и тот же сегмент, несмотря ни на что, а количество сегментов, несомненно, будет увеличиваться.

Пока примерно понятно. Что же дальше?

Говорят, программисты принимают только три вида чисел: 0, 1, ∞. Все должно быть бесконечно расширяемым. Если я смог создать третий сегмент, я должен быть в состоянии создать 1_000_000_003^й. Но я не настоящий программист по этому определению, меня вполне устраивает первоначальное масштабирование до 62 сегментов (а когда у нас закончатся сегменты, я, ну, например, продам бизнес или, хоть это и стыдно, переключусь на короткие URL-адреса из 8 символов.) Первая буква в коротком URL-адресе будет указывать на физический сегмент, жестко закодированный. Я начну с единственного экземпляра, обслуживающего первых пользователей, с именем a. Все ссылки в этом сегменте будут начинаться с a. Например, abcdefg или a8GH0ff. Затем, после первого миллиарда или около того пользователей, я выберу b. Это отвратительный, неэлегантный хак, я в курсе. Зато он работает.

С разбиением на, если хотите, шарды — вроде справились. Что же теперь делать со ссылками в одном и том же шарде? О, вот тут как раз во всем блеске можно пользоваться магией Hashring. Создадим N отдельных хранилищ (это могут быть таблицы в БД или даже каталоги на файловой системе), где N приколочено гвоздями. Я слишком ленив, чтобы навести тут какую-нибудь математику, но это число можно было бы получить, разделив весь объем хранилища на приемлемый для хранилища с быстрым доступом размер, который можно достать из бенчмарков. Для продакшена, скорее всего, все-таки потребуется какой-то сравнительный анализ. Но пока давайте просто ткнем пальцем в небо и положим N тоже равным 62, просто потому, что 62, в конце концов, — достаточно большое число.

По запросу на сокращение URL-адреса будем создавать тарабарщину из коротких 6 символов, добавлять a к ней (текущий «префикс», обозначающий фактический физический сегмент/узел) и проверять, не занят ли он уже в хранилище.

Если занят — ну что ж, повторим попытку. Если нет, запускаем (это псевдокод, который очень легко реализовать прямо на коленке) Hashring.who?(six_symbols), добираемся до локального фрагмента и сохраняем там пару ключ-значение. (Памятка на будущее: в какой-то момент шард заполнится настолько, что много раз будет возвращаться уже существующий ключ: это надо отслеживать метриками и перейти на следующий шард задолго до того, как текущий заполнится на все 100%.)

Доступ к длинному URL-адресу теперь практически мгновенный:

abcdefg
^         имя физической ноды (шарда)
 ^^^^^^   локальный для шарда ключ

Осталось только выбрать его из хранилища по ключу.

Реализация

Помните, я говорил, что в DB может вообще не быть необходимости? Все, что нам нужно на первых порах, — это интерфейс, выглядящий как пара функций get/1 и put/2 (и, возможно delete/1, но об этом можно будет подумать позже). Наивной, но надежной реализацией этого интерфейса было бы множество каталогов на файловой системе, организованных таким же образом, как дистрибутивы Linux хранят пакеты: для ключа из 7 символов это был бы путь типа, /hashring-id/b/c/d/e/f/g где на пути g находится файл, содержимое которого представляет длинный исходный URL. inode работают медленно, когда в каталоге слишком много файлов / подкаталогов, но здесь у нас есть 62 вершины на каждом уровне, так что все в порядке, и доступ будет мгновенным. Если этого не произойдет, мы перейдем к 62 таблицам в СУБД, или к 62 сегментам в NoSQL, или к чему-то еще.

В принципе, это все. У нас есть чистое масштабируемое решение, не зависящее от внутреннего хранилища.

Дальнейшие улучшения

Мы могли бы легко хранить количество обращений по сокращенной ссылке, а также любые другие прикрепленные данные, ведь конечный файл может быть какого-угодно формата (в том числе, он сам может быть директорией). Более того, можно модернизировать этот подход для повторного использования коротких ссылок, что увеличило бы время записи, но сохранило бы время доступа прежним (устранение коллизий было бы самой интересной частью этого решения, и я, пожалуй, оставлю его дизайн дотошному читателю).