База по Базам Данных — Storage (Индексы, Paging, LSM, B+-Tree, R-Tree) | Влад Тен Систем Дизайн

База по Базам Данных — Storage (Индексы, Paging, LSM, B+-Tree, R-Tree) | Влад Тен Систем Дизайн

*https://www.youtube.com/watch?v=i-FFVM4cIXQ
**https://300.ya.ru/v_P1iioNJA

таймкод

00:00:00 Введение в распределённые системы

• Обсуждение важности понимания работы одного компонента системы — сторожа.
• План лекций: сначала анализ работы одной ноды, затем распределение, репликация и шардинг.
• Пример сделки: покупка DataBricks опенсорсной базы данных Notion за миллиард долларов.

00:01:54 Зачем нужны базы данных

• Объяснение преимуществ систем управления базами данных DBMS перед хранением данных в файлах.
• DBMS обеспечивают независимость от формата хранения данных и конкурентный доступ.
• Примеры проблем с файлами: необходимость переписывать программы при изменении схемы или формата.

00:02:49 Функции DBMS

• Data independence: независимость от способа хранения данных.
• Конкурентный доступ: управление транзакциями и одновременным доступом нескольких пользователей.
• Crash recovery: сохранение данных на персистентный диск при отключении питания.
• Security access control: управление доступом к данным.

00:05:47 Архитектура классической DBMS

• Описание компонентов: команды, сервер, парсинг запросов, построение планов, выполнение планов.
• Роль конкатенации, транзакционного менеджера, лок менеджера и recovery менеджера.
• Компоненты: буфер-менеджер, диск-менеджер, данные в виде индекс-файлов и дата-файлов.

00:07:44 Альтернативные архитектуры

• Пример архитектуры Rosh DB: компоненты Gateway, Executor, KV.
• Особенности Notion: разделение PostgreSQL на компоненты компьютер и сторож, использование Amazon ES для репликации.
• Архитектура TIBY: компоненты TIQV, взаимодействие через Raft, кластеризация.

00:09:38 Заключение

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

00:09:48 Введение в сторож

• Обсуждение хранения данных в базе данных.
• Пример с таблицей «юзерс» и её представлением на диске.
• Упоминание движка INA DB и его формата файлов.

00:10:47 Управление файлами

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

00:11:46 Пейджинг

• Разбиение файла на блоки фиксированного размера.
• Преимущества пейджинга для доступа к данным.
• Логический юнит для работы с данными.

00:12:45 Структура пейджи

• Хранение хедера в пейдже для проверки целостности данных.
• Проверка свободного места в пейдже.
• Пример хранения фиксированных по длине записей.

00:14:40 Проблемы с записями разной длины

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

00:16:36 Решение проблемы переменной длины записей

• Использование фиксированных заголовков для атрибутов переменной длины.
• Пример кодирования атрибутов с помощью фиксированных заголовков.
• Решение проблемы с атрибутами, превышающими размер пейджи.

00:18:19 Оверфлоу пейджи

• Механизм оверфлоу пейджи для хранения данных, превышающих размер пейджи.
• Ссылка на данные в оверфлоу пейдже из оригинальной пейджи.
• Применение оверфлоу пейджи в PostgreSQL.

00:19:32 Дополнительный слой дирекции

• Добавление хедера фиксированной длины для каждой записи.
• Указание на запись через хедеры фиксированной длины.
• Пример использования подхода в PostgreSQL.

00:21:13 Дополнительные возможности PostgreSQL

• Хранение чек-суммы, LSN, версии и флагов в хедере пейджи.
• Проверка свободного пространства в пейдже.
• Хранение информации о транзакциях и версиях записей в хедерах записей.

00:22:58 Вставка записей переменной длины

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

00:23:11 Проблема с мёртвыми данными

• Необходимо удалить и переместить данные, чтобы освободить пространство.
• При перемещении данных нужно пересобрать указатели.
• Вакуум решает проблему с мёртвыми данными, помечая их для удаления.

00:24:10 Работа вакуума

• Вакуум удаляет помеченные данные при следующем запуске.
• В зависимости от настройки, данные могут быть записаны в новую область или перемещены внутри текущей страницы.
• Обсуждение альтернатив будет рассмотрено позже.

00:25:09 Колоночные базы данных

• Колоночные базы данных работают с колонками, а не с пейджами.
• Пример с записями в пейджах: «Влад», «7», «Олег», «5», «Игорь», «90».
• Проблема: для расчёта статистики нужно извлекать весь пейдж, хотя требуется только одно число.

00:26:09 Решение проблемы

• Переорганизация сторожа для хранения всех атрибутов рядом одного типа решает проблему.
• Это позволяет извлекать только необходимые данные, избегая извлечения лишних элементов.

00:27:03 Оптимизация хранения атрибутов

• Хранение атрибутов рядом позволяет использовать сжатие и кодирование.
• Векторные операции и параллельные вычисления ускоряют обработку данных.
• Проблема возникает при необходимости собрать запись обратно.

00:28:08 Аналитический и транзакционный workload

• Для аналитического workload подходит один тип хранилища, для транзакционного — другой.
• Тип хранилища напрямую влияет на работу с данными.

00:29:06 Системный каталог

• Системный каталог хранит метаданные о расположении таблиц и индексов.
• Включает информацию о схеме, индексах и пользователях.

00:31:14 Буфер-пул

• Буфер-пул загружает страницы с диска в память для ускорения доступа.
• Выполняет функции кэширования и управления страницами.
• Поддерживает различные стратегии управления страницами, включая LRU.

00:33:39 Стратегия LRU

• LRU наименее недавно использованные страницы.
• Часто используемые страницы остаются в кэше.
• Проблема секвенш флуд: страницы, которые часто используются, могут быть вытолкнуты из кэша.

00:37:30 Индексы

• Индексы ускоряют поиск данных в таблицах.
• Примеры индексов: бинарные, хэш-индексы.

00:37:56 Кластеризованные и некластеризованные индексы

• Кластеризованные индексы определяют порядок хранения записей в файлах.
• Некластеризованные индексы не диктуют порядок хранения записей.
• Пример: в MySQL первичный индекс кластеризованный, а в PostgreSQL используется heap-организация файлов.

00:38:47 Праймерик-индекс и разряженные индексы

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

00:39:46 Секонд-индексы

• Секонд-индексы используются для поиска по вторичным атрибутам, например, по департаменту или зарплате.
• Могут указывать на конкретную запись или хранить ссылку на первичный индекс.
• Второй вариант добавляет дополнительный слой дирекции, но не требует обновления при перемещении страниц.

00:41:19 Хэш-индексы

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

00:44:10 Недостатки хэш-индексов

• Не подходят для поиска диапазонов значений.
• Пример: для поиска значений, превышающих определённое значение, нужно пропускать каждое значение через хэш-функцию.

00:45:08 Индексы B+Tree и B+Tree+

• B+Tree: значения хранятся в листовых нодах, указатели на соседние ноды позволяют быстро находить диапазоны.
• Проблема: перестройка дерева при добавлении новых значений.
• B+Tree+: значения хранятся только в листовых нодах, указатели на соседние ноды упрощают поиск диапазонов, но требуют более сложной реализации при добавлении новых значений.

00:50:30 Реализация B+Tree+

• В листовых нодах могут храниться указатели или пейджи со значениями.
• При перемещении страниц необходимо обновлять указатели.
• Реализация B+Tree+ сложнее, но позволяет быстрее сканировать данные.

00:51:11 Оптимизация B+Tree

• B+Tree требует полной перестройки дерева при модификации записей.
• Оптимизация B-Epsilon позволяет накапливать изменения в буфере и перестраивать дерево постепенно.
• Проблема оптимизации: необходимость проверки наличия записи в буфере при чтении.

00:52:41 Битмап индекс

• Битмап индекс используется для атрибутов с фиксированным количеством значений.
• Пример использования: проверка наличия записи с определённым значением в таблице.
• Пример: проверка наличия «фейл л2» в таблице с помощью битовой маски.

00:54:38 Инвертированный индекс

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

00:56:37 Векторные базы данных

• Векторные базы данных используют имбединги для анализа текстов.
• Имбединги генерируются через модель, которая преобразует текст в вектор.
• Векторы сопоставляются с метаданными, что позволяет находить похожие записи.

00:57:51 Геоиндекс R-Tree

• R-Tree понимает геометрию и минимизирует нахлёсты между диапазонами.
• Пример использования: поиск кафешек между двумя точками на карте.
• R-Tree строит иерархию диапазонов, минимизируя площадь и пересечение диапазонов.

01:01:22 Строительство R-Tree

• R-Tree строится специфично, минимизируя метрику и площадь диапазонов.
• При добавлении новой ноды R-Tree старается минимизировать площадь покрывающего диапазона и пересечение с другими диапазонами.
• Балансировка диапазонов обеспечивает равномерное распределение данных по дереву.

01:03:18 Структура данных на основе геометрии

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

01:04:15 Обзор тем презентации

• Обсуждены сторож и индексы.
• Упоминается использование LSM в различных приложениях.
• Пример использования LSM в Rockstar Games.

01:05:09 Введение в LSM

• LSM — это другой подход к сторожу.
• Проблема с деревом B+3: необходимость перестройки и ребалансировки при добавлении данных.
• LSM поддерживает heavy real-time workloads без необходимости перестройки дерева.

01:06:08 Структура данных в RocksDB

• Записи добавляются в мем-таблицу, которая может быть красно-чёрным деревом, скип-листом или B-деревом.
• При переполнении мем-таблицы данные сбрасываются в SST-файлы на диске.
• SST-файлы компактно сливаются, образуя новые слои.

01:07:08 Сортировка данных

• Мем-таблица хранит данные отсортированными.
• Каждый SST-файл также содержит отсортированные данные.

01:09:05 Процесс записи и чтения

• Запись данных происходит в мем-таблицу, при переполнении данные сбрасываются на диск.
• Чтение данных начинается с проверки мем-таблицы, затем данные могут быть прочитаны с диска.

01:10:04 Уровни и компактирование

• Уровни SST-файлов позволяют поддерживать ограниченную длину файлов.
• Компактирование отсортированных данных упрощается благодаря использованию таймстемпов для определения свежести записей.

01:11:56 Мутабельность файлов

• Файлы остаются мутабельными после слияния, что позволяет архивировать историю изменений.
• Это позволяет возвращаться к определённым точкам в истории данных.

01:13:55 Оптимизация поиска

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

01:15:54 Принцип работы блум фильтра

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

01:19:13 Преимущества блум фильтра

• Блум фильтр не требует обновления при удалении значений, так как файлы остаются мутабельными.
• Это обеспечивает точность и эффективность поиска, ускоряя процесс.

01:20:21 Веб-сайт Compak Шри

• Веб-сайт Compak Шри предлагает различные стратегии для управления таблицами.
• Можно настраивать параметры компактирования, включая размер таблиц и уровни.
• Стратегии включают левел и тайер.

01:21:20 Процесс компактирования

• Файлы последовательно добавляются и сливаются в таблицы.
• После добавления последнего файла все данные смешиваются и добавляются на уровень ниже.
• Можно тестировать различные стратегии компактирования и оценивать производительность.

01:22:17 Логические блоки и кэш

• Каждый SST файл разбивается на логические блоки пейджи.
• Блок кэш позволяет хранить данные в памяти.

01:22:34 Защита данных при отключении электричества

• Данные защищаются с помощью write-ahead-lock перед записью в мем-таблицу.
• Манифест-лок отслеживает состояние SST файлов.

01:23:05 Структура данных мем-таблица

• Мем-таблица использует структуру данных скип-лист.
• Скип-лист применяется в Discord для оптимизации операций.

01:24:06 Принцип работы скип-листа

• Скип-лист — вероятностная структура данных с сложностью O(logn).
• При добавлении элемента значение может «прорасти» на несколько уровней вверх.
• Пересечение уровней может привести к ошибкам, но это нормально.

01:25:40 Введение в скип-лист

• Скип-лист — это структура данных, где значения «прорастают» наверх на несколько этажей.
• Количество этажей, на которое «прорастает» значение, определяется случайным образом.
• Для вставки значения нужно проверить, где оно находится относительно других значений, и вставить его в нужное место.

01:26:49 Преимущества скип-листа

• Благодаря рандому значения «прорастают» так, что в среднем получается логарифмическое распределение.
• Логика работы скип-листа напоминает указатели в B-дереве.
• Значения хранятся в отсортированном виде, что упрощает работу с ними.

01:27:47 Задача на лит-коде

• Рекомендуется решить задачу на лит-коде, связанную со скип-листом.
• Это поможет лучше понять структуру данных и её особенности.

01:28:43 Альтернативный подход к управлению данными

• Обсуждается использование LSM сторожа для управления данными.
• LSM сторож позволяет легче дробить и шордировать значения.
• Рекомендуется изучить репозиторий Talent Plan для построения сторожа на основе LSM.

01:29:41 Процесс оптимизации запросов

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

01:33:23 Законы эквивалентности в реляционной алгебре

• Оптимизатор использует законы эквивалентности для перестройки выражения запроса.
• Примеры законов: коммутативность, ассоциативность, декартово произведение.
• Перестройка выражения позволяет оптимизировать запрос без изменения его логики.

01:36:49 Заключение

• Лекция завершена, автор благодарит слушателей и приглашает задавать вопросы в комментариях.
• Упоминается, что лекция проводится в учебном формате.

Расшифровка видео

