dev notes

2021-04-23 07:39:50 Сегодня, продолжая 3-ю главу, опять поговорим о том, какие бывают индексы и как их правильно использовать.

Индексы могут быть кластеризованными (по ключу хранятся все данные) или некластеризованными (по ключу хранится ссылка на данные). Например, InnoDB в MySQL - использует кластеризованные индексы, т.е. когда мы делаем запрос с индексом, сначала идёт поиск в memory-структуре, в зависимости от типа индекса, и затем, в случае успеха, мы сразу можем получить запрашиваемые данные. У некластеризованных индексов в случае успешно найденного значения, представляющего ссылку, нам потребуется выполнить переход по ней, считать значение и только потом его вернуть.
Бывает так же и компромисс между кластеризованным и некластеризованным - охватывающий индекс. Этот тип индекса хранит в себе не всю строку, а часть столбцов. Как правило, эта та часть, которая чаще всего запрашивается запросами.

Если мы запрашиваем сразу несколько столбцов строки, то нам могут потребоваться составные индексы. Самый частый тип составных индексов - сцепленные индексы: объединение нескольких полей в один ключ, например: имя-фамилия.
Второй по популярности тип составных индексов - многомерные индексы, особенно часто они используются при работе с пространственными данными, например, при работе с PostGIS от Postgres. Для многомерных пространственных индексов используются R-деревья, позволяющие производить поиск по многомерным данным.
Многомерные индексы применяются не только для работы с адресами. Например, можно использовать двумерный индекс (год, температура), чтобы одним запросом найти данные за 2013 год, когда температура была -20 градусов. Иначе, без многомерных индексов, нам придётся сначала найти все данные за 2013 год, а затем фильтровать их по температуре.

Интересная, в плане использования индексов, тема - полнотекстовый поиск. Например, известные индексы Lucene, лежащие в основе эластики, хранят словарь термов в SS-структуре (которую я описывал в прошлый раз), а рядом с этой структурой они хранят небольшой индекс, который описывает, как разбивается (на буквы, или на триграммы, или как-то иначе) каждый терм. На всё это накладываются различные алгоритмы, например конечный автомат в связке с расстоянием Левенштейна, что позволяет очень быстро искать слова по заданному соответствию.

Все описанные выше структуры так или иначе подразумевают запись на диск. Хотя основная работа происходит в оперативной памяти, в случае с LSM-таблицами на диске у нас хранятся уплотнённые сегменты, а в случае с B-деревьями на диске у нас хранится информация, куда ссылается B-дерево. И, само собой, на диске хранятся данные самих таблиц.
По мере удешевления RAM у дискового хранения остался 1 аргумент над хранением в оперативной памяти: надёжность. Хотя в последние годы, благодаря различным инструментам и подходам (репликации на разные сетевые копии; память, питаемая от отдельного аккумулятора; ротация журнала состояния на диск) появилась возможность хранить данные только в оперативной памяти. Уже существуют несколько РСУБД, которые работают в RAM: VoltDB, MemSQL, Oracle TimesTen. Открыть/Комментировать

2021-04-19 05:50:24 Индексы на основе журнала - не самый популярный тип индексов. Чаще используются индексы на основе B-дерева.
В отличии от журналированных индексов, которые индексируют базу данных сегментами по несколько мегабайт и всегда записывают эти сегменты на диск последовательно, B-деревья разбивают базу на сегменты по несколько килобайт (часто - по 4Kb) и читают/пишут по 1 странице за раз. Такое разбитие и такой размер сегментов отлично накладываются на нижележащие аппаратные слои.
Все страницы имеют свой адрес, и на основе таких ссылок строится дерево. Одна из страниц - корень, с него начинается любой поиск ключа. Все ключи во всех сегментах - отсортированы, и любой узел дерева содержит некоторый диапазон сегментов и несколько ссылок на поддиапазоны.
Если на странице заканчивается место, то создаётся ещё одна ссылка, и страница делится на две полу-пустых страницы.
Такой алгоритм гарантирует, что дерево будет сбалансированным, т.е. любой поиск будет занимать O(log n), что весьма быстро.
Чтобы обезопасить данные от потери во время сбоя, на диске так же хранится журнал упреждающей записи, в который все добавляемые данные записываются перед тем, как попасть в B-дерево.

