⚡️Почему большинство баз данных на самом деле не CP и не AP?

Крутая статья от Мартина Клеппмана (автор той самой книги с кабанчиком) на тему того, что на самом деле означают Consistency, Availability, Partition tolerance из CAP-теоремы, и почему большинство популярных БД удоволетворяют лишь Partition tolerance.

⚡Distributed Locking в Redis

❓Проблема:

Есть некоторый ресурс, для которого мы хотим обеспечить эксклюзивный доступ. При этом этот ресурс доступен в рамках нескольких процессов (например, ресурс - объект в БД, процессы - поднятые контейнеры микросевиса).

✅ Решение:

Используем Redis в качестве механизма синхронизации.

1. У нас один Redis мастер. В этом случае все просто:

1) Создаем запись, если таковая не существует по заданному ключу (NX) с таймаутом в 30000 миллисекунд (PX)

SET resource_name random_value NX PX 30000

2) Далее после использования ресурса удаляем лок, если он еще принадлежит нам - именно для этого используется random_value при блокировании.

if redis.call("get",KEYS[1]) == ARGV[1] then
    return redis.call("del",KEYS[1])
else
    return 0
end

2. У нас несколько Redis мастеров. Используем алгоритм Redlock, основная идея которого в следующем:

1) Получаем текущее время
2) Пытаемся сходить во все узлы и захватить там лок
3) Считаем время, которое потребовалось на захваты локов.
4) Если лок успешно захвачен на большинстве (n/2 + 1) узлов и время захвата меньше времени таймаута лока - то считаем, что лок успешно захвачен. В противном случае шлем запросы на разблокировку во все узлы.

❗️В обоих алгоритмах используется допущение, что вы гарантированно завершите работу с ресурсом за время истечения лока, иначе никаких гарантий эксклюзивности уже нет. Если это невозможно гарантировать, нужно использовать идею fencing token.

❗️Во втором алгоритме считается, что часы между узлами синхронизированы.

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

⚡Идемпотентность API

❓Проблема:

Иногда возникает потребность, что несколько вызовов метода API должны иметь тот же эффект, что и один вызов. Например, чтобы в случае ретраев из-за сетевых проблем POST запрос не создавал снова ту же сущность.

✅ Решение:

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

❗️Существуют различные реализации механизма проверки, что запрос таким ключом уже обрабатывался. Но всегда стоит помнить, что наивная реализация check-then-act без каких-либо блокировок подвержена race-conditions (оба клиента почти одновременно проверили, что заданного ключа нет, и оба пошли исполнять запрос).

Имхо, наиболее простая реализация, когда хранилищем выступает реляционная БД с одним шардом, выглядит так:

Создадим таблицу для хранения уже обработанных ключей:

create table used_keys (
    value varchar(256) not null primary key
);

И теперь обработка нашего запроса выглядит примерно так:

begin transaction;
— проверка
insert into used_keys (value)
values ('some_key')
on conflict do nothing
returning *;
— если запрос ничего не вернул, значит уже обрабатывали
— если вернул, то обрабатываем запрос
commit;

insert … on conflict do nothing в рамках транзакции блокирует вставку с данным ключом, пока текущая транзакция либо не закомитится, либо не роллбекнется, что решает проблему с check-then-act: второй клиент просто будет ждать, пока первый успешно/неуспешно обработает запрос.

⚡Декомпозиция системы на модули/микросервисы

Хороший доклад на тему того, как разбить систему так, чтобы она не превратилась в Big ball of mud, и чтобы свести к минимуму синхронизацию между различными сервисами.

⚡Session and Token Authentication

❓Проблема:

Хотим аутентифицировать пользователя и хранить какую-то сессионную информацию, привязанную к пользователю.

✅ Решение:

1. Session based Authentication

Принцип работы обычно выглядит так:
- Пользователь отправляет POST запрос /login с телом {username, password}
- Сервер сохраняет в БД сессию и отдает sessionId пользователю в куки
- При повторных обращениях клиент передает sessionId, а сервер по нему аутентифицирует простым лукапом в базе

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

2. Token based Authentication

Принцип работы обычно выглядит так:
- Пользователь отправляет POST запрос /login с телом {username, password}
- Сервер отдает Json Web Token, клиент у себя его локально сохраняет
- При повторных обращениях JWT передается в хедере запроса, сервер его валидирует и достает данные пользователя

В этом случае токен хранится в локальном хранилище на клиенте.

❗️Если у вас ожидается много пользователей и высокая нагрузка, то вероятно стоит сразу задуматься о JWT. Поскольку для Session based Authentication требуется где-то на сервере хранить эти сессии, валидация требует обращения к БД. Если хранилище шардированное, нужно контролировать, чтобы запросы по одной и той же сессии приходили на один и тот же шард. В свою очередь, JWT позволяет производить stateless валидацию и не хранить сессионные данные на сервере.

⚡️Согласованность данных в межсервисных транзакциях

