Моя реализация кольцевого буфера в NOR flash

Предыстория


Есть торговые автоматы собственной разработки. Внутри Raspberry Pi и немного обвязки на отдельной плате. Подключены монетоприёмник, купюроприёмник, банковский терминал… Управляет всем самописная программа. Вся история работы пишется в журнал на флешке (MicroSD), который потом передаётся через интернет (с помощью USB-модема) на сервер, там складывается в БД. Информация о продажах загружается в 1с, также есть простенький веб-интерфейс для мониторинга и т.п.


То есть журнал жизненно необходим — для учёта (там выручка, продажи и т.д.), мониторинга (всевозможные сбои и другие форс-мажорные обстоятельства); это, можно сказать, вся информация, которая у нас об этом автомате.


Проблема


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


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


Внимание! Лонгрид! Если вам неинтересно "почему", а интересно только "как", можете сразу идти в конец статьи.


Решение


Первое, что приходит в голову: отказаться от MicroSD, поставить, например, SSD, и грузиться с него. Теоретически возможно, наверное, но относительно дорого, и не так уж надёжно (добавляется переходник USB-SATA; по бюджетным SSD статистика отказов тоже не радует).


USB HDD тоже не выглядит особо привлекательным решением.


Поэтому пришли к такому варианту: оставить загрузку с MicroSD, но использовать их в режиме read-only, а журнал работы (и другую уникальную для конкретной железки информацию — серийный номер, калибровки датчиков, etc) хранить где-то ещё.


Тема read-only ФС для малинки уже изучена вдоль и поперёк, я не буду останавливаться на деталях реализации в этой статье (но если будет интерес — быть может и напишу мини-статью на эту тему). Единственный момент, который хочется отметить: и по личном опыту, и по отзывам уже внедривших выигрыш в надёжности есть. Да, полностью избавиться от поломок невозможно, однако существенно снизить их частоту — вполне реально. Да и карточки становятся унифицированными, что заметно упрощает замену для обслуживающего персонала.


Аппаратная часть


С выбором типа памяти особых сомнений не было — NOR Flash.
Аргументы:


  • простое подключение (чаще всего шина SPI, опыт использования которой уже есть, так что "железных" проблем не предвидится);
  • смешная цена;
  • стандартный протокол работы (реализация есть уже в ядре Linux, при желании можно взять стороннюю, которые тоже присутствуют, или даже написать свою, благо всё просто);
  • надёжность и ресурс:
    из типичного даташита: данные хранятся 20 лет, 100000 циклов erase для каждого блока;
    из сторонних источников: крайне низкий BER, постулируется отсутствие необходимости в кодах коррекции ошибок (в некоторых работах рассматривается ECC для NOR, но обычно всё-таки там имеют в виду MLC NOR, бывает и такое).

Прикинем требования к объёму и ресурсу.


Хочется, чтобы гарантированно сохранялись данные за несколько дней. Нужно это для того, чтобы в случае каких-либо проблем со связью история продаж не была потеряна. Будем ориентироваться на 5 дней, за этот срок (даже с учётом выходных и праздников) можно решить проблему.


У нас сейчас за сутки набирается около 100кб журнала (3-4 тысячи записей), однако постепенно эта цифра растёт — увеличивается детализация, добавляются новые события. Плюс иногда бывают всплески (какой-нибудь датчик начинает спамить ложными срабатываниями, например). Будем рассчитать на 10 тысяч записей по 100 байт — мегабайт в сутки.


Итого выходит 5Мб чистых (хорошо сжимаемых) данных. К ним ещё (грубая прикидка) 1Мб служебных данных.


То есть нам нужна микросхема на 8Мб если не использовать сжатие, или 4Мб если использовать. Вполне реальные цифры для этого типа памяти.


Что же до ресурса: если мы планируем, что память целиком будет переписываться не чаще, чем раз в 5 дней, то за 10 лет службы мы получаем менее тысячи циклов перезаписи.
Напоминаю, производитель обещает сто тысяч.


Немного про NOR vs NAND

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


В качестве недостатков NOR можно указать:


  • малый объём (и, соответственно, высокая цена за мегабайт);
  • невысокая скорость обмена (во многом из-за того, что используется последовательный интерфейс, обычно SPI или I2C);
  • медленный erase (в зависимости от размера блока, он занимает от долей секунды, до нескольких секунд).

Вроде бы ничего критичного для нас, так что продолжаем.


Если интересны детали, была выбрана микросхема at25df321a (впрочем, это несущественно, на рынке куча аналогов, совместимых по распиновке и системе команд; даже если мы захотим поставить микросхему одругого производителя и/или другого объёма, то всё заработает без изменения кода).


Я использую встроенный в ядро Linux драйвер, на Raspberry благодаря поддержке device tree overlay всё очень просто — нужно положить в /boot/overlays скомпилированный оверлей и немного модифицировать /boot/config.txt.


Пример dts файла

Честно говоря, не уверен, что написано без ошибок, но работает.


/*
 * Device tree overlay for at25 at spi0.1
 */

/dts-v1/;
/plugin/;

/ {
    compatible = "brcm,bcm2835", "brcm,bcm2836", "brcm,bcm2708", "brcm,bcm2709"; 

    /* disable spi-dev for spi0.1 */
    fragment@0 {
        target = <&spi0>;
        __overlay__ {
            status = "okay";
            spidev@1{
                status = "disabled";
            };
        };
    };

    /* the spi config of the at25 */
    fragment@1 {
        target = <&spi0>;
        __overlay__ {
            #address-cells = <1>;
            #size-cells = <0>;
            flash: m25p80@1 {
                    compatible = "atmel,at25df321a";
                    reg = <1>;
                    spi-max-frequency = <50000000>;

                    /* default to false:
                    m25p,fast-read ;
                    */
            };
        };
    };

    __overrides__ {
        spimaxfrequency = <&flash>,"spi-max-frequency:0";
        fastread = <&flash>,"m25p,fast-read?";
    };
};

И ещё строчка в config.txt
dtoverlay=at25:spimaxfrequency=50000000

Описание самого подключения микросхемы к Raspberry Pi опущу. С одной стороны, я не специалист в электронике, с другой — тут всё банально даже для меня: у микросхемы всего 8 ног, из которых нам нужны земля, питание, SPI (CS, SI, SO, SCK); уровни совпадают с таковыми у Raspberry Pi, никакой дополнительной обвязки не требуется — просто соединить указанные 6 контактов.


Постановка задачи


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


Итак, мы определились с тем, что журнал будет храниться в SPI NOR Flash.


Что такое NOR Flash для тех, кто не знает

Это энергонезависимая память, с которой можно делать три операции:


  1. Чтение:
    Самое обычное чтение: передаём адрес и читаем столько байт, сколько нам нужно;
  2. Запись:
    Запись в NOR flash выглядит как обычная, но у неё есть одна особенность: можно только менять 1 на 0, но не наоборот. Например, если у нас в ячейке памяти лежало 0x55, то после записи в неё 0x0f там уже будет храниться 0x05 (см. таблицу чуть ниже);
  3. Erase:
    Разумеется, нам нужно уметь делать и обратную операцию — менять 0 на 1, именно для этого и существует операция erase. В отличие от первых двух, она оперирует не байтами, а блоками (минимальный erase block в выбранной микросхеме — 4кб). Erase уничтожает весь блок целиком и это единственный способ поменять 0 на 1. Поэтому, при работе с флеш-памятью часто приходится выравнивать структуры данных на границу erase block.
    Запись в NOR Flash:

Двоичные данные
Было 01010101
Записали 00001111
Стало 00000101

Сам журнал представляет последовательность записей переменной длины. Типичная длина записи около 30 байт (хотя иногда случаются и записи длиной в несколько килобайт). В данном случае мы работаем с ними просто как с набором байт, но, если интересно, внутри записей используется CBOR


