BTRFS

Btrfs имеет следующие фичи: встроенная поддержка RAID, снэпшоты, сжатие, криптование.

Нужно сказать, что классические линуксовые файловые системы - ext или xfs - не решают многих насущных проблем, например, таких, как добавление диска к уже существующему тому или фоновое увеличение рабочей партиции. В btrfs это решается одной командой:

btrfs device add < device > < file system >

B-tree

Каждый ключ в такой ноде имеет 3 значения: objectID, тип, и смещение. В данном примере [30,0,0] меньше, чем [30,0,1]. В листе хранятся ключи и данные:

item включают в себя ключ, размер и смещение внутри листа. item-ы растут от начала листа, данные растут в обратном порядке - от конца.

Снэпшоты

При создании файловой системы btrfs рутовая директория также является и под-томом - subvolume. Снэпшот можно делать только по отношению к таким под-томам. Создать под-том /home:

btrfs subvolume create /home

Создать снэпшот для домашнего каталога:

btrfs subvolume snapshot /home/ /home-snap

Удалить снэпшот:

btrfs subvolume delete /home-snap/

Вывести полный список снэпшотов:

btrfs subvolume list /mnt/btrfs-test/

btrfs везде, где только можно, использует 64-битные идентификаторы. Это означает, что она может управлять числом под-томов, равным 2 в 64-й степени. Число нод потенциально возрастает до 2-х в 128-й степени. Это позволяет создавать практически неограниченное число под-томов внутри одной файловой системы. Можно адресовать адресное пространство на диске размером 8 exabytes.

Директории

В btrfs имя файла хешируется, и вместо поиска по файлу, мы ищем по числовому индексу, что быстрее.

Дисковое пространство

Контрольные суммы

Компрессия

mount -o compress

то все последующие записи будут сжиматься.

SSD

Целостность данных

Производительность

**********************

Файловая система btrfs построена по принципу copy-on-write (COW): т.е. если на диске нужно модифицировать какой-то блок, то создается его копия, с которой продолжается работа.

Принцип copy-on-write демонстрирует следующая картинка:

Базовые структуры файловой системы:

Ноды

Файлы и каталоги

Большие файлы хранятся в расширениях. Структура btrfs_file_extent_item хранит указатель на это расширение и число блоков файловой системы, отведенных на хранение файла, а также карту распределения свободных участков, что позволяет эффективно использовать дисковое пространство внутри расширения

 struct btrfs_file_extent_item {
 	/*
 	 * transaction id that created this extent
 	 */
 	__le64 generation;
 	/*
 	 * max number of bytes to hold this extent in ram
 	 * when we split a compressed extent we can't know how big
 	 * each of the resulting pieces will be.  So, this is
 	 * an upper limit on the size of the extent in ram instead of
 	 * an exact limit.
 	 */
 	__le64 ram_bytes;
 
 	/*
 	 * 32 bits for the various ways we might encode the data,
 	 * including compression and encryption.  If any of these
 	 * are set to something a given disk format doesn't understand
 	 * it is treated like an incompat flag for reading and writing,
 	 * but not for stat.
 	 */
 	u8 compression;
 	u8 encryption;
 	__le16 other_encoding; /* spare for later use */
 
 	/* are we inline data or a real extent? */
 	u8 type;
 
 	/*
 	 * disk space consumed by the extent, checksum blocks are included
 	 * in these numbers
 	 */
 	__le64 disk_bytenr;
 	__le64 disk_num_bytes;
 	/*
 	 * the logical offset in file blocks (no csums)
 	 * this extent record is for.  This allows a file extent to point
 	 * into the middle of an existing extent on disk, sharing it
 	 * between two snapshots (useful if some bytes in the middle of the
 	 * extent have changed
 	 */
 	__le64 offset;
 	/*
 	 * the logical number of file blocks (no csums included)
 	 */
 	__le64 num_bytes;
 
 } __attribute__ ((__packed__));
 

 Контрольные файловые суммы хранятся в структуре btrfs_csum_item. 

Счетчики ссылок (Reference Count)

 struct btrfs_extent_item {
 	__le64 refs;
 	__le64 generation;
 	__le64 flags;
 } __attribute__ ((__packed__));
 

