# Валидация

## Описание структуры данных (partitions_storage)
1) Внутри данной структуры данных хранятся множества в виде полуоткрытых интервалов ([X; Y), [Y; Z), ... )
2) В процессе работы множество может быть разбито на два более маленьких для увелечения производительности доступа
3) В процессе работы множество может быть присаеденено к другому если оно стало слишком маленьким
4) Запросы, которые может поддерживать:
    - `get(key)` - отдает множество, в которому принадлежит данный ключ, множество находится в данный момент под mutex_lock

## Описание работы структуры данных
1) Внутри используется персистентное AVL дерево, которое является lock-free и в узлах, хранит как раз так называемые множества
2) У партиции может быть несколько состояний в момент когда пользователь взяль mutex lock и прочитал состояние:
    - ALIVE ( 16 <= `partition.size()` <= 128)
    - NEED_SPLIT ( `partition.size()` > 128)
    - NEED_SHRINK ( 16 > `partition.size()` && partitions_count > 1)
    - DEAD (особое состояние)
3) Как происходит get:
    - сначала получаем из AVL дерева ноду на партицию (она защищена QSBR) и берем у нее mutex lock
    - проверяем состояние, если DEAD, то возвращаемся к предыдущему шагу. Если ALIVE то возвращаем, иначе выполняем соответствующие команды
4) Как происходит split:
    - так как над портицией держится lock то мы пемечяем ее как DEAD
    - разделяем на две по некоторому ключу
    - вставляем в AVL дерево за место ноды связку из таких node (left, split_key, right)
5) Как происходит shrink (shrink происходит когда множеств больше чем одно):
    - отпускаем lock
    - находим предыдущею до нас множество и берем у него lock, проверяя не является ли она DEAD
    - берем lock у нашей партиции и проверяем что она не DEAD
    - находим следующую за нами множество и берем у него lock, проверяя не является ли она DEAD
    - помечаем нашу партицию как DEAD
    - "убираем" нашу партицию из дерева и запоминаем каким ребенком мы были для предка (left, right)
    - если мы были правым ребенком то передаем все множество в следующее множество
    - если мы были левым ребенком то передаем все множество в прошлое множество
6) В начальный момент времени существует либо только одно множество, либо несколько их, которые сбалансированы