Grokking System Design Interview for Engineers

Статья заметка, на основании прохождения курса Grokking Modern System Design Interview for Engineers & Managers (Сертификат)

Составные части системы

Дизайн на реальных примерах

DNS делится несколько уровней: корневой, потом домены стран, потом организации
Используетя итеративный подход, когда опрос начинается с ближайших, и если нет, то идет до корня
Данные кэшируются с ТТЛ и обновляются максимум раз в 3 дня
Load Balancer можно осущесвлять средствами DNS , когда 1 днс соответствует несколько Ip, в это случае:
- NS сервер возвращает ИП по RoundRobin (чтобы менять поведение, уменьшают ТТЛ жизни днс записи)
- балансировка может быть по географическому принципу
- по времени отклика сервера

Load Balancer

Load Balancer - решает сразу 3 проблемы : Расширяемость, Достпность, Производительность
LB - может быть между каждым слоем (веб, апп, бд)
- может быть каскад LB - выбор региона -> внутри региона
- LB можно осущесвлять средствами DNS (см выше)
- LB может быть без сервера, если сам клиент роутит запрос на нужный сервер. (но появляются сложности при проблемах или вводе нового)

Способы LB:
* RoundRobin
* RoundRobin с заранее известными весами (некоторые сервера больше) - статическое LB
* Least Con - если все сервера одинаковые, то выбирается менее загруженный
* Least Resp - аналогично, но по времени отклика (динамическое LB)
* Hash URL - если конкретный сервер ответсвенен за конкретную часть ЮРЛ
- выбор может быть как на верхнем уровне (куки, хеадер и т.д.), так и на сетевом (выбирается сервер, с которым ранее клиент взаимодействовал)
часто их сочетают последовательно (сначала dns, потом сетевой, потом на уровне приложения)
сначала сетевой уровень, чтобы пользователь где начал раотать, там и продолжал
Обратный ответ приложения не идет по всем уровням LB, а сразу пересылается выходному роутеру

LB может выполнять роль Reverse proxy - прокси (nginx) перед сервером: чтобы защитить внутреннюю сеть; чтобы делать на нем шифрование/дешифрование.

Базы данных

Основные 2 типа:
* relation (Atomic , Consisten, Isolation, Durabil - устойчивость к крэшам)
* nosql
+ хранение неструктурированных данных (схема опрделяется во время чтения)
+ простота скалирования, высокая доступность
Подтипы nosql:
* ключ-значение - как хэш массив (HBASE)
* документоориентированная (MONGO) - для хранения XML, JSON (карточка пользователя, товара)
* графовые (Neo4J) - для хранения связей (друзья в соц. медиа)
* колоночные (ClickHouse) - колонки в разных файлах

Репликация - синхронная и асинхронная
По типу передаваемых данных:
* реплицируются запросы - минус: недетерменистичные запросы вернут разные значения
малый объем, рекурсивные вызовы
* реплицируются бинарные данные - большой объем, нет проблем недетерменестичности
* логическая - реплицируются данные измененой строки
По числу ведущих
* Один ведующий - несколько ведомых (для интенсивных чтений)
* Мультилидер репликация - уход от конфликтов:
- все писатели определенной записи всегда выполняются на определенной ноде. (убрать неопределенность)
- последний прав
* Репликация все со всеми (касандра)
решается через кворум: активной записью считается та, которая присутствует на 50%+1 ноде

Шардирование
* по ключу (по диапазону, примеру 1 буквы пользователя), по хэшу, по функциональной области.
Избегать остатка от деления, т.к. добавление/удаление ноды потребует перенесение всех данных.
нужно делить на большее число и хранить соответствие в зукипере (описано в KV)
* автоматически по размеру (как в хане)
* вторичные индексы требуют опрашивать все шарды для поиска в локальном индексе или хранить гдето отдельно глобальный индекс
роутинг клиента на шард: приходит в любой, если данных нет, то роутится на нужную; через мастера;знает куда идти по спец. функции
* распределение данных - справочники везде, факты шардированы

KV Store