А зачем тогда нужны LSM-деревья, если есть B-деревья? LSM-деревья реализуют как одну из подсистем во многих СУБД из-за того, что они быстрее при записи. Нам не нужно идти по дереву и искать место, куда добавить ключ. Нам достаточно записать данные в in-memory-структуру и сдублировать их в журнал, и всё. И для таких задач LSM-деревья до сих пор используются.
В свою очередь, B-деревья быстрее при чтении. Открыть/Комментировать

2021-04-19 05:50:24 Как я уже писал выше - перечитываю "Высоконагруженные приложения" и кидаюсь в вас конспектами с самым соком. К слову, зачем читать книгу второй раз? Лично для себя открыл, что второе чтение оставляет в памяти максимальное количество полезной информации (а параллельное конспектирование основных тем - цементирует прочитанное). Прочитав же 1 раз - в течении пары месяцев 90% забывается.

Итак, сегодня у нас 3-я глава: подсистемы хранения данных. Клеппман описывает, как и на основе чего устроены индексы в современных СУБД и раскрывает 2 основные структуры данных, на основе которых индексы строятся. Зачем это знать? Во-первых, на больших нагрузках нужно понимать, как оптимизировать или скорость, или чтение индексов, в зависимости от задачи. Во-вторых, понимание того, как устроены индексы полезно для выбора СУБД на очередной проект. В-третьих, это просто очень интересно :)
Глава большая, поэтому ниже - конспект первой половины.

Любые индексы в реляционных СУБД, как правило, замедляют запись. Индексы надо подбирать так, чтобы чтение было быстрым, но и запись осталась быстрой.

При любой записи на диск - индекс тоже обновляется, всегда.

Хеш-индексы - индексы, на основе hash-таблицы - один из самых распространённых типов индексов. Например, так работает подсистема хранения Bitcask в NoSQL СУБД Riak.

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

SS-таблица
Отсортированная строковая таблица (sorted string table, SS-таблица) - отсортированная по ключу таблица, хранимая на диске, где каждый ключ встречается 1 раз (благодаря автоматическому процессу уплотнения и слияния сегментов). Преимущества перед журнальными сегментами с хеш-индексами:
1. Объединение сегментов выполняется просто и эффективно, благодаря тому, что сегменты отсортированы. При слиянии мы читаем сразу все сегменты, и оставляем последний записанный ключ в результирующем сегменте.
2. Чтобы найти в файле конкретный ключ, не нужно хранить индекс всех ключей в оперативной памяти. Если мы знаем индекс соседних ключей от искомого - точно можно сказать, что он будет между ними, и нам достаточно посмотреть срез данных между соседями.
3. Блоки, на которые есть индексы в ОП можно сжимать пачками по несколько килобайт, так как расжать и просмотреть несколько Кб данных можно очень быстро.

Красно-чёрные деревья или AVL-деревья позволяют записывать ключи в любом порядке, а читать только в нужном.
Процесс записи в SS-таблицу выглядит так:
1. При поступлении записи помещаем её в оперативной памяти в сбалансированную структуру данных, например в красно-чёрное дерево.
2. Когда размер записи превышает определённое пороговое значение, например несколько мегабайт, записываем его на диск в фиде файла SS-таблицы. Это операция выполняется достаточно быстро, так как записи на выходе отсортированы. Файл становится последним сегментов базы данных.
3. При поиске данных сначала ищем их в memory-сегменте, если там нет, то в последнем, затем в предпоследнем и так далее.
4. В фоне время от времени запускается процесс уплотнения и слияния данных.
5. Так же на диске нужно держать отдельный журнал - копию со всеми записанными в memory-таблицу данными, чтобы в случае фатального сбоя восстановить memory-таблицу.

А это вообще где-то применяется, спросишь ты? Да, например в levelDB и rocksDB - библиотеках, которые можно юзать сами по себе, а можно в рамках других СУБД. Так, levelDB используется в СУБД Riak. Аналогичные системы используются так же в Cassandra и HBase.

Подсистемы хранения, основанные на принципах слияния и уплотнения, часто называют LSM (Log-Strucrured Merge-Tree) подсистемами.

Часто с LSM-системами используют фильтры Блума - структуру данных, позволяющую узнать, есть ли в множестве заданный элемент. Это позволяет не просматривать все сегменты в поисках элемента, которого в них нет. Открыть/Комментировать