Зачастую некоторые бизнес-операции охватывают сразу несколько сервисов, у каждого из которых своя база данных. Появляется закономерное желание сделать эту “транзакцию” атомарной - чтобы соответствующее действие либо выполнилось во всех сервисах, либо не выполнилось ни в одном. В докладе описывается паттерн Saga, призванный решить эту проблему, обеспечив согласованность в конечном счете.

⚡Sticky sessions

❓Проблема:

Есть один инстанс приложения, использующего веб-сокеты, например, мессенджера. Хотим добиться горизонтального масштабирования, добавив несколько инстансов приложения + балансировщик нагрузки.

✅ Решение:

Использовать Sticky session load balancing, который заключается в том, что запросы от одного клиента будут приходить на один и тот же сервер. В контексте веб-сокетов это особенно важно, поскольку часто требуется, чтобы запросы от клиента приходили на тот же бэкенд, с которым изначально было установлено соединение. Например, это полезно, если у нас есть локальный кеш, в котором хранятся клиентские данные, и мы хотим чтобы после разрыва соединения, следующий запрос на установку соединения пришел на тот же бэкенд.

Принцип работы следующий: балансировщик нагрузки смотрит на какие-то параметры запроса, которые будут постоянны для одного клиента/одной сессии и по ним определяет, на какой сервер переадресовать запрос. Например, можно использовать хеш ip адреса клиента.

⚡Паттерны обработки ошибок в Apache Kafka

❓Проблема:

При работе с очередями сообщений возникает вопрос, что делать с сообщением, если его не получилось обработать.

✅ Решение:

Ответ зависит от специфики приложения: проигнорировать это сообщение, остановить чтение, перебросить в error-топик и тд. В статье описываются популярные паттерны обработки ошибок в Apache Kafka вместе с вариантами использования.

⚡Виды индексов в БД

❓Проблема:

Когда таблица увеличивается, длительность seq scan (последовательного чтения строк) растет линейно по отношению к размеру таблицы. Когда размер доходит до нескольких миллионов, простые запросы, например, поиск по идентификатору, начинают работать несколько секунд.

✅ Решение:

Использовать индексы - структуры данных, призванные ускорить поиск. Существует довольно много типов индексов, рассмотрим наиболее популярные:

1. B-Tree

B-Tree - наиболее распространенный и универсальный тип индекса. Представляет собой сбалансированное дерево поиска, которое позволяет быстро производить поиск по равенству, ренжу, префиксу строки.

2. Hash

Hash-индексы работают на основе хеш-таблицы. Позволяют производить быстрый поиск по равенству.

3. GIN

GIN (Generalized Inverted Index) представляет собой инвертированный индекс, который строится по столбцу с типом ts_vector для проведения эффективного полнотекстового поиска. Также (в Postgres) для GIN существуют operator classes, как, например, gin_trgm_ops, который позволяет эффективно искать по текстовому столбцу по запросам … where column like ‘%query%’ с помощью разбиения текста на триграммы.

⚡Индексирование больших таблиц

❓Проблема:

Есть большая таблица, хотим накатить на нее индекс. Обычный create index блокирует таблицу на время создания индекса. В случае таблиц с сотнями миллионами строк длительность создания индекса может достигать часа. В это время все пишущие запросы будут падать с lock timeout из-за невозможности взятия блокировки => сервис начнет пятисотить => фактически получаем даунтайм.

✅ Решение:

Использовать конструкцию create index concurrently. Она позволяет создать индекс, не блокируя пишущие запросы, однако создание индекса в таком режиме занимает существенно больше времени.

Пример: хотим накатить следующий индекс

create index idx__big_table__column
    on big_table(column)

Для этого перед деплоем приложения руками делаем

create index concurrently idx__big_table__column
    on big_table(column)

И в файле миграции пишем

create index if not exist idx__big_table__column
    on big_table(column)

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

⚡Оптимистические блокировки в СУБД

❓Проблема:

В БД есть обновляемая сущность. Период между чтением сущности и записью может быть большим. При этом хотим, чтобы если пользователь отправляет запрос на обновление, он не перезаписывал изменения другого пользователя. То есть хотим избежать ситуаций

user1: read
user2: read
user1: write
user2: write (перезаписали обновления user1)

✅ Решение:

Использовать оптимистические блокировки. Они заключаются в том, что перед обновлением мы проверяем, что на руках имеем актуальную версию сущности. Реализовать это можно так:

1. Добавляем в сущность БД колонку revision с дефолтом 0
2. Навешиваем триггер, чтобы при каждом апдейте колонка инкрементилась
3. При обновлении проверяем версию

Запрос на обновление будет выглядеть так:

update entity
set … 
where id = <entity_id>
and revision = <revision>
returning *;

Далее если returning * ничего не вернул, значит мы имеем неактуальное состояние. Если вернул, то мы имели актуальное состояние и успешно сделали апдейт.

⚡Оптимизация производительности приложений

Качественный обзорный доклад про роль, общие принципы профилирования при разработке ПО, а также про отличия оптимизаций в “зеленой”, “желтой” и “красной” зонах с множеством примеров.

⚡Deadline propagation

❓Проблема:

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

✅ Решение:

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

⚡Consistent hashing

❓Проблема:

Есть шардированное хранилище. При записи объекта по ключу определяем, в какое хранилище писать с помощью hash(key) % n, где n - число серверов. Вдруг место заканчивается и нужно добавить новый шард, для этого мы должны перехешировать все ключи и перераспределить данные между шардами, что долго и дорого.

✅ Решение:

Использовать консистентное хеширование. Это метод заключается в следующем: представим что наши сервера и ключи располагаются на окружности:

1. Назначаем каждому шарду псевдорандомное число-угол из [0, 360), которое определяет место на окружности

2. При записи объекта по ключу определяем его угол как hash(key) % 360

3. От полученного значения идем по окружности против часовой стрелки и находим ближайший шард, куда и записываем значение

Всё это нужно для того, чтобы при добавлении нового шарда B, который попал между A и C, нам достаточно было перехешировать объекты лишь находящиеся между A и B, а не все. Иначе говоря, добавление или удаление нового шарда требует перехеширований в среднем n/m объектов вместо n, где n - общее число объектов, m - число шардов.

⚡CQRS + Event Sourcing

CQRS - паттерн, призванный разделить commands (модифицирующие запросы) и queries (запросы на чтение). Обычно в таком случае для записи и чтения используются разные БД, более подходящие под конкретные нужды.

Event Sourcing - паттерн, при котором состояние сущности представляет собой последовательность некоторых событий, например:

1. entity created
2. name changed
3. size changed
…

В докладе на реальном примере рассказывается, почему CQRS и Event Sourcing хорошо сочетаются, а также преимущества и недостатки подобной архитектуры.

⚡Distributed tracing

❓Проблема:

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

✅ Решение:

Использовать distributed tracing, основными сущностями которого являются:

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

Span - непрерывный сегмент работы, выполняемый в рамках трейса. Span может быть, например, вызовом API или исполнением запроса к базе данных. Каждый span имеет имя, начальное время, продолжительность и дополнительные метаданные. Они выстраиваются в иерархию parent-chlid, например, если один сервис для выполнения запроса должен вызвать другой (на графике сервис A вызывает B, который вызывает C и т.д).

Таким образом, по спенам можно легко понять, что является узким местом, и исправить это.

⚡Bloom Filter

❓Проблема:

Есть высоконагруженная база данных. В случае гарантированного отсутствия запрашиваемого элемента в БД хотим не делать бессмысленное (и дорогое) IO с диском, а просто отдать ответ, что элемента нет.

✅ Решение:

Использовать фильтр Блума - структуру данных, которая по входной строке умеет давать два ответа:
- Элемента точно нет в множетсве
- Элемент возможно содержится в множетсве

Принцип работы следующий:

Заводится битовый массив длины N. Выбираются несколько фиксированных хеш-функций, отдающих значения из [0, N-1]. В примере на картинке их 3.

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

Проверка наличия: если хотя бы для одной хеш-функции ее результат по входной строке в битовом массиве выставлен в 0, то такой строки гарантированно нет (в противном случае при добавлении этой строки, там бы была единичка). Однако, если все единички, то что-то утверждать мы не можем, поскольку единичка могла “прийти” от другой строки.

⚡Почему батчевые update/delete не безопасны

Конкурентно исполняющиеся стейтменты вида

update entity set … where id in (1, 2)

могут приводить к дедлокам.

Почему так происходит? Чтобы произвести обновление или удаление, обычно производится следующий набор операций:

1. Выборка записей, подходящих под условие where
2. Блокировка записей
3. Повторная проверка условия + исполнение самого update/delete

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

tx1: lock(1) _____ lock(2) _____
tx2: _____ lock(2) ______ lock(1)

Наиболее простым решением будет явное взятие блокировок в нужном порядке перед апдейтом:

begin;
select * from entity where id in (1, 2) order by id for update;
update entity set … where id in (1, 2);
commit;

⚡Sharing data between services

❓Проблема:

Чтобы сервису X выполнить запрос, ему нужно получить данные из сервиса Y, который нестабильно/долго отвечает.

✅ Решение:

Сделать в сервисе X локальную копию требуемых данных, и обновлять их по событиям из сервиса Y.

Плюсы:
- уменьшается связность между сервисами, поскольку в случае отказа сервиса Y, сервис X продолжит работать

Минусы:
- сервис Y обязан публиковать события о своих обновлениях
- “лаг репликации” - в локальном view какое-то время могут быть неактуальные данные

⚡Conflict-free replicated data type

❓Проблема:

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

✅ Решение:

CRDT - структура данных, реплицированная на несколько узлов, обладающая следующими свойствами:

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

Разделяют operation-based и state-based типы: в одном случае рассылаются лишь обновления структуры данных, в другом - цельное состояние структуры.

Рассмотрим operation-based.

Принцип работы следующий:

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

Ограничения на функцию update:

- либо гарантировать порядок доставки update-ов, либо гарантировать, что update_1(update_2(state)) = update_2(update_1(state)), иначе говоря, функции update_1 и update_2 должны коммутировать
- если update может быть доставлен несколько раз, то он должен быть идемпотентным, то есть update(state) = update(update(state))

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