не требуется строгая консистентность, но нужная мастшабируемость и доступность
В KV вместо балансировщика используется алгоритм:
* Выбирается такой алгоритм хэширования, чтобы число секций было больше числа нод
* на этом закольцованном связанном списке распределяются равномерно ноды
* в ноде лежат все данные слева (до) от нее до соседней
* при запросу ключа получается значение и смотрится нода справа , там будет лежать наше значение
* при добавлении ноды, только часть ключей между ей и соседней переезжает
* за счет этого легко так же сделать репликацию для отказоустойчивости: делаются реплики на N след. нод по порядку.
если 1 нода выходит из строя, то просто переходим к следующей по списку.

Степень консистентности можно конфигурировать: N нод делается синхронная запись, а в M - асинхронно (как trade of между скоростью и консистентностью)
Аналогично при чтении: данные запрашиваются с 1..N нод

Конфликт при разделении сети:
* последний прав. Для определение последнего используется не время, а счетчик числа изменений.
* через контекст, где клиент при сохранении сам должен указать версию объекта

CDN

быстрей отклик, дублирование контента поблизости (dns + proxy)
DNS сервер выбирает сервер по принципу: скорость доступа (ширина канала), удаленность (отклик), загруженность
Распространение контента:
* push - заливаешь все что есть, меняешь ссылки (дорого все хранить, работает быстро)
чаще для статичного контента
* pull - данные заливаются автоматически при первом обращении (хранится что нужно, лаг на загрузку, могут быть устаревший контент, т.к. он обновляется только по ТТЛ)
удобней для динамического
динамический контент может генерироваться сразу на нужной географической ноде
чтобы географические сервера не завалили оригинальный, делается деревянная структура распространения

Способы устаревания:
* TTL
* Аренда - прокси опрашивает сервер на предмет изменений. Период опроса может быть динамический (например нарастать, если изменений нет)
* при записи на сервере проставляется флаг необхоимости обновить (или обновляется принудительно кэш)

Sequencer

Виды
* UID - 128bit рандомное число (слишком большое, могут быть колизии)
* Database Seq - группа баз для генерации числа, опрос идет последовательно = prev + 1 + номер сервера (гарантирует непересечение)
1: 1, 3, 5, 7
2: 2, 4, 6, 8
- сложности добавление/удаления серверов, т.е. плохо скалируется
* под сервер выделяется рэнж ключей, новый рэнж выдает спец. сервис (минус: если сервер умирает, то рэнж теряется и нужно давать новый)
* Unix TS * номер сервера - слабая уникальность, время может скакать при синхронизации
* Twitter unix ts = бит переполнения | unix ts | worker | sequence
sequence просто инкрементируется, как доп. защита от неуникальности времени
хорошо масштабируется, нет дублей, но возможны скачки, как у Unix TS
* внутренний счетчик | номер машины
при пересылки данных счетчик = MAX(локальный счетчик; пришедший счетчик) + 1
минус: может быстро выйти за пределы 64бит
* true time = unix ts | погрешность замера TS | нода | счетчик (используется в Google Spanner)
точно уникальное, но если погрешность большая, то у 2 событий может быть пересечение по ТС и нельзя со 100% вероятность сказать, кто был 1

Распределенный мониторинг

push и pull модель
хорошо подходят time series базы (где старые периоды сами сжимаются)
- серверная часть:
* текущие показатели
* сбои
* аномалии и отходы от сла
pull подход (центр запрашивает) более распространен:
* дата коллектор собирает данные с источников и кладет в кафку
* откуда брать, узнает из service discover
* складывается в time series бд и арихв в с3
* данные выводятся на дашборд и применяются правила алертинга
если серверов или дц много то делается 2 уровневая система мониторинга: рядом pull мониторинг, а в центр данные отправляются пушем
так же нужно предусмотреть правила архивации

Как мониторить доступность сервисов:
* внешний сервис, который пытается подключитсья и регистрирует ошибки (но только факт ,причина может во многом)
* внедряем пробер прямо в клиенсткое приложение и шлем в несколько независимых сервисов мониторинга на разных уровнях сети, чтобы понять точку отказа

Распределенный кэш

