- PVSM.RU - https://www.pvsm.ru -
Есть торговые автоматы собственной разработки. Внутри Raspberry Pi и немного обвязки на отдельной плате. Подключены монетоприёмник, купюроприёмник, банковский терминал… Управляет всем самописная программа. Вся история работы пишется в журнал на флешке (MicroSD), который потом передаётся через интернет (с помощью USB-модема) на сервер, там складывается в БД. Информация о продажах загружается в 1с, также есть простенький веб-интерфейс для мониторинга и т.п.
То есть журнал жизненно необходим — для учёта (там выручка, продажи и т.д.), мониторинга (всевозможные сбои и другие форс-мажорные обстоятельства); это, можно сказать, вся информация, которая у нас об этом автомате.
Флешки показывают себя как очень ненадёжные устройства. Они с завидной регулярностью выходят из строя. Это приводит как к простоям автоматов, так и (если по каким-то причинам журнал не мог быть передан онлайн) к потерям данных.
Это уже не первый опыт использования флешек, до этого был другой проект с более, чем сотней устройств, где журнал хранился на USB-флешках, там тоже были проблемы с надёжностью, временами число вышедших из строя за месяц исчислялось десятками. Пробовали разные флешки, в том числе и брендовые на SLC памяти, да некоторые модели надёжнее других, но замена флешек не решила проблему кардинально.
Внимание! Лонгрид! Если вам неинтересно "почему", а интересно только "как", можете сразу идти в конец [1] статьи.
Первое, что приходит в голову: отказаться от MicroSD, поставить, например, SSD, и грузиться с него. Теоретически возможно, наверное, но относительно дорого, и не так уж надёжно (добавляется переходник USB-SATA; по бюджетным SSD статистика отказов тоже не радует).
USB HDD тоже не выглядит особо привлекательным решением.
Поэтому пришли к такому варианту: оставить загрузку с MicroSD, но использовать их в режиме read-only, а журнал работы (и другую уникальную для конкретной железки информацию — серийный номер, калибровки датчиков, etc) хранить где-то ещё.
Тема read-only ФС для малинки уже изучена вдоль и поперёк, я не буду останавливаться на деталях реализации в этой статье (но если будет интерес — быть может и напишу мини-статью на эту тему). Единственный момент, который хочется отметить: и по личном опыту, и по отзывам уже внедривших выигрыш в надёжности есть. Да, полностью избавиться от поломок невозможно, однако существенно снизить их частоту — вполне реально. Да и карточки становятся унифицированными, что заметно упрощает замену для обслуживающего персонала.
С выбором типа памяти особых сомнений не было — NOR Flash.
Аргументы:
Прикинем требования к объёму и ресурсу.
Хочется, чтобы гарантированно сохранялись данные за несколько дней. Нужно это для того, чтобы в случае каких-либо проблем со связью история продаж не была потеряна. Будем ориентироваться на 5 дней, за этот срок (даже с учётом выходных и праздников) можно решить проблему.
У нас сейчас за сутки набирается около 100кб журнала (3-4 тысячи записей), однако постепенно эта цифра растёт — увеличивается детализация, добавляются новые события. Плюс иногда бывают всплески (какой-нибудь датчик начинает спамить ложными срабатываниями, например). Будем рассчитать на 10 тысяч записей по 100 байт — мегабайт в сутки.
Итого выходит 5Мб чистых (хорошо сжимаемых) данных. К ним ещё (грубая прикидка) 1Мб служебных данных.
То есть нам нужна микросхема на 8Мб если не использовать сжатие, или 4Мб если использовать. Вполне реальные цифры для этого типа памяти.
Что же до ресурса: если мы планируем, что память целиком будет переписываться не чаще, чем раз в 5 дней, то за 10 лет службы мы получаем менее тысячи циклов перезаписи.
Напоминаю, производитель обещает сто тысяч.
Сегодня, конечно, куда более популярна NAND память, однако для этого проекта я бы не стал её использовать: NAND, в отличие от NOR, обязательно требует использования кодов коррекции ошибок, таблицы сбойных блоков и т.д., да и ножек у микросхем NAND обычно куда больше.
В качестве недостатков NOR можно указать:
Вроде бы ничего критичного для нас, так что продолжаем.
Если интересны детали, была выбрана микросхема at25df321a [2] (впрочем, это несущественно, на рынке куча аналогов, совместимых по распиновке и системе команд; даже если мы захотим поставить микросхему одругого производителя и/или другого объёма, то всё заработает без изменения кода).
Я использую встроенный в ядро Linux драйвер, на Raspberry благодаря поддержке device tree overlay всё очень просто — нужно положить в /boot/overlays скомпилированный оверлей и немного модифицировать /boot/config.txt.
Честно говоря, не уверен, что написано без ошибок, но работает.
/*
* 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?";
};
};
dtoverlay=at25:spimaxfrequency=50000000
Описание самого подключения микросхемы к Raspberry Pi опущу. С одной стороны, я не специалист в электронике, с другой — тут всё банально даже для меня: у микросхемы всего 8 ног, из которых нам нужны земля, питание, SPI (CS, SI, SO, SCK); уровни совпадают с таковыми у Raspberry Pi, никакой дополнительной обвязки не требуется — просто соединить указанные 6 контактов.
Как обычно, постановка задачи проходит несколько итераций, мне кажется, что пришло время для очередной. Так что давайте остановимся, соберём воедино то, что уже было написано, и проясним оставшиеся в тени детали.
Итак, мы определились с тем, что журнал будет храниться в SPI NOR Flash.
Это энергонезависимая память, с которой можно делать три операции:
Двоичные данные | |
---|---|
Было | 01010101 |
Записали | 00001111 |
Стало | 00000101 |
Сам журнал представляет последовательность записей переменной длины. Типичная длина записи около 30 байт (хотя иногда случаются и записи длиной в несколько килобайт). В данном случае мы работаем с ними просто как с набором байт, но, если интересно, внутри записей используется CBOR
Помимо журнала, нам нужно хранить некоторую "настроечную" информацию, как обновляемую, так и нет: некий ID аппарата, калибровки датчиков, флаг "аппарат временно отключен", etc.
Эта информация представляет из себя набор записей key-value, также хранится в CBOR.Этой информации у нас не очень много (максимум несколько килобайт), обновляется она нечасто.
В дальнейшем будем называть её контекстом.
Если вспомнить с чего начиналась эта статья, то очень важно обеспечить надёжность хранения данных и, по возможности, беспрерывную работу даже в случае аппаратных сбоев/повреждения данных.
Какие источники проблем можно рассмотреть?
Я сформулировал требования, выполнение которых, на мой взгляд, необходимо для обеспечения надёжности:
Когда я начал думать над этой задачей, то в голове проносилась куча идей, например:
Часть этих идей была использована, от части было решено отказаться. Давайте по порядку.
Сами события, которые мы фиксируем в журнале, достаточно однотипные и повторяемые ("кинули монетку 5 рублей", "нажали на кнопку выдачи сдачи", ...). Поэтому сжатие должно оказаться достаточно эффективным.
Накладные расходы на сжатие несущественны (процессор у нас достаточно мощный, даже на первом Pi было одно ядро с частотой 700МГц, на актуальных моделях несколько ядер с частотой свыше гигагерца), скорость обмена с хранилищем невысокая (несколько мегабайт в секунду), размер записей невелик. В общем, если сжатие и окажет влияние на производительность, то только положительное (абсолютно некритично, просто констатирую). Плюс у нас же не настоящий embedded, а обычный Linux — так что реализация не должна потребовать много усилий (достаточно просто прилинковать библиотеку и использовать несколько функций из неё).
Был взят кусок лога с работающего устройства (1.7Мб, 70 тысяч записей) и для начала проверен на сжимаемость с помощью имеющихся на компьютере gzip, lz4, lzop, bzip2, xz, zstd.
Итак, данные сжимаются очень хорошо.
Так что (если мы не найдём фатальных недостатков) сжатию быть! Просто потому, что на ту же флешку поместится больше данных.
Давайте подумаем о недостатках.
Первая проблема: мы уже договорились, что каждая запись должна незамедлительно попасть на флеш. Обычно архиватор набирает данные из входного потока до тех пор, пока не решит, что пора писать в выходной. Нам же нужно сразу получить сжатый блок данных и сохранить его в энергонезависимой памяти.
Я вижу три пути:
sync
в файловых системах или commit
в sql.Думаю очевидно, что я выбрал третий вариант, остановимся на нём подробнее.
Нашлась отличная статья [4] про 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 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Кб.
Я задал вопрос [5] на странице проекта в github, получил ответ, что стоит рассчитывать на до 10 байт служебных данных на каждый блок сжатых данных, что близко к полученным результатам, догнать deflate никак не получится.
На этом я решил остановиться в экспериментах с архиваторами (напомню, xz, lzip, lzo, lz4 не показали себя ещё на этапе тестирования без FLUSH, а рассматривать более экзотические алгоритмы сжатия я не стал).
Возвращаемся к проблемам архивации.
Вторая (как говорится по порядку, а не по значению) проблема — сжатые данные представляют из себя единый поток, в котором постоянно идут отсылки на предыдущие участки. Таким образом, при повреждении какого-то участка сжатых данных мы теряем не только связанный с ним блок несжатых данных, но и все последующие.
Есть подхода к решению этой проблемы:
В процессе экспериментов я обнаружил, что более-менее заметные потери уровня сжатия начинаются на блоках сжатых данных рамером менее 10Кб.
Ранее упоминалось, что используемая память имеет страничную организацию, я не вижу причин, по которым не стоит использовать соответствие "одна страница — один блок сжатых данных".
То есть минимальный разумный размер страницы равен 16Кб (с запасом на служебную информацию). Однако столь малый размер страницы накладывает существенные ограничения на максимальный размер записи.
Хоть у меня пока и не предвидится записей больше единиц килобайт в сжатом виде, я решил использовать страницы размером 32Кб (итого получается 128 страниц на микросхему).
Резюме:
И, перед тем как закончить со сжатием, хотелось бы обратить внимание, что сжатых данных у нас получается всего несколько байт на запись, поэтому крайне важно не раздувать служебную информацию, каждый байт тут на счету.
Так как у нас записи переменной длины, то нам нужно как-то определять размещение/границы записей.
Я знаю три подхода:
Проиллюстрирую.
Вариант 1:
Тут всё очень просто: зная длину записи мы можем вычислить адрес следующего заголовка. Так мы перемещаемся по заголовкам, пока не встретим область, заполненную 0xff (свободную область) или конец страницы.
Вариант 2:
Из-за переменной длины записи мы не можем заранее сказать как много записей (а значит и заголовков) на страницу нам потребуется. Можно разнести заголовки и сами данные по разным страницам, но мне симпатичнее другой подход: и заголовки, и данные размещаем на одной странице, однако заголовки (постоянного размера) у нас идут от начала страницы, а данные (переменной длины) — от конца. Как только они "встретятся" (свободного места не хватит на новую запись) — считаем эту страницу заполненной.
Вариант 3:
Тут нет нужды хранить в заголовке длину или другую информацию о расположении данных, достаточно маркеров, означающих границы записей. Однако данные приходится обрабатывать при записи/чтении.
В качестве маркера я бы использовал 0xff (которым заполнена страница после erase), таким образом свободная область точно не будет трактоваться как данные.
Сравнительная таблица:
Вариант 1 | Вариант 2 | Вариант 3 | |
---|---|---|---|
Устойчивость к ошибкам | - | + | + |
Компактность | + | - | + |
Сложность реализации | * | ** | ** |
Вариант 1 имеет фатальный недостаток: при повреждении какого-то из заголовков у нас разрушается вся последующая цепочка. Остальные варианты позволяют восстановить часть данных даже при массовых повреждениях.
Но тут уместно вспомнить, что мы решили хранить данные в сжатом виде, так и так мы теряем все данные на странице после "битой" записи, так что хоть в таблице и стоит минус, мы его не учитываем.
Компактность:
Изначально я рассматривал второй вариант как основной (и даже написал реализацию). Отказался от него я только тогда, когда окончательно решил использовать сжатие.
Возможно, когда-нибудь я всё-таки буду использовать подобный вариант. Например, если мне придётся заниматься хранением данных для корабля, курсирующего между Землёй и Марсом — совсем другие требования к надёжности, космическое излучение, ...
Что же до третьего варианта: я поставил ему две звёздочки за сложность реализации просто потому, что не люблю возиться с экранированием, изменением длины в процессе и т.п. Да, возможно, предвзято, но код писать придётся мне — зачем заставлять себя делать то, что не нравится.
Резюме: выбираем вариант хранения в виде цепочек "заголовок с длиной — данные переменной длины" из-за эффективности и простоты реализации.
Уже сейчас не помню, где я подсмотрел идею, но выглядит всё примерно так:
Для каждой записи выделяем несколько бит для хранения флагов.
Как мы говорили ранее, после erase все биты заполнены 1, и мы можем изменять 1 на 0, но не наоборот. Так что для "флаг не установлен" используем 1, для "флаг установлен" — 0.
Вот как может выглядеть помещение записи переменной длины во flash:
Кроме этого, у нас будет флаг “произошла ошибка”, итого 4 битовых флага.
В этом случае у нас есть два стабильных состояния “1111” — запись не началась и “1000” — запись прошла успешно; в случае непредвиденного прерывания процесса записи получим промежуточные состояния, которые мы потом мы сможем обнаружить и обработать.
Подход интересный, но он защищает только от внезапного отключения питания и подобных сбоев, что, конечно, важно, однако это далеко не единственная (и даже не основная) причина возможных сбоев.
Резюме: идём дальше в поисках хорошего решения.
Контрольные суммы тоже дают возможность удостовериться (с достаточной вероятностью) что мы читаем именно то, что должно было быть записано. И, в отличие от рассмотренных выше битовых полей, они работают всегда.
Если расматривать список потенциальных источников проблем, о которых мы говорили выше, то контрольная сумма способна распознать ошибку независимо от её происхождения (за исключением, пожалуй, злокозненных инопланетян — те могут подделать и контрольную сумму тоже).
Так что, если наша цель проверить, что данные целы, контрольные суммы — отличная идея.
Выбор алгоритма вычисления контрольной суммы вопросов не вызывал — CRC. С одной стороны, математические свойства позволяют в 100% ловить ошибки некоторых типов, с другой — на случайных данных обычно этот алгоритм показывает вероятность коллизий не сильно больше теоретического предела $inline$2^{-n}$inline$. Пусть это не самый быстрый алгоритм, не всегда минимальный по числу коллизий, но у него есть очень важное качество: во встречавшися мне тестах не попадались паттерны, на которых он бы явно проваливался. Стабильность — это главное качество в данном случае.
Пример объёмного исследования: часть 1 [6], часть 2 [7] (ссылки на narod.ru, извините).
Однако задача выбора контрольной суммы не завершена, CRC — это целое семейство контрольных сумм. Нужно определиться с длиной, а потом выбрать полином.
Выбор длины контрольной суммы не такой простой вопрос, как кажется с первого взгляда.
Проиллюстрирую:
Пусть у нас вероятность ошибки в каждом байте $inline$10^{-3}$inline$ и идеальная контрольная сумма, посчитаем среднее число ошибок на миллион записей:
Данные, байт | Контрольная сумма, байт | Необнаруженных ошибок | Ложных обнаружений ошибок | Итого неправильных срабатываний |
---|---|---|---|---|
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 |
Казалось бы, всё просто — выбирай в зависимости от длины защищаемых данных длину контрольной суммы с минимумом неправильных срабатываний — и дело в шляпе.
Однако, с короткими контрольными суммами возникает проблема: они, хоть и хорошо обнаруживают единичные битовые ошибки, могут с достаточно большой вероятностью принять за верные совершенно случайные данные. На хабре уже была статья, описывающая проблему в реальной жизни [8].
Поэтому, чтобы сделать случайное совпадение контрольной суммы практически невозможным, нужно использовать контрольные суммы длиной 32 бита и более (для длин более 64 бит обычно используют криптографические хэш-функции).
Несмотря на то, что ранее я писал, что нужно экономить место всеми силами, всё-таки будем использовать 32-битную контрольную сумму (16 бит мало, вероятность коллизии больше 0.01%; а 24 бита, говорится, ни туда и ни сюда).
Тут может возникнуть возражение: для того ли мы экономили каждый байт при выборе сжатия, чтобы сейчас отдать 4 байта сразу? не лучше ли было не сжимать и не добавлять контрольную сумму? Конечно нет, отсутствие сжатия не означает, что проверка целостности нам не нужна.
По выбору полинома не будем изобретать велосипед, а возьмём популярный сейчас CRC-32C.
Этот код обнаруживает 6 битовых ошибок на пакетах до 22 байт (пожалуй, самый частый случай для наc), 4 битовые ошибки на пакетах до 655 байт (тоже частый случай для нас), 2 или любое нечётное число битовых ошибок на пакетах любой разумной длины.
Статья википедии [9] про CRC.
Параметры кода crc-32c [10] на сайте Купмана [11] — пожалуй, главного специалиста по CRC на планете.
В его статье [12] есть ещё один интересный код [13], обеспечивающий чуть лучшие параметры для актуальных для нас длин пакетов, но я не посчитал разницу существенной, а себя достаточно компетентным, чтобы выбрать кастомный код вместо стандартного и хорошо исследованного.
Ещё, так как у нас данные сжаты, возникает вопрос: считать контрольную сумму сжатых или несжатых данных?
Аргументы "за" подсчёт контрольной суммы несжатых данных:
Аргументы "против" подсчёта контрольной суммы несжатых данных:
В данном проекте я решил отойти от общепринятой практики хранения контрольной суммы несжатых данных.
Резюме: используем CRC-32C, контрольную сумму считаем от данных в том виде, в котором они записываются во flash (после сжатия).
Использование избыточного кодирования не позволяет, конечно, исключить потерю данных, однако, оно может существенно (зачастую на многие порядки) снизить вероятность невосстановимой потери данных.
Мы можем использовать разные виды избыточности для того, чтобы исправлять ошибки.
Коды Хэмминга могут исправлять одиночные битовые ошибки, коды Рида-Соломона символьные, несколько копий данных совместно с контрольными суммами или кодирование вроде RAID-6 могут помочь восстановить данные даже в случае массовых повреждений.
Изначально я был настроен на широкое использование помехоустойчивого кодирования, но потом понял, что сначала нужно иметь представление от каких ошибок мы хотим защититься, а потом уже выбирать кодирование.
Мы говорили ранее, что ошибки нужно выявлять как можно быстрее. В какие моменты мы можем столкнуться с ошибками?
То есть только ошибки третьего типа (самопроизвольная порча данных при хранении) не могут быть исправлены без помехоустойчивого кодирования. Думается, подобные ошибки всё-таки крайне маловероятны.
Резюме: было решено отказаться от избыточного кодирования, но, если эксплуатация покажет ошибочность этого решения, то вернуться к рассмотрению вопроса (с уже накопленной статистикой по сбоям, которая позволит выбрать оптимальный вид кодирования).
Разумеется, формат статьи не позволяет обосновать каждый бит в формате (да и у меня уже иссякли силы), поэтому кратко пробегусь по некоторым моментам, не затронутым ранее.
Очень помог онлайн-генератор [15] кодов Хаффмана. Буквально за несколько минут удалось подобрать нужные коды переменной длины.
Поля, размером превышающие один байт, хранятся в big-endian формате (network byte order), то есть 0x1234 записывается как 0x12, 0x34.
Вся флеш-память разбита на страницы равного размера.
Размер страницы по умочанию 32Кб, но не более, чем 1/4 от общего размера микросхемы памяти (для микросхемы на 4Мб получается 128 страниц).
Каждая страница хранит данные независимо от других (то есть данные одной страницы не ссылаются на данные другой страницы).
Все страницы пронумерованы в естественном порядке (в порядке возрастания адресов), начиная с номера 0 (нулевая страница начинается с адреса 0, первая — с 32Кб, вторая — с 64Кб и т.д.)
Микросхема памяти используется как циклический буфер (ring buffer), то есть сначала запись идёт в страницу с номером 0, потом с номером 1, ..., когда мы заполняем последную страницу, то начинается новый цикл и запись продолжается с нулевой страницы.
В начале страницы хранится 4-байтный заголовок страницы, потом контрольная сумма заголовка (CRC-32C), далее хранятся записи в формате "заголовок, длина, контрольная сумма".
Заголовок страницы (на схеме грязно-зелёный) состоит из:
0xed00 ⊕ номер страницы
;Записи на странице хранятся в сжатом виде (используется алгоритм deflate). Все записи на одной странице сжимаются в одном потоке (используется общий словарь), на каждой новой странице сжатие начинается заново. То есть для декомпрессии любой записи требуются все предыдущие записи с этой страницы (и только с этой).
Каждая запись сжимется с флагом Z_SYNC_FLUSH, при этом в конце сжатого потока оказываются 4 байта 0x00, 0x00, 0xff, 0xff, предварённые, возможно, ещё одним или двумя нулевыми байтами.
Эту последовательность (длиной 4, 5 или 6 байт) мы отбрасываем при записи в флеш-память.
Заголовок записи представляет из себя 1, 2 или 3 байта, хранящие:
Таблица значений 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 обладает свойством "продолжательности", действует (плюс-минус инвертирование бит в процессе) такая формула: $inline$CRC(init, A || B) = CRC(CRC(init, A), B)$inline$.
То есть фактически мы высчитываем 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.
Его не стоит использовать с NAND или MLC NOR (а такая память вообще есть в продаже? встречал упоминания только в работах по кодам коррекции).
Тем более, его не стоит использовать с устройствами, имеющими свой FTL: USB flash, SD, MicroSD, etc (для такой памяти я делал формат с размером страницы в 512 байт, сигнатурой в начале каждой страницы и уникальными номерами записей — иногда из "глюкнувшей" флешки удавалось простым последовательным чтением восстановить все данные).
В зависимости от задач формат без изменений можно использовать на флешках от 128Кбит (16Кб) до 1Гбит (128Мб). При желании можно использовать и на микросхемах большего объёма, только, наверное, нужно скорректировать размер страницы (Но тут уже встаёт вопрос экономической целесообразности, цена на NOR Flash большого объёма не радует).
Если кому-то формат показался интересным, и он захочет использовать его в открытом проекте — пишите, постараюсь найти время, причесать код и выложить на github.
Как видим, в итоге формат оказался простым и даже скучным.
В статье сложно отразить эволюцию своей точки зрения, но поверьте: изначально мне хотелось создать что-то неубиваемое, способное выжить даже после ядерного взрыва в непосредственной близости. Однако, разум (надеюсь) всё-таки победил и постепенно приоритеты сдвинулось к простоте и компактности.
Может ли получиться так, что я ошибся? Да, конечно. Вполне может оказаться, например, что мы закупили партию некачественных флешек. Или по какой-то другой причине оборудование не оправдает ожидания по надёжности.
Есть ли у меня план на этот случай? Я думаю, что по прочтению статьи вы не сомневаетесь, что план есть. И даже не один.
Если чуть более серьёзно, формат разработан одновременно и как рабочий вариант, и как "пробный шар".
На сегодняшний момент на столе всё работает нормально, буквально на днях решение будет развёрнуто (примерно) на сотне устройств, посмотрим, что будет в "боевой" эксплуатации (благо, надеюсь, формат позволяет надёжно детектировать сбои; так что получится собрать полноценную статистику). Через несколько месяцев можно будет делать выводы (а если не повезёт — то и раньше).
Если по итогам использования обнаружатся серьёзные проблемы и потребуются доработки, то я обязательно об этом напишу.
Не хотелось составлять длинный нудный список использованных работ, в конце концов гугл есть у всех.
Тут я решил оставлять список находок, которые мне показались особенно интересными, однако постепенно они перекочевали непосредственно в текст статьи, и в списке остался один пункт:
Автор: edo1h
Источник [17]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/raspberry-pi/339063
Ссылки в тексте:
[1] в конец: #format
[2] at25df321a: https://www.adestotech.com/wp-content/uploads/doc3686.pdf
[3] обсуждения: https://electronics.stackexchange.com/questions/225956/what-would-happen-in-case-of-power-outage-during-nor-flash-erase-or-programming
[4] отличная статья: https://www.bolet.org/~pornin/deflate-flush.html
[5] задал вопрос: https://github.com/facebook/zstd/issues/900
[6] часть 1: http://amsoftware.narod.ru/algo.html
[7] часть 2: http://amsoftware.narod.ru/algo2.html
[8] проблему в реальной жизни: https://habr.com/ru/post/428746/
[9] Статья википедии: https://en.wikipedia.org/wiki/Cyclic_redundancy_check
[10] Параметры кода crc-32c: https://users.ece.cmu.edu/~koopman/crc/c32/0x8f6e37a0_len.txt
[11] сайте Купмана: http://users.ece.cmu.edu/~koopman/crc/notes.html
[12] его статье: http://users.ece.cmu.edu/~koopman/networks/dsn02/dsn02_koopman.pdf
[13] ещё один интересный код: https://users.ece.cmu.edu/~koopman/crc/c32/0xfa567d89_len.txt
[14] кто его знает: https://www.cvedetails.com/vulnerability-list/vendor_id-72/product_id-1820/GNU-Zlib.html
[15] онлайн-генератор: https://planetcalc.com/2481/
[16] infgen: https://github.com/madler/infgen/
[17] Источник: https://habr.com/ru/post/479044/?utm_campaign=479044&utm_source=habrahabr&utm_medium=rss
Нажмите здесь для печати.