Высоконагруженные приложения. Программирование, масштабирование, поддержка

Легендарная книга с Кабанчиком. Рассматриваются всякие бекенд штуки: внутреннее устройство бд, паттерны использования бд. Полезна для собесов и для работы.

Основы информационных систем

Надежность, масштабируемость, удобство

• Надёжность - как система реагирует на сбои
• Сбой - когда кусочек системы работает ненормально
• Отказ - когда вся система не работает

Чтобы система была устройства к сбоям, и чтобы это не переходило в отказ, нужно постоянно тестировать систему, искусственно вызывая сбои (например что-то отключать, и проверять, что система работает)

Виды сбоев:

• Аппаратные сбои - когда железо хромает, помогает сделать несколько железяк (напр raid массивы)

• Программные сбои - ну понятно, всякие кейсы когда сторонние системы не робят, лечится допущениями и ретраями

• Человеческий фактор - тоже понятно, когда чето неправильно настроили, лечится откатами, песочницей, тестированием, метрики

• Масштабируемость - как система реагирует на возросшую нагрузки

Важно понимать что нагрузка возросла. Для этого используются параметры нагрузки

Примеры параметров нагрузки: запросы в секунду, соотношение операций записи и чтения

Способы чтения на примере тви:

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

Время ответа хорошо трекать с помощью перцентилей:

• 50 перцентиль - медиана
• Перцентили выше (95, 99) могут быть важны в случае больших запросов от клиентов (напр большая корзина)

Виды масштабирования:

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

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

Удобство сопровождения - когда мало Легаси; также включает в себя эксплуатацию, простоту и расширяемость

• Эксплуатация - удобство работы системы для операторов
• Операторы оч важны, и хорошие операторы могут работать и с плохими системами
• В обязанности оператораров входят различные типовые операции, удобство эксплуатации заключается в автоматизации таких операций
• Простота - ну понятно, если сложно, то сложно
• Чтобы уменьшить сложность, можно накидать слои абстракции (напр юзать высокоуровневые языки по сравнению с низкоуровневыми)

Модели данных и языки запросов

• SQL = отношения (таблицы) с кортежами (строками)
• NoSQL = Not Only SQL

Причины появления NoSQL:

• Новые возможности масштабирования
• Осс > клозед сурс
• Более сложные запросы
• Динамические схемы
• Объектно-реляционное несоответствие
  • Модели в коде могут иметь сложные связи, типа массива
  • В случае sql нужно делать хуилиард таблиц, и джоинить
  • А в случае NoSQL можно выразить все одним jsonом
  • Хотя и в sql можно json-поля сделать

Связи «многие-к-одному» и «многие-ко-многим»-

Можно хранить повторяющиеся данные (напр. должность) текстом, можно ФК на табличку использовать:

• Если текст, то будет жёсткое дублирование, и при замене может возникнуть ситуация когда что-то обновилось, а что-то нет
• Использование фк удобнее, потому что единообразие, удобно редачить, поиск удобный, локализацию можно сделать
• Использование фк вместо текста называется нормализацией
• Соответственно денормализация - наоборот когда используется текст вместо фк

Поначалу может показаться что делать строки это просто и удобно, но потом текст может разразрастись до сущности ( название компании > сущность компания) - так появляется связь многие ко многим

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

Динамическая и строгая схемы данных

• Динамическая схема = Неструктурированная модель в документоориентированной бд = schema less = schema on read - то есть проверка типов происходит в коде; это удобно когда данные могут быть разных типов (кейс сторонних систем)
• Строгая схема = Реляционный подход = schema on write - когда мы записываем данные и они будут соответствовать схеме данных; и при чтении необязательно проверять типы, они также будут соответствовать схеме
• Динамическую схему очевидно проще менять: так если хотим разбить имя на имя и фамилию, достаточно написать код; в то время как для строгой схемы нужно писать миграцию.
• В некоторых СУБД (мускуль) миграция может вызвать простой системы, тк применение миграции занимает много времени, обойти это можно используя утилиты или в случае с update (которая может тормозить в любой бд) можно выставить значение по умолчанию и заполнять в коде
• Локальность данных = все в одном месте (не разнесено по нескольким таблицам) хороша когда используются все данные ( кейс веб странички); но при этом документ выгружается целиком, что может быть не экономно. Аналогично при записи документ перезаписывается целиком, что тоже может занимать больше времени по сравнению с реляционной бд; так что лучше когда документы мелкие

