Дизайн LittleFS

LittleFS — небольшая отказоустойчивая файловая система, предназначенная для микроконтроллеров.

   | | |     .---._____
  .-----.   |          |
--|o    |---| littlefs |
--|     |---|          |
  '-----'   '----------'
   | | |

Изначально LittleFS была создана в качестве эксперимента для изучения дизайна файловых систем в контексте микроконтроллеров. Вопрос был следующим: как создать файловую систему, устойчивую к потере питания и износу флэш-памяти без использования неограниченной памяти?

Этот документ охватывает высокоуровневый дизайн LittleFS, её отличия от других файловых систем и принятые проектные решения. Для получения низкоуровневых деталей, касающихся каждого бита на диске, обратитесь к SPEC.md.

Проблема

Целевые встроенные системы LittleFS обычно представляют собой 32-битные микроконтроллеры с примерно 32 КБ ОЗУ и 512 КБ ПЗУ. Часто они сочетаются с SPI NOR флеш-чипами объёмом около 4 МБ флеш-памяти. Эти устройства слишком малы для Linux и большинства существующих файловых систем, поэтому требуется код, написанный специально с учётом размера.

Флеш-память сама по себе представляет собой интересную технологию со своими особенностями и нюансами. В отличие от других форм хранения данных, запись во флеш-память требует двух операций: стирания и программирования. Программирование (установка битов в 0) относительно дёшево и может быть очень детализированным. Стирание же (установка битов в 1), напротив, требует дорогостоящей и разрушительной операции, которая и дала название флеш-памяти. На [Wikipedia][wikipedia-flash] можно найти больше информации о том, как именно работает флеш-память.

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

Это оставляет нам три основных требования к встроенной файловой системе.

1. Устойчивость к потере питания — в этих системах питание может быть потеряно в любой момент. Если потеря питания повредит какие-либо постоянные структуры данных, это может привести к тому, что устройство станет невосстановимым. Встроенная файловая система должна быть спроектирована так, чтобы восстанавливаться после потери питания во время любой операции записи.

2. Выравнивание износа — запись во флеш-память является разрушительной. Если файловая система многократно записывает в один и тот же блок, в конечном итоге этот блок изнашивается. Файловые системы, которые не учитывают износ, могут легко сжечь блоки, используемые для хранения часто обновляемых метаданных, и вызвать преждевременную смерть устройства.

3. Ограниченное использование RAM/ROM — если вышеперечисленных требований было недостаточно, эти системы также имеют очень ограниченные объёмы памяти. Это препятствует использованию многих существующих дизайнов файловых систем, которые могут полагаться на относительно большие объёмы оперативной памяти для временного хранения метаданных файловой системы.

Для ПЗУ это означает, что мы должны сохранять наш дизайн простым и повторно использовать пути кода там, где это возможно. Для ОЗУ у нас есть более жёсткое требование: всё использование ОЗУ ограничено. Это означает, что использование ОЗУ не увеличивается по мере изменения размера или количества файлов в файловой системе. Это создаёт уникальную проблему, поскольку даже предположительно простые операции, такие как обход файловой системы, становятся удивительно сложными.

Существующие дизайны?

Итак, что уже существует? Конечно, существует множество различных файловых систем, однако они часто заимствуют и разделяют функции друг у друга. Если мы посмотрим на устойчивость к потере питания и выравнивание износа, то сможем сузить их до нескольких дизайнов.

Во-первых, у нас есть нерезистивные блочные файловые системы, такие как [FAT] и [ext2]. Это самые ранние дизайны файловых систем и зачастую самые простые. Здесь хранилище делится на блоки, причём каждый файл хранится в наборе блоков. Без модификаций эти файловые системы не являются устойчивыми к потере питания, поэтому обновление файла — это просто перезапись блоков на месте. | | | |---|---| | | | B | | | | | | | |'--------'|'--------' |. -' '.-| |v v| |.--------.|.--------.| |C **|D || | | | | | | |'--------'|'--------'

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

2. В совершенно другом направлении у нас есть файловые системы журналирования, такие как JFFS, YAFFS и SPIFFS. Место хранения не привязано к фрагменту данных, вместо этого всё хранилище используется для циклического журнала, который дополняется при каждом изменении в файловой системе. Запись добавляет новые изменения, в то время как чтение требует обхода журнала для восстановления файла. Некоторые файловые системы журналирования кэшируют файлы, чтобы избежать затрат на чтение, но это происходит за счёт оперативной памяти.

                                                         v

.--------.--------.--------.--------.--------.--------.--------.--------. | C | new B | new A | | A | B | | | | |-> | | | | | | | | | | '--------'--------'--------'--------'--------'--------'--------'--------'

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

Основным недостатком является производительность. Если мы посмотрим на сборку мусора, процесс очистки устаревших данных с конца журнала, я ещё не видел чистую файловую систему журналирования, которая не имела бы одной из этих двух затрат:

1. *O(n²)* времени выполнения.
2. *O(n)* оперативной памяти.

SPIFFS представляет собой очень интересный случай, поскольку он использует тот факт, что повторные программы для NOR flash являются атомарными и маскирующими. Это очень изящное решение, однако оно ограничивает тип поддерживаемого хранилища.

3. Возможно, наиболее распространённым типом файловой системы является файловая система журналирования — потомок, возникающий при объединении блочной файловой системы с файловой системой журналирования. Хорошими примерами являются ext4 и NTFS. Здесь мы берём обычную блочную файловую систему и добавляем ограниченный журнал, где отмечаем каждое изменение перед его возникновением.

                         journal
                        .--------.--------.
           .--------.   | C'| D'|     | E'|
           |  root  |-->|   |   |->   |   |
           |        |   |   |   |     |   |
           |        |   '--------'--------'
           '--------'
           .-'    '-.
          v          v
     .--------.  .--------.
     |   A    |  |   B    |
     |        |  |        |
     |        |  |        |
     '--------'  '--------'
     .-'         .-'    '-.
    v           v          v

.--------. .--------. .--------. | C | | D | | E | | | | | | | | | | | | | '--------' '--------' '--------' . -' '.-| v v| .--------.|.--------.| | C |D || | | | | | | |'--------'|'--------'

Этот тип файловой системы берёт лучшее от обоих миров. Производительность может быть такой же быстрой, как у блочной файловой системы (хотя обновление журнала имеет небольшую стоимость), а атомарные обновления журнала позволяют файловой системе восстанавливаться в случае потери питания.

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

4. Последнее, но... Не в последнюю очередь у нас есть файловые системы с копированием при записи (COW), такие как btrfs и ZFS. Они очень похожи на другие блочные файловые системы, но вместо обновления блока на месте все обновления выполняются путём создания копии с изменениями и замены любых ссылок на старый блок нашим новым блоком. Это рекурсивно продвигает все наши проблемы вверх, пока мы не достигнем корня нашей файловой системы, который часто хранится в очень маленьком журнале.

           .--------.                  .--------.
           |  root  |       write      |new root|
           |        |        ==>       |        |
           |        |                  |        |
           '--------'                  '--------'
           .-'    '-.                    |    '-.
          |  .-------|------------------'        v
          v v        v                       .--------.
     .--------.  .--------.                  | new B  |
     |   A    |  |   B    |                  |        |
     |        |  |        |                  |        |
     |        |  |        |                  '--------'
     '--------'  '--------'                  .-'    |
     .-'         .-'    '-.    .------------|------'
    |           |          |  |             v
    v           v          v  v        .--------.

.--------. .--------. .--------. | new D | | C | | D | | E | | | | | | | | | | | | | | | | | '--------' '--------' '--------' '--------'

Файловые системы COW интересны. Они предлагают производительность, аналогичную производительности блочных файловых систем, при этом им удаётся выполнять атомарные обновления без непосредственного хранения изменений данных в журнале. Они даже разъединяют место хранения данных, что создаёт возможность для выравнивания износа.

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

## littlefs

Так что же делает littlefs?

Если мы посмотрим на существующие файловые системы, то выделим два интересных шаблона проектирования, каждый из которых имеет свой набор проблем. Ведение журнала обеспечивает независимую атомарность, но имеет плохую производительность во время выполнения. А структуры данных COW, которые хорошо работают, поднимают проблему атомарности вверх.

Можем ли мы обойти эти ограничения?

Рассмотрим ведение журнала. Оно имеет либо квадратичную сложность по времени выполнения O(n²), либо линейную по объёму используемой памяти O(n). Мы не можем избежать этих затрат, но если мы установим верхний предел размера, мы, по крайней мере, сможем предотвратить превращение теоретической стоимости в проблему. Это опирается на суперсекретный приём из области компьютерных наук, когда можно притвориться, что любая алгоритмическая сложность равна O(1), ограничив входные данные.

В случае структур данных COW мы можем попробовать немного изменить определение. Скажем, наша структура COW копирует не после одной записи, а после n записей. Это не меняет большинство свойств COW (при условии, что вы можете писать атомарно!), но предотвращает движение износа вверх. Этот вид копирования при ограниченном количестве записей (CObW) всё ещё фокусирует износ, но на каждом уровне мы делим распространение износа на n. При достаточно большом n (> коэффициент ветвления) распространение износа больше не является проблемой.

Видите, к чему это ведёт? Отдельно ведение журнала и COW — несовершенные решения, имеющие недостатки, ограничивающие их полезность. Но если мы объединим их, они смогут взаимно решить проблемы друг друга.

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