Extent Block Groups

Snapshots и Subvolumes

Btree Roots

рутовое дерево

дерево расширений

дерево тома по умолчанию

Рутовой дерево хранит ссылки на собственный рутовый блок, а также на рутовые блоки для каждого тома и снепшота. Рутовое дерево - это каталог всех остальных деревьев, в котором хранятся имена всех томов и снепшотов. Каждый снепшот или том имеет свою структуру btrfs_root_item:

 struct btrfs_root_item {
 	struct btrfs_inode_item inode;
 	__le64 generation;
 	__le64 root_dirid;
 	__le64 bytenr;
 	__le64 byte_limit;
 	__le64 bytes_used;
 	__le64 last_snapshot;
 	__le64 flags;
 	__le32 refs;
 	struct btrfs_disk_key drop_progress;
 	u8 drop_level;
 	u8 level;
 } __attribute__ ((__packed__));
 

Расширенные деревья используются для выделения свободного дискового пространства и могут создаваться в соответствии с политикой прав и уменьшения дисковых блокировок.

Базовая структура btrfs - copy-on-write B-tree - впервые была анонсирована Огад Rodeh из IBM в 2007 г. Он предложил добавить механизм reference counts для балансировки деревьев, что повышает их производительность/параллелизм.

Структура btrfs (для 3 различных устройств):

Основные фичи btrfs:

 
 
   расширенная емкость (до 2^64 max file size)
   эффективное использование дискового пространства для малых файлов
   эффективное использование дискового пространства при индексации каталогов
   динамическое выделение нод
   снэпшоты
   вложенные тома (внутренне разбиение на несколько рутов)  
   контрольные суммы для данных и метаданных
   компрессия
   поддержка raid
   бэкап, зеркалирование, дефрагментация 
 
 

В btrfs имеется несколько типов деревьев:

 
   Root tree
   File system tree
   Extent allocation tree
   Checksum tree
   Log tree
   Chunk and device trees  
   Data relocation tree
 
 

    
  
   Дерева корней
   Дерева выделенных экстентов
   Дерева default­субтома
 
 

Дерево   корней   содержит   корневые   блоки   для   дерева   экстентов,   а   также  корневые   блоки   и   имена   деревьев   для   каждого   субтома   и   снапшота   в   ФС.   При  фиксации   транзакции   указатели   на   корневые   блоки   обновляются   по   COW­семантике   в   этом  дереве,  и   его   новый   корневой   блок   записывается   в   суперблок  btrfs. 

Root tree - родитель для всех остальных деревьев, которые вложены в нем, его object id = 1. Остальные типы деревьев могут иметь по несколько инстансов, каждый из которых имеет свой object ID.

File system tree - в нем хранятся файлы и каталоги. Каждый файл или директория имеют свою ноду. Директории проиндексированы для быстрого поиска. Файлы имеют ссылку на родителя. Сами данные файлов хранятся за пределами деревьев в расширениях, расширение имеет размер в 4 КБ,

Extent allocation tree - хранятся ссылки на расширения, в которых хранятся сами данные. Расширения не имеют своих ID, они используют байтовые смещения в ключах. Расширения имеют обратные ссылки на ноды, что позволяет оптимально быстро делать перемещения по диску. Преимущество btrfs по сравнению с той же ext3 в том, что последняя в случае большого файла хранит его более хаотично на диске, в то время как btrfs хранит большой файл более упорядоченно, что увеличивает скорость доступа.

Checksum tree - хранятся контрольные суммы как для данных, так и для метаданных. Это позволяет на лету определять ошибки в файловой системе и исправлять их.

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

Все метаданные хранятся в дереве - btree. Дерево хранит пару ключ/значение - key/item. Ключ служит для идентификации и сортировки значений внутри дерева. Ключ разбит на 3 части: objectid, type, offset. В качестве значения может быть данные произвольного типа.

