Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
23 kB
2
Indexable
Never
 Системный дизайн
1. Сбор требований к системе - что эта система будет делать. Нужно определить конкретный функционал о котором будем говорить далее (для начала базовые для обсуждения сейчас, доп. на будущее).
 - функциональные требования (создание и обновление профиля, подписка на аккаунты, видеть ленту на кого подписан, создание постов)
 - нефункциональьные требования (доступность(скорость), надежность, консистентность) В банке надежность, а в соц. сети доступность и не притично что юзер чуть позже увидит пост - не идеальная консистентность между юзерами в момент времени.
 
2.1 Расчет нагрузки на систему - оценка реалистично ли это относительно наших планов и бюджета. откуда и какая нагрузка, перекосы в стороны чтения или записи, какое железо и интернет канал подойдет
  - Пользовательский трафик:
	MAU, DAU, кол-во юзеров за 5 лет и сколько контента в среднем генерирует юзер. Исходи из этих входных бизнес показателей мы оцениваем РПС,
		кол-во одновременных соединений, нагрузка на сетевой канал и сколько трафика потратим. Сколько займет места в хранилище.
 - Сетевой трафик и соединения
	Состоит из кол-ва удерживаемых соединений и кол-ве передаваемого трафика.
		(2011 - ватсап 1млн, 2015 облачный провайдер на 10млн. по дефолту наш сервис обычный 10-100к будет выдерживать.)
		(трафик обычный сервер 1гигабит/с, между своими частями медная витая пара - 10Гб. оптоволокно - 40Гб, есть и по 100+Гб. Обычно 1Гб и 10Гб если повезет между своими сервисами.
 - Вычислителььная нагрузка - web frameworks benchmark (физ и клауд) - дефолт это 100к рпс для текстовых данных, 10к и 1к чтение и запись для облака. для физ. серверов в ~5 раз выше. реальные хар-ки в ходе тестов.
 - Приращение и общее место в хранилище
		нагрузка на хранилище (хдд 100-300мб/с, до 20тб - 500$, ссд до 3-5гб/с, до 8тб - 2000$, рам до 50 гб/с, до 128гб - 1к$) - 1 тб рам - 10к, ссд - 300, хдд - 30. 1 сервер можно рассчитывать - 1тб рам, 50 тб ссд, 200 тб хдд
		
2.2 Сделаем оценки исходя из следующих допущений:
1. 1М загрузок каждый день. ( MAU 10M, DAU 500K, 2 загрузки в среднем)
 Чтение к записи 10 к 1
- Обращение к сервису в месяц 1М * 10 * 30 = 300М
- Нагрузка на создание 1М/86400=~12RPS, на чтение 12 * 10 = 120RPS
Если каждый запись умещается в 10КБ, то 10КБ * (120+12)RPS = 1.2MB = 10Mb (а сет трафик обычно 1Гб/с)
На горизонте 5 лет - 1М * 30 * 5 * 12 = 1.8МЛРД
1.8 * 10КБ = 18МЛРД КБ = 18 ТБ => хватит одного дорогого ХДД до 20ТБ
2. 100М DAU. Каждый отправляет по 100сообщение размером 1КБ. Чтение 10 к 1 к записи
Сеть: 100М * 100 / 100k = 100k RPS, 100k * 1KB = 1Gbps => 20 PB за 5 лет. Чтение = * 10
Вычисление: 100к РПС и 1М РПС
Хранилище: храним 20ПБ за 5 лет + метаданные
Стоимость: 20ПБ трафиика обоойдется в 2М$ + на хранение 20ПБ уйдлет 600к$ в случае хдд

3 Высокоуровневый дизайн
- Дефолт схема User - Service - DB со спецификой нашего сервиса.
Если работа с файлами, то Service - (Metadata DB/ File Storage)
Если разные сценарии взаимодействия со стороны пользователей (Такси: водитель и пешеход), то (Водитель/Пешеход) -> Service - DB, взависимости от сценариев и нагрузки можно успешнее понять нагрузку.
,. Если нагрузка большая, то больше серверов и инстансов сервиса + лоад балансер с распределением сервисами

4. Выбор БД
CAP теорема. CA - РСУБД. CP - redis hbase mongo. AP - cassandra couchdb dynamodb
Если данные структурированы и много связей между ними ИЛИ данные чувствительны (деньги, баланс) - РСУДБ
Если JSON любой структуры, много запросов к БД - документные, монго или эластик. 
Если кэш для другой БД, счётчики и агрегаторы, по ключу - key value - редис
Если много однотипных записей с фикс колонками и редко запрос к ним - колоночные - кассандра, кликхауус

Какие данные храним?
- профили пользователей (метаданные)
- онлайн данные о пользователях или текущие поездки или текущую ленту
- офлаййн данные о истории поездке
Стандартные метаданные или со сложными связями или чувствительные данные - РСУБД. Если данных миллиарды и они легко связанные, то JOIN делаем программно и храним в колоночной БД Кассандра. (РСУБД сложно масштабировать)
Текущие поездки или недавние, статусы онлайн или открытые чаты - Redis. 
После завершения поездки в постгрес - нуждающиеся в ACID данные фиксируем в постгрес и отправляем выполненные заказ в историю в Кассандра.
Все медиафайлы картинки или видео - в С3
Позиции водителей в спец. гео-БД
Ленту пользователей заранее кэшировать в Redis. 

5. Модульный дизайн
Здесь рисуем квадраты всей логики. Микросервисы + Message Brokers (RabbitMQ or Kafka)
Добавляем брокер сообщений чтобы избавиться от жесткой связи. Иначе скорость выполнения запроса и ответа будет зависеть от самой медленной части выполнения в нашей цепи.
Если нам не нужно срочно получить результат то можно добавить брокер сообщений (долгоиграющая работа по которой мы не получим сразу результат)

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

Сервис бронирования: 3 вида пользователей. Hotel UI/User UI/Booked UI - у каждого свой микросервис на бэк
Hotel UI -> Hotel Service -> Hotels DB
User UI -> User Service -> Users DB
User UI -> Search Service -> Hotels DB
User UI -> Booking Service -> Booking DB

6. Масштабирование системы
При увеличении кол-ва серверов
- распределение нагрузки:
промежуточный LoadBalancer для распределения запросов или BUS (шина, например Kafka)
LB выполняет хелсчеки, что сервисы живые(каждые 10с или 1мин), если не отвечает, то вызывает хелсчек после (через 1мин, через 10мин.) если не отвечает - удаляет из своего пула. exponential backoff
как LB выбирает подходящий сервер? кол-во соединений, время ответа или сетевой траффик, пользовательский хэш по IP или userId, round-robin, weighted round-robin(у каждого сервера весовой кф исходя из его кфг)
то есть если передается что-то большое и запят сетевой канал траффиком, то распределяем с помощью LB по сетевомуу траффику, если висят много соеденинй - то по наименьшим соединениям и т.д.
- распределять данные внутри хранилища (данных слишком много - не помещаются на сервер):
Намного тяжелее чем нагрузка запросов…т к мы должны знать где и какие лежат данные, и доступ должен быть у всех к паблик данным 
Секционирование или партиционирование.
По умолчанию вертикальное секционирование - вынос таблиц или индекса и т д целиком на сервер. Но даже таблица может не влазить
Горизонтальное секционирование - вынос частей таблиц или индекса на отдельные сервера, разделяя по логическому принципу. (Если по дню недели бронирования, то будет перекос на сервер с выходными, важно правильно подобрать ключ: userId, хэширование что-то в мд5 и по модулю 100 на 100 серверов; таймстемп % 100)
Но есть и проблемы: невозможное выполнение join. Решается денормализацией. Невозможность отслеживать валидность внешних ключей. Перекосы нагрузки на сервера, если чтооо выйдет из строя или перераспределение данных на 110 вместо 100 серверов
Костистентное хэширование???
- репликация: пероеживать вывод части машин из строя
Избыточность и репликация - дублирование важных частей системы для повышенной надежности. LB - активный и LB - ожидающий, который хелсчекает активный и заменяет его если выйдет из строя)
Репликация повышает надежность, устойчивость к отказам и доступность системы. Можно например писать в основную, а читать из реплик для улучшения доступности. 