По сравнению с другими файловыми системами сборщик мусора littlefs относительно прост. Мы хотим избежать потребления оперативной памяти, поэтому используем своего рода решение грубой силы, где для каждой записи проверяем, была ли записана более новая запись. Если запись самая последняя, мы добавляем её в наш новый блок. Вот где наличие двух блоков становится важным: если мы теряем питание, у нас всё ещё есть всё в нашем исходном блоке.

Во время этого шага уплотнения мы также стираем блок метаданных и увеличиваем счётчик ревизий. Поскольку мы можем зафиксировать несколько записей одновременно, мы можем записать все эти изменения во второй блок, не беспокоясь о потере питания. Только когда контрольная сумма фиксации записывается, сжатые записи и счётчик ревизий становятся зафиксированными и доступными для чтения.

Если наш блок полон записей и мы не можем найти никакого мусора, что тогда?

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

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

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

Амортизированная стоимость выполнения сборки мусора зависит не только от единовременных затрат (O(n²) для littlefs), но и от того, как часто происходит сборка мусора. Рассмотрим два крайних случая:

1. Лог пуст, сборка мусора происходит один раз каждые n обновлений.
2. Лог полон, сборка мусора происходит **при каждом** обновлении.

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

Рассмотрим проблему в общем виде. Предположим, что у нас есть лог с n байтами для каждой записи, d динамическими записями (записи, которые устаревают во время сборки мусора) и s статическими записями (записи, которые необходимо скопировать во время сборки мусора). Если мы посмотрим на амортизированную сложность выполнения обновления этого лога, то получим следующую формулу:
cost = n + n (s / d+1).

Если мы обозначим r как отношение статического пространства к размеру нашего лога в байтах, мы найдём альтернативное представление количества статических и динамических записей:
s = r (size/n);
d = (1 - r) (size/n).

Подставляя эти значения вместо d и s, получаем красивую формулу стоимости обновления записи с учётом степени заполнения лога:
cost = n + n (r (size/n) / ((1-r) (size/n) + 1)).

Предположим, у нас 100-байтные записи в 4-килобайтном логе. Мы можем построить график, используя размер записи, чтобы найти мультипликативную стоимость:
Metadata pair update cost graph.

Таким образом, при использовании на 50% мы видим среднюю стоимость в 2 раза больше за обновление, а при использовании на 75% — уже в 4 раза больше.

Чтобы избежать такого экспоненциального роста, вместо ожидания заполнения пары метаданных мы разделяем пару метаданных, когда превышаем предел в 50%. Мы делаем это лениво, ожидая, пока нам не понадобится уплотнение, прежде чем проверять, укладываемся ли мы в наш 50%-ный лимит. Это ограничивает накладные расходы сборки мусора до 2x стоимости выполнения, давая нам амортизированную сложность O(1).

**Метаданные и связанные списки метаданных**

На высоком уровне метаданные и связанные списки пар метаданных имеют довольно хорошие затраты времени выполнения. Предполагая n пар метаданных, каждая из которых содержит m записей метаданных, стоимость поиска конкретной записи имеет худшую сложность времени выполнения O(nm). Для обновления конкретной записи худшая сложность составляет O(nm²), с амортизированной сложностью всего O(nm).

Однако разделение на 50% означает, что в лучшем случае наши пары метаданных будут заполнены только наполовину. Если мы включим накладные расходы второго блока в нашу пару метаданных, каждая запись метаданных будет иметь эффективную стоимость хранения в 4 раза превышающую исходный размер. Я полагаю, пользователи были бы недовольны, если бы обнаружили, что могут использовать только четверть своего... |--|        |--|        |  |        |
'--------'  '--------'  '--------'  '--------'  '--------'  '--------'

Дополнительные указатели позволяют нам перемещаться по структуре данных на диске гораздо эффективнее, чем в односвязном списке.

Рассмотрим путь от блока данных 5 к блоку данных 1. Можно увидеть, как полностью был пропущен блок данных 3:

.--------.  .--------.  .--------.  .--------.  .--------.  .--------.
| данные 0 |  | данные 1 |<-| данные 2 |  | данные 3 |  | данные 4 |<-| данные 5 |
|        |  |        |  |        |<-|        |--|        |  |        |
|        |  |        |  |        |  |        |  |        |  |        |
'--------'  '--------'  '--------'  '--------'  '--------'  '--------'

Путь к блоку данных 0 ещё быстрее, требуется только два перехода:

.--------.  .--------.  .--------.  .--------.  .--------.  .--------.
| данные 0 |  | данные 1 |  | данные 2 |  | данные 3 |  | данные 4 |<-| данные 5 |
|        |  |        |  |        |  |        |  |        |  |        |
|        |<-|        |--|        |--|        |--|        |  |        |
'--------'  '--------'  '--------'  '--------'  '--------'  '--------'