0:00
Всем привет. Добро пожаловать на первый урок по распределённым системам и системдизайну от Владатена. Значит,
0:06
перед тем, как нам дизайнить систему, состоящую из множества компонентов, да, нам нужно разобраться, что происходит в
0:13
самом главном компоненте, а именно в сторедже. Значит, эту и все следующие
0:18
лекции мы будем говорить про стордж и будем говорить в рамках только одной ноды. Только одной ноды. А дальше уже мы
0:26
будем придумывать, как его там распределять, как его реплицировать, как его шардировать, что там ещё можно
0:31
сделать. Поговорим там про алгоритмы консенсуса и про всё прочее. Но сначала давайте разберёмся, что происходит с
0:37
одной нодой. Что происходит с одной нодой. Вот про это мы с вами и поговорим. Начать бы хотелось вот с
0:43
чего. Э, недавно DataБК купили openсоourceную базу данных Neon
0:49
1 млрд. За 1 млрд. Если мы посмотрим, а что такое неон? А что такое неон?
0:58
Ne — это у нас серверс постгress, который можно скейлить, бранчить и так далее. Хорошо. Но у нас есть, например,
1:05
ЮBйт, который тоже серверле погрес. И ещё каждый год у нас происходит тонны
1:11
сделок. У нас происходят тонны сделок, которые связаны с базами данных.
1:17
Например, например, например, например, пожалуйста, вот, вот появились новые какие-то базы данных. Вот кто-то кого-то
1:25
купил. Вот произошло финансирование 10 млрд, 8 млн, 8 млн, 9 млн, 12 млн, 24 млн.
1:32
Недавно была новость Дотабрис кого-то купил за 250 млн. В общем, в база данных постоянно что-то происходит. А хочется
1:39
понять, а за что деньги-то платится, почему это так дорого стоит, почему это
1:45
так много стоит. Но типа у нас уже есть условные постгрес, не знаю, my, зачем
1:50
нам появляется ещё база данных, ещё база данных, ещё база данных. И чтобы ответить на эти вопросы и чтобы, когда в
1:56
следующий раз выбирали для себя какое-нибудь новое фнси решение, да, или увидели на Hacker News какую-нибуд новую
2:02
статью про новую базу данных, которая решает все ваши проблемы, вы могли открыть их landing page, открыть их
2:08
оферинг и прочитать, что они на самом деле вам предлагают. Для этого нам нужно разобраться, что происходит в одной
2:15
ноде. Значит, давайте сначала подумаем, а для чего нам вообще нужны DBMS, то
2:20
есть database management system или там на русском систему управления базами данных. Почему мы не можем просто всё
2:25
хранить в файликах? Просто давайте всё хранить в Экселе, да, и всё. Просто будем хранить всё в Экселе ещё как DBMS
2:32
придумали и так далее, потому что DBMS нам даёт
2:38
ключевую функциональность, которую реализовать на файлах нам было бы сложно, да? Например, если это были бы
2:44
файлы, мы на каждый файл писали там свою программу, как это всё распартить, там, допустим, CSV. Если бы поменялась
2:50
условно схема, нам нужно было бы переписывать вот эту программу, которую у нас парси, да, там поменяли как-то формат, тоже бы пришлось переписывать.
2:57
Система управления базами данных нам даёт data independence, то есть мы не
3:02
зависим от того, как там хранятся наши файлы. То есть для нас есть условно постгрес. Мы в него кидаем данные, мы с
3:08
него забираем данные, как он у себя хранит, там раскладывает по директориям, там файлы бьёт на PйG. Нас это ничего не
3:15
интересует. Мы знаем, что вот у нас есть такая абстракция, хранилище данных. Мы в неё закидываем данные, мы из неё забираем данные. Дальше, что она нам
3:21
даёт? Она нам даёт concurrнcy control. Что имеется в виду? Когда несколько пользователей одновременно что-то
3:26
делают, когда идёт какой-то транзакционный workкloadло, там все начинают пытаться дёргать одну один и
3:33
тот же атрибут, менять, как нам это всё правильно зарезовить. Там у нас идёт концерт, не знаю, Тревиса Скотта, все
3:38
покупают билеты, кому дать билет, кому не не дать билет, что с этим делать. То есть система управления базами данных за
3:45
нас может часть этих проблем забрать. Или нам явно сказать, что там вот здесь
3:50
есть проблема, тебе её нужно решить как-нибудь, да, с конкурентным доступом. В случае с файлами там 10 человек, э,
3:57
фиксят один файл, потом как это сохранить, там сохранять какие-то ревизии, что с этим делать, как потом это всё слить в одно. Постоянно
4:03
появляется проблема, система проблем базами данных часть этих проблем от нас забирает. Про то, как она это делает и
4:09
какие могут возникнуть проблемы, мы с вами поговорим позже. Значит, Crash Recovery. Что она делает? Она
4:16
у нас данные хранятся в памяти. Понятно, что электричество выключили. Бм, всё из памяти всё исчезло. Система управления
4:22
базами данных старается максимально вас обезопасить от таких кейсов. То есть она ведёт
4:29
какой-нибудь там есть какой-нибудь recovery менеджер, она ведёт какой-нибудь WR a headadlog, который за
4:35
вас сохранит эти данные на персистентный диск. И потом в следующий раз, когда вы живёте, она у вас до какого-то там валидного состояния откатит, да, и у вас
4:41
не будет там наполовину повисших транзакций, к примеру. Также она даёт вам Security Access Contроol. То есть,
4:47
например, эту часть базы данных ты можешь смотреть, эту часть базы данных ты не можешь смотреть, там пришёл джун
4:53
проект, он схему не может поменять, этот человек может поменять, этот может смотреть, этот не может смотреть. Вот
4:59
весь условный Airbag, да, Security Access Control система управления базовым данных нам тоже может
5:04
предоставить. Давайте посмотрим. на архитектуру классической, условно, там,
5:11
реляционной СУБД, да, и попробуем сами свою же придумать. Но как мы будем
5:19
придумывать? Мы будем придумывать не с нуля, а мы будем опираться на существующее решения. И когда у нас там где-то затык или что-то у нас там где-то
5:26
не хватает, мы будем подглядывать, а как это делается в других местах, а как это делается в реальных системах. Вот. То
5:33
есть ещё раз, мы сейчас не строим, то есть не будет такого, что вы посмотрели эту лекцию, и вы сможете построить там с
5:39
нуля свой сторыжко компонент, но вы будете знать, какие движущиеся части там есть и как они все вместе складываются в
5:45
общий пазл. Давайте посмотрим, а какие бывают архитектуры. Значит, архитектуру
5:50
классической реалиционной системы управления базами данных можно представить вот так. Что у нас здесь
5:56
есть? У нас есть SQL команда. SQL команды нам приходят с нашего приложения там либо с командной строки, откуда
6:02
угодно. Вот нам приходят SQL команды, они попадают в Query Evoluation Engine. Значит, про каждый из этих компонентов
6:08
мы с вами будем в отдельности говорить. Они попадают в querer Evolution Engine. Что там происходит? Там происходит
6:14
партинг запросов. Потом этот запрос бьётся на реляционные выражения. А потом из этих реляционных выражений строятся
6:20
планы, выбирается типа эквивалентные планы сравниваются, выбирается тот из них, который там самый оптимальный в
6:25
зависимости там от статистики данных и от того там кто сколько операций переберёт. На это мы тоже дальше
6:31
посмотрим. И мы говорим: «Вот, вот этот план тебе нужно исполнить». Дальше этот план а у нас работает. Он
6:37
там задействует какие-то методы, которые может, ну, там, например, подёргает индекс или знает, что там вот это будет
6:43
лежать вот тут, это будет лежать вот тут, вот это мне можно заиспользовать. Параллельно с ним работает concurn control, transaction maner, logменеджер,
6:50
который следит, какие сейчас активные транзакции, какая транзакция, там, например, если это какой-нибуд MVC,
6:55
какая версионность, кто какие может видеть версии и так далее. Или там, если это какой-нибудь локинг, у кого сейчас
7:01
на что лог висит. Recovery manager у нас ведёт врата, который пишет там вот такие
7:08
данные, вот такие изменения, вот такие изменения, вот такие вот такие изменения произошли и скидывает их на диск. Вот про все эти компоненты в отдельности мы
7:14
с вами подробнее ещё поговорим в следующих лекциях. Значит, у нас есть буферменеджер, который таскает с диска в
7:19
память, и есть disk space Space Manager, который уже отвечает за, грубо говоря, то, как у меня байтики складываются на
7:25
диске. И вот сама сами данные у нас в виде индекс файлов, датафайлов и систем
7:32
каталога. Значит, это классическая реляционная система управления базами
7:37
данных. Давайте посмотрим, а какие есть ещё варианты. Есть, например, вот такой вариант, который делает как RDB. Значит,
7:45
у них есть три компонента. Это Gateway, Executor, KV. И каждый из этих
7:52
архитектура у нас разбивается на слои. И каждый из этих компонентов выполняет роль нескольких слоёв. Например,
7:57
КВcation Storage. То есть он там то, как мы храним байты, то, как мы там правильно
8:03
варим VCC, как мы это всё раскидываем, как мы это всё синкаем. SQL экзекутер там за транзакции, за то, как это всё
8:10
распределить правильно эту транзакцию, да, там если это какая-нибудь транзакция, которая задействует несколько нот. SQL Gitway отвечает за
8:17
то, чтобы нам этот SQL запрос разобрать уже. Вот, к примеру, тот же неон,
8:23
который вот если вы помните, в начале была новость, купили за очень много денег, что делает
8:28
неон? Ne, условно условно, что делает неон, он разбивает постгрес на два
8:34
компонента: на компьютер и на storage, да? То есть он обманывает Постгрес, и Постгрес условно думает, что он работает
8:42
так же, как он обычно работает. А на самом деле нет. На самом деле под ним лежит условный Amazon EBS, да,
8:48
какой-нибуд там distributed block storage, а Postgress думает, что он работает так же, как он до этого работал. Как они это достигают? Они
8:54
достигают тем, что они перехватывают вот этот recovery сообщения Wstream и уже
8:59
сами в свой кастомный storage, который они написали, уже хранят, распределяют и с помощью этого они могут версионировать
9:06
его, например. То вот вот их основная фича, там бранчинг версионирования, всё благодаря этому они уже могут сделать.
9:13
Вот про то, как примерно выглядит object storage, да, мы с вами тоже поговорим.
9:19
Значит, следующее — это TDB. TDB тоже разбивается на несколько слоёв. У нас
9:24
есть условные TKV, которые на самом деле LSM Storage Rox DB.
9:30
Потом каждый вот этот кв друг с другом синкается с помощью рафта и они уже состоят в кластере, в котором мы
9:36
посылаем наши запросы. Вот все вот эти движущие компоненты мы с вами будем разбирать, чтобы когда вы в следующий раз увидели что-то вроде такого или вот
9:43
такого или вот такого, вы могли понять, а что здесь написано, а что имеется в виду. Ну давайте начнём с самого начала.
9:50
Начнём со сторжи. Значит, стож. Давайте подумаем, а как нам с вами складывать
9:57
байтики? Как нам с вами складывать байтики? Например, у меня есть в базе
10:02
данных таблица users, да? И что мне делать? Как мне эту таблицу users
10:07
представить у себя на диске? Давайте с вами подумаем.
10:14
Значит, мы подумали, подумали и подсмотрим решение у inadb. Значит, и на
10:20
DB. Что это? INDB — это один из движков MyQL. Что делает inb? INDB, вот здесь
10:27
интересно написано table per file. То есть, например, у нас есть таблица users. Таблица users, это
10:34
будет один файл в проприетарном формате, там EBD. Хорошо. Таблица, там, не знаю,
10:40
Orders. Вот второй файл. Давайте, давайте мы эту идею с вами заберём себе.
10:47
Значит, у нас есть таблица users. У нас есть с вами таблица users, и это у нас
10:53
отдельный файл. Хорошо. Значит, теперь в этот файл, что мы хотим в стоage слее?
11:00
Мы хотим с этого файла уметь забирать наши записи. То есть кто-то нам будет говорить: «Отдай мне с этого файла
11:07
запись какую-нибудь там, не знаю, один». И в этот файл нам кто-то будет
11:13
добавлять записи. Например, добавь там 10, а-э, не знаю, Влад семь. Угу.
11:22
Хорошо. Теперь что нам делать? Теперь что нам делать? Теперь нам надо подумать, а куда
11:29
записывать в этот файл, да? То есть нам надо где-то тречить, где у нас конец файла, где у нас есть свободное место
11:36
файле или там кто-то когда-то что-то вычитывает и вдруг они вычитывают один и тот же кусок, а оба начинают его
11:42
редактировать. Как нам заменеджить правильно этот файл, да? То есть нам их складывать друг за
11:48
другом, нам их складывать там, не знаю, через один. Что что нам с этим делать? Значит, мы подсмотрим идею, которая
11:55
называется pagйд. Что мы сделаем? Мы этот файл разобьём на блоке, на пейджи,
12:02
где каждая пейджа будет фиксированного размера. Например, там 4 Кб, 8 Кб, 16
12:08
Кб. Вот кто-то подумает про PG операционной системы. Если вы подумали
12:15
про PG операционной системы, то это здорово. Если нет, то тоже всё хорошо. Но размер
12:20
этих Page не обязательно должен мапиться с размером операционной системы. Вот. А
12:25
база данных лучше понимает, какой размер PG ей будет оптимален для её ворклоуда.
12:32
Вот. Хорошо. Значит, теперь у нас есть PG. Это здорово. Теперь, когда мы хотим
12:38
достать какие-то данные, мы, например, можем сказать: «Эти данные лежат там в первой, в третьей PG, на второй позиции.
12:44
Пожалуйста, вот их забери». Мы их типа раз, раз, раз заберём. Если кто-то другой захочет их же забрать, а мы там с
12:49
ними что-то делаем, мы будем знать, что там тебе придётся подождать. Или там кто-то забрал вот эти три пейджи,
12:54
кому-то нужны там вот эти ещё пейджи. Мы знаем, что эта пейджа у нас как бы уже есть, и мы её можем, грубо говоря, там
13:01
пошарить, например. Найс. Теперь у нас есть какой-то логический юнит, с которым мы можем работать.
13:07
А давайте теперь думать, а как нам писать данные в каждую пейджу? Как нам
13:12
складывать данные в каждую пейджу? Значит, это уже интересно. Вот у нас есть пейджа наша, да? То есть файл
13:19
состоит из пейджей. Вот мы смотрим одну пейджу. Вот у нас есть наша пейджа. Что
13:25
нам в ней нужно хранить? Ну, наверное, наверное, нужно хранить
13:30
какой-то хедер. Какой-то хедер, где мы будем следить, например, за чексуммой,
13:36
проверять, э, пейджа разбилась, не разбилась, когда мы её таскали с памяти на диск дисков память. Нам нужно что ещё
13:42
посмотреть? Нам нужно посмотреть там что-нибудь, связанное с каким-то там свободным местом. Есть ли у нас
13:48
свободное место, когда оно начинается, где оно заканчивается и так далее, и так далее. Плюс ещё там разные моменты, но
13:54
пока, думаю, на этом остановимся. Теперь, допустим, у меня все мои данные,
14:02
да, все мои записи, которые я присылаю в базу, вот уже там запиши 10 Влад 7,
14:08
они у меня фиксированный длины, да? Они у меня фиксированные длины, например, 10
14:13
Влад 7. Они у меня фиксированные длины. Тогда
14:19
как мне их складывать в пейджу? Как мне их складывать в пейджу? Они все пускай весят 32 байта.
14:26
Ну тогда, в принципе, в принципе я могу их складывать в PЖУ друг за другом. Я
14:32
могу складывать в Pageu друг за другом. Одну запись положил, вторую запись положил, третью запись положил, четвёртую запись положил.
14:39
Вроде всё найс. Теперь, если кто-то захочет спросить: «Отдай мне четвёртую запись».
14:45
Да, размер хедера у нас фиксированный, размер одной записи у нас фиксированный. Мы можем сразу ему отдать там четвёртую
14:52
запись, условно вот на забирай. Хорошо, это здорово. Какие могут
14:57
возникнуть проблемы? Проблемы могут возникнуть, когда, например, какая-нибудь запись вот здесь удалится,
15:04
и у нас есть свободное место. То есть нам тут надо условно тречить, что вот это следующее свободное место, там вот
15:09
тут свободное место, от неё тречить вот тут следующее свободное место, да? И там порядковый номер как-то у нас словно
15:14
может сбиться. Теперь четвёртая, она на самом деле ниже. Придётся чучуть погулять. Но гулять от записи к записи
15:23
нам не так сложно. Почему? Потому что она фиксированного размера и можем просто перескакивать 32 32
15:30
и следующую следующую следующую следующую запись забирать. Вроде в принципе всё о’кей, но понятно,
15:36
что мы сталкиваемся с такой проблемой, да, допустим, а на хранение вот этого у
15:43
меня уходит, не знаю, сколько, пускай будет 4 байта на хранение. Вот это у
15:48
меня уходит там, не знаю, 8 байт. Но что делать с вот этим? Что делать с
15:55
вот этим? Что делать с вот этим? Тут уже интересно. Значит, мы можем для
16:01
вот этого всегда с запасом дать какой-то фиксированный размер, да? Мы, например, говорим, что это всегда весит 255. Тогда
16:09
вот, если у меня здесь написано просто Влад, всё остальное неиспользованное место,
16:14
ну, мы просто тратим. Мы как бы себе упростили, что у нас все записи фиксированный длины, но тогда вот это
16:20
всё место мы просто так израсходуем бесполезно. Понятно, что не самый лучший вариант, но
16:27
если у нас начнут записи быть разных размеров, разных размеров,
16:33
тогда по ним вот так гулять от одной к другой мы уже просто не сможем, потому что одна запись вот такой длины, другая
16:38
запись вот такой длины, третья запись вот такой длины, вот такой, потом ещё длинная запись, и уже от одной записи к
16:44
другой там сразу дать, например,чет на четвёртой позиции вот так мы не можем, потому что они разной длины. Плюс ещё
16:51
нам нужно как-то понять, а когда закончилась эта запись, а когда началась
16:56
другая запись? Или в рамках одной записи нам даже нужно понять, а когда начался этот атрибут, а закончился другой
17:04
атрибут. И вот как раз-таки с такими моментами
17:09
мы подглядим, как можно это закодировать. Это можно закодировать следующим образом. Значит, смотрите, у
17:17
нас уже есть, то есть что-то похожее условно делает прото. Значит, у нас уже есть схема, да? Мы пока что в
17:24
реляционной базе данных. У нас есть схема. Мы знаем, что вот здесь у нас условно
17:30
какой-то переменной длины айдишник. Вот здесь он у нас переменной длины фамилия. Вот здесь у меня переменной длины
17:35
департамент. Вот здесь у меня фиксированная. Мы это знаем из нашей схемы, грубо говоря, как у нас вот каждая запись выглядит. Теперь, что мы
17:42
делаем, когда у нас переменной длины? Мы говорим, вот здесь мы храним фиксированный заголовок и ему говорим,
17:48
что вот хочешь найти этот атрибут переменной длины, иди в двадцать первый байт и пять байтов прочитай. Хочешь
17:54
найти этот, иди в двадцать шестой байт и 10 байт прочитай. Хочешь этот, иди в тридцать шестой и 10 байт прочитай. Этот
18:01
вот здесь прямо лежит, потому что он фиксированного размера. Хорошо. Хорошо. Теперь мы можем,
18:07
например, с этой записи сразу забрать там условно третий атрибут, потому что мы знаем, что он переменной длины. Здесь будет там три фиксированных хедера. Вот
18:14
он третий. Мы раз пойдём и прочитаем. Неплохо. Уже лучше. Уже лучше. Хотя бы
18:20
мы теперь можем понять, где один атрибут заканчивается, начинается другой, там, где третий, десятый. Одну запись от
18:27
другой хотя бы можем как-то различить. Но проблема с тем, что они будут лежать,
18:35
они будут лежать и сразу, например, взять четвёртую, да, ну мы пока что не
18:40
можем сразу взять четвёртую мы пока что не можем, потому что они все переменной длины.
18:46
Плюс ещё может быть, что какой-то атрибут какой-то атрибут просто, ну,
18:51
грубо говоря, не залазит в нашу пейджу. Просто он типа больше, чем размер пейджи, да? Что-то вы там решили в нём
18:57
хранить интересно. не знаю, Jйсо какой-нибудь огроменный или там, э, фильм закодировали в BS64, решили
19:04
хранить. Вот эти моменты мы решаем с помощью Overflow Payg. То есть в
19:10
оригинальной Page мы просто будем типа ссылаться, что о’кей, хочешь эти данные, они вон там лежат, иди их возьми. То
19:16
есть это может ссылаться в workflow pageu в постгресе. Это называется у нас,
19:21
а, toast toast.
19:32
Вот overсайized атрибут storage техchne. Как раз-таки для вот этого. Как раз-таки для вот этого. Хорошо.
19:40
О’кей. Эту проблему мы тоже там как-то решили, но теперь у нас проблема, когда
19:47
они разной длины, а мы хотим условно забрать там с вот этой пейджи, да, это, допустим, это там третья пейджа, мы
19:53
хотим дай мне третью пейджу, вторую запись. Вот так быстро ответить мы на этот вопрос, к сожалению, не можем.
20:01
Для этого мы добавляем ещё один слой индирекции, да? То есть, что мы с вами
20:08
делаем? Что мы с вами делаем? Мы берём pageйджу. Мы берём pageйджу. У неё есть фиксированный headдер. А потом для
20:14
каждой записи мы тоже делаем свой headдер. Вот так фиксированной длины.
20:21
Раз, раз, раз, раз, раз. А каждый из этих хедеров хедеры растут из начала в
20:28
конец PG, а из конца в начало Page у нас растут наши данные. И мы можем сказать:
20:34
«Вот этот headдер указывает вот сюда на эту запись. Вот этот указывает вот сюда.
20:41
Там, допустим, вот этот указывает вот сюда. Вот этот указывает вот сюда.
20:47
И теперь, когда нам говорят: «Дай мне с этой PG четвёртую запись», мы можем сразу, вот это фиксированной длины, вот
20:53
это каждый из них фиксированной длины, можем сразу найти четвёртый и ткнуть. Вот он, забирай в этой же
21:00
Pйдже. И ровно такой же подход, ровно такой же подход у нас с вами использует
21:06
Postгрес. Ровно такой же подход у нас с вами использует Postgrгess. Вот, пожалуйста.
21:13
То есть у нас есть каждая, у каждой PG есть свой какой-то, где хранится чек
21:18
сумма. LSN — это для WR head lлоog версия, там флаги. Lower uper.
21:23
Прикольно. Это что? Lower upper это где заканчиваются хедеры, где заканчиваются
21:30
сами у нас уже записи. Что с помощью этого можем сделать? Проверить, сколько у нас свободного пространства, да? То
21:36
есть они растут вот отсюда, эти растут вот отсюда-сюда. И можем проверить, сколько у нас свободного пространства осталось, типа, стоит ли в эту pageйджу
21:42
что-то писать. Постгрес использует ровно такой же подход. Пожалуйста. Вот мы с вами типа
21:50
придумали постгресса. Плюс ещё у каждого хедера этой записи, у
21:55
каждого хедера записи есть свои поля, свой хедер, где мы внутри храним, например, для MVC,
22:03
какую транзакцию он может, какую транзакцию он не может. Там ссылка на следующую запись, да, то есть потому что
22:08
MVC хранит несколько за несколько версий одного одной и той же записи. Вот
22:14
и другие моменты, которые мы с вами посмотрим. И также вот момент, что у самой PG тоже может быть headдер. Он
22:20
фиксированного размера, 24 байта, и в нём уже вот там чек сумма. Ну, это мы с вами видели на другой картинке.
22:27
Хорошо. Супер отлично. Супер отлично. Теперь может другой момент у нас возникнуть.
22:34
Теперь как нам достать с третье PG четвёртую запись? Пожалуйста, каждый день. Но возник другой момент, что мы
22:42
помним, что записи у нас переменной длины, да? И тогда может случиться вот такая ситуация. Вот у меня была запись,
22:49
вот была запись, вот была запись, вот была запись. Это я удалил, это я удалил. Вот это хочу
22:56
вставить. И по идее на него место есть, да? На
23:02
него место есть, по идее. Ну, то есть, допустим, если это весит восемь, это весит на него место есть.
23:12
Но что нам придётся сделать? нам придётся тогда это удалить, это удалить, а потом их друг с другом
23:20
передвинуть, да, передвинуть свободное пространство. То есть вот эту там сдвинуть направо или вот эту сдвинуть
23:25
налево. Что-то придётся с этим сделать. Но когда мы это будем делать, что нам придётся делать? Нам придётся и вот эти
23:31
все указатели пересобирать. А вдруг кто-то работает с этими данными? Тогда нам придётся это всё подлочить и
23:36
посмотреть, чтобы никто их параллельно там не вычитывал и не модифицировал. Проблема. И это проблема. И как раз-таки
23:43
такой проблемой с мёртвыми туплами у нас занимается вакуум. Вакуум — это условный
23:50
гарбадж коллектор в вашем сторадже, который вот vacum reclaim storage occupied by tles in normal postgress
23:58
operation tles are deleted or absoluted by update are not physically removed. То
24:03
есть мы их не удаляем, но мы их просто помечаем, что вот их
24:09
надо убрать. И в следующий раз, когда у нас вакуум отрабатывает, он их убирает. Что он делает там? А дальше уже в вакуум
24:16
вы можете в зависимости от того, как вы его затюнили, то есть он там либо всё это пишет в новую пейджу, либо там в
24:21
этойже двигает. Вот это можете уже отдельно почитать, если вам интересно.
24:27
Хорошо. Здорово. То есть, в принципе, всеми вопросами, которые у нас могут
24:32
возникнуть в рамках стореджа, мы плюс-минус разобрались. Мы плюс-минус разобрались.
24:39
Единственное, что мы не разобрали, это какие есть у нас альтернативы, да? Но на
24:46
альтернативы мы с вами посмотрим позже. Посмотрим позже. Значит, что ещё? Вот вы
24:53
часто могли слышать, что есть там row oriented, colum oriented, да? Или там говорят колоночные базы, колоночные
24:59
базы. Вот покажу на абстрактном примере, что почему, например, есть отдельный
25:05
подкласс, да, баз данных, которые работают с коло с колонками. И как бы что это нам даёт? Вот давайте возьмём на
25:12
таком примере, вспомним, как у нас сейчас хранятся. Вот у нас есть PG, у
25:17
нас есть PG. Если вы подумали про клиck house, это рядом, но клиck использует чуть-чуть другой тип стоджа. Но вот мы
25:23
сейчас берём абстрактны. Вот у меня есть PG, в нём есть записи. В нём есть записи. И записи хранятся вот
25:29
так: 10 Влад семь, да? Допустим, семь — это там
25:35
привлекательность по стобалльной шкале. И у меня есть ещё другие записи, там, не
25:41
знаю, какой-нибудь там Олег 5, не знаю, какой-нибудь там Игорь 90, вот и там
25:48
бла-бла-блаблаблабла. Ещё у меня много, много много миллион, миллион записей.
25:53
Вот. А мы что хотим сделать? Мы хотим, например, посчитать вот так взять и
26:00
посчитать там какую-нибудь сумму, там какую-нибудь медиану, не знаю, среднее, там как-то перемножить
26:07
их. Вот что-то хотим мы с этими числами сделать, да, чтобы посчитать какую-то статистику. И таких записей у меня там
26:13
очень много, там миллиарды, миллионы. Тогда какая проблема? Вспомним, как это всё у нас лежит. Чтобы
26:20
прочитать вот это, мне придётся из PG выгрести вот так целиком.
26:26
Да, мне придётся выгрести page, а потом из page выгрести вот это. Но мне по сути нужно только это число. А зачем я вот
26:33
это забрал всё? Зачем я вот это всё забрал? Оно мне не нужно. И вот тут я лишнего набрал. И вот тут я лишнего
26:38
набрал. И вот тут я лишнего набрал. И вот здесь, и вот здесь, и вот здесь, и здесь. И вот здесь я столько лишнего набрал. Хотя по факту меня только вот
26:44
это интересует. Как я могу этот вопрос решить? Я могу этот вопрос решить так, что я
26:50
переорганизуюсь тоже. И теперь я буду хранить все атрибуты рядом.
26:56
одного типа,
27:03
бла-бла-бла-бла-бла. И вот здесь ID.
27:09
Вот я теперь храню все атрибуты рядом. И теперь, когда мне нужно, например,
27:17
посчитать вот это, я буду их выгребать, и они все реально будут рядом лежать.
27:23
Что я могу ещё сделать теперь? Поскольку это все атрибуты одного типа и они лежат рядом, я могу здесь уже сделать
27:28
какое-нибудь там сжатие, какое-нибудь кодирование. Плюс я ещё могу использовать векторные операции. Я могу
27:33
там параллельны, если это сумма, да, то сумма у нас условно коммутативная, я могу там вот это сложить, с этим сложить
27:39
параллельно. То есть могу различные другие оптимизации делать. И когда я выгребаю данные, я буду выгребать по
27:46
факту только то, что мне нужно, а вот без вот этих вот лишних атрибутов.
27:51
О’кей. для подсчёта чего-то. И это пушка. И это пушка. Но, но, но когда
27:57
возникает проблема, проблема возникает, когда нам нужно будет собрать этот эту
28:04
запись обратно. То есть, когда, например, я хочу узнать, а вот это кто? Я смотрю, что он здесь на четвёртой
28:10
позиции, да? Я должен найти здесь кто на четвёртой позиции, здесь кто на четвёртой позиции. Там условно, если там
28:15
что-то происходит, возможно, их всех подлочить и потом вот это реконструировать. Вот так собрать. А,
28:21
допустим, оно здесь пожато, её надо разжать и выдать, да? То есть поэтому у
28:27
нас условно есть аналитический workклоуд, а есть транзакционный workкloadд. И поэтому для аналитического
28:34
ворклоуда там подходит один тип стоджа, для транзакционного ворклоуда подходит другой тип стоджа, потому что то, как
28:40
хранятся данные, влияет напрямую на то, как мы с ними работаем.
28:46
О’кей. Надеюсь, этот момент стал вам более понятен. То есть вот column
28:51
oriented, мы храним все атрибуты вот так рядышком. Row oented мы храним запись.
28:59
Хорошо. Хорошо. Значит, с этим слоем там датафайл мы как-то более-менее с вами
29:05
разобрались. Теперь что интересно? Теперь здесь есть какой-то systemм-каталог. А что такое systemкаталог? Что такое
29:12
systemталог? Хмм, надо подумать. Делаю вид, что я думаю. Значит, system
29:18
катаalog — это, по сути, директория, которая хранит методанные о том, где что
29:24
находится. Например, вот эта таблица там условно постгреси лежит в этой папке, в этой директории, в этих файлах. На эту
29:30
таблицу вот такая схема. На эту таблицу навешаны вот такие индексы. Эту таблицу можно там читать вот этим вот этим вот
29:37
этим юзером. Или там вот этот индекс находится в вот этом файле, вот это находится вот здесь.
29:43
То есть метаданные о том, где хранятся ваши данные, там сколько, например,
29:49
здесь есть свободного места, сколько там хранится записей. Вот все метаданные мы
29:54
можем хранить в этой директории. Хорошо. Хорошо. Значит, теперь
30:01
интересное. Теперь интересное. Смотрите, нам нужно данные с диска
30:08
таскать в память. Нам нужно данные с диска таскать в память. Почему мы это с вами хотим делать?
30:15
Почему мы с вами это хотим делать? Почему мы хотим их с диска таскать в память?
30:21
А как аналогию скажу, например, с вашим приложением, обычным веб-приложением,
30:27
которое вы разрабатываете, да? Вы там обычно добавляете какой-нибудь кэш в виде редиса и прочее, но сюда, если вы
30:33
добавляете кэш, у вас тоже возникают различные проблемки там с инвалидацией и прочее. Вот здесь мы тоже что-то
30:40
подобное увидим. Ну вот одна из причин, например, что достать это на 2025 год
30:47
числа Planet Scale. Ссылка будет, значит, достать что-то из памяти.
30:53
Roundтрип — это 100 наносекунд. Достать что-то из диска — это 50 микросекунд.
30:59
Чтобы вы представляли скейл, как это происходит. То есть вот мы говорим про вот такой порядок, понимаете? То есть
31:05
пока вы что-то достанете из диска, в памяти уже вообще уже уже там на порядок. Мы уже всё уже закончили, уже
31:11
домой пошли, но при этом памяти у нас меньше и память
31:18
у нас волатильная. Что значит волатильная? Это значит, что когда условно выключится электричество, да,
31:23
что часто происходит в Узбекистане, то все данные из вашей памяти пропадут. Поэтому нам нужно как-то хитро работать
31:30
с ними в памяти, да, но при этом не забывать их скидывать на диск. Не забывайте скидывать на диск.
31:37
И как раз-таки за вот такие моментики, за вот такие моментики у нас будет с вами отвечать буфер пулol. Отвечать
31:45
буфер пулol. Значит, что может делать буфер pool? Буфер пулol может затягивать
31:51
страницы page с диска себе в память. При этом он ещё может выполнять функциональность какую? Он, например,
31:58
видит ваш запрос, да, что вы делаете какой-нибудь там сексн, и он может заранее, например, заприфечить страницы,
32:05
которые вам будут нужны. Либо онвидит, что несколько запросов хотят одну и ту же страницу, он её не будет выталкивать
32:11
из буферпула, а между ними условно пошарит. Или, например,
32:16
э какая-то страница часто используемая, например, директория или там корень индекса, он её может взять и запинить.
32:25
Он её может пометить, что она грязная, значит, её типа там нам нужно, это зависит от стил полиса. Это мы больше с
32:31
вами поговорим, что с ней нужно сделать. Он может там хранить на ней, кто кто сейчас её залочил, кому она сейчас
32:36
нужна, там эксклюзивный лок на ней стоит, лок на ней стоит. Про это мы тоже с вами дальше поговорим. То есть
32:42
буферpol выполняет не только базовую функциональность, что это просто кэш. То есть он выполняет ещё
32:48
различные такие моментики. Но, но, но, но понятное дело, что, предположим, у
32:54
меня там, а, на диске эта база уже разрослась, что она занимает, не знаю,
33:00
терабайты, но памяти у меня нет терабайтов. Памяти у меня ограниченное количество. Тогда возникает вопрос: а
33:08
кого выталкивать? Кого выталкивать из памяти? Кого выталкивать из памяти? Его,
33:13
его, его его. Кого? Не туда ткнул. Его его его его. Кого? Кого вытолкнуть?
33:21
Можно взять самую простую полиси. Можно взять Фифо. Первый пришёл, первый ушёл.
33:27
Хорошо, тогда мы первым, например, затолкаем себе каталог индексы. Мы их первыми же и выгоним, когда у нас идёт
33:33
обычный там селект звёздочек какой-нибуд секскан. Плохо.
33:39
А есть другая полиси. Есть полиси, которая называется.ru есть задача на лидкоде. Я вам всем её
33:47
советую порешать. Либо можете найти, у меня в курсе по алгоритму. Шучу. Значит,
33:52
смотрите, что такое LRU. LRU — это list recently used. На русский переводится не
33:58
очень хорошо, но least recently used — это наименее недавно использованный.
34:05
Наименее недавно использованный или типа тот, кого давно трогали, грубо говоря, тот, кого давно трогали.
34:12
Например, вот у меня есть кэш размером три. Я добавляю 1
34:18
О’кей. Я его недавно потрогал. Я добавляю 220. О’кей, только потрогал. Я добавляю 330.
34:27
О’кей. Только потрогал. Теперь, когда я захочу добавить 440, у меня уже нет
34:33
места в кше моём. Кого-то из них надо толкнуть. Кого толкнуть? Толкну я 10. Почему? Потому что я
34:40
добавлял 10, 20, 30. И получается 10 я самое давнее, кого я трогал. Но если я
34:46
сейчас возьму и потрогаю 10, да, 11, то я его освежу, типа вот я вот я тебя
34:53
потрогал, и тогда у нас появится 20. И если я потрогаю три,
35:01
а за ним потрогаю два, то кто у нас опять стал самый давно нетроганный,
35:09
кроме Влада? 10. Всё верно. И теперь, когда я буду
35:14
добавлять новую запись, она у меня вытолкнется отсюда. Хорошо? Значит, это клёвое полюси. То
35:21
есть, условно, у нас будут какие-нибудь индексы, которые мы будем часто использовать или там, э, табличка
35:28
какая-нибудь популярная, которую мы часто будем пользовать. Она у нас, в принципе, всегда будет прогрета.
35:34
А проблема с LRU, так называемая проблема sequential fluding. Что это
35:39
значит? sequential floading. Если простыми словами объяснять, что у меня что-то было вот здесь, то, что мне
35:46
нужно, да, потом это бы я бы вот здесь где-нибудь заиспользовал бы вообще с
35:53
кайфом, да, и вот здесь бы заиспользовал, да, вообще оно мне нужно. Но вот здесь, допустим, происходит
36:00
какой-нибудь огромный сексскан. Огромный сексскан, который посчитает, ну, не
36:05
знаю, какою сумму атрибутов, да, какое-нибудь такое одноразовое значение. Но вот этот секскан, он будет
36:12
выполняться, и пока он будет выполняться, он начнёт прогревать, прогревать, прогревать, прогревать, прогревать, прогревать. И и
36:19
получится, что они все те, кого недавно потрогали. А вот эти окажутся, что их давно не
36:24
трогали, они вытолкнутся. Хотя они бы нам вообще с кайфом вот здесь пригодились. Вот это проблема. А можете
36:31
про неё ещё прочитать. Называется сек флудинг.
36:36
Найс, найс, найс, найс, найс, найс. Теперь, значит,
36:42
что мы с вами поняли? Мы с вами увидели, значит, что там, как мы что храним на
36:47
диске, да, как мы что-то там достаём в память себе прогреваем какие-то там
36:53
каталоги, которые нам говорят, где что искать. Но, но, но, но, но а кто
36:58
приходит к нам в сторедж и говорит, что если я хочу найти вот эту запись, она
37:03
лежит в этой пейдже вот в таком-то отступе. Кто это? Кто ты? Кто кто ты
37:10
воин? Кто этим занимается? Да и вообще,
37:16
как мы можем сейчас это решать? Допустим, мы мы хотим найти что-нибудь там из таблички с определённым там
37:22
айдишником или атрибутом. Как мы это можем сделать? Ну, можем типа выгрез вообще всю таблицу, перебрать и найти
37:29
то, что нам нужно. А можем можем можем использовать определённые механизмы
37:34
структуры данных, которые ускорят этот поиск, доступ к нужным нам данным или
37:40
по-другому. Йя дробь, спойлер арт, индексы. Всё верно.
37:48
Подумайте, какие индексы вы знаете. Какие индексы вы знаете?
37:56
Какие индексы вы знаете? Хорошо, вы подумали, значит. Но давайте разберёмся сначала с основной
38:03
терминологией. Значит, какие могут быть индексы? Индексы могут быть кластеризованные, не кластеризованные.
38:10
Значит, что значит кластеризованный? Кластеризованный — это значит индекс диктует то, в каком порядке будут
38:17
храниться записи в файлах. Вот прямо типа то, как они хранятся, да, то как они хранятся в индексе, условно. Также и
38:25
диктуется порядок здесь. Некластерные — это когда такой порядок не диктуется. Например, например,
38:32
например, в MySQL в NDB primary индекс кластерный, он будет диктовать то, как
38:38
хранятся в каком порядке файла. А в постгресе используется хипа куча
38:43
организации файлов, и они у вас в рандомном порядке. У вас есть там
38:48
primary индекс, да, который там задаёт primary key, но этот primary индекс у
38:54
вас отвечает только за Unique constraint, чтобы вы благодаря нему могли отличать одну запись от другой.
39:00
Одну запись от другой, да, условный какой-нибудь там автоинкремент, но за порядок записей он нам не даёт.
39:10
Зачем нам нужны, например, записи в порядке? Потому что, если у нас записи лежат в порядке индекса, мы можем
39:16
построить разряженный индекс. Что нам даёт разряженный индекс? Вот посмотрим. Вот они хранятся в порядке
39:23
айдишников, да? У нас есть плотный и разряженный spars den indкс. Значит,
39:28
плотный индекс мапит один к одному записи. Разряженный индекс может мапить
39:35
диапазоны. Например, вот здесь записи находятся с 10101 до там 3243. Вот здесь
39:40
3 2 3 4 3 до 76 766. Что нам это даёт? Что нам это даёт?
39:47
Благодаря этому мы можем сделать сам индекс меньше и обновлять его реже. Но мы это можем
39:55
сделать только когда у меня вот здесь есть порядок. Видите, они отсортированы по айдишником.
40:01
Понятно, что если порядка нет, то вот этот диапазон нам ничего не даст. Здесь может быть любое рандомное значение.
40:08
Дальше мы можем строить иерархию из этих разряженных индексов, да, там, чтоб ещё
40:13
измельчить, но это уже специфика. Что такое Secondary икс? Значит,
40:19
secondary индекс — это когда вы ищете по какому-нибудь другому атрибуту. Например, я ищу не по айдишнику, я ищу
40:26
по, не знаю, почему, я ищу по какому-нибудь там компьютер science департамента, по
40:32
какому-нибуд департаменту, где он работает. Я ещё по какой-нибудь зарплате, я ищу по фамилии, что-нибудь такое, да? То есть, если у вас условно
40:39
есть какой-то, э, прай key, а вы ищете не по
40:46
нему, а ищете по какому-то вторичному признаку, да, то вы используете secondнary indкс. Значит, о’кей.
40:53
Как он может быть устроен? Он может быть устроен так, что он либо будет указывать
40:59
также, где найти конкретно эту pageu эту запись, да? Но тогда какая проблема?
41:06
Тогда, если будет работать вакуум, потом надо будет все индексы вот здесь поменять. Ээ когда они переедут, где кто
41:14
находился. Ещё какая проблема есть?
41:19
Ещё какая проблема есть? Подумайте. Либо второй вариант, хранить ссылку на
41:24
primary индекс. То есть мы говорим: «Вот эта запись, это там условно 151 332 343
41:32
это запись вот эти, это запись вот эти, это запись вот эти». Тогда какая проблема? Тогда если где-нибудь туплы в
41:38
PG переедут, вам ничего обновлять в своём индексе не надо, да? Но у вас добавляется слой индирекция, что вам нужно сходить потом ещё в primary
41:45
индекс. Хорошо. Значит, одни из самых
41:52
популярных индексов, которые можно назвать, это шнкс и B3. Давайте
41:58
посмотрим с вами на Шиндекс для начала. Что такое шдекс?
42:03
Для того, чтобы разобраться, как работает шдекс, давайте посмотрим, как работает мапа. Я вам советую посмотреть
42:09
видео на моём YouTube канале или где-нибудь ещё, но давайте вкратце объясню. Значит, у вас есть какое-то значение X, вы его пропускаете через
42:16
хэш-функцию, оно вам говорит, куда это положить, условно, в какой бакет, да?
42:21
Вот сюда, вот сюда или вот сюда. Теперь, если, например, оно попало вот
42:27
сюда, а там же что-то было, какие есть варианты? Есть вариант вот здесь их заченить и хранить несколько значений,
42:34
тогда какая проблема? Если у меня хэш-функция неравномерно распределяет,
42:39
да, или данные так распределены, то у меня может получиться, что все они попадают в один бакет, и они будут друг
42:45
за другом, друг за другом. И тогда мы вот от хэшфункции получим, что у нас линию занимает, да, оn, хотя мы хотим
42:53
это доставать за за константу. Какая есть другая другой вариант? Есть вариант делать, что если вот здесь занято, давай
43:00
напишем в следующий бакет. Но тогда может быть такой например порядок добавления, что все
43:05
сначала добавились не в свои бакеты, а когда ребята придут уже в свои бакеты, там уже будут заняты, и они начнут ещё
43:10
дальше переезжать. Есть вариант добавить вторую хэш-функцию. Есть вариант добавить, а, например, extendable
43:18
hasшиing. Что это значит? Это, например, вы бьёте какой-то префикс и сначала берёте по первому биту префикса
43:24
выбираете, куда она пойдёт. В первый, второй бакет. Как только там место закончилось, вы берёте уже вто следующее
43:32
значение в префиксе и разбиваете в какой из четырёх. А дальше там в какой из восьми, дальше в
43:37
какой там из шестнадцати. Вот. То есть вы всегда расширяете префикс, куда она у вас пойдёт.
43:44
Хорошо. Значит, для чего хороша хэш-функция? Хэш-функция хороша, когда мы хотим найти конкретное значение.
43:50
Конкретное значение. Например, я хочу найти computer science. Computer
43:56
science. кто работает в computer science. О’кей, на этот атрибут мы навесили, условно хэш-индекс. Мы пропустили через хэш-функцию. Она нам
44:02
скажет: «О’кей, вот эти ребята там, вот эти адишники дватри там восемь работают
44:08
в компьютер science. Nice. Когда плохо работает ш хэш индекс хэш индекс плохо
44:15
работает, когда нам нужно найти что-нибудь, например, кто зарабатывает больше 7.000. Кто
44:22
зарабатывает больше 7.000? Почему? Потому что порядок того, как
44:28
данные сложатся с хэш-функцией, да, нам никто не гарантирует. Нам никто не гарантирует.
44:34
И поэтому, чтобы найти те, кто больше 7.000, что мне нужно делать? Мне нужно будет 7.000 пропустить через хэш-функцию. Найти о’кей, вот эти, вот
44:40
эти, вот эти ребята. 7.0001, 7.0002, 7.003, 7.004. То есть каждый из этих
44:47
чисел нужно будет пропускать и смотреть. Какой из этого вывод? Когда у нас идёт,
44:53
что нам нужно точечно доставать какие-то конкретные данные, да, по какому-то конкретному значению, тогда ш супер
45:00
хорошо. Но когда нам нужно доставать какие-то ренжи диапазоны, тогда у нас уже идёт поплава.
45:08
Хорошо. Значит, наиболее распространённый и везде
45:14
использованный индекс и там возможный индекс по умолчанию, который вы всегда видите — это B + 3. Давайте с вами
45:21
поговорим про B + 3. Давайте мы сначала с вами посмотрим, как работает B3, а
45:27
потом посмотрим, как работает B + 3. Значит,
45:32
будем рандомно добавлять какие-нибудь значения, да? Здесь я поставлю параметр пониже. Вот мы их рандомно добавили.
45:38
Бам-бам-бам-бам-бам-бам-бам. Теперь, когда я хочу найти 761,
45:45
как я могу это сделать? Я смотрю, 761 меньше 214. Нет, он между 214 768.
45:54
Да, значит, я иду ниже. Он меньше 719. Нет, он больше. Да, иду
46:02
направо, получаю 761. 761.
46:07
Бам, бам, бам, бам. Найс. Я хочу найти 984.
46:13
Я иду также сюда направо, сюда направо. Вот его нахожу. И оно у нас так дальше растёт, растёт, растёт. Смотрите, когда
46:20
получается интересный момент. Я хочу добавить 985.
46:26
Здесь у меня стоит note 2. Здесь уже места нет. Что тогда мне делать? Чтобы
46:32
вот добавить сюда, мне надо это разбить на две ноды, распределить между ними, а
46:39
вот сюда добавить новый указатель. Да, что вот у меня появилась ещё одна нода с новым
46:45
диапазоном. Давайте на это посмотрим. Бабам. Но, но, но нам надо помнить, что каждая
46:53
из вот этих нот, она тоже как-то у нас хранится. Она тоже у нас как-то хранится. То есть, условно, каждая эта
47:00
нода у нас, допустим, отдельная пейджа. И то есть, чтобы просовершить вот эту
47:06
операцию, мне нужно будет вот эту пейджу залочить, разбить на два, вот здесь
47:13
залочить, вот здесь обновить и всё это проделать. Хорошо, больно. Довольно
47:18
больно. Теперь я хочу добавить 921. Оно пойдёт вот сюда. А теперь я хочу
47:23
добавить 922. Я хочу добавить 922. Что надо будет с
47:29
этой нодой сделать? Что надо будет с эти с этой нодой сделать? Её нужно будет разделить на две, перераспределить.
47:38
Ну, когда мы её разделим на две, сюда нужно повесить новый указатель. Здесь уже нет места для нового указателя.
47:44
Значит, её надо разделить на две. Тогда сюда надо навесить новый указатель. А здесь тоже нет уже места, тогда надо её
47:50
разделить на две и сюда навесить на указатель. И то есть, смотрите, я просто добавление 92 нам может стоить вот
47:56
столько. 1 2 3 бабам.
48:02
У нас почти всё дерево с корня перестроилось. Это супер больно. Помним, что вот это
48:07
какая-нибудь педжа, вот это пейджа, вот это педжа, вот это педжа, вот это пейджа. Оно всё у нас вот так сейчас перераскидалось.
48:15
Больно, больно, больно, больно. Но, но что она нам даёт? Она нам даёт, что
48:20
когда я хочу найти какое-то конкретное значение, я могу её найти за O log MN,
48:26
где m — это сколько у меня фанаут, сколько у меня выходит из каждой ноды
48:33
указателей, да? То есть там в бинарном дереве BST мы говорим: «Это log n»N,
48:38
потому что мы имеем в виду log 2n, а здесь это log mn, где m — это фанаут,
48:44
который сколько у меня выходит нот из и из сколько у меня выходит указателей из одной ноды.
48:50
Хорошо, это больно. Но теперь, когда я хочу найти, например, все значения от 271 до 761,
48:56
ну, о’кей, я иду вот сюда, беру бам 271, бам 688. Потом, к сожалению, придётся
49:02
идти наверх. Потом придётся опять спускаться вниз. Вот это чуть неприятно. Вот это чуть неприятно. И плюс ещё, если
49:09
мы здесь посмотрим, у нас значения хранятся иногда не только в листовых
49:15
нодах, но ещё и хранятся вот здесь. Ещё и хранятся вот здесь. Это ещё больнее.
49:20
Поэтому для этого у нас есть B + 3. И во всех базах данных используется B + 3. B
49:27