Декларативный и императивный подходы

• SQL - декларативный подход к запросу данных, то есть мы пишем лишь то, что нам нужно, используя ограниченный синтаксис, а как данные будут получены решает оптимизатор. Также такой подход облегчает внутренние оптимизации и параллелизм.
• Императивный подход напротив требует написания кода: например получаем все доки, итерируемся по ним в цикле, фильтруя данные
• Ещё пример декларативного подхода - css по сравнению с js. Поиск css-селектора осуществляется браузером, так что создатели браузера могут оптимизировать его работу и не нужно будет переписывать код, js-код по поиску элемента оптимизируешь только ты, и придется менять код
• MapReduce - гибридный подход - пишешь чистые функции, которые могут выполняться в любом порядке и параллельно
  • Минус - в отсутствии декларативности
  • но в монге есть aggregation pipeline синтаксис, который позволяет писать мап-редьюс с помощью ограниченного синтаксиса, что обеспечивает внутреннюю оптимизацию

Графовые модели данных

• Графовые модели данных - соцсети, ссылки на веб страницах, дороги
• Граф состоит из вершин и ребер
• Алгоритмы на графах поиск кратчайшего пути для автомобилей, pageRank для рейтинга веб страниц

Графы свойств

• Графы свойств - neo4j, titan, infinite graph
• Вершины содержат айди, входящие и исходящие ребра и произвольные свойства
• Ребра содержат айди, начальные и конечные вершины и произвольные свойства
• И на основе этих данных можно соединять ребрами любые вершины, совершать обход графа, и хранить разную информации

Графы хороши тем что их можно расширять:

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

Cypher - язык запросов для графов (neo4j), там все стрелочками отписывается, плюс он декларативный, что хорошо

Все это можно реализовать как 2 таблицы - таблица вершин и таблица ребер, и использовать обычный SQL, но запрос будет больше и сложнее для понимания, так что своей задаче - свой инструмент

Тройные кортежи = Turtle формат = N3 (notation 3)

• Субъект, предикат, объект
• Если объект - примитив (число, строка), то предикат и объект - пара ключ-значение (Маша, возраст, 20 => возраст=20)
• Если объект - вершина, то предикат - ребро (Маша, жената на, Пете => Маша и Петя - вершины, жената на - ребро)
• Семантическая паутина = RDF - альтернативный способ записи тройных кортежей для веб страниц в xml-формате
• SPARQL - язык запросов для тройных кортежей
• Datalog - предшественник Cypher и SPARQL; сам язык - подмножество Prolog - так что это логическое программирование;
• Cascalog - Hadoop реализация языка

Подсистемы хранения и извлечения данных

Структуры данных SQL = подсистемы хранения = Log-structured и page-oriented

Log-structured подход и Индексы

• Log-structured - данные записываются в конец файла (журнала, log)
• Индекс - структура данных для поиска, производная от данных
• Индексы можно добавлять и удалять, не затрагивая содержимое бд
• Поддержка индексов требует затрат на запись. Любая запись в бд будет сопровождаться обновлением индекса
• Так что индексы ускоряют чтение, но замедляют запись, и создание индексов лежит на плечах у разраба

Хеш-индекс

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

• Хеш-индекс используется в системе хранения Bitcask в NoSQL бд Riak, и такую систему хорошо использовать для счётчиков просмотров

• При log-structured подходе есть проблема того, что файл с логом будет большим, решается она разбивкой файла на несколько файлов лимитированного размера (сегменты) + применение уплотнения (compaction) - т.е. отбрасывание дублирующихся ключей

• Затем получившиеся стройные файлы можно слить

• Таким образом получаем файлы-сегменты и по ним строим хеш-таблицы и храним в ореративе

Типовые проблемы и решения при таком подходе:

• Формат файла - бинарный
• Удаление - делаем спец метку (tombstone), которая говорит о том что нужно игнорировать предыдущие значения ключа
• Сбои - чтобы не считать заново хеш-таблицы, можно хранить их на диске
• Недописанное записи - используем контрольные суммы
• Конкурентный доступ - несколько файлов и несколько сегментов - значит можно параллелить чтение
• Почему запись в конец файла? Потому что быстрые операции, лёгкость конкурентного доступа и восстановления, решение проблемы фрагментирования
• Ограничения хеш-таблиц: они должны помещаться в оперативу, и запросы по диапазону неэффективны

Ss-таблицы и lsm-деревья