Мы можем найти сложность выполнения, посмотрев на путь к любому блоку из блока, содержащего наибольшее количество указателей. Каждый шаг вдоль пути делит пространство поиска для блока пополам, что даёт нам сложность выполнения O(log n). Чтобы добраться до блока с наибольшим количеством указателей, мы можем выполнить те же шаги назад, что приводит к сложности выполнения O(2 log n) = O(log n). Интересно отметить, что этот оптимальный путь возникает естественным образом, если мы жадно выбираем указатель, который покрывает наибольшее расстояние, не проходя мимо нашей цели.

Итак, теперь у нас есть структура данных [COW], которая дешева для добавления со сложностью выполнения O(1), и может быть прочитана со сложностью выполнения в худшем случае O(n log n). Учитывая, что эта сложность также делится на объём данных, которые мы можем хранить в блоке, эта стоимость вполне разумна.

Это новая структура данных, поэтому у нас всё ещё есть несколько вопросов. Какова дополнительная нагрузка на память? Может ли количество указателей превысить размер блока? Как мы храним CTZ-пропускной список в наших парах метаданных?

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

Поскольку размер нашего файла ограничен шириной слова, которую мы используем для хранения размеров, мы также можем решить вопрос о максимальном количестве указателей, которое нам когда-либо понадобится хранить в блоке. Если мы установим дополнительную нагрузку на указатели равной размеру блока, то получим следующее уравнение. Обратите внимание, что как меньший размер блока (![B][bigB]), так и большая ширина слова (![w]) приводят к большей дополнительной нагрузке на память.

Решение уравнения для ![B][bigB] даёт нам минимальный размер блока для некоторых распространённых ширин слов:

1. 32-битный CTZ-пропускной список => минимальный размер блока 104 байта
2. 64-битный CTZ-пропускной список => минимальный размер блока 448 байтов

littlefs использует 32-битную ширину слова, поэтому наши блоки могут переполняться указателями, только если они меньше 104 байт. Это лёгкое требование, поскольку на практике большинство размеров блоков начинаются с 512 байт. Пока наш размер блока больше 104 байт, мы можем избежать дополнительной логики, необходимой для обработки переполнения указателей.

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

Однако вычисление пары индекс + смещение по размеру немного сложнее. Мы можем начать с суммирования, которое проходит через все блоки вплоть до нашего заданного размера. Пусть ![B][bigB] будет размером блока в Вот перевод текста на русский язык:

Пусть w будет шириной слова в битах, n — индексом блока в списке пропуска, а N — размером файла в байтах:

N = sum(i=0->n(B-(w/8)(ctz(i)+1)))

Это работает довольно хорошо, но требует времени O(n) для вычисления, что приводит к полному времени чтения файла до O(n² log n). К счастью, это суммирование не требует обращения к диску, поэтому практическое влияние минимально.

Однако, несмотря на интеграцию побитовой операции, мы можем фактически свести это уравнение к форме O(1). Просматривая удивительный ресурс, которым является [Онлайн-энциклопедия целочисленных последовательностей (OEIS)], мне удалось найти [A001511], который соответствует итерации инструкции CTZ, и [A005187], которая соответствует её частичной сумме. К моему большому удивлению, оба они являются результатом простых уравнений, приводящих нас к довольно неожиданному свойству, которое связывает две, казалось бы, несвязанные побитовые инструкции:

sum(i=0->n(ctz(i)+1) = 2n-popcount(n)),

где:

• ctz(x) — количество конечных нулевых битов в x;
• popcount(x) — число битов, равных единице в x.

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

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

N = Bn - (w/8)(2n-popcount(n)).

К сожалению, функция popcount неинъективна, поэтому мы не можем решить это уравнение для нашего индекса. Но что мы можем сделать, так это решить для индекса n' больше n с ошибкой, ограниченной диапазоном функции popcount. Мы можем многократно подставлять n’ в исходное уравнение до тех пор, пока ошибка не станет меньше нашего целочисленного разрешения. Как оказалось, нам нужно выполнить эту подстановку только один раз, что даёт нам следующую формулу для нашего индекса:

n = floor((N-(w/8)popcount(N/(B-2w/8))) / (B-2w/8)).

Теперь, когда у нас есть наш индекс n, мы можем просто подставить его обратно в приведённое выше уравнение, чтобы найти смещение. Мы сталкиваемся с небольшой проблемой целочисленного переполнения, но мы можем избежать этого, немного переставив уравнение:

off = N - (B-2w/8)n - (w/8)popcount(n).

Наше решение требует довольно много математики, но компьютеры очень хороши в математике. Теперь мы можем найти как наш индекс блока, так и смещение из размера за O(1), позволяя нам хранить списки пропуска CTZ только с указателем и размером.