• 3. Смотрите, что такое B + 3. У меня значения хранятся только в листочках.
  49:35
  При этом у меня все значения друг с другом подшиты. Что имеется в виду? У
  49:40
  меня есть указатель на соседнюю ноду. И теперь, когда я хочу достать что-нибудь от 176 до 429, я могу пойти слева
  49:46
  направо, бабам, и за раз их забрать. Кайф. Вот это кайф.
  49:54
  Но какая у этого проблема? Когда я сюда, например, добавляю 388, оно пойдёт вот сюда. Я хочу добавить 389. Что мне
  50:02
  придётся делать? 1 2 3 389. Вот сюда.
  50:07
  Бабам. Опять пересобирать дерево. Но теперь, когда мы будем его пересобирать, нам нужно следить не только за
  50:13
  родительскими связями, нам ещё нужно следить за вот этими указателями. Они тоже у нас пересобираются. Смотрите.
  50:19
  Бабам. Это, конечно, более неприятно в реализации это гораздо сложнее окажется.
  50:26
  Советую вам попробовать. Хорошо. Но зато теперь ренжсканы у нас
  50:32
  просто берут и за раз прямо можем пропылесосить. Теперь, что у нас хранится? Что я говорю под что у нас
  50:39
  хранится вот здесь в листочках, в значениях? Значит, у нас есть вот такие варианты. У нас в листочках могут
  50:45
  храниться либо указатели, то есть вот это можно найти в седьмой PG, а вSET 2.
  50:51
  Ну тогда, когда они будут перемещаться, нам нужно будет здесь тоже обновить. Либо-либо это может быть вообще
  50:57
  какой-нибудь index organized storage, где у меня в листочках хранятся прямо pageйджи со значениями. Page со
  51:05
  значениями, да,
  51:11
  хорошо, хорошо. Это мы с вами увидели. Значит, какие ещё у нас могут быть
  51:17
  индексы? То есть боль B +3 в том, что как некоторые записи у нас супербольные,
  51:25
  супербольные, потому что, чтобы произвести вот эту операцию сейчас сюда 393, мне придётся лочить
  51:32
  почти всё дерево для того, чтобы его потом правильно ребалансировать, правильно засптить эти синоды. Баба. То
  51:38
  есть мы представляем, что вот это пейджа, вот это пейджа, вот это пейджа, вот это пейджа, вот это пейджа, вот это пейджа. Всё это придётся лощадь, потому
  51:44
  что произойдёт модификация, да, и там вдруг кто-то другой работает в этом же дереве, и для него всё изменится. Поэтому надо сказать: «Слушай, я сейчас
  51:51
  буду его пересобирать». Для этого есть оптимизации. Например, у нас есть BP3,
  51:57
  да? То есть это вот оптимизация,
  52:03
  что она нам предлагает? А нам предлагает рядом с каждой нодой не сразу её
  52:08
  перестраивать, а хранить определённый буфер. Хранить определённый буфер. Хранить определённый буфер. И мы
  52:15
  накапливаем эти изменения и потом либо там снизу с нуля перестраиваем, а либо
  52:21
  либо там, ну сами решаем, что нам, когда где перестроить, да? То есть мы можем копить какой-то предел этих изменений.
  52:29
  Вот. Но тогда проблема появляется с чтением, что нам надо будет тогда ещё проверить, а есть ли эта запись в этом
  52:35
  буфере, плюс это всё правильно заменеджить. Хорошо.
  52:42
  Хорошо. Значит, какие у меня ещё бывают индексы? У меня может быть bitmap
  52:48
  индекс. Что такое bitmap? Bitmap — это когда
  52:55
  у вас есть атрибут, у которого фиксированное количество значений, да?
  53:01
  То есть это не так, что он может принимать там миллиарды значений, а он принимает довольно фиксированное количество значений какое-нибуд там, да,
  53:07
  то есть он принимает только mail, femil или там L1, L2, L3, L4, L5. И я хочу проверить, в этой таблице есть
  53:14
  кто-нибудь FIL L2 или нет сразу. Как я могу это сделать? Как я могу это
  53:20
  сделать? Смотрите, вот у меня здесь пять записей, пронумерованных с нуля, да? Что
  53:25
  я делаю? Все, у кого mail, я ставлю бит один на этой позиции 1, значит, нулевой
  53:32
  бит о и 1 2 третий бит о Что это значит? Это значит, у первой записи будет mail и
  53:38
  у третьей записи будет mail. Fail 1 1. Вот 1 1 1. Ага. То же самое делать для
  53:45
  L1, L2, L3, L4, L5. Для L1 я делаю здесь. единица, потому что на L1 и на
  53:52
  второй позиции единица, потому что тоже L1. Например, L4. Почему здесь единица?
  53:58
  Потому что вот третья запись — это L4. Хорошо.
  54:03
  Что я теперь могу сделать? Если я хочу проверить, ес ли в этой табличке FIL L2,
  54:08
  я могу взять вот эту маску, вот эту маску и сделать по битвой. И я делаю по
  54:15
  битвой. И, у меня остаётся один, да, на второй позиции. Что это значит? Это
  54:20
  значит, что на первой позиции, что первая позиция у нас будет FMIL L2. Ну,
  54:25
  понятно, тогда проблема, если маска слишком длинная, мне надо будет выискивать вот эти биты, которые включены. Поэтому в основном это
  54:31
  используется для того, что есть ли вообще там Femil L2 и как бы если значение больше нуля, то FMIL L2 там
  54:38
  есть. Если значение ноль, то FMIL L2 там в принципе нет. В этой таблице можно не искать.
  54:44
  Хорошо. Следующий индекс. Следующий индекс — это инвертированный индекс. Да.
  54:50
  Для чего нам нужен инвертированный индекс? Например, у меня есть три песни. У меня есть три песни. И вот здесь я
  54:56
  тебя так любил, ты от меня ушла. Любовь, любовь, любовь. Вот здесь там у подъезда мы стоим, но без тебя вот тут, а солнце
  55:06
  как луна, твоя любовь ушла. Вот три песни. И теперь я хочу найти все песни, в которых было
  55:13
  слово любовь. слово любовь и его производные, например, там lovers или
  55:19
  там loves и что-нибудь подобное. Вот что мне придётся делать. Мне придётся идти и
  55:26
  перелопачивать каждую песню и там искать, есть ли там такое слово, и в
  55:32
  конце сказать, что да, о’кей, вот в первой песне было такое и в третьей песне было такое.
  55:38
  Но у нас для этого есть инвертированный индекс, да? Это там апачалу в эластике,
  55:43
  в постгресе у вас тоже есть инвертированный индекс. Что он нам позволяет делать? Он возьмёт,
  55:50
  распарсит эти песни, вычистит слова на все похожие на производные и заранее
  55:56
  создаст вот такого вида индекс. Что, например, слово абобаба
  56:02
  в первой песне, в третьей песне, слово лов было во второй песне, в четвёртой
  56:08
  песне, там слово XYZ встречалось у меня там в первой песне. Вот. То есть это
  56:15
  инвертированный индекс. И теперь, когда вы хотите найти, например, лов, вы сразу будете знать, о’кей, это вторая и четвёртая песня. Это вторая и четвёртая
  56:21
  песня. Значит, мы живём в 2025 году, и теперь мы умеем ещё по-другому кое-что делать. Например,
  56:29
  например, песня построена на метафорах, да? То есть он везде писал: «Ты как лягушка, а я как пруд, я скочу без
  56:37
  тебя». Вот что-нибудь такое. То есть понятно, что он поёт про лягушку и пруд, но все мы поняли, что он поёт про
  56:42
  любовь. Все мы поняли, что он поёт про любовь, но конкретного слова любовь там нет в тексте песни. Но смысл песни мы
  56:49
  понимаем, что это про любовь. Значит, для этого, что у нас есть? Для этого у нас есть имбединги, да? Что вы можете
  56:56
  сделать? Вы можете взять какую-то модель, нагенерировать имбединги, то есть флоу примерно вот такое. Это вот
  57:03
  я сейчас говорю про раги, про векторные базы данных. Вы берёте, генерируетебединги через бединг модель,
  57:09
  она нам даёт типа вектора. Она даёт вектора, то есть это массивы флоутов, да, что вот этот вот эта песня, она вот
  57:15
  в этих векторах. Дальше, что вы делаете? Вы эти вектора мачите с метаданными, что там, о’кей,
  57:21
  это вот это вот эта песня или там вот эта капучино и что-нибудь там что что уже вы хотите от вашего бизнеса, что вам
  57:28
  надо, и суёте это векторной базы данных. А потом вы можете спросить у векторной
  57:34
  базы данных, какая песня про любовь, и там происходит либо топка похожих результатов, либо там берётся там
  57:39
  расстояние косинусов, смотрится как как какой вектор ближе. И уже по смыслу вы можете выгребать
  57:46
  то, что вам нужно. Хорошо.
  57:51
  Значит, нам остался больнючий индекс. Нам остался больнючий индекс, а именно
  57:58
  геоиндекс. А именно геоиндекс. Значит, приготовьтесь. Для этого мы возьмём R3.
  58:05
  R3, да? То есть есть пост. Постгиз используется как раз-таки R3. Значит,
  58:10
  что такое R3? Почему мы не можем использовать наши обычные индексы?
  58:15
  Допустим, мы возьмём наш обычный какой-нибудь B3 композитный индекс, и мы хотим найти
  58:21
  вот здесь у меня Y, вот здесь у меня X, вот здесь у меня Y, и я хочу найти, например, вот эти все кафешки между X и
  58:28
  Y. Как у меня композитный индекс построится? Он отсортирует сначала по X, потом отсортирует по Y. Что мы получим?
  58:35
  Мы получим 0,1 0, 03, 0,4, там 0,5, 11,
  58:42
  1 2 13 и бла-бла-бла-бла-бла-бла-бла-бла. Но мы понимаем, что ближайшие кафешки
  58:49
  это те, у которых там 44, 55, 66, 45.
  58:55
  Но если мы построим вот такой обычный индекс, он как бы не понимает связь между этими двумя переменными. Но он просто их отсортирует по одному, потом
  59:01
  по-другому, да? И нам придётся условно делать перебор и потом каждый или там каждый с каждым мерить расстояние, да,
  59:07
  обычноя, а которое √ квадрат.
  59:13
  Нехорошо. Или это не обязательно локация, это может быть, например, рост, вес, да, зависимость. И мы хотим там
  59:20
  найти оптимальный рост вес, когда у меня есть зависимость от нескольких переменных. Плюс это может быть не две
  59:25
  переменные, это может быть трёхмерное пространство, да, там какой-нибудь болид формула 1 и там насколько шины и стёрты,
  59:31
  там какая максимальная скорость, ещё что-то, там, какие-то параметры мы хотим найти в пересечении.
  59:36
  Вот для таких задач у нас есть R3. Значит, что такое R3? R3 — это
  59:46
  условно B3, который понимает геометрию. Что имеется в виду? Что имеется в виду,
  59:53
  когда я хочу найти, например, какой-нибудь R12, да, я себе рисую
  59:58
  диапазон и говорю: «Это диапазон куда попал? В верхней иерархии в R1 или в R2?» Допустим, он попал в оба. Тогда иду
  1:00:04
  там в левое подерево, в правое поддере, потом смотрю в этом поддере куда попал? В R3, R4, R5. Он там попал в R4, иду,
  1:00:10
  достаю R12. Вот. Но у нас могут быть нахлёсты. У нас могут быть нахлёсты, да.
  1:00:17
  И наша задача, задача R3- минимизировать эти нахлёсты. Потому что каждый раз, когда у нас происходит нахлёст, нам
  1:00:23
  приходится перебирать типа лишнее под дерево, которое в котором наших значений нет. Если смотреть на карте, то это
  1:00:30
  будет выглядеть вот так. Например, я хочу найти все кафешки, которые там все достопримечательности, которые находятся
  1:00:35
  вот здесь. Я вот так рисую квадрат. Как это произойдёт? Смотрится, вот этот квадрат, который я нарисовал, он куда
  1:00:41
  попадает? В бокс 2 или в бокс 3? Он попадает в бокс 2. Хорошо. Теперь этот
  1:00:46
  квадрат куда попадает? Бокс 4, бокс 5. Он попадает в бокс 4. И я говорю:
  1:00:52
  «О’кей, ты, значит, Бруклин Бриш, иди сходи». Либо если это визуализировать, это будет выглядеть вот так.
  1:01:00
  Я ещё вот этот диапазон. И вот каждый раз я смотрю, о’кей, это в четвёртом, а это я потом бью на два. Где? В седьмом
  1:01:07
  или в восьмом? О’кей, в седьмом. 13, 14, 15. О’кей, где 13 и в 14.
  1:01:16
  Чуть-чуть, конечно, необычно на это перестроиться.
  1:01:22
  Значит, основная проблема в том, что как им пользоваться. Пользоваться вы с точки
  1:01:28
  зрения пользователя вы, в принципе, просто его накинете, да, и у вас начнёт всё работать великолепно. Но как это
  1:01:34
  строится? Это строится супер специфично, честно. Это строится суперспецифично.
  1:01:42
  Давайте я перезагружу страничку. Что-то с ней не то стало. Строится супер специфично. Значит, R3 строится таким
  1:01:50
  образом, что мы стараемся
  1:01:56
  Так, где этот йпер? Ага, вот R3. Вот тут есть правило, как
  1:02:03
  построить R3. Если кому-то интересно, можете посмотреть, можете попробовать реализовать. Здесь прямо пошагово каждый
  1:02:08
  раз, что делать, как инициализировать, как с чем проверять, как там искать, как строить пересечение. Вот. Но мы, по
  1:02:14
  сути, стараемся минимизировать вот эту метрику. То есть когда мы добавляем
  1:02:20
  новую ноду, что мы стараемся делать? Мы стараемся минимизировать площадь вот
  1:02:25
  этой коробки, которая покроет эти ноды. И при этом стараемся ещё, чтобы она минимально пересекалась с другими
  1:02:30
  коробками, да? То есть, например, вот сейчас смотрим, у нас сейчас одна коробка. Я добавляю ещё точку. ещё
  1:02:36
  точку. Построилось две коробки. Теперь R0 R1 R2 теперь, когда я добавлю вот
  1:02:43
  сюда точку, оно будет мерить. А что лучше с ней сделать? Её лучше при прибить к этой коробке или к этой
  1:02:49
  коробке? Какая минимизирует площадь? Если никакая анимизирует площадь, он попробует: «А может быть, тогда из этих
  1:02:54
  двух мне новую коробку составить?» Тогда, может, лучше будет, а здесь новую коробку оттечь, либо верхнюю коробку
  1:03:00
  разбить, потому что ещё помним, что это работает как B3. Оно ещё старается его балансить, чтобы типа всё было
  1:03:05
  равномерно по дереву раскидано, чтобы мы получили свою асимптотику поиска. И теперь вот я добавляю сюда точку, она к
  1:03:12
  этому дереву. Добавляю сюда точку, к этой коробке, добавляю сюда точку, разбилась на три коробки. Добавляю сюда
  1:03:18
  точку к этой коробке, к этой коробке, разбилась ещё на коробке. То есть он старается поддерживать высоту дерева и
  1:03:25
  при этом минимизировать вот эту площадь покрытия. Вот супер специфичная структура данных,
  1:03:30
  потому что она построена на геометрии. Я много скидывал в Telegram-канал блокпостов интересных, где это может
  1:03:36
  применяться. Это применяется даже в геймдеве, где вы смотрите там, что какую часть вам сейчас надо
  1:03:42
  отрендерить, что вам нужно показать. Плюс оно применяется в нрных пространствах, как я до этого говорил.
  1:03:47
  То есть это можно посмотреть на Википедии, что это не обязательно вот такая двумер
  1:03:53
  двумерная плоскость, что это может быть ещё и трёхмерное пространство, и там вы кубы вы такие строите. Вот. Ну, в общем,
  1:04:01
  супер необычная структура данных. Про неё написаны целые книги. Плюс ещё есть различные вариации R3, R +3, R звёздочка
  1:04:08