• Ss-таблица (sorted string table) - формат файла, где ключи отсортированы + ключ встречается в сегменте один раз
• Формирование ss-таблицы получается путем эффективного слияния нескольких сегментов в блок
• Индекс при этом получается разряженным (не обязан хранить все ключи), и можно искать ключ используя факт что он находится между двумя другими ключами
• Сами блоки небольшого размера, по ним быстро происходит чтение + можно сжать
• Как происходит вставка с сохранением порядка? Используются деревья (красно-черные, avl) - memtable - которые размещаются в оперативе
• Когда размер memtable достигает лимита, то сохраняем ss-table на диск
• Также ведём журнал с записью в конец для кейса восстановления
• Этот алгоритм используется в подсистемах хранения LevelDb и RocksDb, которые используются в Riak. Также аналогичная подсистема в Cassandra и HBase.
• Вся эта система (с уплотнением, слиянием отсортированных файлов) называется LSM (Log-Structured Merge-Tree)
• Также похожий принцип используется в Lucene - поисковый движок, на котором работает Elastic Search. Ключ-значение состоит из терма и списка айди документов, которые содержат терм
• У такой системы есть проблема: поиск ключей, которых нет, может занимать много времени - но для этого есть спец структуры данных, типа Фильтр Блума
• Уплотнение и слияние бывает разным: size-tiered compaction, leveled compaction

B-деревья

• Хранят пары Ключ-значение, ключи отсортированы
• В отличие от LSM, данные разбиваются не на сегменты переменного размера, а на блоки/страницы фиксированного размера, аналогично разбивке на диске
• Каждый блок имеет ссылку на другой блок, так можно создать дерево страниц, по которому просто искать
• Одна из страниц - корневая, представляет из себя ключи и ссылки на дочерние страницы; ключи указывают диапазон страниц
• То есть 10 (граничный ключ) ссылка (на диапазон страниц в границах ключей) 20 (второй граничный ключ)
• При поиске постепенно сужаются границы ключей, и мы попадаем в страницу-лист, где ключу соответствует значение
• Branching factor - кол-во ссылок на дочерние страницы, зависит от дискового пространства
• Запись значения происходит как и поиск - O(log n). Если место кончилось, то блок разбивается на два, и родитель обновляется
• Отказоустойчивость достигается с помощью WAL (write ahead log) = redo log - куда записывается операция записи в b-дерево до совершения операции
• Конкурентная запись происходит с помощью latch - облегченный вариант блокировок

Усовершенствования b-деревьев:

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

Сравнение b-tree и lsm-tree:

• Чтение: B-tree > LSM-tree
• Запись: B-tree< Lsm-tree
• Размер на диске: B-tree< Lsm-tree

Минусы LSM

• Уплотнение может занимать время, и время на больших перцентилях возрастёт
• Большое количество операций на запись отсравивает уплотнение, что замедляет чтение

Еще про индексы

• Вторичные индексы - индексы по столбцам, не являющихся первичными ключами
• Значение ключа в индексе может быть строкой (напр айди записи), может быть ссылкой на кучу - heap file, где хранится строка. Использование кучт хорошо чтобы избавиться от дубликатов
• Ходить в кучу бывает не оч эффективно, тогда хранят строку, то есть индекс кластерный
• Covering index = index with included columns - использование обоих подходов.
• Когда запрос можно выполнить используя только данные из индекса - значит индекс охватывает запрос
• Concatenated index - когда ключ состоит из нескольких полей (фамилия и имя), при этом важен порядок! (Поиск по имени бесполезен)
• Многомерные индексы - когда ищем по области (поиск ресторанов в промежутке координат) - R-дерево
• Fuzzy-запросы - когда ищем текст с ошибками. Помогает использование редакторского расстояния.
• In-memory db - когда храним все в оперативе, примеры: redis, memcache. Для надёжности можно делать слепки на диск, использовать спец железо, журналирование и тд. Если место кончается, то можно использовать антикеширование - старье на диск складывать

OLAP

