Spacemap в ZFS

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

Когда-то применяли простые bitmaps: каждый бит показывает занят ли или
свободен блок на жёстком диске. С увеличением объёма накопителей это
становится очень расточительным -- bitmap-ы занимают много места. Как
решение их можно разбить на несколько частей и по необходимости в память
загружать только часть. Однако bitmap-ы нужно обновлять не только по
мере выделения блоков под хранения, но и по мере их освобождения. Это
легко приведёт к огромному кол-ву IO операций.

Можно применять B-деревья -- но проблемы IO остаются. Можно вместо
блоков использовать extent-ы: показывающие продолжительные линейные
участки на диске. Но это всё малоэффективно.

В ZFS применяют, на мой взгляд, гениальный ход. Во-первых весь pool
бьётся на сотни относительно небольших metaslab-ов, несколько частей.
Каждый metaslab представляет из себя буквально журнал операций по
заниманию и освобождению extent-ов на диске. Это append-only место куда
помещается факт alloc/free участка диска: по идее, добавление просто
пары integer-ов с фактом alloc или free. То есть, любые операции
связанные с изменением свободности места: выполняются крайне быстро.
Чтобы понять что же конкретно свободно: нужно просто считать весь этот
лог и "проиграть" -- создав настоящую "карту" свободного места. Так как
диск разбит на metaslab-ы, то работа в памяти может производиться
например только с одним, небольшого размера. Проблема с IO решена.

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

https://blogs.oracle.com/bonwick/space-maps