Списки пропуска CTZ дают нам структуру данных COW, которую легко пройти за O(n), можно добавить за O(1) и прочитать за O(n log n). Все эти операции работают в ограниченном объёме оперативной памяти и требуют только двух слов служебных данных на блок. В сочетании с парами метаданных списки пропуска CTZ обеспечивают отказоустойчивость и компактное хранение данных. ### Распределитель блоков

Итак, теперь у нас есть основа для атомарной файловой системы с выравниванием износа. Небольшие пары метаданных из двух блоков обеспечивают атомарные обновления, а списки пропуска CTZ обеспечивают компактное хранение данных в блоках COW.

Но теперь нам нужно взглянуть на проблему. Откуда берутся все эти блоки?

Ответственность за принятие решения о том, какой блок использовать дальше, лежит на распределителе блоков. В дизайне файловых систем распределение блоков часто является второстепенным вопросом, но в файловой системе COW его роль становится гораздо более важной, поскольку оно необходимо почти для каждой записи в файловую систему.

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

littlefs использует осторожный подход. Вместо того чтобы доверять списку свободных блоков на диске, littlefs полагается на тот факт, что файловая система на диске является зеркальным отображением свободных блоков на диске. Распределитель блоков работает во многом как сборщик мусора в скриптовом языке, сканируя неиспользуемые блоки по требованию.

          .----.
          |root|
          |    |
          '----'
   v-------'  '-------v
.----.    .    .    .----.
| A  |    .    .    | B  |
|    |    .    .    |    |
'----'    .    .    '----'
.    .    .    .  v--'  '------------v---------v
.    .    .    .----.    .         .----.    .----.
.    .    .    | C  |    .         | D  |    | E  |
.    .    .    |    |    .         |    |    |    |
.    .    .    '----'    .         '----'    '----'
.    .    .    .    .    .         .    .    .    .
.----.----.----.----.----.----.----.----.----.----.----.----.
| A  |    |root| C  | B  |         | D  |    | E  |         |
|    |    |    |    |    |         |    |    |    |         |
'----'----'----'----'----'----'----'----'----'----'----'----'
        ^                   ^    ^                   ^    ^
         '-------------------'----'-------------------'----'-- свободные блоки

Хотя этот подход может показаться сложным, решение не поддерживать список свободных блоков значительно упрощает общий дизайн littlefs. В отличие от языков программирования, здесь есть только несколько структур данных, которые нам нужно пройти. И блок... Освобождение блоков, которое происходит почти так же часто, как и выделение блоков, является простой операцией no-op. Эта стратегия «брось это на пол» значительно снижает сложность управления структурами данных на диске, особенно при работе с условиями ошибок высокого риска.

Нашему распределителю блоков необходимо эффективно находить свободные блоки. Можно было бы пройти по каждому блоку в хранилище и проверить каждый из них по нашему дереву файловой системы; однако время выполнения было бы ужасным. Нам нужно каким-то образом собирать несколько блоков за один проход.

Рассматривая существующие проекты, некоторые более крупные файловые системы, которые используют аналогичную стратегию «брось его на пол», хранят растровое изображение всего хранилища в оперативной памяти (RAM). Это хорошо работает, потому что растровые изображения удивительно компактны. Мы не можем использовать ту же стратегию здесь, поскольку она нарушает наше постоянное требование к оперативной памяти, но мы можем быть в состоянии модифицировать эту идею в работоспособное решение.

.----.----.----.----.----.----.----.----.----.----.----.----.
| A  |    |root| C  | B  |         | D  |    | E  |         |
|    |    |    |    |    |         |    |    |    |         |
'----'----'----'----'----'----'----'----'----'----'----'----'
  1    0    1    1    1    0    0    1    0    1    0    0
 \---------------------------+----------------------------/
                             v
               bitmap: 0xb94 (0b101110010100)

Распределитель блоков в littlefs представляет собой компромисс между растровым изображением размером с диск и перебором. Вместо растрового изображения размером с хранилище мы отслеживаем небольшое растровое изображение фиксированного размера, называемое буфером опережающего просмотра. Во время выделения блока мы берём блоки из буфера опережающего просмотра. Если буфер опережающего просмотра пуст, мы сканируем файловую систему для получения дополнительных свободных блоков, заполняя наш буфер опережающего просмотра. В каждом сканировании мы используем увеличивающееся смещение, обходя хранилище по кругу по мере выделения блоков.

Вот как может выглядеть выделение 4 блоков в достаточно загруженной файловой системе с 32-битным опережающим просмотром и общим количеством 128 блоков (512 килобайт хранилища, если блоки имеют размер 4 килобайта):

boot...         lookahead:
                fs blocks: fffff9fffffffffeffffffffffff0000
scanning...     lookahead: fffff9ff
                fs blocks: fffff9fffffffffeffffffffffff0000