Вот. Но думаю, для собеседования вам этого будет достаточно.
1:04:15
Хорошо. Хорошо. Значит, смотрите,
1:04:22
мы с вами посмотрели на сторж, посмотрели на индексы. Мы вообще много
1:04:28
на что с вами уже успели посмотреть, да? То есть, если мы смотрим вот эту картинку, то мы на вот это посмотрели,
1:04:36
да, там мы на вот это чуть-чуть посмотрели. Что нам осталось? Нам осталось вот этот большой кусок, вот эти большие куски, вот эти большие куски.
1:04:43
Но, но, но, но, но помните, в самом начале в презентации мы смотрели и вот
1:04:49
здесь часто мелькалам. Вот тут построено на LSM. Вот здесь это
1:04:55
построено на LSM. Если вы возьмёте, например, самый популярный сторож LSM
1:05:01
какой-нибудь Rox DB, вы увидите, что много чего построено на LSM. Много чего
1:05:06
построено на LSM, да? Что имеется в виду? Например, вы открываете CROCH,
1:05:12
находите вот здесь storage модель.
1:05:18
Вот. И оно построено на Kvalue на LSM. Хм.
1:05:24
Div from Rox DB. А что такое LSM? LSM — это вообще другой подход к стореджу.
1:05:31
Вообще другой подход к стореджу. Значит, какая у меня была проблема
1:05:37
с деревом с B +3, что когда мы добавляли,
1:05:43
мне приходилось иногда лочить и перестраивать дерево. Так, перестраивать дерево, ребалансировать, перестраивать,
1:05:48
ребалансировать, сплитить. Вот LSM как бы призвана
1:05:54
решить эту проблему и поддерживать вхвиad.
1:05:59
Как она это делает? Как она это делает? Давайте я сейчас открою текстовый редактор.
1:06:07
Ага. И давайте посмотрим на Rocksdb.
1:06:13
Ага. Значит, это их официальный репозиторий. Facebook RDB
1:06:19
storage engine server work storage focus fast storage. Хорошо, хорошо, хорошо, хорошо. Так и смотрим на вот эту
1:06:28
структуру. Как это устроено? Как это устроено? Значит, это устроено довольно специфично. Довольно специфично, когда у
1:06:35
нас идут записи. Когда у нас идут записи, записи добавляются в MМ Table.
1:06:41
Как только MМ переполняется, оно скидывается вниз в SST файл. Потом эти
1:06:46
СT файлы друг с другом компакт subджатся, да? Строится новый слой СТ файлов. Они компакт subмертся. Новый
1:06:51
слой СТ файлов, новый слой SST файлов. При этом мы ведём в WR head log. И у нас
1:06:57
есть какой-то манифест log. Тут пока ничего непонятно. Тут пока ничего непонятно.
1:07:03
Но вот что имеется в виду. Вот что имеется в виду.
1:07:08
Допустим, мы сейчас возьмём, что мы в памяти будем хранить структуру данных,
1:07:13
которая называется. Мы называем mem table, но это структура данных. Это может быть красно-чёрное дерево, может
1:07:19
бытьлист, может быть тот же самый наш B3, который мы видели. Хорошо. И у нас есть на диске
1:07:28
уже конкретно наши уровни.
1:07:35
И мы увидим вот что происходит у нас. Вот что у нас происходит. Смотрите,
1:07:40
когда мы добавляем новую запись, значит, это квсто, то есть хранить ключ значения, но вас это не должно в
1:07:47
заблуждение вводить. Вы можете хранить, например, ключ какой-нибудь прай один, а значение — это может быть там
1:07:53
закодированный вообще весь тупол, вся запись. Значит, вы
1:07:58
добавляете первичные значения. Значит, m table её одно свойство, что оно держит
1:08:03
их отсортированными. Это структура данных, которая нам держит данные отсортированными. Order set. При этом
1:08:11
каждый из вот этих SST, это sorted string table. Он тоже их
1:08:16
держит отсортированными. Мы сейчас увидим, зачем нам это нужно. Давайте добавлять A2, а, B3, C4,
1:08:25
D5, Е6.
1:08:30
Хорошо, мы добавили пять записей. Здесь места нет. Что мы делаем? Мы берём их, флюшим на диск. Флюшим на диск. О’кей.
1:08:39
Теперь здесь опять есть место. Давайте сделаем что-нибудь интереснее. Типа там А теперь стало три, а C стало deleted
1:08:51
и H стало 5. Hi, J стало 3 и
1:08:59
M стало 2. Опять переполнилось. Её мы тоже флюшим на диск.
1:09:06
И тут уже поднялась типа там. Теперь мы опять можем писать здесь опять свободно. Значит, фишка в том, фишка в том, почему
1:09:12
мы хорошо поддерживаем WR heavy workload здесь, потому что мы пишем сразу в m table.
1:09:19
Как только она переполнитсь, мы её скидываем на диск, опять пишем table. Как только она переполнитсь, скидывали на диск, опять пишем able. То есть
1:09:25
никакой вот здесь там перебалансировки, там ещё что-нибудь не происходит. Мы
1:09:31
пишем, пишем, пишем. Раз скинули. Пишем, пишем, пишем. Разкинули, пишем, пишем, пишем. Раз скинули.
1:09:38
Теперь, что у нас происходит в этот момент на диске, да? То есть то, что записи у нас
1:09:45
классные стали, это мы с вами поняли. А что у нас с чтением? Что у нас с чтением? Вот это проблема. Допустим, у
1:09:52
меня бы ещё добавилось здесь А10, B13. Да? Теперь, если кто-то бы пришёл и сказал: «Я хочу прочитать А». Мы бы
1:09:58
сначала проверили в мемблее данные, мы бы сказали: «А10, всё, уходи».
1:10:04
Хорошо. Но если кто-то придёт за D или кто-то придёт за C, что ему отдать?
1:10:10
Тогда придётся идти на диск. О’кей, уже пунктик мы с вами запомнили. А на диске
1:10:16
у нас условно, да, несколько таких файлов. А ещё есть какие-то уровни. Зачем нам эти
1:10:22
уровни? Смотрите, здесь мы ставим тоже ограничение. Здесь мы ставим, например, что мы поддерживаем
1:10:28
только там, э, не знаю, два файла определённой длины. Когда они заполнились,
1:10:35
что нам нужно сделать? Нам нужно их смерть, скомпактить и слить на уровень ниже. Благодаря тому, что они
1:10:42
отсортированные, мержити и компактить нам их гораздо легче. То есть вы можете увидеть такую задачу, например, на
1:10:49
лидкоде, да, merka sorted linked list или там merch sorted, как это сделать
1:10:55
правильно? То есть от того, что они отсортированы, нам это сделать гораздо проще. Даже если их там у нас может быть
1:11:01
несколько этих тата табличек, к табличек, нам всё равно это сделать проще, да? То есть мы используем
1:11:06
какую-нибуд там минхипу, либо когда их две, ставим там два указателя, просто выбираем, какой из них меньше. Один двигаем, другой не двигаем. Это
1:11:13
специфика, можете посмотреть где-нибудь, либо у меня там на курс по алгоритму. Теперь нам нужно их слить вместе.
1:11:20
Как мы их будем сливать? У каждой этой записи есть таймстп, когда она добавилась. Мы смотрим в одной А2, в
1:11:27
одной А3. Какая свежее? Свежее А3. Значит, сюда пойдёт А3. У одной B3, у
1:11:33
другой B вообще нету. Пойдёт B3. У одной C4, у другой C удалено вообще. Значит,
1:11:39
какое пойдёт? C вообще сюда не прорастёт теперь. У одной D5, у другой D вообще
1:11:46
нет. У одной E6 нету. И вот это сюда вот так пойдёт.
1:11:51
Хорошо. Отсюда что мы ещё видим? Отсюда мы видим, что они растут от уровня к уровню. То есть здесь уже SST файл
1:11:58
условно больше размером, да? Потом понятно, это отсюда можно удалять, это можно удалять, добавится ещё, они
1:12:06
заполнятся, мы их сольём вот сюда вниз, появится здесь второй файл, да, тут тоже
1:12:12
какое-то ограничение на уровень, когда его нужно сливать. Мы их сольём, скинем на уровень ниже, скинем на уровень ниже.
1:12:17
Скинем на уровне ниже. Хорошо. При этом все файлы у нас иммутабельные. Что это
1:12:24
значит? Вот мы их слили, да, мы их никак на месте не модифицируем. То есть там, когда что-то обновляется, удаляется, мы
1:12:30
ничего не делаем. Мы их слили друг с другом на нижний уровень. Эти файлы можно, например, всё сносить. Либо,
1:12:36
либо, либо, как вот делает неон, про который мы в начале лекции с вами поговорили,
1:12:41
что благодаря тому, что они иммутабельные, мы их можем где-то у себя как-то архивировать, какую-то историю
1:12:47
хранить, и мы можем конкретно как снапшоту, к определённой точке, как к определённым ССТ файлам, вот так бам и
1:12:54
вернуться. То есть вы можете как-то их версионировать и потом с одного в другое конкретно возвращаться, вот где вы
1:13:00
сейчас находитесь. То есть LSM log oriented storage, да, LSM storage —
1:13:07
это вообще другой подход, как вы храните данные. То есть вы их не храните так, как мы в начале обсуждали, с пейджами,
1:13:14
да, или ещё с чем-нибудь. Нет, вы храните их в мембле, потом скидываете на диск. У ССТ файлов тоже своя структура,
1:13:22
у них там есть там свой формат, свой заголовок, но пока что примерно можете представить, что это просто ключ значения, ключ значения, ключ значения,
1:13:28
ключ значения, ключ значения. Найс, найс, найс, найс, найс. Значит,
1:13:36
где у нас проблема? Проблема, что читать эти SST файлы дорого. Читать эти
1:13:46
SST-файлы дорого. Например, когда я хочу найти А2,
1:13:52
А2, что придётся делать? Придётся читать
1:13:57
этот SST файл, да? Этот SST файл. Или тут, если их нет, придётся читать файл ниже, например, и там искать А2.
1:14:05
Проблемка, проблемка, проблемка, проблемка. Понятно, можем это распараллелить, параллельно искать в этих файлах. Проблемка. Значит, какие
1:14:11
для этого есть решения? Одно решение — это подход, который
1:14:16
называется leveling. Значит, в одном подходе, что вы делаете? Вы в сT файле
1:14:22
на нижних уровнях начинаете хранить рейджи. То есть, например, вы точно знаете, что вот этот файл — это реange
1:14:29
от A до C. Этот файл от D до E, нет, до F, до G, например. А когда они сольются,
1:14:36
вот здесь, например, будет от A до G. О’кей. Это уже вам упрощает поиск. То
1:14:42
есть вы теперь знаете, что если мой ключ в этом рендже, то он должен быть где-то
1:14:47
в этих файлах. Другая оптимизация, это другой вариант, то есть это называется левелинг. Есть
1:14:54
ещё тайринг — это когда вы не смотрите на это, не обращаете на это внимание на Kнжи, а сливаете вот как как есть, так и
1:15:00
сливаете. Значит, чем один вариант лучше, чем другой. В одном вам нужно менеджить вот эти KNG, чтобы они
1:15:06
сохранялись, а в другом вы сливаете, как вам далось. Хорошо, вроде KG чуть-чуть помогли, но
1:15:13
есть ещё одна гениальная идея, которую мы можем увидеть вот здесь. Это использовать Bloomilльтр. Использовать
1:15:20
Bloom фильтр. Значит, что такое? Что такое BLomфильтр? Что такое
1:15:27
BLфильтр? Смотрите, у меня есть мы берём и делаем условно 20 битов, да, маску. Мы
1:15:35
делаем 20 битов с вами маску и говорим, что вот у нас есть там, не знаю,
1:15:43
пять хэш-функций. То есть получается у меня 100 битов. И теперь каждая хэш-функция мапит моё значение.
1:15:48
Например, аа если у меня ke — это какой-нибудь там, не знаю, Влад, да,
1:15:54
или что это может быть? Ну, давайте 10. Он говорит 10 мапится вот вот эти
1:16:01
значения. Вот сюда, вот сюда, вот сюда, вот сюда. Теперь 13 мапится вот сюда,
1:16:09
15 мапится вот сюда. И теперь, значит, на этот файл, когда он строится файл, мы
1:16:16
на него создаём вот такой bloom фильтр. На него создаём BL фильтр. И что мы
1:16:22
благодаря ему можем сделать? Мы можем сразу сказать: «А здесь вообще есть
1:16:27
семь?» И он нам скажет: «Се здесь нет». Почему?
1:16:32
Потому что семь подсветят определённые биты, который в этой маске нет. А если
1:16:38
бы это число семь здесь было, то этот бит бы подсветился точно, да? То есть,
1:16:44
когда мы ищем 10, он нам подсветил биты, где есть 10. Но
1:16:51
и теперь мы знаем, что 10 здесь, наверное, есть. Почему я говорю, наверное? Почему я говорю наверное?
1:16:57
Потому что потому что в хэшфункции у вас могут быть коллизии. И что у вас может быть? У вас могут эту ячейку одну и ту
1:17:04
же подсветить несколько значений, да? То есть самого
1:17:11
10, например, там нет. Самого 10 там, например, нет. Вот.
1:17:19
О’кей. Не, вот смотрите, самого 13 здесь нет,
1:17:26
но ячейки, где на которой мапится 13, подсвечены.
1:17:33
Почему так произошло? Потому что просто пересечение нескольких значений
1:17:38
замапилось в коэш функцию на эти же ячейки. И нам кажется по блумфильтру как будто
1:17:44
оно там есть, но его на самом деле там нет. Его на самом деле там нет. То есть,
1:17:50
то есть Blomфильтр нам вот что говорит. Если нам BLМФтер, то есть сейчас прозвучит как цитата из пацанского
1:17:56
паблика. Если нам блумфильтр сказал, что есть, то там его может и не
1:18:04
быть. Почему? Потому что просто у вас произошло пересечение.
1:18:12
А, например, давайте ещё раз этот момент подсвечу, потому что он важен. Например, X у меня мапится в 01, да? G у меня
1:18:20
мапится в 1 и Z у меня мапится в 1, нет, в 0 0 1 1.
1:18:30
Вот до этого в BLМФILр мы добавили G и Z. Какой у меня получится бумфильтр? Он
1:18:35
получится 1011. Придёт X со своим 1001, скажет, что там
1:18:41
мои биты подсвечены. Ему скажут: «Да, братан, подсвечены твои биты». Но самого X там нет. Это просто G и Z дали такое
1:18:47
пересечение, понимаете? И поэтому, если блумфильттер сказал, что есть, то там его может не быть. Но если
1:18:55
Блумфильтер, если Блумфильттер сказал, что его там нет, то там точно нет. Там точно нет.
1:19:06
Почему? Потому что если бы оно там было, его биты бы подсветились. Мы только
1:19:11
зажигаем их. Но если они вообще не горят, да, то там ни пересечения, никак
1:19:17
вообще там его нет. Найс. При этом, при этом мы помним, что каждый
1:19:24
этот файл иммутабельный у нас. Каждый этот файл иммутабельный.
1:19:29
Что это нам даёт? Это нам даёт то, что никогда из Блумфильтра никто удаляться не будет. Как мы его вот сюда повесили,
1:19:35
он так у нас и будет висеть. Блумфильтр сам менять не надо, потому что если какое-то значение удалится, тогда
1:19:41
появляются проблемы. Нам надо смотреть, а кто эти ячейки поджёг, типа мне их нужно теперь вычищать, мне их не нужно
1:19:46
вычищать. вдруг они на другом пересечении нам попались. Но поскольку файлы мутабельные, теперь Bloomfieldр
1:19:52
нам точно говорит, что может быть здесь есть, но когда нет, он то он точно
1:19:57
говорит нет. И теперь, когда вы хотите найти определённый ключ, вы можете сходить в BLфильтр параллельно, и он вам
1:20:04
скажет: «Слушай, вот эти файлы сказали, что может в них есть, иди посмотри». И ты идёшь, бам, и смотришь, и твой поиск
1:20:12
ускорился. Пушка. Сказка.
1:20:21
А вот здесь есть вот такой веб-сайт, который называется Compction. А у них ещё есть
1:20:28
и доклад вроде на Ютбе есть, который можете посмотреть. Здесь различные виды того, когда мы решаем, а когда нам
1:20:36
сливать вот эти таблички, там до какого размера их расти. Плюс эти параметры можно тюнить либо использовать другие
1:20:41
стратегии того, как ты их компактишь. Да, при этом у вас могут быть стратегии,
1:20:47
что там несколько уровней — это level, несколько уровней — это тар, да? То есть вот так разделено здесь.
1:20:55
Ну там помните, да, что это пересекаешься, не пересекаешься RNG. Давайте посмотрим на ванилу. То есть,
1:21:02
грубо говоря, LSM будет выглядеть вот так вот. Вы набиваете один файл, набиваете второй файл, набиваете третий
1:21:08
файл, набираете четвёртый файл, бам, флюшнули их. Их их слили, флюшнули.
1:21:14
Дальше набиваете ещё четыре флюшны. Набиваете ещё четыре флюшнули. Набиваете
1:21:20
вот набиваете последний четвёртый. Теперь он смертся с добавится вот сюда. Они все смертся и добавятся на уровень
1:21:26
ниже. Флюшнули, добавили. Флюшнули. Смерли. Смерли. Смерли, смерли. Смерли.
1:21:34
Смерли. Смерли. Смерли. Смерли. Смерли. При этом вот здесь можно смотреть, например, а как нам различные
1:21:42
стратегии того, когда мы когда мы компактим и там как мы менеджем наши
1:21:48
ренжи, какой нам даст перформанance там в плане потребления, в плане IO, там как часто мы будем на диск ходить. Вот.
1:21:55
Супер интересно поиграться. Советую просто открыть, посмотреть, доклады посмотреть. То есть здесь можно менять
1:22:01
потом параметры. Как вы видите, здесь есть интересные параметры типа буфер и есть page sizй.
1:22:08
Entry size. Так, page size. Что имеется в виду page size? Я вроде говорил, никакого нет здесь slotted pages. И вот
1:22:13
как мы до этого увидели, slotted pages здесь нет. Но, но, но каждый SST файл,
1:22:20
каждый сам вот этот SST файл бьётся на логические блоки PG. Вот. И потом там
1:22:27
есть блок кэш, который тоже их умеет затягивать типа в память.
1:22:34
Фух. Вопрос возникает, когда мы пишем Mem ttable, у нас может выключиться
1:22:40
электричество. Что делать? Что эти данные пропали? Нет, эти данные не пропали, потому что мы делаем write
1:22:46
ahead. То есть перед тем, как писать мем таблицу, мы пишем WR headlog и говорим:
1:22:51
«Вот такие вот такие изменения делаю. Вот такие вот такие ключе добавляю. Такие вот такие ключи добавляю». Плюс у нас есть манифест log, который вообще
1:22:57
трекает, что там, какое состояние, у каких SST файлов.
1:23:05
Что мы не посмотрели, мы примерно представляем, как выглядят сT файлы, примерно понимаем, как выглядит merge.
1:23:11
Мы не понимаем, что это такое, что за table. А давайте посмотрим, что нам на это говорит Roxdb.
1:23:18
Что нам на это говорит Roxdb? А давайте я напишу вот сюда skip lister alert. И
1:23:24
мы смотрим default implementation of table robblist
1:23:30
skip list sorted set. Найс. При этом, если мы пойдём на Википедию, мы увидим, что этот скиплист
1:23:37
используется в дискорде.
1:23:43
Хмм, интереснее ещё стало. Зачем в дискорде скиплист? Что за скиплист такой? Значит, приготовьтесь, потому что
1:23:52
skipлист — это супер необычная структура данных. Представим, у нас есть обычный linked list. Я в него добавляю один,
1:24:00
я в него добавляю два. Я в него добавляю 10.
1:24:06
Я в него добавляю 11. О’кей, всё понятно. Теперь, чтобы
1:24:13
добавить там семь, нужно будет дойти до туда, где надо добавить семь. Там бамбамба, сюда вставить.
1:24:20
О’кей, хорошо. Пока порядок держит сортировано, но какие-то, конечно, вставки дорогие, да,
1:24:27
поиск получается линейный, поэтому придумали вот такую хитрую оптимизацию, которая называется skipлиist. Значит,
1:24:33
skipлиist — это вероятностная структура данных, которая нам даёт сложность log и использует подход, похожий, как работает
1:24:41
Binary Search 3. Смотрите, я сюда добавлю пять и вот сюда поставлю параметр 1. Этот параметр здесь я задаю
1:24:49
руками в учебных целях, но вообще он выбирается рандомно. И смотрите, что он сделает.
1:24:57
Ты что вообще? Это что такое было? Он прорастил значение пятёрки наверх на
1:25:07
несколько этажей. Да, тут, к сожалению, сейчас этажи пересеклись.
1:25:12
Ой, что я сделал? Ах, как жалко.
1:25:18
Ну, давайте ещё поднаправляем. Как жаль, как жаль, как жаль.
1:25:40
Да. И давайте, я бы хотел, чтобы у меня,
1:25:48
например, семь вот здесь не был, а семь у меня прямо хорошо пророс.
1:25:57
Во, неплохо. Значит, каждый раз, когда добавляется значение, оно ещё прорастает
1:26:03
наверх на несколько этажей. И вот этот момент, на сколько этажей она прорастёт наверх, сдаётся нам рандомно. Но что нам
1:26:11
теперь это даёт? Теперь, когда я хочу вставить, например, де
1:26:16
сделать? Я иду по верхнему этажу и смотрю, а девять где? Вот я дошёл до
1:26:21
семи. Я такой: «О’кей, 9 больше семи, значит, это в правой части вот этого линкетлиста». Оно меньше 12, значит, оно
1:26:28
где-то между 7 и 12. Я отсюда опускаюсь вниз. Теперь есть ссылка вниз, на следующий этаж. Я смотрю,
1:26:36
а де больше семи, больше, а больше восьми, больше. О’кей. Значит, оно где-то вот здесь уже находится.
1:26:42
Опускаясь отсюда вниз и вставляю нашу девятку.
1:26:49
И благодаря рандому у нас посчитано так, что у нас ноды будут прорастать наверх,
1:26:56
да, и они прорастут таким образом, что в среднем мы получаем log n. В среднем мы получаем log n. То есть он у нас так
1:27:04
разрядится, что смотрите, получается логика такая же, как у нас в
1:27:09
Binary Search 3. То есть это как указатели. Мы такие: «О’кей, больше семи, меньше семи. Если больше, то мы
1:27:14
точно знаем, что во второй половине этого линкетлиста там справа надо проверять». При этом можем опуститься вниз, там будут какие-то новые,
1:27:21
например, указатели. Мы по ним можем понять. А вот здесь уже будет храниться там наши значения Kvalue, которые мы
1:27:28
возьмём, они у нас в отсортированном виде. Бам! Флюшнем на диск.
1:27:33
Пушка. Супер необычная структура данных. Я понимаю, супер необычная структура данных, но
1:27:41
что есть, то есть. Что есть, то есть.
1:27:47
Есть, э, задача на лидкоде
1:27:52
Skip list. Есть задача на литкоде. Дизайн Skipлиist. Я вам рекомендую её
1:27:57
порешать. Рекомендую её порешать. вообще просто для себя разобраться со скиплистом, что здесь происходит. Вот
1:28:04
очень необычная структура данных, супер интересная, да, шанс, что вы ещё где-то её встретите, конечно, маловат, но для
1:28:10
себя разобраться будет прикольно. Хорошо. Значит, мы посмотрели с вами ещё и на
1:28:18
альтернативный подход, как можно менеджить свой storage, это LSM Storage. То есть
1:28:25
сейчас уже не так очевидно, потому что у нас есть вот эти вариации B3 с буферами, да,
1:28:31
но примерно на вот этой на вот этом примерно вы должны почувствовать, почему
1:28:37
для там heavy, WR intensive или почему для распределения вы используете LSM
1:28:42
storage. Во-первых, вам у вас тут типа kевалю значения. Вы можете ренжи легче
1:28:47
дробить или легче это там куда-нибудь зашардировать. Потом, э,
1:28:53
вы на запись не тратите время, вы просто флюшите. Это у вас там внизу компакт
1:28:58
происходит. При этом на чтение, конечно, вы теряете. Вот Rocks DB реализация LSM
1:29:04
Stage, который мне где используется. При этом я опять же вам рекомендую вернуться к тому репозиторию, про который я уже
1:29:10
часто говорил. Talлентплан. Talлентплан. А таки кв, где вы будете строить свой
1:29:17
сторедж поверх ээ lsmстоджа. Там не использовать баджер. Вот
1:29:24
посмотрите, посмотрите. Правда, будет интересно. Хорошо. Значит, в картине мира мы разобрались с
1:29:31
вот этим, разобрались с вот этим. Нам осталось вот это и вот это. Вот это тема
1:29:36
двух будущих лекций. А с вот этим можно, в принципе, и разобраться сейчас. Смотрите. Но вот это люди карьеры и
1:29:44
научные труды тратят, да, вот это миллионы долларов. Потому что если вы делаете вот это хорошо, то, ну, у вас
1:29:51
получаете перфоманс бур-бур, и это миллионы долларов. К сожалению, я вам не смогу сейчас рассказать на миллион
1:29:57
долларов, но расскажу, расскажу, как знаю. Значит, смотрите, когда к вам приходит запрос, да, вы пишете свой
1:30:03
стандартный SQL, там select from, бла-бла-бла-бла-бла-бла-бла, бла-бла-бла-бла-бла. А, да, вам не видно
1:30:09
слайд. Здесь написано статистика о данных. Статистика о данных. Значит,
1:30:15
select from blint bl. Вот вот пришёл вам запрос. Сначала он попадает в
1:30:20
parcerсертator. Что происходит? Он просто как условно когда вы пишете свой
1:30:26
программистский код, да, он у вас парсится и проверяется вообще валидна эта конструкция. Ну, то есть этот код в
1:30:32
принципе валиден. То, что вы написали, это валидный SQL или невалидный SQL. После того, как он поймёт, что это
1:30:38
валидный SQL, он построит из вашего запроса выражение реляционной алгебры. Что имеется в виду?
1:30:45
Имеются в виду вот такие вот э каракули, да? Сейчас мы их разберём. После этого
1:30:50
он построит вам несколько эквивалентных выражений, пойдёт в статистику о данных,
1:30:56
там где, в какой реляции, сколько туплов, там, ээ, где какой индекс навешен, там насколько это прогрето,
1:31:03
насколько это не прогрето. В общем, максимально о ваших данных соберёт соберёт информации, пропустит через
1:31:09
оптимайзеры, выберет план, который для вас будет самый оптимальный. Потом этот план выполнится на ваших
1:31:15
данных, и вы получите, соответственно, свой результат, да? То есть план, например, вашего запроса вы можете
1:31:21
посмотреть через Explain Analy. Через Explain Analyse, потом вставить какой-нибудь вот такой
1:31:26
веб-сайт, и он вам нарисует, что с вашим планом. И, например, там, что было самое дорогое в вашем плане, где там дольше
1:31:33
всего, больше i операции. Тут вы увидите, что, например, секскан, и, может быть, вы поймёте, что на этот
1:31:39
запрос может попробовать какой-нибудь индекс накинуть, чтобы не делать сексскан, да, или там как-то прогреть
1:31:44
по-другому за запрос перестроить. Вот. Но оптимизатор запросов попытается
1:31:52
оптимизировать за вас и построить запрос оптимальным образом. Например, смотрите,
1:31:58
вот вот этот момент, когда он строит выражение реляционной алгебры.
1:32:04
Вот каждый вот этот значок, он что-то значит. Он что-то значит. Спасибо, капитан. Очевидности. Каждый этот значок
1:32:10
что-то значит. Золотые цитаты Влате, запишите. Значит, вот этот значок, да, это проекция. Что это значит? Это значит
1:32:17
курс IDLE и курс. Если переводить на SQL, это select курс
1:32:24
курс ID title from Вот так вот то, что мы выбираем курс ID
1:32:31
title. Вот этот значок — это joint teaches. Вот этот значок — это joints instructor. Вот этот значок de name
1:32:38
равно music. Это типа select по условию. То есть выглядит select звёздочка from
1:32:44
откуда? Ну вот от из этого выражения, которое у вас получилось вере ver вере.
1:32:51
Вот name равно music where deep name равно
1:32:57
music. Вот вот это веря. Вот это вот вот этот значок. Вот этот значок. Хорошо.
1:33:04
Что мы отсюда понимаем? Значит, у нас выгребаются все курсы. Они джойнтся, стичатся, чтобы посмотреть, там
1:33:10
какая-то, скорее всего, маппингтаблица, где мы смотрим, какой преподаватель что преподаёт, какой курс. Мы мапим, джойним
1:33:16
с ним, потом джойним с преподавателями, и нам нужны только преподаватели, которые в департаменте музыки работают.
1:33:23
Значит, оптимизатор смотрит на это выражение не такое. А зачем мне джойнить со всеми преподавателями,
1:33:30
если я могу заджойнить только с теми, кто преподаёт музыку, потому что я их всё равно там сверху их отфильтрую?
1:33:36
Давай я сразу отфильтрую тех, кто работает в музыке, а потом начну джойнить. И вот эти,
1:33:42
например, операции я могу сделать теперь параллельно. Он перестраивает этот запрос,
1:33:48
перестраивает это дерево и получает там и выдаёт вам оптимальный запрос. Как он
1:33:53
понял, что я могу безболезненно вот это вот сюда типа опустить, и всё будет нормально, да? Там вот этот оператор
1:33:59
опустить вниз. Но он не просто так это понял, потому что у нас есть законы, по
1:34:04
которым в реляционной алгебре можем выражение типа перетаскивать, да? У нас есть закон эквивалентности, например,
1:34:10
например, смотрите, вот это сект по одному условию и по второму условию из
1:34:17
таблички то же самое, что сект по одному вложенный в селект по-другому. То есть,
1:34:23
если это переводить, а в SQL, если это переводить в SQL, то это будет
1:34:29
выглядеть вот так, типа вы делали select, а звёздочка from
1:34:37
select звёздочка from where condition 1 where condition 2.
1:34:44
Это то же самое. То же самое, что я сделал бы вот так.
1:34:49
Select звёздочка from X condition 1
1:34:57
и condition 2. То есть вот это то же самое, что вот
1:35:03
это. Я могу вот это превратить в вот это, например. Или от того, что я вот здесь conditionition 1, conditionition 2 поменяю местами, тоже ничего не
1:35:10
изменится, да? Это уже закон коммутативности. Вот, вот это здесь написано. Вот condition 1 и 2 то же
1:35:16
самое, что вот эта вложенность или то же самое, что я их местами поменяю. Следующий закон. Когда я делаю джоин по
1:35:22
какому-то условию, это то же самое вот этот джоин и вот этот джоин. Если мы джойним вот это потом с вот этим, это то
1:35:28
же самое, что джойнить вот это с вот этим. Либо вот то, что используется как раз-таки в нашем примере. Если я джойню,
1:35:35
а потом фильтрую по какому-то условию, это то же самое, что сначала отфильтровую по условию, а потом
1:35:40
заджойню. Либо вот это, вот это декартовое произведение. Это все попарно комбинации.
1:35:47
Взять все попарно комбинации, а потом из них выбрать по условию то же самое, что заджойнить по условию. Или вот здесь
1:35:55
заджойнить по условию два, а потом выбрать по условию один — это то же самое, что заджойнить сразу по условию 1
1:36:01
и 2. И вот с помощью вот таких операторов,
1:36:07
с помощью вот таких операторов, с помощью вот таких законов, да, там, ну, можете почитать в книге Паруса,
1:36:13
здесь их навал. С помощью вот таких законов и операторов мы можем превращать
1:36:19
одно дерево выражения в другое дерево выражение, в эквивалентное, да? эквивалентная, то есть это значит, она
1:36:24
несёт там такой же смысл, да? Мы ничего не потеряли, мы саму логику запроса не поменяли. Мы поменяли
1:36:31
дерево выражения, но как бы смысл запроса он не изменился, да? Мы не
1:36:37
сделали так, что ты там хотел фильтровать по музыке, а теперь ты не фильтруешь по музыке. Нет, мы всё сохранили, просто перестроили так, чтобы
1:36:44
было оптимальнее. [музыка]
1:36:49
На этом эта лекция закончена. Спасибо вам большое. Сердечно благодарен, что вы
1:36:55
со мной посидели, меня послушали. Значит, вот этот компонент и вот этот компонент мы обсудим на следующих
1:37:01
лекциях. Будут вопросы, пожалуйста, пишите комментарии. А что-то где-то вам
1:37:06
не понравилось, что-то где-то вы там увидели, пожалуйста, мне обязательно об этом сообщите. Но ещё раз, дисклеймер,
1:37:12
это всё делается в учебном формате, как бы мы как будто каждый раз что-то изобретаем. Вот. Спасибо большое.
1:37:21
Спасибо, спасибо за внимание, правда. Ценю, ценю вас. Удачи. Пока. Ну всё,
1:37:27
чал, не могу говорить пока. Домашка в описании.