требования схожи с KV, но нет требования к устойчивости
* данные могут писаться и в кэш и в бд; или в бд и подниматься в кэш при 1 обращении; или только в кэш и асинхронно сохранятсья в бд
* удаление из кэша: lru/mru
какой именно определяется практически или нагрузочным тестом
* устаревание: TTL
* распределение:
список серверов хранится и обновляется на каждом аппликейшене
есть управляющий сервис, который говорит куда коннектся за кэшем и следит за выбывшими серверами (трафик идет не через него)
для устранения отказа - делается стендбай
для выбора используется хэширование по кругу с диапазонами как у KV (доступ и перехэширование = LogN)
* хранение
хэш массив для быстрого доступа
двунаправленный связанный список для быстрого выстраивания по частоте и удаления устаревшего/неиспользуемого
+ блум фильтр для быстрой приблизительной проверки
* кэш чаще отделяют от сервера приложений, чтобы по разному скалировать
кэш популярных данных может быть сразу на нескольких серверах, чтобы размазать нагрузку

MemCache vs Reddis
MemCache:
- есть только строки - нужна сериализация
- нет шардирования, сервера не знаю друг о друге
- константное время доступа
- давно есть, используется исторически (Facebook)
Reddis
- может хранить разные типы данных
- может персистить данные на диск
- может использоваться как шина данных
- есть репликация, шардирование, понимает MemCache
- редис объединяет запросы в батчи и получает ответ так же пачкой

Распределенная шина данных

разделение 2 систем с разной скоростью или даже доступностью (минимизирует пики)
возможность параллельной записи или обработки
разные приоритеты задач

Упорядоченность при записи:
* TS
* монотонный счетчик (sequence)
* unix ts || worker || sequence
если событие приходит позже окна обработки, то оно кладется в отдельную очередь для доп. обработки
если входит, то сортируем
Физически представляет из себя: лоад балансер - фронтенд связанный с мета сервисов (бд+кэш) и бэкендом, где данные

Pub-Sub

отличие от queue - сообщение в очереди может читать множество получателей
* описывается модель, когда очередь знает своих получателей, для этого используется отдельная база
для сообщений используется счетчик прочитавших, когда он = числу читалаей, то сообщение удаляется
* модель где топик бьется на партишены по Round Robin, а каждое сообщение имеет офсет
в бд хранится на каком смещении находятся читатели
партишены реплицируются между собой, чтобы не потерять данные
задается время жизни

Rate Limiter

лимиты на пользователя, распределение реурсов, защита от перегрузки, экономия денег
отдельный сервис, к которому обращается сервер приложений
* база с правилами
* кэш на касандре или редис
* фоновые задания обрабатывающие правила
* потребитель только запрашивает значение (расчет в фоне)
Алгоритмы:
* ведро токенов - бакет с заданной периодичностью пополняет ведро, если оно полное, то не добавляется
приходящий реквест берет токен из ведра, если токена нет, то рекв. отвергается
- на стыках периодов пополнения, может быть превышение допустимого лимита
* дырявое ведро реквестов - наоборот, в ведро складываются реквесты, и удаляются из него с заданной периодичностью
очень похоже на sliding window
- не может быть повышенного рейта на границах опустошения
* фиксированное окно - счетчик увличивается при реквесте и сбрасывается в фиксированные моменты
- работает рывками, может быть превышение трафика в моменты сброса
* sliding window - добавляются ревесты по времени в очередь
фоновый процесс удаляет начало очреди при выходе за границу
можно хранить отдельный размер очереди и считывать только его при обращении
* сместь sliding window + fixed window - значение из последнего sliding виндоу +
% пересечения фиксированного окна с предыдущим sliding window

Blob storage

клиент - рэйт лимитер - лоад балансер - (метадата, мэнэджер нода)- сторэдж
данные побиты на чанки, блоб может быть разбит на эти части
* Метадата сервер(мета дб + мэнэджер нода для бэкенда): содержит информацию где лежит конкретный чанк файла данных (64МБ) + реплики
* группы серверов объединяются в партиции, по которым распределяются блобы
ключ включает пользователя, чтобы все блобы пользователя были в 1 партиции (партицирование по рэнжу)
* blob index - KV бд для хранения атрибутов
* листинг с пагинацией (фильтр по порядковому номеру?)
* репликация - синхронная на копии внутри ДЦ и асинхронная в другие
копии так же могут использоваться для ускорения чтения
* ГЦ после удаления - помечаем удаленные в мете, а удаляем асинхронно
* большие файлы читаются частями черзе офсеты