alloc = 21      lookahead: fffffdff
                fs blocks: fffffdfffffffffeffffffffffff0000
alloc = 22      lookahead: ffffffff
                fs blocks: fffffffffffffffeffffffffffff0000
scanning...     lookahead:         fffffffe
                fs blocks: fffffffffffffffeffffffffffff0000
alloc = 63      lookahead:         ffffffff
                fs blocks: ffffffffffffffffffffffffffff0000
scanning...     lookahead:         ffffffff
                fs blocks: ffffffffffffffffffffffffffff0000
scanning...     lookahead:                 ffffffff
                fs блоков: ffffffffffffffffffffffffffff0000
scanning...     lookahead:                         ffff0000
                fs блоков: ffffffffffffffffffffffffffff0000
alloc = 112     lookahead:                         ffff8000
                fs блоков: ffffffffffffffffffffffffffff8000

Этот подход опережающего просмотра имеет сложность выполнения O(n²) для полного сканирования хранилища; однако растровые изображения удивительно компактны, и на практике обычно требуется только один или два прохода, чтобы найти свободные блоки. Кроме того, производительность распределителя можно оптимизировать, регулируя размер блока или размер буфера опережающего просмотра, обменивая либо детализацию записи, либо оперативную память на производительность распределителя.

Выравнивание износа

У распределителя блоков есть вторая роль: выравнивание износа.

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

littlefs имеет два метода защиты от износа:

1. Обнаружение и восстановление после плохих блоков
2. Равномерное распределение износа по динамическим блокам

Восстановление после плохих блоков на самом деле не имеет ничего общего с самим распределителем блоков. Вместо этого он полагается на способность файловой системы обнаруживать и удалять плохие блоки при их возникновении.

В littlefs довольно просто обнаружить плохие… | | 4 КиБ | | | | | | | | | | | | | | | '----------------' /

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

Строгое связывание пар метаданных и каталогов также даёт пользователям прямой контроль над использованием хранилища в зависимости от того, как они организуют свои каталоги.

Несколько файлов хранятся в паре метаданных, 4 байта стоят ~4 КиБ.

   .----------------.
  .|    revision    |
  ||----------------|
  ||    A name      |
  ||   A skiplist  -----.
  ||----------------|   |  \
  ||    B name      |   |  +- metadata
  ||   B skiplist  ---. |  |  4x8 bytes
  ||----------------| | |  /  32 bytes
  ||    checksum    | | |
  ||----------------| | |
  ||       |        | | |
  ||       v        | | |
  |'----------------' | |
  '----------------'  | |
     .----------------' |
    v                   v

.----------------. .----------------. \
| A data | | B data | +- data | | | |----------------| / 4 bytes | | | | | | | | | | | | | | | | | | | | + data block | | | | 4 КиБ | | | | |----------------| | | | | | | | | | | | | | | '----------------' '----------------' /

Второе улучшение, которое мы можем сделать, заключается в том, что мы замечаем, что для очень маленьких файлов наши попытки использовать списки пропуска CTZ для компактного хранения приводят к обратным результатам. Пары метаданных имеют стоимость хранения примерно в 4 раза больше, поэтому, если наш файл меньше 1/4 размера блока, фактически нет никакой выгоды в хранении нашего файла вне нашей пары метаданных.

В этом случае мы можем сохранить файл непосредственно в нашей паре метаданных каталога. Мы называем это встроенным файлом, и он позволяет каталогу хранить множество небольших файлов довольно эффективно. Наш предыдущий 4-байтовый файл теперь занимает всего лишь теоретически 16 байт на диске.

Встроенные файлы хранятся в паре метаданных, 4 байта стоят ~16 байтов.

.----------------. .| revision | ||----------------| || A name | || A skiplist ---. ||----------------| |
|| B name | | +- data || B data | | | 4x4 bytes ||----------------| | / 16 bytes || checksum | | ||----------------| | || | | | || v | | |'----------------' | '----------------' | .---------' v .----------------. | A data | | | | | | | | | | | | |

Как только файл превышает 1/4 размер блока, мы переходим к списку пропуска CTZ. Это означает, что наши файлы никогда не используют более чем в 4 раза накладные расходы на хранилище, уменьшаясь по мере увеличения размера файла.

Граф стоимости хранения файлов.

Каталоги

Теперь нам просто нужны каталоги для хранения наших файлов. Как упоминалось выше, мы хотим строгого связывания каталогов и пар метаданных, но есть несколько сложностей, которые нам нужно устранить.