Подтома (Subvolume) - именованные деревья, хранящие файлы и каталоги. Каждый снэпшот представляет из себя такой Subvolume. Вложенный том - это как вложенная отдельная партиция, созданная без дополнительного разбиения диска. Это позволяет делать снэпшоты - снимки файловой системы на момент времени, что в свою очередь может избавить от необходимости в журналировании. Логика создания снэпшота следующая: создается - причем мгновенно - копия файловой системы, вернее ее файловой структуры, а сами данные не копируются сразу, а лишь тогда, когда происходит их модификация. таким образом поддерживается атомарность данных, т.е. неблокировка данных для других операций.

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

Суперблок:

 
 struct btrfs_super_block {
       u8 csum[BTRFS_CSUM_SIZE];     /* контрольная сумма */
       u8 fsid[16];                  /* UUID файловой системы */
       __le64 bytenr;                /* номер этого блока */
       __le64 flags;
       __le64 magic;                 /* 8 байт, "_B5RfS_M" */
       __le64 generation;            /* ID последней удачной транзакции */
       __le64 root;                  /* указатель на дерево корней */
       __le64 chunk_root;            /* указатель на дерево сегментов */
       __le64 total_bytes;           /* размер ФС в байтах */
       __le64 bytes_used;            /* использовано байт */
       __le64 root_dir_objectid;     /* objectid корневого каталога */
       __le64 num_devices;           /* количество устройств в пуле */
       __le32 sectorsize;            /* размер сектора */
       __le32 nodesize;              /* размер узла дерева */
       __le32 leafsize;              /* размер листа дерева */
       __le32 stripesize;
       __le32 sys_chunk_array_size;
       u8 root_level;                /* глубина основного дерева ФС */
       u8 chunk_root_level;          /* глубина дерева сегментов */
       struct btrfs_dev_item dev_item;     /* дескриптор этого устройства */
       char label[BTRFS_LABEL_SIZE];       /* символьная метка ФС */
       u8 sys_chunk_array[BTRFS_SYSTEM_CHUNK_ARRAY_SIZE];
 };
 

 struct btrfs_header {
     u8 csum[32];
     u8 fsid[16];
     __le64 blocknr;
     __le64 flags;
 
     u8 chunk_tree_uid[16];
     __le64 generation;
     __le64 owner;
     __le32 nritems;
     u8 level;
 }
 
 	
 
 struct btrfs_disk_key {
     __le64 objectid;
     u8 type;
     __le64 offset;
 }
 
 	
 
 struct btrfs_item {
     struct btrfs_disk_key key;
     __le32 offset;
     __le32 size;
 }
 

Поле generation соответствует ID транзакции, в рамках которой был размещен  или   переразмещен   данный   блок.   Оно   позволяет   легко   поддерживать  инкреметальные бэкапы (снапшоты) и подсистему COW­транзакций — совершенно  так же, как это сделано в ZFS. 

Inodes хранятся в структуре btrfs_inode_item (ctree.h), поле offset ключа inode­ итема   всегда   равно   нулю,   поле   type   -   единице.

 
 struct btrfs_inode_item {
       __le64 generation;      /* ID транзакции создания файла */
       __le64 size;            /* Размер файла в байтах */
       __le64 nblocks;         /* Количество занимаемых блоков */
       __le64 block_group;     /* Предпочитаемая группа блоков */
       __le32 nlink;           /* Счетчик ссылок на файл */
       __le32 uid;             /* UID владельца */
       __le32 gid;             /* GID владельца */
       __le32 mode;            /* Маска типа и прав доступа */
       __le64 rdev;            /* [minor:major] для устройств */
       __le16 flags;           /* Флаги */
       __le16 compat_flags;    /* Флаги совместимости */
       struct btrfs_timespec atime; /* Времена доступа, модификации, и т.д. */
       struct btrfs_timespec ctime;
       struct btrfs_timespec mtime;
       struct btrfs_timespec otime;
 };
 
 

Предыдущие файловые системы организовывали данные следующим образом:

В btrfs это делается по другому:

Блоки красного цвета на обоих диаграммах указывают неиспользуемое дисковое пространство.

Метаданные и данные в файловой системе хранятся как часть item. Если еще раз вернуться к структуре

 
 struct btrfs_disk_key {
     __le64 objectid;
     u8 type;
     __le64 offset;
 }