7. Повышение отзывчивости
 - Кэширование данных
Кэш может быть на любом уровне. Используется чтобы быстрее получить данные, чтобы не идти по шардам в исходные данные, или чтобы не проводить вычисления вообще. Редис в оперативной памяти. Принцип поретто. 20% активных данных генерируют 80% нагрузки. 
 - инвалидация кэша 
 1. Сквозная запись
 2. Запись в обход
 3. Реверсивная запись  
 6 видов алгоритма замены кэша.
Можно самые популярные активные юзеры хранить в рам редис, остальных на ссд, в непопулярных на хдд

CDN кэширование.
Netflix open connect

 - Индексация БД 
В распределенной системе можно в индексе указывать шард где находится нужная запись.
 - Cоздание ID записи
 4. автоинтеркмент не на 1, а на кол-во инстанстов БД - тогда не пересекаются ИД (число статично и сложно подстраиваться, так же ид между БД могут сильно разбежаться, если один сервер с БД более мощный)
 5. UUID - униткальное строковое значение. 128 бит. Нельзя соотнести по времени. Коллизии почти невозможны на горизонте долгих лет. Синхронизировать между серверами не нужно.
 6. Сервис ИД Генератор для всех БД и таблиц. ИД всегда будет упорядочен по времени. ИД пересекаться никогда не будут. Проблема в том, что этот генератор - единая точка отказа в системе, без него ничего не будет записываться, для надежности нужно думать о надежности и репликации.
 7. snowflake от твиттера - помещается в 64 бит. упорядочено по времени. ид генерируется независимо, так же по ид можно сразу определить датацентр и машину в нем - упрощается маршрутизация при доступе к данным.
 ⁃ Соединения и протоколы 
 8. ajax polling - клиент постоянно спрашивает сервер об изменениях., при отсутствии сервер возвращает пустой ответ
 9. long polling - клиент создает висящий запрос и по изменениям на сераере отдается ответ. т.е. пересылаем данные только тогда когда это нужнО, нет пустого ответа. Можно в клиенте поставить тайм-аут. Все равно забиваем соедининя
 10. Web-Socket - устанавливается соединение между клиентом и сервером для взаимного обмена ивентами. Минимальные издержки при передачи.(TCP, не ХТТП, а протокол связи на основе сообщений)
 11. SSE - как веб-сокет только в одну сторону. Server Sent Event (HTTP)
 