Сами по себе каждый каталог представляет собой связанный список пар метаданных. Это позволяет нам хранить неограниченное количество файлов в каждом каталоге, и нам не нужно... Мы не беспокоимся о сложности выполнения (runtime complexity) неограниченного количества журналов. Мы можем хранить другие указатели каталогов в парах метаданных, что даёт нам древовидную структуру каталогов, подобную тем, которые можно найти в других файловых системах.

            .--------.
           .| root   |
           ||        |
           ||        |
           |'--------'
           '---|--|-'
            .-'    '-------------------------.
           v                                  v
      .--------.        .--------.        .--------.
     .| dir A  |------->| dir A  |       .| dir B  |
     ||        |       ||        |       ||        |
     ||        |       ||        |       ||        |
     |'--------'       |'--------'       |'--------'
     '---|--|-'        '----|---'        '---|--|-'
      .-'    '-.            |             .-'    '-.
     v          v           v            v          v
.--------.  .--------.  .--------.  .--------.  .--------.
| file C |  | file D |  | file E |  | file F |  | file G |
|        |  |        |  |        |  |        |  |        |
|        |  |        |  |        |  |        |  |        |
'--------'  '--------'  '--------'  '--------'  '--------'

Основная сложность заключается в обходе дерева с постоянным объёмом оперативной памяти (RAM). Дерево каталогов — это дерево, и, к сожалению, вы не можете обойти дерево с постоянным RAM.

К счастью, элементы нашего дерева — пары метаданных, поэтому, в отличие от списков пропуска CTZ, мы не ограничены строгими операциями COW. Одна вещь, которую мы можем сделать, — это связать список через наше дерево, явно обеспечивая дешёвый обход всей файловой системы.

            .--------.
           .| root   |-.
           ||        | |
   .-------||        |-'
   |       |'--------'
   |       '---|--|-'
   |        .-'    '-------------------------.
   |       v                                  v
   |  .--------.        .--------.        .--------.
   '->| dir A  |------->| dir A  |------->| dir B  |
     ||        |       ||        |       ||        |
     ||        |       ||        |       ||        |
     |'--------'       |'--------'       |'--------'
     '---|--|-'        '----|---'        '---|--|-'
      .-'    '-.            |             .-'    '-.
     v          v           v            v          v
.--------.  .--------.  .--------.  .--------.  .--------.
| file C |  | file D |  | file E |  | file F |  | file G |
|        |  |        |  |        |  |        |  |        |
|        |  |        |  |        |  |        |  |        |
'--------'  '--------'  '--------'  '--------'  '--------'

К сожалению, отказ от чистых операций COW создаёт некоторые проблемы. Теперь, когда мы хотим манипулировать деревом каталогов, необходимо обновить несколько указателей. Если вы знакомы с проектированием атомарных структур данных, это должно вызвать множество красных флагов.

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

Благодаря возможности сиротства мы можем создавать устойчивые к потере питания операции, поддерживающие древовидность файловой системы с связанным списком для обхода.

Добавление каталога в наше дерево:

         .--------.
        .| root   |-.
        ||        | |
.-------||        |-'
|       |'--------'
|       '---|--|-'
|        .-'    '-.
|       v          v
|  .--------.  .--------.
'->| dir A  |->| dir C  |
  ||        | ||        |
  ||        | ||        |
  |'--------' |'--------'
  '--------'  '--------'

выделить каталог B
=>
         .--------.
        .| root   |-.
        ||        | |
.-------||        |-'
|       |'--------'
|       '---|--|-'
|        .-'    '-.
|       v          v
|  .--------.    .--------.
'->| dir A  |--->| dir C  |
  ||        | .->|        |
  ||        | | ||        |
  |'--------' | |'--------'
  '--------'  | '--------'
              |
   .--------. |
  .| dir B  |-'
  ||        |
  ||        |
  |'--------'
  '--------'

вставить каталог B в связанный список Создание «осиротевшего» элемента в связанном списке:

linked-list, creating an orphan => .--------. .| root |-. || | | .-------|| |-' | |'--------' | '---|--|-' | .-' '-------------. | v v | .--------. .--------. .--------. '->| dir A |->| dir B |->| dir C | || | || | || | || | || | || | |'--------' |'--------' |'--------' '--------' '--------' '--------'

Добавление каталога dir B к родительскому каталогу:

add dir B to parent directory => .--------. .| root |-. || | | .-------------|| |-' | |'--------' | '--|-|-|-' | .------' | '-------. | v v v | .--------. .--------. .--------. '->| dir A |->| dir B |->| dir C | || | || | || | || | || | || | |'--------' |'--------' |'--------' '--------' '--------' '--------'

Удаление каталога:

Removing a directory:

               .--------.
              .| root   |-.
              ||        | |
.-------------||        |-'
|             |'--------'
|             '--|-|-|-'
|        .------'  |  '-------.
|       v          v           v
|  .--------.  .--------.  .--------.
'->| dir A  |->| dir B  |->| dir C  |
  ||        | ||        | ||        |
  ||        | ||        | ||        |
  |'--------' |'--------' |'--------'
  '--------'  '--------'  '--------'