2021-04-08 06:48:10 Почему ещё НЕ следует использовать документоориентированные СУБД: если документ большой, то при update требуется перезаписать весь документ (невозможно внести локальные изменения)
Некоторые драйверы для MongoDB разрешают, автоматически, ссылки на БД как в реляционных СУБД.

Декларативные языки (SQL, напр.) могут автоматически задействовать параллельную реализацию языка запросов, что гораздо сложнее сделать в случае с императивным описанием.

MapReduce - модель программирования для обработки большого количества данных от Google. В ограниченном виде поддерживается MongoDB и CouchDB в качестве механизма, выполняющего только чтение запросов по многим документам.
Например, аналогичные запросы в PostgreSQL и MongoDB с использованием mapreduce:
SQL:
SELECT date_trunc('month', observation_timestamp) as observation_month,
sum(num_animals) as total_animals
FROM observations
WHERE family = 'Sharks'
GROUP BY observation_month;
MongoDB с mapreduce:
db.obsercations.mapReduce(
// вызывается однократно для каждого документа
function map() {
var year = this.observationTimestamp.getFullYear()
var month = this.observationTimestamp.getMonth() + 1;
emit(year + '-' + month, this.numAnimals) // на выходе порождает строку вида (дата, кол-во животных)
},
function reduce(key, values) { // все пары из map автоматически группируются по ключу (т.е. с одной и той же датой)
return Array.sum(values); // для них однократно вызывается reduce, суммирующий количество животных
},
{
query: { family: "Sharks" }, // отсеиваем только акул декларативно, это расширение MongoDB модели MapReduce
out: "monthlySharkReport" // итоговые результаты записываются в коллекцию minthlySharkReport
}
)
map и reduce должны быть чистыми, т.е. могут только выполнять однозначную работу и передавать данные, но не могут делать доп. запросы

В Mongo с версии 2.2. добавлена поддержка декларативного описания запросов - конвейер агрегирования, где тот же запрос будет выглядеть так:
db.observations.aggregate([
{ $match: { family: "sharks" } },
{ $group: {
_id: {
year: { $year: "$observationsTimestamp" },
month: { $month: "$observationsTimestamp" }
},
totalAnimals: { $sum: "$numAnimals" }
} }
]) Открыть/Комментировать

2021-04-08 06:48:10 Спрашивают тут, куда пропал: никуда не пропадал, просто было много работы и параллельно пилил небольшой пет-проект, который продолжаю пилить по мере времени.
Тем временем, спустя несколько месяцев после первого прочтения "Высоконагруженных приложений" решил перечитать и забить в памяти интересные моменты. Пока успешно повторил и законспектировал 2 главы, и ниже представляю краткий конспект главы "Модели данных и языки запросов". Завтра будет конспект 3-ей главы: "Подсистемы хранения и извлечения данных".

Какие причины широкого внедрения NoSQL-решений?

1. Потребность в бОльшей масштабируемости, чем у реляционных СУБД: возможность обрабатывать очень большие объёмы данных и возможность большой пропуской способности
2. Открытый исходный код
3. Некоторые запросные операции, плохо поддерживаемые реляционной моделью
4. Стремление к более динамичным моделям, выходящим за рамки реляционных схем

Какой вопрос стоит себе задать чтобы понять, можно ли для набора информации использовать документоориентированную СУБД?
- Вполне очевидный: является ли самостоятельным документом набор информации?

Извлекая документ (например, резюме), представленное в реляционном виде, придётся сделать множество запросов (к каждой таблице по внешним ключам). Если документ лежит в документоориентированной базе, то его можно извлечь одним запросом.

Идея исключения полного дублирования (напр, хранение внешних ключей вместо строк) лежит в основе нормализации баз данных
ЭМПИРИЧЕСКОЕ ПРАВИЛО: если значения, которые могут храниться в одном месте - дублируются, то база НЕ НОРМАЛИЗОВАНА

В древовидной структуре, которую пропагандирует документоориентированная модель, соединения (по внешним ключам) - не нужны, и их поддержка очень слаба (сложно сделать свзяь многие-к-одному (напр, многие люди к одному городу))
Соединения поддерживаются в RethinkDB, не поддерживаются в MongoDB и поддерживаются в заранее описанных представлениях в CouchDB.

В реляционных СУБД оптимизатор запросов автоматически принимает решение о том, в каком порядке выполнять запрос, и делает это так, чтобы это было максимально эффективно. В случае, если был объявлен новый индекс - оптимизатор запросов перестраивает логику выполнения запроса.

Основные доводы в пользу документноориентированных СУБД - гибкость схемы, лучшая производительность вследствие локальности и большая близость к применяемым структурам данных (не всегда). Реляционная модель отвечает на это лучшей поддержкой соединений, а также связей "многие-к-одному" и "многие-ко-многим".

Если структура приложения представляет собой дерево связей "один-ко-многим", причём всё дерево загружается сразу - документоориентированная модель - ОК.
Если в приложении используется множество связей "многие-ко-многим", то документоориентированная модель не так привлекательна. Количество соединений можно снизить за счёт денормализации, но придётся написать больше кода для поддержки согласованности. Соединения эмулируются в коде, а не в СУБД, что обычно медленнее, чем через СУБД.

Документоориентированные базы не требуют проверку схемы и часто их называют бессхемными. По-факту, они проверяют схему при чтении (schema-on-read), в отличии от проверки схемы при записи в реляционных СУБД (schema-on-write). Схема при чтении аналогично динамической проверке типов в ЯП, в то время как схема при записи аналогична статической (во время компиляции) проверке типов.

MySQL - известный пиздец, когда требуется выполнить alter table. Есть утилиты, которые позволяют сделать это более комфортно:
* https://www.percona.com/software/database-tools/percona-toolkit
* https://github.com/soundcloud/lhm
* https://github.com/github/gh-ost

Оператор UPDATE будет выполняться медленно в любой базе данных на большой таблице, как так требуется перезаписывать все строки.

"schema-on-read" предпочтительна, если:
* существуют множество различных типов объектов, и нет смысла помещать их в разные таблицы
* структура данных определяется внешними системами, которые могут изменять данные, и это нам не подконтрольно Открыть/Комментировать

2021-01-13 05:13:31 Интересная мысль из "Чистой архитектуры": последние полвека мы, как разработчики, учимся тому, как делать не надо.

Судите сами: первый подход, выделенный как подход к разработке и доживший до наших дней - это структурное программирование. Используя 3 основные конструкции: последовательность, итерацию и выбор - мы можем написать любую программу. Когда Дейкстра проводил свои исследования и доказал, что прямая передача управления посредством оператора goto - опасна, он выделил структурное программирование как одну из парадигм разработки, которая дожила до наших дней.
Структурное программирование запрещает нам передавать управление напрямую.

Вторая парадигма - объектно-ориентированное программирование. Мы привыкли думать, что ООП дало нам наследование, инкапсуляцию и полиморфизм. Это не совсем так. Инкапсуляция была до появления ООП: отличный пример - .h файлы в С. Клиенты этих файлов могут работать с методами, зная только их сигнатуру, описанную в заголовочном файле.
Наследование, хоть и в менее удобном виде, тоже было задолго до появления ООП: имея 2 структуры с одинаковой сигнатурой первых функций, мы можем дописать в одну из структур ещё несколько методов, и создавать её через родительскую, приводя тип. Вторая структура занимает то же состояние стека, что и первая, дополняя его своими методами. По-сути, так и работает наследование в ООП, только выполнено оно в более красивой обёртке.
Что-то похожее на полиморфизм тоже проделывали до появления ООП: оперируя указателями на функции, можно было подменять дочерние функции на другие, с такой же сигнатурой. ООП только лишь усилило полиморфизм и позволило нам работать с ним гораздо удобней. Таким образом, вторая парадигма лишь отнимает у нас возможность косвенной передачи контроля - она делает полиморфизм более строгим.

Третья парадигма - функциональное программирование. Функциональная программа делает удивительную вещь: она ограничивает нас в присваивании. Каноничный функциональный код не имеет изменяемых переменных, только инициализируемые.

Индустрия обрастает новыми технологиями, под капотом которых - старые и базовые знания, которые с годами становятся всё строже. Открыть/Комментировать

2021-01-12 04:13:20 Выходя из праздничного анабиоза решено было вернуться к чтению всякого полезного. Начал читать "Чистую архитектуру" дяди Боба. И вот вам оттуда интересная история.

