второй способ даж и не знал. оч полезно
== Условная вероятность и формула Байеса. Задача про два кубика
https://youtu.be/0THgI47uqaA

Дедлоки (1/2)

Всех с наступившим! 🐌

Решил я тут почитать, что умные дядьки пишут про дедлоки. Как обычно оказалось, что поверхностное понимание уровня «пройти интервью» неверно от начала до конца, а в реальности всё супер интересно и конечно известно уже последние лет 50.

Дедлок или deadly embrace, как их называл товарищ Дейкстра (тот самый, который алгоритм) — ситуация бесконечного ожидания, при которой группа процессов не может продолжать работу, пока «внешние силы» не совершат определенные действия. Слово «процесс» здесь не имеет отношения к процессам в операционной системе. Процесс в дедлоке — некий автомат с набором состояний. Такими состояниями могут быть «процесс А не владеет ресурсами» или «процесс B владеет ресурсом alpha и пытается получить ресурс beta». На самом деле определение не совсем корректное в 100% ситуаций, но для обсуждения большинства подходов подойдёт.

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

Такой дедлок называется либо ресурсным, либо interleaved дедлоком. Первое более привычное и популярное название, второе я нашёл только в [4]. Для возможности его возникновения необходимо выполнение 3 условий:

1. Exclusive access. Только один процесс может захватить ресурс одновременно.
2. No-preemption. Процесс, захвативший ресурс, не может быть прерван.
3. Hold and wait condition. Должны разрешаться ситуация, при которой процесс захватил сначала один ресурс, а теперь ждёт пока освободится второй. Не отпуская при этом первый.

Наличие этих условий в системе ещё не гарантирует возникновение дедлока! Это только необходимые условия. Их наличие означает существование unsafe region[5] — такого набора состояний процессов, попав в которое, ни один из процессов не может завершить свою работу.

При наличии unsafe region достаточно найти лишь 1 набор состояний, чтобы обеспечить дедлок. Оно же последнее условие:

4. circular wait condition. Процессы и ресурсы должны иметь возможность собираться в «цепочку». К примеру: Процесс A владеет ресурсом a при этом хочет захватить ресурс b, которым владеет процесс B, который хочет завладеть ресурсом a. Если обозначить эти отношения стрелочками:

a -> A значит процесс A владеет ресурсом a.
A -> b значит процесс A хочет завладеть ресурсом b.

Схематично получится круг (ну или квадрат):

a  -> A
^     |
|     v
B <-  b

Дедлоки (2/2)

Первый инсайт: дедлоки не возникают просто так, для них необходимо 3 условия: exclusive access, no-preemption, hold-and-wait + одно достаточное: circular wait.

Второй инсайт: чтобы побороть дедлок, достаточно избавить от одного из условий!

Пункт 2 особенно интересен, и позволяет другими глазами взглянуть на работу с ресурсами и привычные «программистские трюки». Например: почему часто разделяют локи на read-only и write-only локи? Для перформанса, конечно. Но ещё и потому что в read-only локе не может возникнуть дедлок, так как он не эксклюзивный (первое условие)!

Или вот я недавно сделал нечаянно не concurrent индекс в postgres на табличку с парой сотен миллионов записей и всё встало колом. Решение проблемы — preemption! Руками грохаем транзакцию и дедлок перестаёт существовать. И это магистры компьютерных наук знали ещё в 70-ых. Подобные же механизмы можно и автоматизировать. Правда не так просто. С одной стороны, обнаружение дедлока — в сущности задача на графах, где просто нужно правильно пройтись по ребрам от процессов до ресурсов. С другой, граф постоянно меняется буквально пока по нему проходишься. Кажется решений проблемы в общем случае нет, но в частных, например только в БД, они есть и работают.