Помимо журнала, нам нужно хранить некоторую "настроечную" информацию, как обновляемую, так и нет: некий ID аппарата, калибровки датчиков, флаг "аппарат временно отключен", etc.
Эта информация представляет из себя набор записей key-value, также хранится в CBOR.Этой информации у нас не очень много (максимум несколько килобайт), обновляется она нечасто.
В дальнейшем будем называть её контекстом.


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


Какие источники проблем можно рассмотреть?


  • Отключение питания в момент операций write/erase. Это из разряда "против лома нет приёма".
    Информация из обсуждения на stackexchange: при отключении питания в момент работы с flash что erase (установка в 1), что write (установка в 0) приводят к undefined behavior: данные могут записаться, записаться частично (скажем, мы передали 10 байт/80 бит, а успели записаться только 45 бит), не исключено и то, что часть битов окажется в "промежуточном" состоянии (чтение может выдать как 0, так и 1);
  • Ошибки самой flash-памяти.
    BER хоть и очень низок, но не может быть равным нулю;
  • Ошибки по шине
    Данные, передаваемые по SPI никак не защищены, вполне могут случиться как одиночные битовые ошибки, так и ошибки синхронизации — потеря или вставка бит (что приводит к массовым искажениям данных);
  • Прочие ошибки/сбои
    Ошибки в коде, "глюки" Raspberry, вмешательство инопланетян...

Я сформулировал требования, выполнение которых, на мой взгляд, необходимо для обеспечения надёжности:


  • записи должны попадать во флеш-память сразу, отложенная запись не рассматривается;- если ошибка возникла, то она должна обнаруживаться и обрабатываться как можно раньше;- система должна по возможности восстанавливать работу после ошибок.
    (пример из жизни "как не должно быть", с которым, думаю, все встречались: после аварийной перезагрузки "побилась" файловая система и операционная система не грузится)

Идеи, подходы, размышления


Когда я начал думать над этой задачей, то в голове проносилась куча идей, например:


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

Часть этих идей была использована, от части было решено отказаться. Давайте по порядку.


Сжатие данных


Сами события, которые мы фиксируем в журнале, достаточно однотипные и повторяемые ("кинули монетку 5 рублей", "нажали на кнопку выдачи сдачи", ...). Поэтому сжатие должно оказаться достаточно эффективным.


Накладные расходы на сжатие несущественны (процессор у нас достаточно мощный, даже на первом Pi было одно ядро с частотой 700МГц, на актуальных моделях несколько ядер с частотой свыше гигагерца), скорость обмена с хранилищем невысокая (несколько мегабайт в секунду), размер записей невелик. В общем, если сжатие и окажет влияние на производительность, то только положительное (абсолютно некритично, просто констатирую). Плюс у нас же не настоящий embedded, а обычный Linux — так что реализация не должна потребовать много усилий (достаточно просто прилинковать библиотеку и использовать несколько функций из неё).


Был взят кусок лога с работающего устройства (1.7Мб, 70 тысяч записей) и для начала проверен на сжимаемость с помощью имеющихся на компьютере gzip, lz4, lzop, bzip2, xz, zstd.


  • gzip, xz, zstd показали близкие результаты (40Кб).
    Удивило, что модный xz показал тут себя на уровне gzip или zstd;
  • lzip с настройками по умолчанию дал чуть худший результат;
  • lz4 и lzop показали не очень хороший результат (150Кб);
  • bzip2 показал на удивление хороший результат (18Кб).

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


Давайте подумаем о недостатках.


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


Я вижу три пути:


  1. Сжимать каждую запись с помощью словарного сжатия вместо рассмотренных выше алгоритмов.
    Вполне рабочий вариант, но мне он не нравится. Для обеспечения более-менее приличного уровня сжатия словарь должен быть "заточен" под конкретные данные, любое изменение приведёт к тому, что уровень сжатия катастрофически падает. Да, проблема решается созданием новой версии словаря, но это же головная боль — нам нужно будет хранить все версии словаря; в каждой записи нам нужно будет указывать с какой версией словаря она была сжата...
  2. Сжимать каждую запись "классическими" алгоритмами, но независимо от других.
    Рассматриваемые алгоритмы компрессии не рассчитаны на работу с записями такого размера (десятки байт), коэффициент сжатия будет явно меньше 1 (то есть увеличение объёма данных вместо сжатия);
  3. Делать FLUSH после каждой записи.
    Во многих библиотеках сжатия есть поддержка FLUSH. Это команда (или параметр к процедуре сжатия), получив которую архиватор формирует сжатый поток так, чтобы чтобы на его основании можно восстановить все несжатые данные, которые уже были получены. Такой аналог sync в файловых системах или commit в sql.
    Что важно, последующие операции сжатия смогут использовать накопленный словарь и степень сжатия не будет страдать так сильно, как в предыдущем варианте.

Думаю очевидно, что я выбрал третий вариант, остановимся на нём подробнее.


Нашлась отличная статья про FLUSH в zlib.


Сделал по мотивам статьи наколенный тест, взял 70 тысяч записей журнала с реального устройства, при размере страницы в 60Кб (к размеру страницы мы ещё вернёмся) получил:


Исходные данные Сжатие gzip -9 (без FLUSH) zlib с Z_PARTIAL_FLUSH zlib с Z_SYNC_FLUSH
Объём, Кб 1692 40 352 604

На первый взгляд цена, вносимая FLUSH чрезмерно высока, однако на самом деле у нас небогатый выбор — или не сжимать вовсе, или сжимать (и весьма эффективно) с FLUSH. Не надо забывать, что у нас 70 тысяч записей, избыточность, вносимая Z_PARTIAL_FLUSH составляет всего 4-5 байт на запись. А коэффициент сжатия оказался почти 5:1, что более, чем отличный результат.


Может показаться неожиданным, но на самом деле Z_SYNC_FLUSH - более эффективный способ делать FLUSH

В случае использования Z_SYNC_FLUSH 4 последних байта каждой записи всегда будут 0x00, 0x00, 0xff, 0xff. А если они нам известны — то мы можем их не хранить, таким образом итоговый размер оказывается всего 324Кб.


В статье, на которую я ссылаюсь, есть объяснение:


A new type 0 block with empty contents is appended.

A type 0 block with empty contents consists of:
  • the three-bit block header;
  • 0 to 7 bits equal to zero, to achieve byte alignment;
  • the four-byte sequence 00 00 FF FF.

Как несложно заметить, в последнем блоке перед этими 4 байтами идёт от 3 до 10 нулевых бит. Однако практика показала, что нулевых бит на самом деле минимум 10.


Оказывается, столь короткие блоки данных обычно (всегда?) кодируются с помощью блока типа 1 (fixed block), который обязательно заканчивается 7 нулевыми битами, итого получаем 10-17 гарантированно нулевых бит (а остальные будут нулевыми с вероятностью около 50%).


Итак, на тестовых данных в 100% случаев перед 0x00, 0x00, 0xff, 0xff идёт один нулевой байт, а более, чем в трети случае — два нулевых байта (возможно, дело в том, что я использую бинарный CBOR, а при использовании текстового JSON чаще встречались бы блоки типа 2 — dynamic block, соответсвенно встречались бы блоки без дополнительных нулевых байт перед 0x00, 0x00, 0xff, 0xff).


Итого на имеющихся тестовых данных можно уложиться в менее, чем 250Кб сжатых данных.


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


Итого, я из своих тестовых данных получил 3-4 байта на запись, коэффициент сжатия получился более 6:1. Честно скажу: я на такой результат и не рассчитывал, на мой взгляд всё, что лучше 2:1 — уже результат, оправдывающий использование сжатия.


Всё отлично, но zlib (deflate) — всё-таки архаичный заслуженный и немного старомодный алгоритм сжатия. Уже одно то, что в качестве словаря используются последние 32Кб из потока несжатых данных, сегодня выглядит странным (то есть если какой-то блок данных очень похож на то, что было во входном потоке 40Кб назад, то он начнёт архивироваться заново, а не будет ссылаться на прошлое вхождение). В модных современных архиваторах размер словаря чаще измеряется мегабайтами, а не килобайтами.


Так что продолжаем наше мини-исследование архиваторов.


Следующим был опробован bzip2 (напоминаю, без FLUSH он показал фантастическую степень сжатия, почти 100:1). Увы, с FLUSH он показал себя очень плохо, размер сжатых данных оказался больше, чем несжатых.


Мои предположения о причинах провала

Libbz2 предлагает всего один вариант flush, который, похоже, очищает словарь (аналог Z_FULL_FLUSH в zlib), говорить о каком-то эффективном сжатии после этого не приходится.


И последним был опробован zstd. В зависимости от параметров он сжимает или на уровне gzip, но гораздо быстрее, или же лучше gzip.


Увы, с FLUSH и он показал себя "не очень": размер сжатых данных вышел около 700Кб.


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


На этом я решил остановиться в экспериментах с архиваторами (напомню, xz, lzip, lzo, lz4 не показали себя ещё на этапе тестирования без FLUSH, а рассматривать более экзотические алгоритмы сжатия я не стал).


Возвращаемся к проблемам архивации.


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


Есть подхода к решению этой проблемы:


  1. Предупреждать появление проблемы — добавлять в сжатые данные избыточность, которая позволит определять и исправлять ошибки; об этом мы поговорим позже;
  2. Минимизировать последствия в случае возникновения проблемы
    Мы уже говорили ранее, что можно каждый блок данных сжимать независимо, при этом проблема исчезнет сама собой (порча данных одного блока приведёт к потере данных только этого блока). Однако, это крайний случай, при котором сжатие данных будет неэффективно. Противоположная крайность: использовать все 4Мб нашей микросхемы как единый архив, что даст нам отличное сжатие, но катастрофические последствия в случае порчи данных.
    Да, нужен компромисс с точки зрения надёжности. Но нужно помнить, что мы разрабатываем формат хранения данных для энергонезависимой памяти с крайне низким BER и декларируемым сроком хранения данных 20 лет.

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


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


Хоть у меня пока и не предвидится записей больше единиц килобайт в сжатом виде, я решил использовать страницы размером 32Кб (итого получается 128 страниц на микросхему).


Резюме:


  • Данные мы храним сжатыми с помощью zlib (deflate);
  • Для каждой записи устанавливаем Z_SYNC_FLUSH;
  • У каждой сжатой записи обрезаем конечные байты (например, 0x00, 0x00, 0xff, 0xff); в заголовке указываем как много байт мы отрезали;
  • Данные храним страницами по 32Кб; внутри страницы идёт единый поток сжатых данных; на каждой странице сжатие начинаем заново.

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


Хранение заголовков данных


Так как у нас записи переменной длины, то нам нужно как-то определять размещение/границы записей.


Я знаю три подхода:


  1. Все записи хранятся в непрерывном потоке, сначала идёт заголовок записи, содержащий длину, а потом сама запись.
    В этом варианте и заголовки, и данные могут иметь переменную длину.
    По сути, у нас получается односвязный список, который используется сплошь и рядом;
  2. Заголовки и сами записи хранятся в раздельных потоках.
    Используя заголовки постоянной длины, мы добиваемся того, что порча одного заголовка не влияет на остальные.
    Подобный подход используется, например, во многих файловых системах;
  3. Записи хранятся в непрерывном потоке, граница записи определяется по некоторому маркеру (символу/последовательности символов, который/которая запрещены внутри блоков данных). Если внутри записи встречается маркер, то мы заменяем его на некоторую последовательность (экранируем его).
    Подобный подход используется, например, в протоколе PPP.

Проиллюстрирую.


Вариант 1:
Вариант 1
Тут всё очень просто: зная длину записи мы можем вычислить адрес следующего заголовка. Так мы перемещаемся по заголовкам, пока не встретим область, заполненную 0xff (свободную область) или конец страницы.


Вариант 2:
Вариант 2
Из-за переменной длины записи мы не можем заранее сказать как много записей (а значит и заголовков) на страницу нам потребуется. Можно разнести заголовки и сами данные по разным страницам, но мне симпатичнее другой подход: и заголовки, и данные размещаем на одной странице, однако заголовки (постоянного размера) у нас идут от начала страницы, а данные (переменной длины) — от конца. Как только они "встретятся" (свободного места не хватит на новую запись) — считаем эту страницу заполненной.


Вариант 3:
Вариант 3
Тут нет нужды хранить в заголовке длину или другую информацию о расположении данных, достаточно маркеров, означающих границы записей. Однако данные приходится обрабатывать при записи/чтении.
В качестве маркера я бы использовал 0xff (которым заполнена страница после erase), таким образом свободная область точно не будет трактоваться как данные.


Сравнительная таблица:


Вариант 1 Вариант 2 Вариант 3
Устойчивость к ошибкам - + +
Компактность + - +
Сложность реализации * ** **

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


Компактность:


  • в первом варианте нам нужно хранить в заголовке только длину, если использовать целые переменной длины, то в большинстве случаев можно обойтись одним байтом;
  • во втором варианте нам нужно хранить начальный адрес и длину; запись должна быть постоянного размера, я оцениваю в 4 байта на запись (два байта на смещение, и два байта на длину);
  • третьему варианту достаточно всего одного символа для обозначения начала записи, плюс сама запись из-за экранирования вырастет на 1-2%. В целом примерный паритет с первым вариантом.

Изначально я рассматривал второй вариант как основной (и даже написал реализацию). Отказался от него я только тогда, когда окончательно решил использовать сжатие.


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


Что же до третьего варианта: я поставил ему две звёздочки за сложность реализации просто потому, что не люблю возиться с экранированием, изменением длины в процессе и т.п. Да, возможно, предвзято, но код писать придётся мне — зачем заставлять себя делать то, что не нравится.


Резюме: выбираем вариант хранения в виде цепочек "заголовок с длиной — данные переменной длины" из-за эффективности и простоты реализации.


Использование битовых полей для контроля успешности операций записи


Уже сейчас не помню, где я подсмотрел идею, но выглядит всё примерно так:
Для каждой записи выделяем несколько бит для хранения флагов.
Как мы говорили ранее, после erase все биты заполнены 1, и мы можем изменять 1 на 0, но не наоборот. Так что для "флаг не установлен" используем 1, для "флаг установлен" — 0.


Вот как может выглядеть помещение записи переменной длины во flash:


  1. Устанавливаем флаг “запись длины началась”;
  2. Записываем длину;
  3. Устанавливаем флаг “запись данных началась”;
  4. Записываем данные;
  5. Устанавливаем флаг “запись закончилась”.

Кроме этого, у нас будет флаг “произошла ошибка”, итого 4 битовых флага.


В этом случае у нас есть два стабильных состояния “1111” — запись не началась и “1000” — запись прошла успешно; в случае непредвиденного прерывания процесса записи получим промежуточные состояния, которые мы потом мы сможем обнаружить и обработать.


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


Резюме: идём дальше в поисках хорошего решения.


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


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


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


Так что, если наша цель проверить, что данные целы, контрольные суммы — отличная идея.


Выбор алгоритма вычисления контрольной суммы вопросов не вызывал — CRC. С одной стороны, математические свойства позволяют в 100% ловить ошибки некоторых типов, с другой — на случайных данных обычно этот алгоритм показывает вероятность коллизий не сильно больше теоретического предела $2^{-n}$. Пусть это не самый быстрый алгоритм, не всегда минимальный по числу коллизий, но у него есть очень важное качество: во встречавшися мне тестах не попадались паттерны, на которых он бы явно проваливался. Стабильность — это главное качество в данном случае.


Пример объёмного исследования: часть 1, часть 2 (ссылки на narod.ru, извините).


Однако задача выбора контрольной суммы не завершена, CRC — это целое семейство контрольных сумм. Нужно определиться с длиной, а потом выбрать полином.


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


Проиллюстрирую:
Пусть у нас вероятность ошибки в каждом байте $10^{-3}$ и идеальная контрольная сумма, посчитаем среднее число ошибок на миллион записей:


Данные, байт Контрольная сумма, байт Необнаруженных ошибок Ложных обнаружений ошибок Итого неправильных срабатываний
1 0 1000 0 1000
1 1 4 999 1003
1 2 ≈0 1997 1997
1 4 ≈0 3990 3990
10 0 9955 0 9955
10 1 39 990 1029
10 2 ≈0 1979 1979
10 4 ≈0 3954 3954
1000 0 632305 0 632305
1000 1 2470 368 2838
1000 2 10 735 745
1000 4 ≈0 1469 1469

Казалось бы, всё просто — выбирай в зависимости от длины защищаемых данных длину контрольной суммы с минимумом неправильных срабатываний — и дело в шляпе.


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


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


Несмотря на то, что ранее я писал, что нужно экономить место всеми силами, всё-таки будем использовать 32-битную контрольную сумму (16 бит мало, вероятность коллизии больше 0.01%; а 24 бита, как говорится, ни туда и ни сюда).


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


По выбору полинома не будем изобретать велосипед, а возьмём популярный сейчас CRC-32C.
Этот код обнаруживает 6 битовых ошибок на пакетах до 22 байт (пожалуй, самый частый случай для наc), 4 битовые ошибки на пакетах до 655 байт (тоже частый случай для нас), 2 или любое нечётное число битовых ошибок на пакетах любой разумной длины.


Если кому интересны детали

Статья википедии про CRC.


Параметры кода crc-32c на сайте Купмана — пожалуй, главного специалиста по CRC на планете.


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


Ещё, так как у нас данные сжаты, возникает вопрос: считать контрольную сумму сжатых или несжатых данных?


Аргументы "за" подсчёт контрольной суммы несжатых данных:


  • нам в конечном итоге нужно проверить сохранность хранения данных — вот мы её напрямую и проверяем (при этом будут заодно проверены возможные ошибки в реализации компрессии/декомпрессии, повреждения, вызванные битой памятью и т.п.);
  • алгоритм deflate в zlib имеет достаточно зрелую реализацию и не должен падать при "кривых" входных данных, более того, зачастую он способен самостоятельно обнаружить ошибки во входном потоке, снизив общую вероятность необнаружения ошибки (провёл тест с инвертированием одиночного бита в короткой записи, zlib обнаружил ошибку примерно в трети случаев).

Аргументы "против" подсчёта контрольной суммы несжатых данных:


  • CRC "заточен" именно под немногочисленные битовые ошибки, которые характерны для флеш-памяти (битовая ошибка в сжатом потоке может дать массовое изменение выходного потока, на котором, чисто теоретически, мы можем "поймать" коллизию);
  • мне не очень нравится идея передавать декомпрессору потенциально битые данные, кто его знает, как он отреагирует.

В данном проекте я решил отойти от общепринятой практики хранения контрольной суммы несжатых данных.


Резюме: используем CRC-32C, контрольную сумму считаем от данных в том виде, в котором они записываются во flash (после сжатия).


Избыточность


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


Мы можем использовать разные виды избыточности для того, чтобы исправлять ошибки.
Коды Хэмминга могут исправлять одиночные битовые ошибки, коды Рида-Соломона символьные, несколько копий данных совместно с контрольными суммами или кодирование вроде RAID-6 могут помочь восстановить данные даже в случае массовых повреждений.
Изначально я был настроен на широкое использование помехоустойчивого кодирования, но потом понял, что сначала нужно иметь представление от каких ошибок мы хотим защититься, а потом уже выбирать кодирование.


Мы говорили ранее, что ошибки нужно выявлять как можно быстрее. В какие моменты мы можем столкнуться с ошибками?


  1. Незаконченная запись (по каким-либо причинам в момент записи отключилось питание, завис Raspberry, ...)
    Увы, в случае подобной ошибки остаётся только игнорировать невалидные записи и считать данные потерянными;
  2. Ошибки записи (по каким-либо причинам в flash-память записалось не то, что записывалось)
    Подобные ошибки мы можем сразу обнаружить, если мы непосредственно после записи будем делать контрольное чтение;
  3. Искажение данных в памяти в процессе хранения;
  4. Ошибки чтения
    Для исправления достаточно в случае несовпадения контрольной суммы несколько раз повторить чтение.

То есть только ошибки третьего типа (самопроизвольная порча данных при хранении) не могут быть исправлены без помехоустойчивого кодирования. Думается, подобные ошибки всё-таки крайне маловероятны.


Резюме: было решено отказаться от избыточного кодирования, но, если эксплуатация покажет ошибочность этого решения, то вернуться к рассмотрению вопроса (с уже накопленной статистикой по сбоям, которая позволит выбрать оптимальный вид кодирования).


Прочее


Разумеется, формат статьи не позволяет обосновать каждый бит в формате (да и у меня уже иссякли силы), поэтому кратко пробегусь по некоторым моментам, не затронутым ранее.


  • Решено делать все страницы "равноправными"
    То есть не будет каких-то специальных страниц с метаданными, отдельными потоками и т.п., вместо этого единый поток, который переписывает все страницы по очереди.
    Это обеспечивает равномерный износ страниц, остутствие единой точки отказа, ну и просто нравится;
  • Обязательно нужно предусмотреть версионность формата.
    Формат без номера версии в заголовке — зло!
    Достаточно добавить в заголовок страницы поле с неким Magic Number (сигнатурой), которое будет указывать на используемую версию формата (не думаю, что их на практике будет даже десяток);
  • Использовать для записей (которых очень много) заголовок переменной длины, стараясь для большинства случаев сделать его длиной в 1 байт;
  • Для кодирования длины заголовка и длины обрезаемой части сжатой записи использовать бинарные коды переменной длины.

Очень помог онлайн-генератор кодов Хаффмана. Буквально за несколько минут удалось подобрать нужные коды переменной длины.


Описание формата хранения данных


Byte order


Поля, размером превышающие один байт, хранятся в big-endian формате (network byte order), то есть 0x1234 записывается как 0x12, 0x34.


Деление на страницы


Вся флеш-память разбита на страницы равного размера.


Размер страницы по умочанию 32Кб, но не более, чем 1/4 от общего размера микросхемы памяти (для микросхемы на 4Мб получается 128 страниц).


Каждая страница хранит данные независимо от других (то есть данные одной страницы не ссылаются на данные другой страницы).


Все страницы пронумерованы в естественном порядке (в порядке возрастания адресов), начиная с номера 0 (нулевая страница начинается с адреса 0, первая — с 32Кб, вторая — с 64Кб и т.д.)


Микросхема памяти используется как циклический буфер (ring buffer), то есть сначала запись идёт в страницу с номером 0, потом с номером 1, ..., когда мы заполняем последную страницу, то начинается новый цикл и запись продолжается с нулевой страницы.


Внутри страницы


Страница
В начале страницы хранится 4-байтный заголовок страницы, потом контрольная сумма заголовка (CRC-32C), далее хранятся записи в формате "заголовок, данные, контрольная сумма".


Заголовок страницы (на схеме грязно-зелёный) состоит из:


  • двухбайтного поля Magic Number (он же — признак версии формата)
    для текущей версии формата он считается как 0xed00 ⊕ номер страницы;
  • двухбайтного счётчика "Версия страницы" (номер цикла перезаписи памяти).

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


Каждая запись сжимется с флагом Z_SYNC_FLUSH, при этом в конце сжатого потока оказываются 4 байта 0x00, 0x00, 0xff, 0xff, предварённые, возможно, ещё одним или двумя нулевыми байтами.
Эту последовательность (длиной 4, 5 или 6 байт) мы отбрасываем при записи в флеш-память.