Был один учёный, оказавший огромное влияние информатику - Эдсгер Дейкстра. Из под его пера в середине двадцатого века вышла статья "Go To Statement Considered Harmful" - статья, доказавшая с точки зрения математики то, что программы, где слишком часто используется оператор goto - опасные.
А пришёл Дейкстра к этому вот как: в далёких пятидесятых он решил найти универсальный способ писать качественные программы. Проделав огромную работу длиною в пару лет, он пришёл к выводу, что если программу раздробить на маленькие части, выделив под каждое атомарное действие один метод, эти атомарные части можно интерпретировать как математический алгоритм, и доказать с помощью типичных математических доказательств, таких как, например, доказательство по индукции.
И тут обнаружился интересный момент: те программы, где использовался оператор goto - часто не доказывались математически. "Чистые" же программы, которые не использовали оператор передачи управления - доказывались и их можно было назвать корректными.

После публикации статьи в журналах - Дейкстра, по-факту, устроил первый холивар в it мире. Споры продолжались много лет, но факты остаются фактами: через 10 лет с момента публикации во многих языках оператор goto был ограничен, а какие-то и вовсе реализовывлись без него. Вот как правильно устраивать холивары :) Открыть/Комментировать

2020-12-22 06:00:01 Интересная мысль, описываемая Клеппманом в его "Высоконагруженных приложениях" - это внедрение паттерна репликации master-slave в рамках разных систем. Если просто, то: есть реляционная СУБД, пусть будет Postgres. Она выступает как master-реплика. И есть, например, система с поисковыми индексами, пусть будет ElasticSearch - она выступает как slave-реплика.

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

Основываясь на этом журнале, были разработаны инструменты, которые декорируют работу с журналом в виде API. Например, для Postgres - https://github.com/confluentinc/bottledwater-pg (или https://debezium.io/documentation/reference/connectors/postgresql.html), для MongoDB - https://github.com/stripe/mongoriver. Мы можем вычитывать данные из этого журнала и перекладывать их в журнал брокера, например, Apache Kafka. Потребители, в свою очередь, смогут последовательно и в том же порядке применять эти данные на другую систему, в нашем примере - ElasticSearch.

Таким образом, мы можем записывая данные в один источник реплицировать их на разные системы хранения данных. Открыть/Комментировать

2020-12-21 04:04:41 По какому принципу обычно выбирают брокера сообщений? Из моего опыта, как правило, звучит что-то вроде "да давайте kafka возьмём, я о ней на конференции слышал, попробуем". И берут. Даже, если kafka не подходит под задачи, которые приходится решать.

Как выбрать правильно? Клеппман даёт простой алгоритм: если задача, обрабатываемая брокером, занимает много времени - лучше подходит стиль обработки сообщений формата JMS/AMQP (из самого известного - RabbitMQ). Если задача выполняется быстро и без задержек - можно взять брокера на основе журнала, например, Kafka.
Почему?

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

2020-12-18 07:52:03 Много раз слышал восхищение разработчиков касательно Apache Kafka: "Этот брокер позволяет даже в случае отключения сервера восстановить все сообщения в очередях!"
Многие говорят о том что Kafka - единственный брокер, гарантирующий доставку в случае любых сбоев. И так оно и есть, практика это показывает.
Но только сегодня, с подачи Клеппмана в его "Высоконагруженных приложениях" я узнал, почему это так работает.
Apache Kafka - брокер на основе журнала. Т.е. вместо прямой доставки сообщений через очередь, читай через оперативную память (как это работает, например, в RabbitMQ), Kafka всё записывает в файл, указывая каждому сообщению соответствующее смещение. Подписчики, вычитывая смещения, точно знают, откуда читать свежую запись. В случае, если произошёл сетевой сбой - журнал остался нетронутым, и Kafka считывает оттуда сообщения обратно в очередь.
Теперь на вопрос на собеседовании: можно ли сломать Kafka - можешь смело отвечать, что достаточно дискового сбоя.

Возникает вопрос: как достигается такая пропускная способность? По скорости и объёму передаваемых данных Apache Kafka не уступает своим конкурентам с прямой доставкой сообщений. А достигается это за счёт крутой системы секционирования сообщений, и системы репликаций по журналам, что даёт журналируемому подходу ещё больше надёжности.

Так же заблуждением является то, что Kafka единственный брокер с таким подходом. На основе журналов так же работают: Amazon Kinesis Streams и Twitter DistributedLog. Есть ещё Google Cloud Pub/Sub, но этот парень чтение и запись в журнал абстрагирует в виде API.

Всем новых знаний, пацаны Открыть/Комментировать