remove dir B from parent directory, creating an orphan
=>
         .--------.
        .| root   |-.
        ||        | |
.-------||        |-'
|       |'--------'
|       '---|--|-'
|        .-'    '-------------.
|       v                      v
|  .--------.  .--------.  .--------.
'->| dir A  |->| dir B  |->| dir C  |
  ||        | || orphan!| ||        |
  ||        | ||        | ||        |
  |'--------' |'--------' |'--------'
  '--------'  '--------'  '--------'

Помимо обычных операций с деревом каталогов, мы можем использовать осиротевшие элементы для удаления блоков метаданных, когда блок становится плохим или превышает выделенное количество стираний. Если мы теряем питание во время удаления блока метаданных, может возникнуть ситуация, когда файловая система ссылается на замещающий блок, а связанный список всё ещё содержит удалённый блок. Мы называем это «полуосиротевшим» элементом.

In addition to normal directory tree operations, we can use orphans to evict
blocks in a metadata pair when the block goes bad or exceeds its allocated
erases. If we lose power while evicting a metadata block we may end up with
a situation where the filesystem references the replacement block while the
threaded linked-list still contains the evicted block. We call this a
half-orphan.

           .--------.
          .| root   |-.
          ||        | |

.-------------|| |-' | |'--------' | '--|-|-|-' | .------' | '-------. | v v v | .--------. .--------. .--------. '->| dir A |->| dir B |->| dir C | || | || | || | || | || | || | |'--------' |'--------' |'--------' '--------' '--------' '--------'

Попытка записи в каталог dir B:

try to write to dir B => .--------. .| root |-. || | | .----------------|| |-' | |'--------' | '-|-||-|-' | .--------' || '-----. | v |v v | .--------. .--------. .--------. '->| dir A |---->| dir B |->| dir C | || |-. | | || | || | | | | || | |'--------' | '--------' |'--------' '--------' | v '--------' | .--------. '->| dir B | | bad | | block! | '--------'

oh no! bad block detected, allocate replacement => .--------. .| root |-. || | | .----------------|| |-' | |'--------' | '-|-||-|-' | .--------' || '-------. | v |v

В littlefs глобальное состояние привело к появлению механизма, называемого «глобальное состояние».

Глобальное состояние — это небольшой набор состояний, который можно обновить из любой пары метаданных. Объединение глобального состояния с возможностью обновления нескольких записей в одной фиксации даёт нам мощный инструмент для создания сложных атомарных операций.

Как работает глобальное состояние?

Глобальное состояние существует как набор дельт, которые распределены по парам метаданных в файловой системе. Фактическое глобальное состояние может быть построено из этих дельт путём применения операции XOR ко всем дельтам в файловой системе.

Чтобы обновить глобальное состояние из пары метаданных, мы берём известное глобальное состояние и применяем операцию XOR к нашим изменениям и любой существующей дельте в паре метаданных. Фиксация этой новой дельты в паре метаданных фиксирует изменения в глобальном состоянии файловой системы.

Для повышения эффективности мы всегда храним копию глобального состояния в оперативной памяти. Нам нужно только перебрать наши пары метаданных и построить глобальное состояние, когда файловая система смонтирована.

Возможно, вы заметили, что глобальное состояние очень затратно. Мы храним копию в оперативной памяти и дельту в неограниченном количестве пар метаданных. Даже если мы сбросим глобальное состояние до его начального значения, мы не сможем легко очистить дельты на диске. По этой причине очень важно, чтобы мы сохраняли размер глобального состояния ограниченным и чрезвычайно малым. Но даже при строгом бюджете глобальное состояние невероятно ценно.

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

$\lim_{n \to \infty} \frac{1}{n} \sum_{i=0}^n (ctz(i) + 1) = \sum_{i=0} \frac{1}{2^i} = 2$

[ctz-formula2]: $B = \frac{w}{8} \left\lceil \log_2 \left( \frac{2^{w}}{B - 2 \cdot \frac{w}{8}} \right) \right\rceil$

[ctz-formula3]: $N = \sum_i^n \left[ B - \frac{w}{8} (ctz(i) + 1) \right]$

[ctz-formula4]: $\sum_i^n (ctz(i) + 1) = 2n - popcount(n)$

[ctz-formula5]: $N = Bn - \frac{w}{8}(2n - popcount(n))$

[ctz-formula6]: $n = \left\lfloor \frac{N - \frac{w}{8}\left(popcount \left(\frac{N}{B - 2\cdot\frac{w}{8}} - 1\right) + 2\right)}{B - 2\cdot\frac{w}{8}}\right\rfloor$

[ctz-formula7]: $off = N - (B - 2\cdot \frac{w}{8})n - \frac{w}{8}popcount(n)$.

Также в тексте запроса есть ссылки на изображения и некоторые переменные, которые не удалось перевести.