• Oltp - обработка транзакций в реальном времени - чтение небольшого количества записей, пользователь интерактивно добавляет/меняет записи, скорость выполнения транзакций должна быть высокой
• Olap - аналитическая обработка данных в реальном времени - всякая статистика - обработка большого количества записей , причем лишь некоторых столбцов; запросы могут выполняться долго
• Data warehouse - склад данных - бд для аналитики
• ETL - extract - transform - load - процесс загрузки данных из oltp баз в data warehouse
• Примеры data warehouse: Teradata, Vertica, SAP HANA, ParAccel (Amazon Redshift), Hive, Spark, Big Query.
• Схема Звезда - типовая модель данных в складах данных. Ключевая сущность - таблица фактов - таблица из событий, которые состоят из столбцов (зачастую фк) других таблиц - таблиц изменений
• Схема Снежинка - подвид звезды, но таблицы изменений разбиваются на подизмерения
• В складах данных данные располагаются не построчно, а по столбцам - так в запросах, которые аггрегируют несколько полей, не придется грузить строки, в которых столбцов может быть сильно больше чем в запросе
• Также для оптимизации столбцы можно сжать, тк значения в них повторяется. Типовой метод сжатия - bitmap encoding - значения перебираются, и результат кодирование это количество нулей (значение отсутствует) и количество единиц (подряд идущие позиции: 1 2 3 3 => 1 - 0 1 2 - 1 1 3 - 2 2
• Если нулей много, то битмапа разряжена, и ее можно дополнительно сжать алгоритмом кодирования длин серий
• Модели данных в Cassandra, HBase, BigTable используют понятие column family - это не то же самое что столбчатое хранилище
• На уровне железа для хранилищ данных применяется векторизированная обработка
• Сортировка строк по определённым столбцам имеет смысл для более эффективного поиска, и более эффективного сжатия
• Также можно хранить несколько сортировок (используется в Vertica)
• Материализованные сводные показатели - речь об агрегируемых функциях типа sum, и о том почему бы их не кешировать.
• Один из способов - materialized view - похоже на обычный view в бд (сокращенная форма запроса), но это именно результат выполнения запроса
• Data Cube = OLAP Cube - частный случай materialized view - сетка показателей по данным столбцов
• Важно понимать что materialized view полезны лишь для некоторых запросов

Кодирование и эволюция

• Rolling update= staged rollout - постепенный деплой - когда сервер развернут на нескольких инстанцах, обновление происходит не сразу а постепенно, по инстансу за раз, проверяя все ли ок
• При обновлении приложения - тут сам клиент решает обновляться ли ему

Совместимость:

• Обратная совместимость - новый код способен читать старые данные
• Прямая совместимость - старый код может читать новые данные

Сериализация

Данные приложения могут быть в двух состояниях: в виде объектов и структур данных в оперативе, либо в виде последовательности байтов (Напр. Json) при передаче данных по сети или хранении на диске

Процесс перевода данных из формата оперативы в формат для передачи называется encoding=serialization=marshalling, а обратный процесс - deciding=deserialization=parsing=demarshaling

Языки программирования предоставляют свой способ сериализации данных, напр pickle в Python, но это работает только в рамках одного языка, не очень безопасно, контроль версий хромает, и производительность тоже может хромать

Json, xml, csv - популярные, человеко-читаемые текстовые форматы данных. Но у них есть некоторые проблемы: отсутствие возможности указания точности чисел и больших чисел, отсутствие возможности передавать двоичные данные (но обходится с помощью base64 кодирования, но и увеличивает размер данных), в коже приходится зашивать логику парсинга, и csv довольно хрупкий формат

Бинарные форматы

Двоичное кодирование имеет смысл когда данных много

Для json и xml есть свои бинарные аналоги, типа messagepack, bson, wbxml, хотя они не сильно экономят место

Thrift и Protocol Buffers - либы двоичного кодирования, обе работают на основе схемы (на своем языке), по этой схеме можно генерировать код. Суть кодирования в применении тегов полей - вместо хранения названия поля, просто храним цифру. Совместимость обеспечивается за счёт того что новые добавляемые поля - необязательны

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

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

Передача данных

Данные передаются на разных уровнях: на уровне бд, на уровне сети, при асинхронном общении

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

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

Сервис - то что предоставляет апи

Сервис-ориентироаанная арх= микросервиснач арх - когда у сервиса своя задача, напр сервер работает с бд

Веб-сервис - сервис использующий хттп

Rest и soap - 2 подхода к написанию веб сервисов

Rest(ful) подход: применение урла для доступа к ресурсам, активное использование возможностей хттп: аутентификация, кешироаание, часто используется json, с помощью которого можно генерить доку и код (openapi, swagger)

Soap - xml подход, не использует возможности хттп, а свои спеки, описываемые с помощью wsdl. Этот подход сильно завязывается на спец утилитах, так что где-то интеграцию с соап сделать сложно