B-Trees

Ранее книжный клуб нашей компании изучил отличную книгу:

Martin Kleppmann - Designing Data-Intensive Applications

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

Это - лучшая книга о создании комплексных масштабируемых программных систем, которые я когда-либо читал. 💪

Как обычно, я подготовил краткий обзор и майнд-мапу.

Глава 5:

• Вступление. Как масштабировать приложения. Репликация и партиционирование.
• Три алгоритма репликации
• Репликация с одним лидером
  • Лидеры и последователи
  • Синхроная и асинхронная репликация
  • Добавление новых последователей
  • Обработка перебоев в работе узлов
  • Технические реализации и все возможные проблемы
• Многолидерная репликация
  • Случаи использования, когда это хорошо
  • Обработка конфликтов на запись
  • Три топологии и потенциальные проблемы
• Репликация без лидера
  • Запись в базу данных, когда узел не работает
  • Кворумы и проблемы с ними
  • Обнаружение одновременных записей и способы разрешения конфликтов

Скачать всю майнд-мапу в PDF

Ранее в этом году книжный клуб нашей компании изучил отличную книгу:

Martin Kleppmann - Designing Data-Intensive Applications

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

Это - лучшая книга о создании комплексных масштабируемых программных систем, которые я когда-либо читал. 💪

Как обычно, я подготовил краткий обзор и майнд-мапу.

Глава 3:

• Структуры данных:
  • Log-structured. SSTables / LSM-деревья (когда мы ничего не обновляем, а пишем в конец). Очень крутая идея, как хранить данные.
    • Отсортированные файлы.
    • Индексы для каждого.
    • Более того, индексы могут быть созданы не для всех записей, потому что они отсортированы, и если размеры записей одинаковы, то поиск между двумя известными проиндексированными записями является бинарным поиском O(log n).
    • Мы всегда пишем в последний файл.
    • Процесс слияния файлов - это школьный алгоритм: как записать O(n) слияние двух отсортированных массивов в один отсортированный массив.
  • Обновление-на-месте. B-деревья (когда мы напрямую обновляем записи). Тоже очень умно.
    • Деревья - более простая идея, но тут классно придумано с сегментами заточенными под работу дисков - и отсюда возможные проблемы с SSD т.к. много перезаписей сегментов
• Индексирование: первичное, вторичное, многоколоночное, полнотекстовое
  • По поводу индексов - очевидно, что чудес не бывает и нужны дополнительные конструкции.
  • Интересно, что иногда значения могут храниться внутри индексов.
  • К сожалению, о полнотекстовом поиске написано очень мало - интересно узнать о нем больше.
• OLTP vs OLAP. Четкое разделение OLAP / OLTP очень интересно.
• Столбцово-ориентированное хранилище.
  • Есть очень интересный аспект сжатия данных: сколько нулей, сколько единиц - своего рода компрессор. Это возможно только в памяти - только на одну следующую SSTable

Намного больше деталей в майнд-мапе: