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

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

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

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

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

## littlefs

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

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

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

Рассмотрим ведение журнала. Оно имеет либо квадратичную сложность по времени выполнения или линейную по объёму используемой оперативной памяти. Мы не можем избежать этих затрат, *но* если мы установим верхний предел размера, мы, по крайней мере, сможем предотвратить превращение теоретической стоимости в проблему. Это опирается на суперсекретный хакерский приём в информатике, где вы можете притвориться, что любая алгоритмическая сложность равна 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 (размер/n);
d = (1 - r) (размер/n).

Подставляя их вместо d и s, получаем хорошую формулу стоимости обновления записи с учётом степени заполнения лога:

cost = n + n (r (размер/n) / ((1-r) (размер/n) + 1)).

Предполагая, что размер записи составляет 100 байт в 4 КБ логе, мы можем построить график, используя размер записи, чтобы найти мультипликативную стоимость:

График стоимости обновления пары метаданных.

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

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

**Если мы рассмотрим пары метаданных и связанные списки пар метаданных на высоком уровне, у них будет довольно хорошая стоимость времени выполнения.**

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

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

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

$N = \sum_{i=0}^{n}(B - (w/8)(ctz(i) + 1))$, где ctz — формула 3.

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

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

$\sum_{i=0}^{n} (ctz(i)+1) = 2^n - popcount(n)$, где:
* ctz($x$) — количество конечных нулевых битов в $x$;
* popcount($x$) — число битов, равных единице в $x$.

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

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

$N = Bn - (w/8)(2^n - popcount(n))$, где — формула 5.

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

$n = floor((N-(w/8)popcount(N/(B-2w/8))) / (B-2w/8))$, где — формула 6.

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

$off = N - (B-2w/8)n - (w/8)popcount(n)$, где — формула 7.

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

Списки пропуска CTZ дают нам структуру данных COW, которую легко пройти за $O(n)$, можно добавить за $O(1)$ и прочитать за $O(n log n)$. Все эти операции работают в ограниченном объёме оперативной памяти и требуют только двух слов служебных данных на блок. В сочетании с парами метаданных списки пропуска CTZ обеспечивают отказоустойчивость и компактное хранение данных. **Освобождение памяти**, которое происходит почти так же часто, как выделение блока,
является простой операцией no-op. Эта стратегия «брось это на пол» значительно снижает
сложность управления структурами данных на диске, особенно при обработке
условий с высоким риском ошибки.

---

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

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

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

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

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

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

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

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

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

---

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

В littlefs довольно просто обнаружить плохие блоки... Блоки при записи.

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

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

Фактический процесс удаления плохого блока и замены его новым блоком остаётся за структурами данных файловой системы copy-on-bounded-writes (CObW). Одним из свойств структур данных CObW является то, что любой блок может быть заменён во время операции COW. Часть с ограниченными записями обычно запускается счётчиком, но ничто не мешает нам запустить операцию COW, как только мы найдём плохой блок. Мы можем обнаружить, что новый блок также является плохим, но, будем надеяться, после повторения этого цикла мы в конечном итоге найдём новый блок, где запись будет успешной. Если нет, это означает, что все блоки в нашем хранилище являются плохими, и мы достигли конца срока службы нашего устройства. На этом этапе littlefs вернёт ошибку «недостаточно места». Технически это верно, так как больше нет хороших блоков, но в качестве дополнительного преимущества это также соответствует состоянию ошибки, ожидаемому пользователями данных динамического размера.

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

ECC — это расширение идеи контрольной суммы. В то время как контрольная сумма, такая как CRC, может обнаружить, что в данных произошла ошибка, ECC может обнаруживать и фактически исправлять некоторое количество ошибок. Однако существует предел тому, сколько ошибок может обнаружить ECC: граница Хэмминга. По мере приближения количества ошибок к границе Хэмминга мы всё ещё можем обнаруживать ошибки, но уже не можем исправить данные. Если мы достигли... На данный момент блок является невосстановимым.

Littlefs сам по себе **не** предоставляет ECC. Блоковая природа и относительно большой объём ECC плохо сочетаются с динамически изменяемыми размерами данных файловых систем, исправление ошибок без оперативной памяти затруднительно, а ECC лучше сочетается с геометрией блочных устройств. Фактически, некоторые микросхемы NOR-флеш имеют дополнительное хранилище, предназначенное для ECC, и многие микросхемы NAND могут даже вычислять ECC на самом чипе.

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

---

Чтобы избежать ошибок чтения, мы должны действовать на опережение, в отличие от того, как мы реагировали на ошибки записи.

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

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

Как правило, алгоритмы распределения износа делятся на две категории:

1. Динамическое распределение износа, при котором мы распределяем износ по «динамическим» блокам. Этого можно достичь, рассматривая только неиспользуемые блоки.

2. Статическое распределение износа, при котором мы распределяем износ как по «динамическим», так и по «статическим» блокам. Чтобы это работало, нам нужно учитывать все блоки, включая блоки, которые уже содержат данные.

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

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

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

![График кумулятивного распределения износа][wear-distribution-graph]

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

Мы действительно можем использовать данные на диске для непосредственного управления нашим генератором случайных чисел. На практике это реализуется путём xor-инга контрольных сумм каждой пары метаданных, которая уже рассчитана для извлечения и монтирования файловой системы. | |                                  |         |
|---| .--------------> xor ------------> xor
|    | ^       |         ^
| v  crc       crc      v        crc
.--------. \  ^   .--------. \  ^   .--------. \  ^
.|metadata|-|--|-->|metadata| |  |  .|metadata| |  |
||        | +--'  ||        | +--'  ||        | +—'
||        | |     ||        | |     ||        | |
|'--------' /     |'--------' /     |'--------' /
'---|--|-'        '----|---'        '---|--|-'
.-'    '-.            |             .-'    '-.
v          v           v            v          v
.--------.  .--------.  .--------.  .--------.  .--------.
| data  |  | data  |  | data  |  | data  |  | data  |
|        |  |        |  |        |  |        |  |        |
|        |  |        |  |        |  |        |  |        |
'--------'  '--------'  '--------'  '--------'  '--------'

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

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

## Файлы
Теперь, когда у нас есть строительные блоки, мы можем начать рассматривать нашу файловую систему в целом.
Первый шаг: как мы на самом деле храним наши файлы?
Мы определили, что списки пропуска CTZ довольно хороши для компактного хранения данных, поэтому, следуя прецеденту, найденному в других файловых системах, мы могли бы дать каждому файлу список пропуска, хранящийся в паре метаданных, которая действует как индексный дескриптор файла.

Однако это не работает хорошо, когда файлы маленькие, что характерно для встроенных систем. По сравнению с ПК все данные во встроенной системе малы.
Рассмотрим небольшой 4-байтовый файл. С двухблочной парой метаданных и одним блоком для списка пропуска CTZ мы обнаруживаем, что используем целых 3 блока. На большинстве NOR flash с 4 KiB блоками это составляет 12 KiB накладных расходов. Нелепое увеличение в 3072 раза.

Файл хранится как индексный дескриптор, 4 байта стоят ~12 КиБ.

 .----------------.                  \
.|    revision    |                  |
||----------------|    \             |
||    skiplist   ---.  +- metadata   |
||----------------| |  /  4x8 bytes  |
||    checksum    | |     32 bytes   |
||----------------| |                |
||       |        | |                +- metadata pair
||       v        | |                |  2x4 КиБ
||                | |                |  8 КиБ
||                | |                |
||                | |                |
||                | |                |
|'----------------' |                |
'----------------'  |                /
          .--------'
         v
 .----------------.    \             \
 |      data      |    +- data       |
 |----------------|    /  4 bytes    |
 |                |                  |
 |                |                  |
 |                |                  |
 |                |                  +- data block |                  |  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

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

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

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

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

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

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

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

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

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

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

               .--------.
              .| 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   |-.
          ||        | |

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

**Если бы у нас было какое-то глобальное состояние**, мы могли бы также сохранить флаг и избегать поиска потерянных объектов, если бы не знали, что были специально прерваны во время манипуляции с деревом каталогов (предзнаменование!).

### Проблема перемещения

У нас есть ещё одна проблема: проблема перемещения. Сформулировать проблему просто:

Как атомарно переместить файл между двумя каталогами?

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

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

Итак, что мы можем сделать?

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

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

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

В конце концов, решение проблемы перемещения потребовало создания нового механизма совместного использования. **Глобальное состояние**

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

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

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

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

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

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

Теперь мы можем решить проблему перемещения. Мы можем создать глобальное состояние, описывающее наше перемещение атомарно с созданием нового файла, и мы можем очистить это состояние перемещения атомарно с удалением старого файла. |
   '--------'

begin move, add reference in dir C, change gstate to have move
=>
               .--------.    gstate = moving file D in dir A (m1)
              .| root   |-.
              ||        | |
.-------------||        |-'
|             |'--------'
|             '--|-|-|-'
|        .------'  |  '-------.
|       v          v           v
|  .--------.  .--------.  .--------.
'->| dir A  |->| dir B  |->| dir C  |
  ||        | ||        | || gdelta |
  ||        | ||        | || =m1    |
  |'--------' |'--------' |'--------'
  '----|---'  '--------'  '----|---'
       |     .----------------'
       v    v
     .--------.
     | file D |
     |        |
     |        |
     '--------'

complete move, remove reference in dir A, change gstate to no move
=>
               .--------.    gstate = no move (m1^~m1)
              .| root   |-.
              ||        | |
.-------------||        |-'
|             |'--------'
|             '--|-|-|-'
|        .------'  |  '-------.
|       v          v           v
|  .--------.  .--------.  .--------.
'->| dir A  |->| dir B  |->| dir C  |
  || gdelta | ||        | || gdelta |
  || =~m1   | ||        | || =m1    |
  |'--------' |'--------' |'--------'
  '--------'  '--------'  '----|---'
                               v
                           .--------.
                           | file D |
                           |        |
                           |        |
                           '--------'

                 .--------.    gstate = moving file D in dir A (m1)
                .| root   |-.             ^
                ||        |------------> xor
.---------------||        |-'             ^
|               |'--------'               |
|               '--|-|-|-'                |
|        .--------'  |  '---------.       |
|       |            |             |      |
|       |     .----------> xor --------> xor
|       v     |      v      ^      v      ^
|  .--------. |  .--------. |  .--------. |
'->| dir A  |-|->| dir B  |-|->| dir C  | |
  ||        |-' ||        |-' || gdelta |-'
  ||        |   ||        |   || =m1    |
  |'--------'   |'--------'   |'--------'
  '----|---'    '--------'    '----|---'
       |     .---------------------'
       v    v
     .--------.
     | file D |
     |        |
     |        |
     '--------'
We can also move directories the same way we move files. There is the threaded linked-list to consider, but leaving the threaded linked-list unchanged works fine as the order doesn't really matter.

           .--------.    gstate = no move (m1^~m1)
          .| root   |-.
          ||        | |

Global state gives us a powerful tool we can use to solve the move problem. And the result is surprisingly performant, only needing the minimum number of states and using the same number of commits as a naive move. Additionally, global state gives us a bit of persistent state we can use for some other small improvements.
## Conclusion
And that's littlefs, thanks for reading!

[wikipedia-flash]: https://ru.wikipedia.org/wiki/Флеш-память
[wikipedia-sna]: https://ru.wikipedia.org/wiki/Арифметика_последовательных_номеров
[wikipedia-crc]: https://ru.wikipedia.org/wiki/Циклический_избыточный_код
[wikipedia-cow]: https://ru.wikipedia.org/wiki/Copy-on-write
[wikipedia-B-tree]: https://ru.wikipedia.org/wiki/B-дерево
[wikipedia-B+-tree]: https://ru.wikipedia.org/wiki/B%2B_дерево
[wikipedia-skip-list]: https://ru.wikipedia.org/wiki/Список_пропусков
[wikipedia-ctz]: https://ru.wikipedia.org/wiki/Подсчёт_количества_нулей_в_конце_двоичного_представления
[wikipedia-ecc]: https://ru.wikipedia.org/wiki/Обнаружение_и_исправление_ошибок
[wikipedia-hamming-bound]: https://ru.wikipedia.org/wiki/Граница_Хэмминга
[wikipedia-dynamic-wear-leveling]: https://ru.wikipedia.org/wiki/Динамическое_равномерное_распределение_стираний
[wikipedia-static-wear-leveling]: https://ru.wikipedia.org/wiki/Статическое_равномерное_распределение_стираний
[wikipedia-ftl]: https://ru.wikipedia.org/wiki/Flash_Translation_Layer

[oeis]: https://oeis.org
[A001511]: https://oeis.org/A001511
[A005187]: https://oeis.org/A005187

[fat]: https://ru.wikipedia.org/wiki/Файловая_система_FAT
[ext2]: http://e2fsprogs.sourceforge.net/ext2intro.html
[jffs]: https://www.sourceware.org/jffs2/jffs2-html
[yaffs]: https://yaffs.net/documents/how-yaffs-works
[spiffs]: https://github.com/pellepl/spiffs/blob/master/docs/TECH_SPEC
[ext4]: https://ext4.wiki.kernel.org/index.php/Ext4_Design
[ntfs]: https://ru.wikipedia.org/wiki/NTFS
[btrfs]: https://btrfs.wiki.kernel.org/index.php/Btrfs_design
[zfs]: https://ru.wikipedia.org/wiki/ZFS

[cow]: https://upload.wikimedia.org/wikipedia/commons/0/0c/Cow_female_black_white.jpg
[elephant]: https://upload.wikimedia.org/wikipedia/commons/3/37/African_Bush_Elephant.jpg
[ram]: https://upload.wikimedia.org/wikipedia/commons/9/97/New_Mexico_Bighorn_Sheep.JPG

[metadata-formula1]: https://latex.codecogs.com/svg.latex?cost%20%3D%20n%20+%20n%20%5Cfrac%7Bs%7D%7Bd+1%7D
[metadata-formula2]: https://latex.codecogs.com/svg.latex?s%20%3D%20r%20%5Cfrac%7Bsize%7D%7Bn%7D
[metadata-formula3]: https://latex.codecogs.com/svg.latex?d%20%3D%20%281-r%29%20%5Cfrac%7Bsize%7D%7Bn%7D
[metadata-formula4]: https://latex.codecogs.com/svg.latex?cost%20%3D%20n%20+%20n%20%5Cfrac%7Br%5Cfrac%7Bsize%7D%7Bn%7D%7D%7B%281-r%29%5Cfrac%7Bsize%7D%7Bn%7D+1%7D

[ctz-formula1]:

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

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

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