8. Система для поиска
- Автодополнение
префиксное дерево (trie от retrieval)
к - карпов(999)
к - кур - курица(16)/курсы(150)
если только в листьях указывать count, то сложность o(p + clogc) p-кол-во вершин до нужного узла, с - кол-во элементов поддерева
но можно в каждом узле записывать информацию о всём поддереве, то сложность константа: к - кур ([курица(16)/курсы(150)] - курица(16)/курсы(150) - тогда просто находим необходимый узел и достаем уже всю инфу о поддереве
только при обновлении данных нужно обновлять не только лист, но и все узлы выше этого листа. 
- Текстовый поиск
поиск подстроки - строится префикс-функция за линейное время особым алгоритмом (курс#карповкурс(4)ы)
поиск набора слов целиком в тексте - алгоритм Ахо-Корасик. Сначала строится автомат для соответствующего набора. Потом фраза-строка прогоняется через автомат. Обрабатываются буквы по очереди, мы находим все вхождения. 
поиск по шаблону - стандарт wildcard. Строится матрица (m - вертикально паттерн, n - горизонтально строка для проверки) - проверяются совпадения. если по диагонали единицы по углам, то совпадает. . Сложность - m*n
ы 0 0 0 0 0 1
с 0 0 0 0 1 0 
* 0 0 1 1 1 1 
у 0 1 0 0 0 0
к 1 0 0 0 0 0
  к у р р с ы
- Поиск по геолокации
geohash - разделяеем область (шар/город) на 4 квадрата (00 01 10 11), квадрат ещё на подквадрат, составляем хэш 000110011010 и т.д. (12 бит - точность до км, 20 бит - до 1м.)
легко находить радиус. Если префикс с одинаковых цифр, то они рядом, обратное не гарантировано. Нужно перехешировать, если что-то пойдет не так или нужно что-то поменять в алгоритме. Легкая реализация. Новая запись = новое заведение.
quadtree - делим на квадрат, квадрат на ещё квадраты и так до тех пор, пока не будет достаточно. если много заведений - то больше квадратов, чтобы в 1 квадрате не было сильно много. легко находить в рамках квадрата. 
на уровне выше квадрата (парент квадрат) ещё 3 таких же квадрата - расширение происходит вправо вниз (если было сверху слева). Uber использует гексаганальную фигуру, чтобы распределение было более менее равным.
 Нужно создавать структуру и постоянно балансировать её.

Пример сервисов:
- Search UI -> Search Service -> Logging Service -> (Query DB) <- Indexing Service -> (Trie DB) <- Autocomplete Service <- Search UI
- Search UI -> LB -> Search Service -> ElasticSearch (DB) <- Indexer Service -> (Any_db)
- Editor UI -> Editor Service -> (DB) <- Indexing Service -> (Geo Index). (Cache DB) <- Geo Search Service <- Search UI

9. Доп. подсистемы
- Ограничение нагрузки (целенаправленная или нет - любая)
кол-во запросов пользователя/устройства/ип-адреса. Так же для безопасности: перебор паролей, банк. карт или любая ддос атака. 
небезопасно ставить рейт лимитер на фронте, типа дизейбл кнопки, ибо можно сниффать запрос или через деф тулс и отправлять руками.
User UI -> Rate Limiter -> Application
User UI -> Application <-> Rate Limiter
5 разных видов рейт лимитера. Фаервол настройка.
Можно использовать внешние сервисы типа клаудфлаер.
- Мониторинг 
grafana - в первую очередь используется для отображения показателей в дашборде
прометеус - хранилище. можно сохранять метрики и отображать например в графане.
все сервисы должны логировать события, либо вызывть логгер сервис, либо в кафку(лучше), из кафки читает логгер сервис и сохраняет метрики в хранилище (колоночная бд или прометеус например),
 после сервис аналитики или графана может отображать или анализировать все метрики и на основе них принимать какие-то решения.
В ML можем использовать spark + hadoop + ML в хадуп кластере от МЛ инженеров на ходу. анализируем и отдаем обработанные данные дальше в кафку в наши сервисы. 
- разбор полетов (жалобы пользователей)
логируем все действия пользователя, на ккаждом этапе отправляем в кафку лог событий, сервис обработки - архивал сервис слушает и обрабатывает все события, как-то хранит и анализирует.
 К этому сервису есть доступ с Admin UI, админ может восстановить всю хронологию событий и сказать как все было.