С hold-and-wait тоже интересно. А что если бы процесс сразу же запрашивал все ресурсы, которые ему требуются? Или по крайней мере захватывал бы их постепенно, но при успехе отпускал бы все уже захваченные. Такой подход, оказывается, тоже убирает проблему дедлоков. К сожалению, не каждый процесс знает наперёд ни все нужные ему ресурсы, ни порядок, в котором они будут захватываться. Опять в общем случае решить тяжело, в частном вполне. Например обычно заранее известно, сколько памяти и CPU нужной новой виртуалке/контейнеру, а это тоже ресурсы, за которые тоже может быть конкуренция. Там правда ситуация не обязательно завершиться дедлоком, а скорее перемещением одного из процессов, но это детали. Раскидывать задачи по компьютерам — очень сложная задача, поэтому в как-нибудь в следующий раз.

Наконец, circular-wait. А пусть все ресурсы должны захватывать только в определенном порядке. К примеру, перечислим все ресурсы в системе от 1 до n. И добавим условие: если процесс захватил ресурс 1 <= k <= n, он может захватить только любой другой ресурс с номером m, где m < k. Другими словами, процессу сначала нужно захватить самый «высокоуровневый» ресурс, а дальше все ресурсы пониже. Наличие нумерованных ресурсов и одного условия на их захватывание также позволяет избавиться от дедлоков. Полный пруф есть в [5].

Все эти подходы можно широкими мазками разделить на 3 категории:

- Detection. Подходы, которые по графу ресурсов и их зависимостей позволяют обнаружить дедлок. Для борьбы используется preemption.
- Prevention. Цель: задизайнить систему таким образом, чтобы дедлок был невозможен. Например: пронумеровать ресурсы и ввести условие их захвата. Или запретить захватить ресурс, а затем ждать второй.
- Avoidance. Подходы, при которых система переходит только из одного «безопасного» состояния в другое. Решение о выдаче ресурса принимается динамически, к примеру во время запроса. Самый популярный алгоритм: алгоритм банкира. К сожалению для него необходимо, чтобы процессы сразу знали, какие ресурсы им нужны.
- Алгоритм страуса. Или ничего не делать. Стратегия при которой программист сажается на on-call и ему выдаётся кнопка «отмена».

Ресурсы:
1. E.G. Coffman, M. Elphick, A. Shoshani. System Deadlocks.
2. Richard C. Holt. Some deadlock properties of computer systems.
3. S.S. Isloor, T.A. Marsland. The Deadlock Problem: An Overview.
4. Gertrude Neuman Levine. Defining deadlocks.
5. Charles M. Shub. A Unified Treatment of Deadlock.

как всегда пишут... оставайтесь на уровне 3 и не ИИте мозги

Нормальные формы баз данных

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

00:00 Введение
01:20 Что такое нормализация
02:08 Что такое избыточность данных с примерами
04:51 Какие бывают нормальные формы БД
08:00 Ненормализованная форма
09:37 Первая нормальная форма
11:24 Вторая нормальная форма
15:29 Что такое декомпозиция
16:18 Третья нормальная форма
18:54 Нормальная форма Бойса-Кодда
21:54 Четвертая нормальная форма
27:45 Почему обычно не нормализуют до 5 или 6 формы
29:14 Пятая нормальная форма
35:39 Шестая нормальная форма
38:02 Выводы и заключение

Смотреть это видео на youtube: youtu.be/zqQxWdTpSIA

== SQL/JSON в PostgreSQL: настоящее и будущее
https://youtu.be/CPoNZRpcHf4

нахер монгу. хоронить её пора) а все с ней пытаются сравнивать

== Топ ошибок со стороны разработки при работе с PostgreSQL
https://youtu.be/HjLnY0aPQZo
- планирование
- мониторингг

OLTP+OLAP = HTAP =)

foreign tables !!!

мониторить долгие транзакции. все что больше 20 мин надо автоматом резать ! таблицы начинают медленней работать

очереди можно строить на основе pgQ

автоматизация:
- SplitBrain
- Cascade Failover

про ошибки проектирования

