Individual-task/validate

Валидация

Описание структуры данных (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. В начальный момент времени существует либо только одно множество, либо несколько их, которые сбалансированы