Search     or:     and:
 LINUX 
 Language 
 Kernel 
 Package 
 Book 
 Test 
 OS 
 Forum 
 iakovlev.org 
 Kernels
 Boot 
 Memory 
 File system
 0.01
 1.0 
 2.0 
 2.4 
 2.6 
 3.x 
 4.x 
 5.x 
 6.x 
 Интервью 
 Kernel
 HOW-TO 1
 Ptrace
 Kernel-Rebuild-HOWTO
 Runlevel
 Linux daemons
 FAQ
NEWS
Последние статьи :
  Тренажёр 16.01   
  Эльбрус 05.12   
  Алгоритмы 12.04   
  Rust 07.11   
  Go 25.12   
  EXT4 10.11   
  FS benchmark 15.09   
  Сетунь 23.07   
  Trees 25.06   
  Apache 03.02   
 
TOP 20
 MINIX...3057 
 Solaris...2933 
 LD...2904 
 Linux Kernel 2.6...2470 
 William Gropp...2180 
 Rodriguez 6...2012 
 C++ Templates 3...1945 
 Trees...1937 
 Kamran Husain...1866 
 Secure Programming for Li...1792 
 Максвелл 5...1710 
 DevFS...1694 
 Part 3...1684 
 Stein-MacEachern-> Час...1632 
 Go Web ...1624 
 Ethreal 4...1618 
 Arrays...1607 
 Стивенс 9...1603 
 Максвелл 1...1592 
 FAQ...1538 
 
  01.01.2024 : 3621733 посещений 

iakovlev.org

B-trees, Shadowing, Clones

Ohad Rodeh

IBM Haifa Research Labs

Сам документ можно скачать тут

Бинарные деревья используются многими файловыми системами для представления файлов и каталогов. Время поиска, вставка, удаление в таких файловых системах имеет логарифмическую зависимость. Такие файловые системы, как WAFL или ZFS, имеют встроенный механизм shadowind, или copy-on-write, на основе которого реализуются снэпшоты, восстановление после аварий, RAID. Этот документ описывает набор алгоритмов, реализующих этот самый shadowing (я не знаю, как лучше перевести это слово :) , который позволяет сделать достаточное количество снэпшотов в фоновом режиме и при этом достигается хороший параллелизм работы самой файловой системы.

Бинарные деревья - это альтернативный алгоритм реализации файловых систем по сравнению с традиционным юниксовым подходом (ext), использующим косвенную индексацию блоков. Файловая система представляет из себя дерево, состоящее из страниц фиксированного размера. Shadowing буквально означает следующее: если нам нужно модифицировать какую-то страницу из такого дерева, мы читаем эту страницу в память, модифицируем эту копию и потом сбрасываем эту копию обратно на диск. После этого необходимо будет тут же изменить родительскую ссылку, которая будет вести на обновленную копию. Это т.н. строгий (strict) shadowing-алгоритм: на рисунке показано, что была промодифицирована целая ветка вплоть до корня

Т.е. данный алгоритм позволяет иметь для файловой системы более одного (!) рута в зависимости от количества снэпшотов. И каждый рут будет указывать на свой собственный мгновенный снимок файловой системы. Удалить такой рут можно только вместе со снэпшотом.

Обычно файловые системы (XFS,JFS) используют вариант бинарных деревьев, который называется b+tree. В них ноды делятся на корневые и на листья. Корневые ноды содержат только индексные ключи, в листьях находятся сами данные.

Основное требование, предьявляемое к бинарным деревьям - это устойчивость и восстанавливаемость. Обновление дерева происходит снизу-вверх. Модифицируются листья. Иногда листья могут клонироваться или наоборот обьединяться, что может вызвать рекурсивное изменение вверх. Листья обьединяются в цепочку для балансировки самого дерева.

Основные проблемы, которые возникают при попытке сделать shadowing для классического типа деревьев:

