Как устроен сервис коротких ссылок ?! Часть 2.
UniLecs
Схема Базы данных
Определение схемы БД на ранних этапах собеседования поможет понять поток данных между различными компонентами, а в дальнейшем поможет распределить данные.
Несколько замечаний о природе данных, которые мы будем хранить:
- Нам нужно хранить миллиарды записей.
- Каждый объект, который мы храним, имеет небольшой размер (менее 1 КБ).
- Между записями нет никаких связей - кроме хранения информации, какой пользователь создал URL.
- Наш сервис предназначен для чтения.
Схема базы данных:
Нам потребуются две таблицы: одна для хранения информации об отображениях URL-адресов, а другая - для данных пользователя, создавшего короткую ссылку.
Какую базу данных мы должны использовать?
Так как мы ожидаем сохранения миллиардов строк, и нам не нужно использовать отношения между объектами, лучше использовать хранилище ключей NoSQL, например DynamoDB, Cassandra или Riak. Выбор NoSQL также будет легче масштабировать.
Базовый дизайн системы и алгоритм
Проблема, которую мы здесь решаем, состоит в том, как создать короткий и уникальный ключ для данного URL.
В примере Google Shortener в Разделе 1 сокращенный URL-адрес «https://goo.gl/6gZT7P». Последние шесть символов этого URL - это короткий ключ, который мы хотим сгенерировать. Здесь мы рассмотрим два решения:
a. Кодирование фактического URL
Мы можем вычислить уникальный хеш (например, MD5 или SHA256 и т.д.) данного URL. Хеш может быть закодирован для отображения. Это может быть base36 ([a-z, 0-9]) или base62 ([A-Z, a-z, 0-9]), и если мы добавим ‘-’ и ‘.’, Мы можем использовать кодировку base64. Резонный вопрос: какой длины должна быть короткая клавиша? 6, 8 или 10 символов.
Используя кодировку base64, ключ длиной 6 букв даст 64 ^ 6 = ~ 68,7 миллиардов возможных строк.
Используя кодировку base64, ключ длиной 8 букв может привести к 64 ^ 8 = ~ 281 триллиону возможных строк.
С 68.7B уникальными строками, давайте предположим, что для нашей системы будет достаточно шести буквенных ключей.
Если мы будем использовать алгоритм MD5 в качестве нашей хеш-функции, он создаст 128-битное хеш-значение. После кодирования base64 мы получим строку, содержащую более 21 символа (поскольку каждый символ base64 кодирует 6 битов значения хеш-функции). Поскольку у нас есть место только для 8 символов на одну короткую клавишу, как тогда мы выберем нашу клавишу? Мы можем взять первые 6 (или 8) букв за ключ. Это может привести к дублированию ключа, после чего мы можем выбрать некоторые другие символы из строки кодирования или заменить некоторые символы.
Какие существуют проблемы с нашим решением?
У нас есть следующая пара проблем с нашей схемой кодирования:
- Если несколько пользователей вводят один и тот же URL-адрес, они могут получить один и тот же сокращенный URL-адрес, что недопустимо.
- Что делать, если части URL-адреса закодированы? например, http://www.google.com/distributed.php?id=design и http://www.google.com/distributed.php%3Fid%3Ddesign идентичны за исключением кодировки URL.
Обход проблемы: мы можем добавить увеличивающийся порядковый номер к каждому входному URL, чтобы сделать его уникальным, а затем сгенерировать его хеш. Нам не нужно хранить этот порядковый номер в базах данных. Возможные проблемы с этим подходом могут быть постоянно увеличивающимся порядковым номером. Это может переполниться? Добавление увеличивающегося порядкового номера также повлияет на производительность службы.
Другим решением может быть добавление идентификатора пользователя (который должен быть уникальным) к входному URL. Однако, если пользователь не вошел в систему, мы должны попросить пользователя выбрать ключ уникальности. Даже после этого, если у нас есть конфликт, мы должны продолжать генерировать ключ, пока не получим уникальный.
b. Генерация ключей в автономном режиме
У нас может быть отдельная служба генерации ключей (KGS), которая заранее генерирует случайные шестизначные строки и сохраняет их в базе данных (давайте назовем ее key-DB). Всякий раз, когда мы хотим сократить URL-адрес, мы просто берем один из уже сгенерированных ключей и используем его. Такой подход сделает все довольно просто и быстро. Мы не только не кодируем URL, но и не должны беспокоиться о дублировании или коллизиях. KGS обеспечит уникальность всех ключей, вставленных в базу данных ключей.
Может ли параллелизм вызвать проблемы? Как только ключ используется, он должен быть отмечен в базе данных, чтобы он больше не использовался. Если несколько серверов одновременно считывают ключи, мы можем получить сценарий, когда два или более серверов пытаются прочитать один и тот же ключ из базы данных. Как мы можем решить эту проблему параллелизма?
Серверы могут использовать KGS для чтения / маркировки ключей в базе данных. KGS может использовать две таблицы для хранения ключей: одну для ключей, которые еще не используются, и одну для всех используемых ключей. Как только KGS дает ключи одному из серверов, он может переместить их в таблицу используемых ключей. KGS всегда может хранить некоторые ключи в памяти, чтобы быстро предоставлять их в любое время, когда они нужны серверу.
Для простоты, как только KGS загрузит некоторые ключи в память, он может переместить их в таблицу используемых ключей. Это гарантирует, что каждый сервер получает уникальные ключи. Если KGS умрет до того, как назначит все загруженные ключи какому-либо серверу, мы будем тратить эти ключи впустую - что приемлемо, учитывая огромное количество ключей, которые у нас есть.
KGS также должен следить за тем, чтобы не давать один и тот же ключ нескольким серверам. Для этого он должен синхронизировать (или получить блокировку) структуру данных, в которой хранятся ключи, прежде чем удалять из нее ключи и передавать их на сервер.
Каков будет размер базы данных ключей? С помощью кодировки base64 мы можем генерировать 68.7B уникальных шести буквенных ключей. Если нам нужен один байт для хранения одного буквенно-цифрового символа, мы можем сохранить все эти ключи в:
6 (символы на клавишу) * 68,7 Б (уникальные клавиши) = 412 ГБ.
Разве KGS не является единственной точкой отказа? Да, это. Чтобы решить эту проблему, у нас может быть резервная копия KGS. Каждый раз, когда основной сервер умирает, резервный сервер может вступать во владение, чтобы генерировать и предоставлять ключи.
Может ли каждый сервер приложений кешировать некоторые ключи из key-DB? Да, это может ускорить процесс. Хотя в этом случае, если сервер приложений умирает до того, как поглотит все ключи, мы потеряем эти ключи. Это может быть приемлемо, так как у нас есть 68B уникальных шестибуквенных ключей.
Как бы мы выполнили поиск ключа? Мы можем найти ключ в нашей базе данных или хранилище значений ключей, чтобы получить полный URL. Если он присутствует, отправьте в браузер статус «HTTP 302 Redirect», передав сохраненный URL-адрес в поле «Location» запроса. Если этот ключ отсутствует в нашей системе, введите статус «HTTP 404 Not Found» или перенаправьте пользователя обратно на домашнюю страницу.
Должны ли мы устанавливать ограничения по размеру для пользовательских псевдонимов? Наш сервис поддерживает пользовательские псевдонимы. Пользователи могут выбрать любой «ключ», который им нравится, но предоставление произвольного псевдонима не является обязательным. Однако разумно (и часто желательно) наложить ограничение на размер пользовательского псевдонима, чтобы обеспечить согласованную базу данных URL. Предположим, что пользователи могут указать максимум 16 символов на ключ клиента (как показано в приведенной выше схеме базы данных).