== Как устроить хайлоад на ровном месте
https://youtu.be/jcCLqVQs5No?t=678
ошикби:
- неэффективное использование ресурсов
- база наружу
- разные сервисы на одной машине
- одна синхронная реплика ПОНИМАЖАЕТ надежность. Лучше одна синхронная и онда Асинхроннная с быстрым переключением
- неправильное тестирование
- пиковые нагрузки (по времени, по событиям, таймзонам)
- разумный отлуп роботов

Ошибки проектирования БД
- пагинация
- узкие таблицы (оверхед заголовков)
- широкеи таблицы (не более 50-100 колонок)
- NoSQL когда не надо
- json/xml когда не надо
- ненужная точность вычислений
- виртуализация для ДБ = ЗЛО

В индии ОДНА таймзона. нагрузка по времени в пике просто дичайшая!

F-sync через ядро ОС гостя, через фс ОС, дойти до ядра ОС, потом до ОС хоста, и тп...

== Транзисторный ключ, эмиттерный повторитель, пуш-пулл, полумост и мост. Самое подробное объяснение.
https://youtu.be/MgpT7ZICZSk

== Полнотекстовый поиск в PostgreSQL
https://youtu.be/5ZATiyvPQ-A
Индексы
- GIN - указатель (часто ищу)
- GIST - хэш дерево (редко ищу)
- RUM (extension)

Fuzzy search
- pg_trgm (extension)

прикольно, я думал что MIRO будут на редиске до конца жизни))) но...

== Отказоустойчивый кластер PostgreSQL + Patroni.
https://youtu.be/ZvLw9PU--_w

== Odyssey - масштабируемый пулер соединений для PostgreSQL
https://youtu.be/Wq7wQ9oyvSw
под каждый запрос постгрес делает FORK процесса !!! поэтому экономить подключения необходимо !!!

== Основы мониторинга PostgreSQL
https://youtu.be/Hbi2AFhd4nY

== PostgreSQL worst practices
https://youtu.be/HxwLCyCY8ec
- используйте индексы
- не используйте ОРМ
- юзайте джоины
- НЕ юзайте json поля
- не юзайте EAV (entity, attr, value)
- не ставьте индексы везде, только где надо и только где выигрыш по времени, меряй!
- не юзайте реплику как бэкап
- тестируйте бэкапы
- НЕ выключайте автовакуум
- архивируйте старые данные !
- используйте SLONY если надо, не юзайте велики!
- реплики и мастеры должны быть на одинаковом железе и с одинаковыми настройками!!!!
- не исполльзуйте синхронную репликацию для разных ЦОД
- юзайте FK. контроль целостности должен работать на строне БД а не приложения !!!!
- не патчите постгрес!
- надо делать маленькие транзакции !
- хранимка это место для только внутренних запросов. никаких запусков сторонних сервисов
- писать код нужно для того что бы потом читать
- оптимизируйте запросы
- юзайте PgQ
- попробуйте PL/pgSQL
- используйте Exceptions
- меньше коннекшнов! т.к. один запрос = 1процесс = 1ядро
- юзайте pgbouncer
- НЕ ЮЗАЙТЕ pgPool
- настраивайте shared_buffers! дефолтные натсройки PG для самого гголимого железа !
- не юзайте xmin/xmax для продакшна !
- мониторинг!
- надо делать меньше потоков
- юзайте COPY

== Блокировки в PostgreSQL
https://youtu.be/_R2-IsKfsUU
pg_stat_activity
pg_wait_sampling
pg_locks

SELECT pid, query, pg_blocking_pids(pid) AS blocking FROM pg_stat_activity

pg_row_locks

SELECT llocked_row, xids, modes, pids FROM pgrowlocks('t);

SELECT pid, locktype, transactionid AS xid, tuple as t, granted FROM pg_locks;

deadlock_timeout

== Девять кругов ада или PostgreSQL Vacuum
https://youtu.be/TDWC66qzxCs

MVCC - multiversion concurency control

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