Заголовок записи представляет из себя 1, 2 или 3 байта, хранящие:


  • один бит (T), означающий тип записи: 0 — контекст, 1 — журнал;
  • поле переменной длины (S) от 1 до 7 бит, определящее длину заголовка и "хвост", который нужно добавить к записи для распаковки;
  • длину записи (L).

Таблица значений S:


S Длина заголовка, байт Отбрасывается при записи, байт
0 1 5 (00 00 00 ff ff)
10 1 6 (00 00 00 00 ff ff)
110 2 4 (00 00 ff ff)
1110 2 5 (00 00 00 ff ff)
11110 2 6 (00 00 00 00 ff ff)
1111100 3 4 (00 00 ff ff)
1111101 3 5 (00 00 00 ff ff)
1111110 3 6 (00 00 00 00 ff ff)

Попробовал проиллюстрировать, не знаю, насколько наглядно получилось:
Запись с заголовком
Жёлтым тут обозначено поле T, белым — поле S, зелёным L (длина сжатых данных в байтах), голубым — сжатые данные, красным — конечные байты сжатых данных, которые не пишутся во флеш-память.


Таким образом, заголовки записей самой распространённой длины (до 63+5 байт в сжатом виде) мы сможем записать одним байтом.


После каждой записи хранится контрольная сумма CRC-32C, у которой в качестве начального значения (init) используется инвертированное значение предыдущей контрольной суммы.


CRC обладает свойством "продолжательности", действует (плюс-минус инвертирование бит в процессе) такая формула: $CRC(init, A || B) = CRC(CRC(init, A), B)$.
То есть фактически мы высчитываем CRC всех предыдущих байт заголовков и данных на этой странице.


Непосредственно за контрольной суммой лежит заголовок следующей записи.


Заголовок сконструирован таким образом, чтобы первый его байт был всегда отличен от 0x00 и 0xff (если вместо первого байта заголовка мы встречаем 0xff, то значит это пока неиспользуемая область; 0x00 же сигнализирует об ошибке).


Примерные алгоритмы


Чтение из флеш-памяти


Любое чтение идёт с проверкой контрольной суммы.
Если контрольная сумма не сошлась — чтение повторяется несколько раз в надежде прочитать-таки верные данные.


(это имеет смысл, Linux не кэширует чтение из NOR Flash, проверено)


Запись в флеш-память


Записываем данные.
Читаем их.


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


Подготовка новой микросхемы к работе


Для инициализации в первую (точнее нулевую) страницу записывается заголовок с версией 1.
После этого в эту страницу записывается начальный контекст (содержит UUID автомата и дефолтные настройки).


Всё, флеш-память готова к работе.


Загрузка автомата


При загрузке читаются первые 8 байт каждой страницы (заголовок + CRC), страницы с неизвестным Magic Number или неверным CRC игнорируются.
Из "правильных" страниц выбираются страницы с максимальной версией, из них берётся страница, имеющая наибольший номер.
Считывается первая запись, проверяется корректность CRC, наличие флага "контекст". Если всё нормально — эта страница считается текущей. Если нет — откатываемся на предыдущую, пока не найдём "живую" страницу.
а найденной странице считываем все записи, те, которые с флагом "контекст" применяем.
Сохраняем словарь zlib (нужен будет для дозаписи в эту страницу).


Всё, загрузка завершена, контекст восстановлен, можно работать.


Добавление записи в журнал


Сжимаем запись с правильным словарём, указывая Z_SYNC_FLUSH.Смотрим, помещается ли сжатая запись на текущей странице.
Если не помещается (или на странице были ошибки CRC) — начинаем новую страницу (см. ниже).
Записываем запись и CRC. Если произошла ошибка — начинаем новую страницу.


Новая страница


Выбираем свободную страницу с минимальным номером (свободной мы считаем страницу с неправильной контрольной суммой в заголовке или с версией меньше текущей). Если таких страниц нет — выбираем страницу с минимальным номером из тех, что имеют версию равную текущей.
Делаем выбранной странице erase. Сверяем содержимое с 0xff. Если что-то не так — берём следующую свободную страницу, и т.д.
На стёртую страницу записываем заголовок, первой записью текущее состояние контекста, следующей — незаписанную запись журнала (если она есть).


Применимость формата


По моему мнению, получился неплохой формат для хранения любых более-менее сжимаемых потоков информации (простой текст, JSON, MessagePack, CBOR, возможно, protobuf) в NOR Flash.


Конечно, формат "заточен" под SLC NOR Flash.


Его не стоит использовать с носителями с высоким BER, например NAND или MLC NOR (а такая память вообще есть в продаже? встречал упоминания только в работах по кодам коррекции).


Тем более, его не стоит использовать с устройствами, имеющими свой FTL: USB flash, SD, MicroSD, etc (для такой памяти я делал формат с размером страницы в 512 байт, сигнатурой в начале каждой страницы и уникальными номерами записей — иногда из "глюкнувшей" флешки удавалось простым последовательным чтением восстановить все данные).


В зависимости от задач формат без изменений можно использовать на флешках от 128Кбит (16Кб) до 1Гбит (128Мб). При желании можно использовать и на микросхемах большего объёма, только, наверное, нужно скорректировать размер страницы (Но тут уже встаёт вопрос экономической целесообразности, цена на NOR Flash большого объёма не радует).


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


Заключение


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


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


Может ли получиться так, что я ошибся? Да, конечно. Вполне может оказаться, например, что мы закупили партию некачественных микросхем. Или по какой-то другой причине оборудование не оправдает ожидания по надёжности.


Есть ли у меня план на этот случай? Я думаю, что по прочтению статьи вы не сомневаетесь, что план есть. И даже не один.


Если чуть более серьёзно, формат разработан одновременно и как рабочий вариант, и как "пробный шар".


На сегодняшний момент на столе всё работает нормально, буквально на днях решение будет развёрнуто (примерно) на сотне устройств, посмотрим, что будет в "боевой" эксплуатации (благо, надеюсь, формат позволяет надёжно детектировать сбои; так что получится собрать полноценную статистику). Через несколько месяцев можно будет делать выводы (а если не повезёт — то и раньше).


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


Литература


Не хотелось составлять длинный нудный список использованных работ, в конце концов гугл есть у всех.


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


  1. Утилита infgen от автора zlib. Умеет в понятном виде отображать содержимое архивов deflate/zlib/gzip. Если вам приходится разбираться с внутренним устройством формата deflate (или gzip) — настоятельно рекомендую.