На следующем рисунке представлена дерево с цепочкой связи между листьями. Если мы будем стандартный copy-on-write для ноды C, у нас порвется связь в созданном снэпшоте для ноды C.

Параллелизм: в момент copy-on-write изменения листьев, происходит модификация всей ветки, вплоть до корня, что вызывает блокировку всего дерева на момент апдэйта.

Модификация ключей: на следующем рисунке нода A имеет 2 соседних ноды - L и R. Из ноды A удаляется ключ, при этом происходит модификация дерева(серый цвет). Если удаляемый ключ относится к ноде L, то возникают дополнительные проблемы с модификацией дерева.

Мы изменим подход и вместо алгоритма "снизу-вверх" выберем алгоритм прохода дерева "сверху-вниз". Также вместо цепочки связей между листьями мы будем использовать механизм обратных ссылок.

Checkpoint - моментальный снимок файловой системы на диске. Если в файловой системе происходит сбой. то будет откат к предыдущему чек-пойнту. Рассмотрим дерево:

На следующем рисунке серым цветом показана его модификация

На следующем рисунке картина после закомиченного чек-пойнта

Чек-пойнты эффективны, потому что их запись происходит в пакетном режиме, и всегда можно откатиться в случае чего. Логирование представляет дополнительные возможности в том плане, что все модификации файловой системы логируются в одном журнале. Комбинация чек-пойнтов и логов дает эффективный механизм плюс дополнительное кеширование дерева в памяти, при котором все модификации происходят на лету и в нужный момент сбрасываются на диск.

Как я уже отметил, в этой статье используются b+tree. В таких деревьях листья включают пары "ключ-данные", а индексные ноды содержат связи между ключами и дочерними нодами. На следующем рисунке нода A - рутовая нда, B - индексная нода, C - нода-лист. При этом между листьями нет никакой связи. Каждая нода занимает 4 килобайта дискового пространства. Наше дерево также сбалансировано - это означает что расстояние от любого листа до рута одинаково.

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

Нода может включать листья в диапазоне b и (2b + 1) для b>=2. Если нода имеет (2b + 1) листьев, то при добавлении очередного листа она разбивается. Если нода содержит b листьев, то при удалении листа из такой ноды она обьединяется с соседом. Мы берем для всех примеров b=2 и диапазон [2...5].

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

При удалении дерева используется post-order проход. Для дерева

удаление будет выполнено по правилу:

Вставка одного ключа может сопровождаться спонтанным разбиением/добавлением нод сразу на нескольких уровнях. Сказанное иллюстрирует следующий рисунок: вставляется ключ 8, при этом происходит: 1) разбиение рутовой ноды 2) добавление промежуточных нод

Удаление одного ключа может привести к обратным массовым модификациям всего дерева: например, удаление ключа 3 из второго уровня:

На практике, ограничение для числа листьев находится в пределе [b,3b].

При вставке/удалении число модифицируемых дисковых страниц может быть равно (2 * глубину дерева). Поскольку дерево сбалансировано, глубина дерева может быть, в худшем случае, логарифм от N по основанию b, где N - число ключей в дереве.

На следующем рисунке показано клонирование дерева. Справа ноды B и C увеличивают свои ссылочные счетчики на 1. Нет нужды в создании полной копии дерева слева - это неэффективно, просто создается еще одна корневая нода Q:

На следующем рисунке показано, как после удаления дерева Tq уменьшаются счетчики ссылок в нодах C, Y:

Рассмотрим пример файловой системы. Рутовая нода указывает на meta-file, хранящий дисковые ноды, при этом каждая нода укзывает на дерево, хранящее файловые данные - в данном случае ноды 2,5, 7 имеют такие данные. Еще один meta-file хранит свободные счетчики:

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

При клонировании файла происходит следующее:

Оставьте свой комментарий !

Ваше имя:
Комментарий:
Оба поля являются обязательными

 Автор  Комментарий к данной статье