33 lines
3.6 KiB
Markdown
33 lines
3.6 KiB
Markdown
# Валидация
|
||
|
||
## Описание структуры данных (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) В начальный момент времени существует либо только одно множество, либо несколько их, которые сбалансированы
|