Комментарии 83

    +1
    Не хотелось составлять длинный нудный список использованных работ, в конце концов гугл есть у всех.

    А вот этого не могу одобрить. Список литературы — это может быть еще и список рекомендуемый автором к ознакомлению по данной теме.

      0
      В своё оправдание могу сказать, что в тексте есть несколько ссылок.

      «Список, рекомендуемый автором к ознакомлению по данной теме» — затронуто слишком много тем (флеш-память, deflate, crc, вскользь другие коды обнаружения и коррекции ошибок, linux devicetree). По каждой теме есть десятки заслуживающих внимания публикаций. Боюсь, что даже если бы я и нашёл силы составить достойный список, один его вид убивал бы весь энтузиазм.
      +1

      Насчет списка литературы поддержу.


      А так — спасибо за статью

        +1
        Из жизни — при активной работе, и даже иногда без нее — в SPI NOR памяти довольно часто возникают битовые ошибки. Atmel, Winbond, ST — не важно. Поэтому CRC — обязательно к применению. В тех устройствах которые мы исследуем/ чиним производители железок много лет (сколько используются SPI NOR) используют CRC для контроля считанных данных — и кода, и секций с данными. PS: уточню — я про 25 серию
          0
          Да, встречал такую информацию.

          «На столе» битовых ошибок пока не попадалось, но это не показатель, конечно.
          Я уже писал, что было очень горячее желание добавить ECC, но я понял, что для принятия решения нужна статистика.

            0
            Если для вас потеря записи будет несущественна — то ECC вам не нужен. В таком случае с помощью CRC вы лишь сможете определить факт появления «битой» записи. Если нужно обеспечить еще и коррекцию — я бы сделал простой 1-битовый алгоритм коррекции ошибок, в паре с CRC32. В сети полно реализаций алгоритма, например загуглите доку Samsung по Hamming ECC for NAND Flash — его вполне можно применить и на SPI. Причем вы можете защищать с помощью ECC не пакет данных (запись в вашей терминологии), а страницу, к примеру размером 64-256 байт.
              0
              мне потеря более-менее критична так как данные пишутся одним сжатым потоком, я потеряю не одну запись, а её и все последующие на странице.

              В сети полно реализаций алгоритма, например загуглите доку Samsung по Hamming ECC for NAND Flash

              Вы про этот алгоритм:
              github.com/torvalds/linux/blob/master/Documentation/driver-api/mtd/nand_ecc.rst
              ?

              Он почему-то везде называется кодом Хэмминга, хотя он требует 22 добавочных бит на блок из 2048бит, а «настоящий» код Хэмминга — 12 добавочных бит (а в 24 добавочных бита ЕМНИП помещается код, исправляющий 2 битовые ошибки).

              Как я понимаю, преимущество у этого кода — простота реализации и скорость.

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

              это не сработает, если нужны операции записи размером меньше страницы, NOR не позволит переписать уже записанный ECC для страницы.
                0
                Да, визуально он. У меня лежат pdf с описанием, там приблизительно то же. Ну а насчет страниц — да, это действительно проблема. Может быть имеет смысл просто дублировать записи — писать их два раза или в две флешки. Это будет проще чем городить огород с ецц
                  0
                  Я рассматривал и этот вариант тоже. Повторю: накоплю статистику, а там видно будет.
                    0

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

                0
                Вот в этом проекте есть реализации ecc: github.com/dlbeer/dhara
            0
            А почему не смотрели в сторону EEPROM?
            Вроде бы у вас копеечные размеры, а EEPROM позволяет миллион перезаписей (на самом деле больше, но миллион гарантируется).
              0
              Я в начале статьи написал, что хочется иметь объём не меньше нескольких мегабайт, так что EEPROM отпадает.
              Что же до числа записей, по грубым прикидкам и с NOR у нас есть запас в пару порядков.

              P.S. «в простонародье» когда говорят EEPROM часто имеют в виду именно NOR Flash.
                0
                В простонародье сильно ошибаются. Разница в надёжности на порядок. Но, если вам хватает, почему бы и нет. Хотя, если пару порядков, то и нормальная SLC должна была бы справиться.
                0
                Они только в этом году к 4 мегабитам (512 килобайт) приблизились, и это будет конская цена. Пруф — STMicro Introduces the World’s First 4Mbit SPI EEPROM — новость 22 ноября 2019 года. M95M04. Обещают 4 миллиона циклов записи и 40 лет сохранности.
                  0
                  Во-первых мегабитная микруха стоит 140р. в розницу. Во-вторых, кто вам мешает их хоть 8 штук повесить, например по i2c? Я бы даже сказал, что кольцевую запись было бы проще организовать.
                  А вообще, у меня в аквариуме SD-карта на 128Мб (SLC) уже много лет трудится, журналы пишет, жива-здорова, но тут тоже как повезёт…
                    0
                    1 мегабит — это всего 128 килобайт, автору их прийдется распаять 64 штуки чтобы достичь сравнимой емкости. Насчет вашей SD карты — а сейчас просто купить такие новые недорого? В те времена когда ваша SD карта была выпущена (это начало нулевых) — кроме SLC другой памяти и не существовало…
                      0
                      У меня вообще складывается впечатление (из собственного опыта), что порча данных на флешках чаще бывает из-за нештатного пропадания питания, нежели от недостатков архитектуры NAND. У меня в фотоаппаратах данные чаще теряются, чем в видеорегистраторе авто, при том, что там нагрузка выше. Потому что регистратор одной ногой подключен к гарантированному батарейному питанию и всегда выключается корректно.
                        0
                        Я бы сформулировал так: чаще глючит/умирает контроллер, чем сама память.
                        С SSD, кстати, то же самое.
                          0
                          Контроллер не умирает в них вообще никогда. Занимаемся Data recovery — поэтому знаем о чем говорим. Повреждаются служебные данные — таблицы трансляции, страницы с микрокодом в нандах, много чего. В основном проблемы связаны со стеканием заряда и, как следствие, с невозможностью прочитать (и скорректировать с помощью ECC) нужные для старта накопителя объекты.
                            0
                            Интересовался как именно работает ftl в реальных устройствах, так ничего не нашёл. Плохо искал? Или никто не делится информацией — ни разработчики, ни те, кто реверсят?
                              0
                              Такую информацию можно добыть реверсом и изучением расположения данных в нандах.
                          0
                          нет, при постоянном обновлении данных вы не сталкиваетесь со стеканием заряда в ячейках, а с редко используемой флешкой — в полный рост проявляется data retention — для TLC памяти он гарантируется всего в 3 месяца для изношенной памяти. Кстати, для Enterpice SSD производитель указывает разный ресурс памяти в циклах, в зависимости от того, сколько данные должны храниться. Например, если нужно 3 месяца — то это 500 циклов, типичных для TLC. Если нужно неделю — то это уже будет (по памяти, могу ошибиться) 10000.
                            0
                            при постоянном обновлении данных вы не сталкиваетесь со стеканием заряда в ячейках, а с редко используемой флешкой — в полный рост проявляется data retention

                            И что делать, чтобы максимально продлить срок службы MicroSD с системой?

                            Получается, часто пишем (изначальный подход) — плохо. Не пишем (readonly) — опять плохо, заряд а ячейках не обновляется.
                              0
                              Если карта памяти новая — у вас есть гарантированно полгода-год. Дальше уже может сдохнуть даже в режиме RO.
                  0
                  К стати, по поводу влияния пропажи питания. После первого же инцидента, связанного с пропаданием питания на моем сервере умного дома (малинка 3.0, ОС выжила, а вот последние настройки слетели) озаботился и купил на Али БП со встроенным аккумулятором 18650. Uptime года три уже, обычная micro sd карта на 16Гб, журналы тоже непрерывно пишутся, показания датчиков температуры, влажности, давления и др. каждую секунду…
                    0
                    О, хотел же перечислить часто встречаемые глюки с флешками, вот один из них: на карту пишется вроде бы нормально, после перезагрузки видим данные давностью несколько часов/дней/недель.
                      0

                      Про кеширование: на CortexA9 (zynq 7000) столкнулся с тем что функция линейного чтения из флеш кэширует данные в кэше проца. Это канешно зависит от настроек translation_table, но по умолчанию она настроена на кеширование. При обычном чтении ( не линейном ) кеширования нет.

                        0
                        Речь про SPI NOR или что-то другое?
                          0

                          Да, о ней.

                            0
                            используются модули ядра m25p80 и spi_nor?
                              0

                              Я обнаружил это когда работал в bare metal. То есть это фактически возможно и надо иметь это ввиду.

                                0

                                ИМХО вы явно что-то недоговариваете.


                                не может быть такого, что вы выплюнули в spi 03 XX YY ZZ, а процессор что-то закэшировал.

                                  +1

                                  Есть такой режим линейного чтения. Реализован в контроллере qspi специально для работы с флеш памятью. Как я понимаю, в этом режиме определенное адресное пространство процессора отображается на флеш память и может кешироваться в L2 кеше как и все остальное адресное пространство.

                                    0

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


                                    в моём случае есть программная обвязка (стек mtd/spi-nor/spi в ядре linux), я её проверил на предмет отсутствия кэширования, о чём и написал в статье (то есть если я читаю из /dev/mtdX, то обязательно идёт обращение к микросхеме).


                                    как обнаружили, кстати?

                                      0

                                      Замерял скорость чтения. В линейном режиме при повторном чтении показал какую то невероятную скорость, потом понял.

                    0
                      0
                      Цена же на порядок выше
                      0
                      С одной стороны великолепная статья с важными техническими подробностями.
                      Но с другой пример лечения пореза пальца пересадкой мозга в клонированное тело.

                      Как разработчик ПЛК тоже сталкиваюсь с жалобами клиентов на устойчивость работы с USB накопителями.
                      И анализ проектов пользователей показал что оно и должно ломаться со временем.
                      Что делает типичный «автоматизатор»:
                      1. Создаёт множество файлов логов, особенно в корне (корень у той же FAT очень особенная область)
                      1а. Создаёт множество файлов с одинаковым началом и различием в районе 10-50 го символа имени. Как результат механизм формирования коротких имён в FAT в зависимости от реализации стека либо сходит с ума, либо работает как черепаха в бетоне.
                      2. Пишет в файлы по чуть-чуть. (запись на 50 байт — а трётся страница флеши в глубине флешки)
                      3. Пишет непрерывно (нет времени для встроенного контроллера флеши на сбор мусора и релокацию)
                      4. Не используются алгоритмы контроля качества питания (сигнал по первичке щита на пропадание питания, отдельный БП увеличенной мощности на питание ПЛК) — в результате пропадание питание встречает программу логирования со «спущенными штанами»
                      5. Дешевые флешки — это самый простой пункт.

                      Соответственно, простые рекомендации по вышеизложенным пунктам позволяют логировать на флешки без проблем с их выходом из строя.
                      1. Файлов должно быть мало.
                      2. Файлы должны именоваться уникально начиная с первых символов, имя надо делать в формате 8.3
                      3. Пишем сразу не менее чем блок FAT (до 64 кБайт!)
                      4. Пишем атомарно, открыл, записал, закрыл, сделал FLUSH.
                      5. Пишем с паузами. По опыту желательно не менее 1 минуты
                      6. Система питания должна удерживать питание на флешке не менее 5-6 секунд после получения сигнала о пропадании питания. Естественно в это время надо закрыть все файлы и не писать.

                      И внезапно проблемы с флешками исчезают.
                        0

                        хорошо, расскажу, как было в предыдущем проекте с USB-флешками, которые периодически подыхали.


                        Файлов должно быть мало.

                        запись была в один-единственный файл.
                        притом даже без циклической перезаписи, просто один файл.
                        объёма флешки было достаточно на несколько лет работы.


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


                        Пишем сразу не менее чем блок FAT (до 64 кБайт!)

                        ну не нужно мне было столько писать. писал по 512 байт.


                        Пишем атомарно, открыл, записал, закрыл, сделал FLUSH.

                        именно так оно и было (разве что файл не переоткрывался, зачем?)


                        Пишем с паузами. По опыту желательно не менее 1 минуты

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


                        или имеется в виду "после каждой записи ждать минуту"?

                          0
                          1 файл тоже не самый хороший вариант, нормальное число файлов от 10 до 100, мы стараемся чтобы файл хотя бы раз в сутки менялся. И удалялся после устаревания
                          512 байт слишком мало, реально флешка имеет страницу от 2 до 4 кбайт.
                          Раз файл не переоткрывался — то он не закрывался. А значит ФС не могла (тут зависит от реализации) делать flush правильным образом.
                          Пауза желательна после каждой.
                          Ну и питание, питание на первом месте, если не использовать журналируемые ФС.

                          Но NOR — это хорошее решение, т.к. тут качество микросхемы под контролем разработчика. Что там запаяют во флешке — вопрос.
                            0
                            512 байт слишком мало, реально флешка имеет страницу от 2 до 4 кбайт.

                            Можете обосновать подробнее? У большинства NAND 512 байт — как раз минимально допустимый размер записи для срабатывания ECC.
                              0
                              у современных нандов размер страницы 16к, но это вас не должно волновать совсем. Флешке в общем-то совершенно все равно сколько и куда вы пишете. И ей как устройству совершенно все равно сколько там файлов в ФС. Ей вообще все равно как организованы данные. Для транзакций, не кратных размеру страницы нанда все контроллеры флешек используют механизм «апдейтов» — такое послойное наложение новых секторов поверх изначального содержимого страниц.
                                0
                                Размер страницы это скорее деталь реализации и способа адресации. Только spare area привязана к странице, писать по целой странице не так уж и обязательно, только для скрамблинга может быть выгодно писать целую страницу. А вот уважеть минимальный размер записываемого приходится, иначе не сработает ECC. Поэтому ftl обычно делит нанд на логические сектора минимального допустимого размера. Альтернатива — это только что-то наподобие UBI и запись в размер стираемого блока, а он довольно велик.
                          0
                          Цена, конечно, важный фактор, но цена флешки это ничего от цены автомата и стоимости его обслуживания, так что www.terraelectronica.ru/news/6282
                            0

                            Вы сейчас про замену замену NOR Flash?


                            А в чём смысл?
                            Вот посмотрите, например, pdf от Macronix. "Data retention" падает в зависимости от числа Erase и температуры, после 10к Erase при температуре 80℃ данные будут сохранны в течение года.
                            Для предполагаемого применения этого более, чем достаточно.

                            0
                            Никто не упомянул такой важнейший фактор, как рабочая температура flash памяти. Изолированный затвор полевых транзисторов ячеек теряет заряд намного быстрее при высоких температурах. Перегревающаяся ячейка быстро обнулится. Средний срок хранения данных каждый производитель пишет очень по-разному. Но я считаю, что нужно брать самый минимальный срок из всех, исходя из того, как часто на практике память выходит из строя или частично обнуляется сама по себе. А это 10 лет при 25 градусах. Отсюда можно сделать вывод, что при нагреве срок ощутимо уменьшится. Ну и как вывод, при длительном хранении необновляемых данных, их нужно регулярно перезаписывать, стирая ячейки (заряжая затворы транзисторов) скажем, каждые 5 лет. Теперь вопрос ограниченности циклов записи на ячейку, которые у flash памяти стираются страницами. Нужно ориентироваться на опять же минимальное число, заявляемое производителями. Это 1 тысяча циклов. Значит, чтобы флешка жила долго, нужен как можно больший объём ячеек, дабы часто их не перезаписывать. И последнее. В последних версиях ядра Linux реализована поддержка файловой системы exFAT. Она оптимизирована под более равномерный износ флеш-памяти. Думаю оптимальный ценовой вариант это 32ГБ MicroSD + exFAT + около 25 градусов рабочей температуры. Успехов! P. S.: Забыл упомянуть об ускорении обнуления ячеек, при чтении соседних. Электроны близко бегают, видимо подогревают. )))
                              0
                              В последних версиях ядра Linux реализована поддержка файловой системы exFAT. Она оптимизирована под более равномерный износ флеш-памяти.

                              А можно детали?
                              Тут, например, я сходу не увидел ничего, что должно серьёзно повлиять на число перезаписей.


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


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

                              я уже писал, не помогает.


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


                              в любом случае раз есть возможность не играть в азартные игры с USB/SD/MicroSD/etc — я буду этой возможностью пользоваться.

                                0
                                Тогда в роли надёжной и быстродействующей памяти для индексов и контрольных сумм к flash хранилищу использовать что-то вроде дешёвой FRAM типа FM25L04B-GTR.
                                  0

                                  Вы уже третий, кто рекомендует F-RAM. Но никто так и не аргументировал чем F-RAM лучше NOR в этом случае.
                                  Больше число перезаписей? Ну так и с NOR у нас запас на пару порядков.
                                  Нет проблемы с data retention? Так я писал чуть выше, что даже в неблагоприятных условиях NOR справится.
                                  Ниже BER? Я не видел оценки ни для NOR, ни для F-RAM.


                                  Тогда в роли надёжной и быстродействующей памяти для индексов и контрольных сумм к flash хранилищу

                                  Данные писать на MicroSD, а CRC (и, возможно, некоторые метаданные) на F-RAM?
                                  То есть вы предлагаете собрать воедино недостатки обоих подходов "хранить данные на MicroSD" и "держать MicroSD в RO, хранить данные где-то ещё": с одной стороны, мы усложняем аппаратную часть, вводя дополнительное хранилище; с другой, при выходе карточки памяти из строя мы всё равно теряем данные.

                                  +1
                                  Кстати индексы можно записывать самым щадящим методом прямо во flash, используя натуральный счёт из битов. Стираем блок ячеек, получаем единицы. Записываем нули по одному. Количество нулей и будет числом индекса. Получается большой расход объёма, но при этом редчайшее стирание ячеек. Из 32 мегабит отдай мегабит на индекс, и можно вести отсчёт до 1 048 576. Затем весь мегабит стирается, и всё по новой.
                                0
                                Автор, годная статья, радует подход с разных углов, избыточное кодирование и прочее. Если данные относятся к коммерческим транзакциям, то хранить их ни на USB-флэшке, ни на [micro]SD, конечно, нельзя. Даже на двух в режиме RAID:) Поведение внутреннего контроллера при отключении питания хотя и зависит от стоимости изделия, но всё равно без гарантий. Поэтому альтернативный и контролируемый способ записи информации, конечно, напрашивается…

                                Но это долгое и недешёвое удовольствие. У Вас proof of concept или реально работающий проект? Сколько устройств в эксплуатации, как давно, какая статистика по отказам?

                                Иногда можно упростить реализацию добавлением контроля качества питания с запасом энергии на гарантированное закрытие транзакции. Не берусь утверждать, что это Ваш случай, но всё же.
                                  0
                                  Но это долгое и недешёвое удовольствие. У Вас proof of concept или реально работающий проект?

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


                                  Сколько устройств в эксплуатации, как давно, какая статистика по отказам?

                                  чуть больше сотни, поддержка SPI flash с нового года, пока особой статистики нет.

                                  0
                                  Можно было использовать NILFS2 или F2FS. Готовые файловы системы циклического типа. И писать на них что хочешь.

                                  Есть в ядре Линукса.
                                    0

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

                                      0
                                      А зачем было заморачиваться с крохотной микросхемой, если есть поддержка MicroSD?
                                        0

                                        так в статье же написано: чтобы перевести microsd в readonly

                                          0
                                          И проблемы бы с флэшками не было бы, если бы использовали такую ФС.
                                            0

                                            не верю. в сети достаточно много отзывов о погибших флешках, эксплуатировавшихся в режиме r/o (справедливости ради, у меня за три месяца ан примерно сотне устройств пока ни одной, но так и срок невелик)

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

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

                                                когда-то давно я делал просто линейную запись в файл на флешке (в циклической записи не было нужды из-за смешных объёмов). один-единственный preallocated файл. и они всё равно дохли пачками.


                                                хотя говорить «дохли» неправильно.
                                                самое частое: записываешь в файл, записываешь. после каждой записи делаешь fsync. всё отлично. но только после ребута в файле оказывается информация на какой-то момент несколько дней назад. и всё опять «работает», после ребута опять откат.
                                                вторая, наверное, по частоте проблема: считаешь md5 флешки, перевтыкаешь, считаешь ещё раз — не сходится.
                                                ну и банальное "флешка перестала определяться" случается тоже.


                                                из всего этого на износ NAND похоже разве что второе. только оно и на новых флешках встречается, вы уверены, что замена файловой системы поможет? )

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

                                                  2. Даже если вы пишете очень корректно, так что не затрагиваются FAT таблицы, то всё равно переписываются аттрибуты (mtime), которые лежат на определённых секторах и сектор вылетает вместе с остальной флэшкой.

                                                  3. Поэтому и нужны ФС, которые умеют любую запись самостоятельно записывать в новое пространство.
                                                    +1
                                                    1. ещё раз повторю: я не переписывал данные в файле, только дозапись.
                                                      так что хоть единственный файл, хоть 1024 разных файла — роли не играет.
                                                    2. да, я в курсе. только вот список типичных проблем, который приводил чуть выше, наводит на мысли, что дело не в этом.

                                                    вообще у меня устойчивое ощущение, что в флешках чаще выходит из строя/глючит контроллер чем NAND

                                                      0
                                                      ещё раз повторю: я не переписывал данные в файле, только дозапись.
                                                      так что хоть единственный файл, хоть 1024 разных файла — роли не играет.


                                                      В таком случае вы постоянно переписывали FAT c каждой следующей дозаписью. Рецепт лечения тот же — использовать ФС приспособленную для флэш: NILFS2 или F2FS или подобную.
                                                        0
                                                        В таком случае вы постоянно переписывали FAT c каждой следующей дозаписью.

                                                        один-единственный preallocated файл

                                                          0
                                                          2. Даже если вы пишете очень корректно, так что не затрагиваются FAT таблицы, то всё равно переписываются аттрибуты (mtime), которые лежат на определённых секторах и сектор вылетает вместе с остальной флэшкой.


                                                          ещё раз повторю: я не переписывал данные в файле, только дозапись.
                                                          так что хоть единственный файл, хоть 1024 разных файла — роли не играет.


                                                          Если файл preallocated, то вы именно переписывали, а не делали дозапись.

                                                          А если файл был sparse — то ещё и FAT переписывалась при каждой дозаписи.
                                                            0

                                                            файл не был sparse. и да, я переписывал, но каждый сектор только по 2 раза (первый раз — заполнение нулями при создании файла, второй — запись данных).


                                                            не считая модификации mtime, такая запись ничем не отличается от последовательной записи в блочное устройство руками (и не сильно отличается от тех же flash-friendly fs, только overhead меньше)

                                                      0
                                                      Некровопрос: на флешке ftl при перезаписи не переносит данные в другой физический сектор?
                                                        0
                                                        На большинстве микросд и многих флэшках нет полноценного контроллера, который осуществляет выравнивание износа. А ftl там примерно 1 к 1.
                                                          0
                                                          Тогда почему это называется ftl?!
                                                            0
                                                            flash translation layer. Это не означает что он должен уметь делать выравнивание износа. Он ответственен только за трансляцию логических адресов в физическое адресное пространство микросхем.

                                                          0

                                                          речь про usb/sd? единого ответа, как я понимаю, нет, каждый производитель решает сам

                                          0
                                          А чем NILFS2/F2FS лучше/надежнее UBIFS?
                                            0
                                            NILFS2 позволяет откатиться практически на любой момент времени назад в прошлое.
                                            И я не слышал, чтобы при внезапном отключении питания nilfs2 теряла работоспособность, в отличии от UBIFS (есть статья на Хабре о таких проблемах).
                                              0
                                              Не могли бы уточнить ссылку? А то поиск в хабре по ubifs не нашел.
                                                0
                                                Гуглом нужно искать.
                                                habr.com/ru/post/273425
                                                  0
                                                  Спасибо.
                                                    0
                                                    Я правильно понял, что разница в том, что ubifs может «проморгать» битые данные, а nilfs2 — нет. Но откатываться на предыдущую версию без последних изменений все-равно придется?
                                                      0
                                                      Я думаю, разница в другом. NILFS2 если видит проблемы, то сама по себе откатывается к предыдущему снепшоту секундной давности.
                                                        0
                                                        Не уверен, что ей всегда можно быть благодарным за это)
                                            0

                                            .

                                              0

                                              Продолжая обозначенную в самом начале тему readonly SBC. Что вы думаете о материале он ещё актуален?

                                                0

                                                если воспринимать его как сборник относящейся к теме информации — да, конечно.
                                                как инструкцию — сложно сказать, именно такую задачу (сделать из стандартного debian ro систему, которую при желании временно можно перевести в rw) я не решал.


                                                если вопрос был про то, стоит ли переводить в ro, то стоит.

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

                                            Самое читаемое