Распределенный поиск

Индексирование:
* reverse index - текст разбивается на термы в инфинитиве. Хранится хэш массив: ключ - терм, значение - документ, позиция, частота
- занимает много места, сложно обновлять, сложность поиска сочетания (нужно искать документы где встерчается оба слова)
* indexer/seacher - мап-редюс для индексирования и поиска
- индексер собирает и сохраняет в blob storage (в reduce/объединенном варианте), поисковые ноды поднимают в папять из стораджа
* 3 репликация для отказоустойчивости
* для частых запросов иметь готовый ответ

Distribute Logging

При большом объеме логов, можно исопльзовать сэмплирование, в которое попадают только частые или долгие события
нужно разделять события по важности. Важные нужно логировать всегда.
Дизайн:
* Логи сохряняются локально на ноде
в некий буфер, и процесс который скидывает в общую очередь
* Центральный сервер логирования получает в очередь их периодически и кладет в блоб сторадж
агрегация, фильтрация, незамедлительные алерты
* Индексер - индексирует (п. Распределенный поиск)
* Визуализация

Распределенный шедуллер

Дизайн:
* Лимитер - ограничение по доступным ресурсам для пользователя
* Генерация ID, сохранение параметров и статуса в БД
- реалиционная для статуса и параметров
- графовая для пострения DAG
- очередь для сейчас выполняющихся тасок
очереди делятся по приоритетам
нужен обязательно лимит на время выполнения таски
размазывание по времени необязательных тасок
требуемый сла
- выполнение в облаке
таски должны быть идепотентны: готовы к перезапуску, проверить и выполнить при необходимости еще раз или лучше довыполнить с точки останова

Распределенный счетчик

пишем счетчик на рандомный шард, при считывании складываем значения с шардов
изначально число шардов зависит от числа читаталей (подписчиков)
после фоновые процесс опрашивает их и увеличивает или уменьшает
плюс проверка на перегрузку конкретного счетчика
выбор шарда для инкремента или создания:
* round Robin
* random
* исходя из нагрузки через балансер
при чтении есть фоновые процесс, который опрашивает шарды и суммирует
для объединенного счетчика может использоваться: кассандра или реддис
счетчик бьется на уровни по географическому признаку

Дизайн на реальных примерах

Общие вопросы до начала

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

