Даже немножко страшно думать, что еще несколько лет назад, когда использование k8s разрасталось до сегодняшних масштабов, люди предлагали и даже пытались разворачивать в нем базы данных с прикрученными volume-ами около своих приложений. Говоря о дизайне высоконагруженных систем, хоть и с минимумом бизнес-логики, иногда задумываешься даже о bare-metal имплементации, сравнивая ее с виртуализацией (в некоторых компаниях иногда и второго порядка). Чтобы избежать подобных мыслей, я решил для себя подумать, как можно организовать что-нибудь простое, но масштабированное и к чему однозначно не подойдут требования к нагрузке в 1 запрос в секунду.

URL Shortener-ы, или как пропустить пару мультов запросов в час

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

Говоря об интернете в его текущем виде и вспоминая рекламные кампании, удобные короткие ссылки для чатов или СМС-ок, скрывающие под собой километры UTM-меток или домашних реферальных параметров для дата сатанистов, определенно имеют место быть. Такие сервисы, как bit.ly или tiny.url еще и умудряются пропускать прохожих через свои фронты с накрученной рекламой. Как можно такое организовать?

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

• Сокращать ссылки до приемлемого состояния

• Подсчитывать количество переходов по ссылкам (ведя статистику типа IP-адресов, UserAgent-ов и времени перехода)

• Работать быстро.

Задаваясь вопросами о бизнес-сущностях:

• Сколько должна жить ссылка? Всегда, пока мы не решим удалить ее руками

• Можно ли создавать собственные кастомные ссылки? Допустим, что можно, учитывая лимит длины айдишника в 8 символов

• Сколько запросов на создание ссылки мы ожидаем в течении одного месяца? Назовем цифру в 100 миллионов

• Какой должен быть аптайм? Мерим uptime и apdex так, что смотрим на 99.995-й перцентиль пользователей.

• Сколько планируется переходов по ссылкам? Представим, что у нас очень оптимизированная кампания и назовем соотношение в 100:1 на read:write (100 переходов к одному созданию ссылки).

Глядя на требования, можно примерно подсчитать, сколько ссылок будет генериться клиентами. 100 миллионов / (30 дней * 24 часа * 60 минут * 60 секунд) = 40 RPS, к которым применимо требование в 99.995 перцентиль. Посчитав соотношение к переходам, сервис должен обслуживать 4000 RPS для переходов в секунду в периоды нагрузки.

Представив более или менее, сколько бы стоило хранить один ответ на http-запрос по короткой ссылке с кодом 302 и редиректом (порядка 300 байт), можно подсчитать, что пропускная способность бэкэнда в день составит 4000 RPS * 86400 секунд = 345,600,000 запросов в день. Очевидно, что при 346 миллионах read-операций в день нам не очень поможет каждый раз ходить за одним и тем же в базу, но зато существует принцип Парето - 80% запросов всегда для 20% данных. Учитывая простоту сервиса, первым делом хочется кешировать всякие дела в IMDB (in-memory database), а для таких целей отлично подходит memcached или Redis. А учитывая принцип Парето - нам необходимо кешировать 20% этих запросов - требования к памяти бы были в районе 346 миллионов * 0.2 * 300 байт = 21 ГБ кешей - даже не страшно, но это поможет нам предоставить почти 99.995% клиентов быстрые редиректы туда, куда им нужно.

Итак, подводя математику:

• Количество ссылок, созданных в год: 120,000,000

• Количество переходов по ссылкам в год: 126,144,000,000

• Необходимое пространство для хранения: 335,6ГБ

• Необходимое количество памяти для кеширования: 21ГБ.

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

Верхнеуровневая архитектура

Учитывая простые User stories:

• Я, как пользователь, хочу уметь создавать короткие ссылки;

• Я, как прохожий генератор трафика, хочу уметь получать длинные ссылки, переходя по коротким;

• Я, как аналитик, хочу иметь возможность в риалтайме видеть переходы по ссылкам и выгружать отчеты

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

Так что там с базами?

Время сравнить характеристики паттернов, на которых построено хранение всего в мире:

RDBMS

Самая распространенная архитектура БД в мире и не зря. Жестко задаваемые на уровне схем БД ограничения и правила не позволят вставить фигню, а индексирование таблиц поможет быстро собрать нужную модельку данных. Но нужны ли нам комплексные модели данных? Информация о переходах в риалтайме стримится в OLAP, а множество read и write запросов к мастер-ноде приведет к ее деградации и не даст нам 99.995% доступности.

NoSQL базы

