3.6 KiB
3.6 KiB
Валидация
Описание структуры данных (partitions_storage)
- Внутри данной структуры данных хранятся множества в виде полуоткрытых интервалов ([X; Y), [Y; Z), ... )
- В процессе работы множество может быть разбито на два более маленьких для увелечения производительности доступа
- В процессе работы множество может быть присаеденено к другому если оно стало слишком маленьким
- Запросы, которые может поддерживать:
get(key)- отдает множество, в которому принадлежит данный ключ, множество находится в данный момент под mutex_lock
Описание работы структуры данных
- Внутри используется персистентное AVL дерево, которое является lock-free и в узлах, хранит как раз так называемые множества
- У партиции может быть несколько состояний в момент когда пользователь взяль mutex lock и прочитал состояние:
- ALIVE ( 16 <=
partition.size()<= 128) - NEED_SPLIT (
partition.size()> 128) - NEED_SHRINK ( 16 >
partition.size()&& partitions_count > 1) - DEAD (особое состояние)
- ALIVE ( 16 <=
- Как происходит get:
- сначала получаем из AVL дерева ноду на партицию (она защищена QSBR) и берем у нее mutex lock
- проверяем состояние, если DEAD, то возвращаемся к предыдущему шагу. Если ALIVE то возвращаем, иначе выполняем соответствующие команды
- Как происходит split:
- так как над портицией держится lock то мы пемечяем ее как DEAD
- разделяем на две по некоторому ключу
- вставляем в AVL дерево за место ноды связку из таких node (left, split_key, right)
- Как происходит shrink (shrink происходит когда множеств больше чем одно):
- отпускаем lock
- находим предыдущею до нас множество и берем у него lock, проверяя не является ли она DEAD
- берем lock у нашей партиции и проверяем что она не DEAD
- находим следующую за нами множество и берем у него lock, проверяя не является ли она DEAD
- помечаем нашу партицию как DEAD
- "убираем" нашу партицию из дерева и запоминаем каким ребенком мы были для предка (left, right)
- если мы были правым ребенком то передаем все множество в следующее множество
- если мы были левым ребенком то передаем все множество в прошлое множество
- В начальный момент времени существует либо только одно множество, либо несколько их, которые сбалансированы