Система	Функциональные требования	Нефункциональные	Оценка ресурсов	Минимум изходя из функц	Функциональное апи	Усовершенствования
YouTube	стрим, загрузка, поиск, оценка, комменты, предпросмотр	высокая доступность, расширяемость, быстрота, надежность (выбрать кирпичи выше для их реализации) строгая консистентность не нужна	общее число пользователей, активность в день, средняя длина видео, размер до и послеж сжатия * даем примерную оценку какой % людей загружает видео - исходя из этого оцениваем место, размер канала для загрузки * оцениваем канал для просмотра: оцениваем среднее число просмотров на видео в сек. Число просмотров * средний размер - оцениваем число серверов для обработки (в среднем 64к/с для сервера), прикидываем число пользователей и прикидываем по макс	бд, блоб сторадж, цдн, лоад балансер, сервер для энкодинга	* загрузка видео: название, теги, контент, категория, язык, настройки * поиск: текст, длина, разрешение, дата * предпросмотр: пользователь, видео * лайк: юзер, видео, лайк/диз * коммент: юзер, видео, текст - проектируем для апи бд: пользователь, видео, канал, коммент - расширяем схему на поиск: асинхронный опрос, сохранение в кв, процессинг реверсивного индекса	* C из CAP - делаем все асинхронно или через очередь * для кэша подходит memcache, т.к. не нужно хранить сложные типы данных * для хранения данных юзеров подойдет mysql/pg, для картинок - hdfs + cassandra (column family + kv + распределенная по ключу шардирования) * поиск дубликатов через сравнение хэшей * для скалирования mysql - можно физически бить данные на партиции, а клиент обращается к нужному через фасад сжатие: видео в разных разрешениях, аудио - битрейте. Простое прджатие можно сделать на клиенте. степень сжатия при чтении определяется автоматически на основании какой размер данных клиент может получить за отрезок времени. чем медленней сеть/клиент, тем хуже битрейт дается для быстро доставки используются спец. кэширующие сервера в крупных сетевых узлах, так же они используются для бродкаса стрима. рекомендации на основании решающих деревьев на оснвое предыдущих просмотров язык: c++ для бизнес критикал частей (энкодинг), в другим местах для быстрой разработки: python
Quora	задать/ответить на вопрос, голосовать, поиск, рекомендации, выставление ранка ответу	доступность, масштабируемость, скорость, консистентность с оговорками быстрая расширяемость не нужна (нагрузка прогнозируемая), но проще разместиться в готовом облаке	общее число пользователей/в день, процент с видео/картинкой - оцениваем число потосв в день = числу юзеров и число ответов = 2, 10 отметок, 5 комментов - число серверов оценивается исходя из чистающих в день / 64т - место и канал: место считает из вводных и умножаем на 365, канал входящий = место в день / число секунд в дне исходящий канал: оцениваем число просматриваемых вопросов (20) * на число юзеров * средний размер сообщения	бд, блоб сторадж, балансер, кэш веб сервер, kv бд (hbase) для хранения голосов и разных доп. свойств , обучение мл происходит офлайн на hbase, применение может быть онлайн очередь для отправки уведомлений подписчикам	* вопрос: юезр, вопрос, описание, теги, видео, изображение * ответ: юезр, вопрос, ответ, видео, изображние * голосование: вопрос, ответ, юзер * коммент, поиск и т.д.	* сеть между веб серовером и api сервером - объединям в на одном (общаются через сокеты или шаред память) * mysql - бьется на несколько независимых партиций/таблиц/колонок, чтобы узнать где наши данные - используется zookeper * RockDB дает лучшую производительность чем HBase * InMem очереди заменяются на Kafka (она же используется для замены распределенных счетчиков) язык: c++ для бизнес критикал частей (извлечение фич для ML), в другим местах для быстрой разработки: python веб сервер узнает о изменениях по средствам long poling (или web sockets в новых браузерах) для катастрофоустойчивости достаточно бэкапов, которые синхронизируютя в S3
Google Map	текущее положение, быстрейший путь, текстовое сопровождение	доступность (репликация сегментов), масштабируемость, скорость, точность консистентность - не нужна	число серверов: предположим что число активных юзеров 32М /64К = 500 serv диск - фиксированный размер (20ПБ) трафик: входящий - минимален (только реквесты), исходящий: карта и текст (2МБ) * (32м*50 реквестов в день) / 3600/24	балансер, graph db, система поиска, pub/sub, KV store	* передача тек. положения не сервер * поиск пути: срц, дст, тип транспорта * следующий шаг (направление, сколько метров)	* как обходить громадный граф: бить на части и распараллеливать (55 км) внутри части уже можно использовать алгоритм Дейкстры - в реальности используются более быстрые с эвристиками (предсказаниями) расстояния и время между всеми точками (без учета трафика) расчитываются заранее и сохраняются в распределенную БД при расчете берутся сегменты которые на растоянии между точками от обеих расчетное время прибытие - данные положения отправляются в pub/sub. Имея значения других водителей, паттерны других дней, делается ML прогноз и отправляется обратно. Детали реализации сегментов: * Сегменты хранятся в KV, как ссылка на сервер Graph db Дополнительно тут же могут хранится координаты сегмента и список соседей * Графовая бд собственно содержит граф сегмента * +Обычная бд в которой храним: сегмент, путь, часы пробок сегменты могут быть разного размера, в зависимости от числа дорог
Yelp	информация о бизнесе, бронирование, отзывы - личный кабинет, возможность добавлять отзывы, поиск по координатам	доступность (репликация сегментов), масштабируемость, скорость, консистентность	число серверов: пользователей в день 60м /64т = 1000 серверов место: под места (500 млн) каждое по 1.5КБ (фото в блоб сторадже у каждого 3МБ) - добавляется по 5? мест, 1 млн ревью/день (600Б) и всего 180млн пользовательских акков (300Б) трафик входящий на добавление: 1,5КБ+3МБ+600Б * 5 новых мест + 1млн юзеров * ревью трафик исходящий: поиск возвращает 20 мест (3МБ) * 60м акт. пользователей / 3600/24	балансер, блоб сторадж, база, кэш	* поиск в категории в радиусе локации пользователя * поиск по имени в радиусе локации пользователя * добавить место: название, описание, категория, точка, фото * ревью: место, пользователь, описание, рейтинг на основе апи делается схема бд: фото выносится в отдельную таблицу, видимо, чтоб можно было вбудущем приложить несколько	* KV - для обработки гео-сегментов: - карта бьется на сегменты- 1 сегмент - 1 сервер число сегментов динамическое, 1 сегмент = 500 точек в нем (под это нужны отдельные сервера для процессинга) - Сегменты хранятся в KV - value - список точек - сегменты хранятся в виде дерева (QuadTree), сверху большие квадранты, в дочерниях узлах детализация в листьях находяится максимальная детализация. Все листья соедины 2-направленным списком, что позволяет быстро переходить к соседям - внутри сегмента ищем растояния до точек - сегменты еще можно побить на независимые партиции, к примеру по городу - для доступности делается несколько копий дерева через репликацию - в кэш кладем популярные места
Uber	текущее положение водителя, поиск водителей, запрос поездки оплата, время прибытия, подтверждение поездки, завершение поездки	доступность, масштабируемость, консистентность, надежность, фрод детект	число серверов: ( 20м пассажиров + 3м водителей ) / 64К = 360 серверов место: всего 500м пользователей * 1КБ+ 5м водителей * ( 1КБ + 36 положение) +10020 пользователей/день на хранение информации о поездках 365 дней так же оцениваем прирост и его * 365 канал: по большей части нужен только для обновления положения водителей = 3м * (3 - id driver + 16 - location)	балансер (вебсокет после до бд), цдн, кэш, бд	- обновить положение водителя - поиск пассажиром водителя - запрос поездки : откуда, куда, тип таски - время прибытия водителя - подтверждения поездки: водитель, пассжир - обновить статус поездки: водитель, пассажир, положение, время езды, осталось - завершить поездку: поездка, время поездки, положение	- сервис, который хранит текущие положения водителей и пассажиров (reddis / mysql) - карта побита на сегменты (QuadTree), как в Yelp для быстрого поиска ближайших водителей - отдельные pub/sub сервисы для запроса машины и обновления статуса поездки - сервис оценки времени прибытия, поиск кратчайшего пути (также бьем на части и делаем MR) - если проблемы с сетью или сервисами, данные могут сохраняться локально в телефоне ML модель для оценки трафика - БД: Mysql для inprogress поездок, чтобы была Consisten, а для длительного хранения: cassandra Схема бд: пассажир, водитель (человек и х-ки машины), текущее положение водителя, текущая поездка (обновить статус поездки) для доступности используются реплики: 1 для записи N для чтения Система оплаты работает через Kafka с помощью системы событий: создать заказ, найти заказ, оплатить, вернуть результат оплаты, записать факт перед поездкой ML модельу проверяет риск клиента фрод детекс водителя: увеличение времени/дистанции, манипуляции с gps, принуждение к завершению, не тот водитель/машина но фрод должен подтвердить человек
Twitter	создать сообщение, удалить, лайкнуть, ответить, поиск, просмотр таймлайн, подписка, ретвит	доступность, отклик, масштабируемость, консистентность, надежность	исло серверов: ( 500м пользов * 20 просмотров ) / 64К = 157т серверов диск: X=50м 3 твита 250Б; +X10% 200КБ на изображения; +X5%3МБ видео; 365д = 93ПБ сеть = 500м 50тв*250Б (+10% изобр, +5% видео) /3600/24 = 400ГБ/с	днс, балансер, секвенсер, бд, блоб, kv store, pub/sub, счетчики, кэш, цдн, мониторинг	функц. + user, location, tag (hash,user), media	хранение: хдфс или блоб сторадж бд: разные под разные функции (для рекламы - реалиц.), иначе kv образные kafka используется как шина для передачи данных в аналитику (bq) множество микросервисов, чтобы не усложнять балансировщик клиент сам делает балансировку: * выбирается N случайных, между ними выбирается менее загруженный * клиенты разбивают сервера равномерно по кругу
News feed	генерация фида новостей, отображение (комменты вынесены за скобки)	доступность, отклик, масштабируемость, надежность (толерантность разделению)	число серверов: ( 500м ) / 64К = 8т серверов диск: 1млрд пользователей * 50кб личная страница + 50кб сообщение500м акт. пользов.200 постов на пользоват 365 дней = 50ТБ в бд + 1/5 потостов видео (2мб)+4/5 изображ (200кб) 365 дн = 60ПБ (в блоб сторадж) сеть = 500м * (50КБ + 2МБ/5 + 200кб4/5 ) 20 постов на главной /3600/24 = 500Гбит/с	бд, кэш, блоб, цдн, балансер	* генерация фида для юзера с нужным числом сообщений бд: юзер, сообщение, группа, медиа, связь пользов-пользов	* генерация фида: получить список друзей и друзей друзей (можно использовать графовую бд), выбор постов на основании пред. лайков/просмотра (ML), сохранение в кэш кэшировать можно не сами посты, а ссылки на них (тогда и грузить их отдельно) * ранжирование постов: время, просмотры, лайки и т.д. * pub/sub для обновления кэша при добавлении нового поста * мониторинг, репликация для доступности и надежности
Инстраграмм	фото/видео, follow, лайк, поиск, фид	доступность, масштабируемость, скорость, консистентность с оговорками,, расширяемость	число серверов = 500м юзеров /64К=8к серверов оценка места: 60м3мб+30м150мб365=2к ПБ сеть: место 100 дублирование в лентах	балансер, бд, блоб, шедуллер, кэш, цдн	* пост: пользователь, тип медиа, хэш теги, описание * follow/un: юзер 1, юзер 2 * лайк/диз: юзер, пост * поиск: текст * генерация фида: юзер, с даты схема бд: лучше подходит классическая бд, т.к. нужны разные фильтрации и джойны схема бд соотвествует апи. Таблицы связки: последователи, лайки	* разделяем чтение и запись, т.к. сущ. разница в нагрузке * кэшируем популярно, лениво загружаем картинки * генерация фида: хранится в KV базе, value даже может лежать в blob storage - pull: фото добавляетя в общее хранилище, сервис офлайн генерирует ленты пользователям используется для акков с большим числом подписчиков - push: фото добавляется в ленты пользователей сразу для всех остальных - таск шедуллер для чистки сторисов спустя 24ч - лоад балансер кэширет данные в цдн - шаред счетчики для лайков
Сокращатель ссылок	генерация юрл, редирект, кастомные ссылки, U/D, expiration	+ к стандартным - непредсказуемость (для секретных ссылок), легкая запоминаемость. Консистентность не нужна.	диск: 1 к 100 - добавление к переходу, 200м ссылок, 500б - 1 ссылка, 5л - время хранения, 100м пользователей серверов: 100м/64к сеть: 500100м/3600/248б память под кэш 20% активных ссылок: 200м1000,2*500/3600/24	бд, секвенсер, балансер, кэш, лимитер	* сократить: ключ, юрл, алиас, дата удаления * редирект: ключ, шорт юрл * удалить и т.д.	* бд шардированная: 1 сервер для записи и несколько реплик чтения шардировать можно по 1 символу краткой ссылки MongoDB - более read нацеленная * генератор ссылок: секвенсер перекодирует 10б число (64бит длинной = 19 символов) в 58битную строку (буквы мелкие+заглавные+цифры) почему 58, а не 64 - исключены 0/o , I/l +/ для читаемости 10 ричное число в 58: значение разряда = %58, след. шаг /58. Полученное число 1-58 использует таблицу алфавита 58 в 10ное: sum(число в разряде из таблицы 58^номер разряда) 1 млрд значений можно использовать под платные короткие значения каждому серверу генератора ссылок дается уникальные ID, что гарантирует непредсказуемость финального ID memcache - для кэша, т.к. не нужны сложные структуры * rate limiter - для ограничения потока соращений с 1 аккаунта
Индексатор для поиска	читать содержимое, сохранять, повторять по расписанию или запросу	+ к стандартным: расширяемость, нужно уметь парсить не только текст всякие надежности нужны не очень	диск: 5млрд 2МБ серверов: нужен полный обход раз в день, время 1 страницы = 0,06с 5млрд0,06/3600/24/число ядер в машине (16) = 217 сеть: диск /3600/24/8бит	шедуллер, днс, кэш, блоб		Шедуллер: * очередь - url для обработки лучше распределенную для быстроты чтения (не изза объема) и разные очереди для разных приоритетов частота обновления зависит от замеренной частоты обновления ранее и robots.txt * база для списка url Днс - лучше свой, чтобы быстрей резолвить адрес Дедубликатор проблемы: динамические/цикличные ссылки ограничивать чисо страниц на домен, как то фильтровать используя ML? настраивать интенсивность в зависимости от скорости отклика, чтобы не перегружать
WhatsApp	обмен сообщениями, статус сообщ., отправка медиа, хранение медиа до получения, нотификации	скорость, конс, доступ., защищен, расширяемость	диск: 100млрд сообщ/д100б/сообщ+медиа (каждое 5)+профили 365д сеть: размер сообщ./д / 3600/24 серверов: 2 млрд пользователей / 64т	бд, блоб, цдн, балансер, кэш, очередь	методы апи соответствуют функц. требованиям без неожиданностей	минусы и последующие усовершенствования: * websockets для соединения через балансер * веб сокет менеджер+редис - маппинг юзера и сервера с вебсокетом (тут может быть кэш) * шардированная бд для хранения сообщений * на стороне клиента: шифрование, сжатие в блоб сторадж и распространяется в цдн, в веб сокет отсылается только ссылка * для групповых чатов используется кафка * данные о пользотвателях в mysql * для консистентности нужен распределенный счетчик (можно сохранять в кафке) * при разделении сети , приоритетна консистентность, т.е. сервис перестает работать
Система подсказок в форме ввода	топ 10 подсказок	быстрота, отказоустойчивость, расширяемость	диск/память: 2 млрд уникальных запроса/д * 15 байт * 2 байта в букве * 365д сеть: 2млрд10 топ сообще 15 * 2 б/букв / 3600 /24 серверов: 3,5млрд*3 вариации ввода / 64к = 164к серверов	бд, балансер, кэш	* получить подскаку по префиксу * добавить запрос в бд	структура для хранения: TRIE - префиксное дерево кэшируем топ 10 предложений в каждой ветви после 3 букв можно сделать несколько trie зашардированных по начальной букве число запросов фразы обновляется MR офлайн на копии дерева, которая периодически подменяется суммы сохраняются в кассандру - сервис строит trie и сохраняет в noslq бд обращение к сервису должно быть после задержки в 200мс (исключить промежуточные вводы) кэш на клиенте, кэш в цдн, веб сокет соединение устанавливается заранее при входе
Гугл. документ	может быть пир2пир, может быть через сервер, у нас вариант через сервер функц: совм. ред. документа, резолв конфл., подсказки+спел чекинг, счетчик просмотров, история	скорость, консистентность, достпуность, расширяемость	вводные: 80млн пользов/день, док. 100кб, в 30% - фото (800к), 2% видео (3м), каждый пользвот. создает 1 док, макс 20 активных юзеров/док диск = 80млн1(100кб+800кб0,3+30000,02)365 сеть: вход=диск за день / 3600/24, исх=20док/двход.сеть серверов: 80м/64т=1,3т	балансер, бд, pub/sub, кэш, блоб, очередь, цдн		* pub/sub - для нотификаций * очередь с фифо для последовательной обработки доп. компоненты: api gateway, websockets, тайм сирис бд для версий, редис для кэша сессий и подсказок (но основа в KV бд), KV бд для комментов, mysql для данных пользователя аппликейшенен сервер для загрузки и выгрузки в другие форматы Борьба с конфликтами: * Operational transformation (OT) - действия пользователей объединяются 2 юзера добавляют букву в 1 место - будет 2 буквы, при удалении 2 юзерами 1 буквы - удалятся 2 буквы т.е. фактически действия сериализуются и выполняются последовательно * Conflict-free Replicated Data Type (CRDT) данные вставляются именно на нужные позиции, как изначально задумывалось (т.е. будет мешанина)

Скахин Алексей / pihel

Страницы

среда, 3 июля 2024 г.