Здесь все становится интереснее - допустим, как ключ мы используем id короткой ссылки, а как значение - длинную ссылку. Нам нужны индексы на объектах, соответственно стоит смотреть в сторону Apache Cassandra: Zookeeper для этого медленный, а масштабируется Cassandra легче и быстрее, чем та же MongoDB.

При этом Cassandra может и гарантирует консистентность на маленьком количестве нод, но при росте количества реплик возникают вопросы о кворуме:

• Сколько реплик должны отреагировать при записи перед тем, как клиенту вернется ответ?

• Что делать с репликами, до которых не дошел write-запрос?

Так что поехали дальше.

Best of both worlds

Мы уже примерно понимаем, что нам нужно от физического уровня хранения данных: быстрота read и write операций и репликация и консистентность, чтобы важные ссылки не терялись. Догадываетесь, что случилось? Шарды развалились.

Шарды и паттерны шардирования

Думаю, что немногие еще не слышали или глазами не видели упоминание термина "shards". Что он означает?

Говоря о шардировании, кажется, что нужно сравнить его с партиционированием. Если кратко, партиции - это виртуальные регионы датаспейса в рамках одного физического сервера, а шарды - множество регионов датаспейса, каждый разбросанный по множеству серверов. Если объяснять в парадигме PostgreSQL (возможно, кому-то будет легче), то

1. Я могу разделить одну таблицу на партиции по тому или иному признаку (допустим, времени)

2. Я могу создавать новые таблицы, используя созданные мной правила партиционирования (нарезки мастер-таблицы)

3. Имплементация шардирования в PostgreSQL основана на партициях, то есть существует одна централизованная (или реплицированная) мастер-таблица и ее партиции на соседних серверах.

С другой стороны, возьмем в качестве примера Elastic. Там реализуется index-паттерн, который позволяет держать те или иные данные рядом, как в классических RDBMS, но алгоритмы шардирования позволяют разделять данные на десятки связанных между собой этим индексом шардов, позволяя распределять данные и не давая одной условной мастер-таблице сдохнуть, потому что данные уже лежат распределенно без упомянутой мастер-таблицы. А учитывая требования к нашему сервису - однажды созданная ссылка меняться не будет и о блокировке строк или объектов при одновременных обращениях задумываться не придется.

Дистрибуция данных по шардам может быть как алгоритмической, так и динамической:

• Алгоритмический разброс подразумевает заданные правила, по которым данные пишутся в шарды: если у нас есть индекс, мы можем шардировать его по дате записи или другому параметру и это даст нам отдельные шарды, поиск по которым будет тривиален.

• Динамический разброс данных реализуется "локаторами" - это координаторы, которые решают, где что будет лежать в зависимости от индекса. Локаторов может быть один или несколько, в зависимости от количества индексов и необходимости в этом, но из-за этого идейно локаторы - Single Point of Failure (единая точка отказа) для определенного набора индексов и доступность тех или иных данных под нагрузкой не гарантируется.

История с шардированием хорошо реализуется в ClickHouse с его распределенностью. У ClickHouse при должной настройке нет единого мастера, шарды реплицируются асинхронно (но при этом весьма быстро, считай сетевые задержки) и его имплементация позволяет увидеть 4000 RPS на read-операции благодаря шардам. А еще ClickHouse исполняет SELECT-подзапросы на всех шардах в кластере, потому что слету не знает, где что лежит, так что потерять что-либо сложно.

Давайте теперь допустим, что мы сделали так, что индекс шарда находится в ссылке. Генерируя короткую ссылку в 8 символов английского upper и lowercase-а с 10 цифрами (62 символа на все про все), мы получаем 62!/(8! * 54!) = 3.3e10 ссылок. При этом, используя первых два символа как ключ/индекс, мы получим 62!/(2! * 60!) = 1891 уникальный индекс, в которые могут динамически распределяться ссылки.

Все так хорошо?

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

In conclusion...

В этой статье я только немножко в рамках "мыслей в душе" коснулся основных идей распределения данных и построения хайлоада на железе. Стратегии репликации могут засновываться на правилах шардов или выбираться динамически, региональная репликация строиться на количестве запросов к серверам в определенных регионах... Здесь главное - понимание того, что ничего из этого сильно не магия и все строится достаточно логически, исходя из бизнес-процессов и вещей, которые мы видим как горлышки бутылок. Производительность запросов между партициями даже отдаленно не пахнет хайлоадом, а шарды, идея которых - облегчить эти страдания, должны быть более или менее равномерно распределены и найти баланс между удобством, производительностью и стоимостью не всегда просто. Многие веб-сервисы до сих пор работают без шардирования и живут же как-то.

На этом часть 1 всё, удачи, ребята!