Предистория

Имаме търговски автомати, разработени от нас. В тях има Raspberry Pi и малко свързващи платки. Свързани са монетоприемник, банкнотоброяч и банков терминал... Всичко се управлява от самостоятелна програма. Цялата история на работата на автоматите се записва в журнал на флашка (MicroSD), която после се предава онлайн (чрез USB модем) на сървър, където се съхранява в база данни. Информацията за продажбите се зарежда в 1С, има и простичък уеб интерфейс за мониторинг и т.н.

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

Проблема

Флашките показват, че са много ненадеждни устройства. Те конструктивно се развалят с завидна редовност. Това води до спирания на автоматите и (ако по някаква причина журналът не може да бъде предаден онлайн) до загуба на данни.

Това не е първият опит с флашките; преди това имаше друг проект с повече от сто устройства, където журналът се съхраняваше на USB флашки, там имаше също проблеми с надеждността, понякога броят на повредените устройства за месец достигаше десетки. Опитвахме различни флашки, включително и маркови на SLC памет, но въпреки че някои модели са по-надеждни от други, смяната на флашките не реши проблема коренно.

Внимание! Дълъг текст! Ако не ви интересува "защо", а само "как", можете веднага да отидете в края статията.

Решение

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

USB HDD също не изглежда особено привлекателно решение.

Затова стигнахме до такъв вариант: да оставим зареждането от MicroSD, но да ги използваме в режим само за четене, а журналът за работа (и друга уникална информация, специфична за конкретното устройство — серийен номер, калибровки на сензори и т.н.) да съхраняваме на друго място.

Темата за файлови системи с режим само за четене за Raspberry Pi вече е проучена в детайли, няма да се спирам на детайлите в тази статия. (но ако се прояви интерес, може би ще напиша мини-статия за тази тема). Единственото нещо, което искам да подчертая: и по личен опит, и по отзивите от вече внедрили, има прилични подобрения в надеждността. Да, напълно да се избавим от повреди не е възможно, но е напълно реално значително да се намали тяхната честота. Освен това картите стават унифицирани, което значително опростява замяната за обслужващия персонал.

Хардуерна част

Не беше имало особени съмнения относно избора на тип памет — NOR Flash.
Аргументи:

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

Да предвидим изискванията за обем и ресурс.

Искам да гарантирам, че данните ще се запазват за няколко дни. Нужно е това, за да не се изгуби историята на продажбите в случай на проблеми с връзката. Ще се ориентираме на 5 дни, за този период (включително уикенди и празници) може да се реши проблемът.

В момента натрупваме около 100кб журнал на ден (3-4 хиляди записа), обаче постепенно тази цифра нараства — увеличава се детайлизацията, добавят се нови събития. Плюс има и периодични изблици (например, някой сензор започва да спами с фалшиви сработвания). Ще изчислим на 10 хиляди записа по 100 байта — мегабайт на ден.

В крайна сметка излиза 5Мб чисти (добре компресируеми) данни. Към тях още (груба преценка) 1Мб служебни данни.

Т.е. ни трябва микросхема от 8Мб, ако не използваме компресия, или 4Мб, ако използваме. Съвсем реалистични цифри за този тип памет.

Що се отнася до ресурса: ако планираме, че паметта ще бъде презаписвана не по-често от веднъж на 5 дни, то за 10 години експлоатация ще получим по-малко от хиляда цикъла презаписване.
Напомням, производителят обещава сто хиляди.

Няколко думи за NOR срещу NAND

Днес, разбира се, NAND паметта е много по-популярна, но за този проект не бих я използвал: NAND, за разлика от NOR, задължително изисква използването на кодове за корекция на грешки, таблици за дефектни блокове и т.н., а и крачетата на NAND чиповете обикновено са много повече.

Като недостатъци на NOR можем да посочим:

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

Изглежда, че няма нищо критично за нас, така че продължаваме.

Ако ви интересуват детайли, избран е чипът 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. Изтриване:
   Разбира се, трябва да можем да извършим и обратната операция — да променим 0 на 1, именно за това съществува операцията изтриване. В отличие от първите две, тя оперира не с байтове, а с блокове (минималният erase block в избраната микросхема е 4KB). Изтриването унищожава целия блок и това е единственият начин да сменим 0 на 1. Следователно при работа с флаш памет често е необходимо да се подравняват структурите на данните на границата на erase блока.
   Запис в NOR Flash:

Двоични данни

Беше
01010101

Записахме
00001111

Стана
00000101

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

Освен журнала, трябва да съхраним някаква „настройваща“ информация, както обновяема, така и не: някакъв ID на устройството, калибровки на сензорите, флаг „устройството е временно изключено“ и др.
Тази информация представлява набор от записи ключ-стойност, също съхранявани в CBOR. Нямаме много от тази информация (максимум няколко килобайта), обновява се не често.
Нататък ще я наричаме контекст.

Ако си спомним откъде започна тази статия, много важно е да се осигури надеждност на съхранението на данните и, по възможност, непрекъсната работа дори в случай на хардуерни аварии/повреждане на данни.

Какви източници на проблеми можем да разгледаме?

• Изключване на захранването в момент на операции write/erase. Това е от рода на „няма против лома прием“.
  Информация от обсъждане stackexchange: при изключване на захранването в момента на работа с флаш памет, какво erase (задаване на 1), така и write (задаване на 0) водят до неопределено поведение: данните могат да бъдат записани, записани частично (да речем, предадохме 10 байта/80 бита, а успяхме да запишем само 45 бита), не е изключено и част от битовете да бъде в „междинно“ състояние (четенето може да даде както 0, така и 1);
• Грешки на самата флаш памет.
  BER макар и много нисък, не може да бъде равен на нула;
• Грешки по шината.
  Данните, предавани по SPI, не са защитени, и могат да възникнат както единични битови грешки, така и грешки в синхронизацията — загуба или добавяне на битове (което води до значителни изкривявания на данните);
• Други грешки/сбои
  Грешки в кода, "глюкове" на Raspberry, намеса на извънземни...

Формулирах изисквания, изпълнението на които, според мен, е необходимо за осигуряване на надеждност:

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

Идеи, подходи, размисли

Когато започнах да мисля по тази задача, в главата ми преминаха множество идеи, например:

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

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

Сжимане на данни

Сами събитията, които записваме в дневника, са достатъчно однотипни и повтарящи се ("хвърлихме монета от 5 лева", "натиснахме бутона за връщане на ресто", ...). Затова компресията трябва да се окаже достатъчно ефективна.

Разходите за компресия са незначителни (процесорът ни е достатъчно мощен, дори на първия Pi имаше едно ядро с честота 700MHz, на актуалните модели няколко ядра с честота над един гигахерц), скоростта на обмен с хранилището е ниска (няколко мегабайта в секунда), размерът на записите е малък. Общо взето, ако компресията повлияе на производителността, то само положително. (абсолютно не е критично, просто констатирам). У нас не е истински embedded, а стандартен Linux, така че реализацията не би трябвало да изисква много усилия (достатъчно е просто да свържем библиотеката и да използваме няколко нейните функции).

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

• gzip, xz, zstd показаха близки резултати (40KB).
  Изненада ме, че модерен xz показа резултати на нивото на gzip или zstd;
• lzip с настройки по подразбиране даде малко по-слаб резултат;
• lz4 и lzop показаха не много добър резултат (150KB);
• bzip2 изненадващо показа добър резултат (18KB).

И така, данните се компресират много добре.
Така че (ако не намерим фатални недостатъци) компресия ще има! Просто защото на същата флашка ще се побере повече информация.

Нека помислим за недостатъците.

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

Виждам три решения:

1. Да компресираме всяка запись с помощта на речникова компресия вместо разгледаните алгоритми по-горе.
   Това е доста работещ вариант, но не ми харесва. За да осигурим приемлив ниво на компресия, речникът трябва да бъде „приспособен“ за конкретни данни, всяка промяна ще доведе до катастрофално спадане на нивото на компресия. Да, проблемът се решава с разработването на нова версия на речника, но това е главоболие — ще трябва да съхраняваме всички версии на речника; в всяка запись ще трябва да посочим с коя версия на речника е компресирана…
2. Да компресираме всяка запись с „класически“ алгоритми, но независимо от другите.
   Обсъжданите алгоритми за компресия не са предназначени да работят с записи с такъв размер (десетки байта), коэффициентът на компресия ще е явно под 1 (т.е. увеличаване на обема на данните вместо компресия);
3. Да направим FLUSH след всяка запись.
   В много библиотеки за компресия има поддръжка на FLUSH. Това е команда (или параметър на процедурата за компресия), получавайки която архиваторът формирa искан поток така, че на неговата основа да могат да бъдат възстановени всичко не компресираните данни, които вече са били получени. Такъв аналог 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Кб.

В статията, на която се позовавам, има обяснение:

Нов тип 0 блок с празно съдържание е добавен.

Тип 0 блок с празно съдържание се състои от:

• три битовия заглавен блок;
• от 0 до 7 бита, равни на нула, за постигане на байтно подравняване;
• четирибайтовата последователност 00 00 FF FF.

Както не е трудно да се забележи, в последния блок преди тези 4 байта има от 3 до 10 нулеви бита. Въпреки това практиката показа, че нулевите битове всъщност са минимум 10.

Оказва се, че толкова кратки блокове данни обикновено (винаги?) се кодират с помощта на блок тип 1 (фиксиран блок), който винаги завършва с 7 нулеви бита, така получаваме 10-17 гарантирано нулеви бита (а останалите ще са нулеви с вероятност около 50%).

И така, при тестовите данни в 100% от случаите пред 0x00, 0x00, 0xff, 0xff има един нулев байт, а в повече от една трета от случаите — два нулеви байта. (възможно е да е свързано с факта, че използвам бинарен CBOR, а при използването на текстов JSON блковете тип 2 — динамичен блок, биха се срещали по-често, съответно биха се срещали блкове без допълнителни нулеви байта пред 0x00, 0x00, 0xff, 0xff).

В заключение, на наличните тестови данни можем да се вместим в по-малко от 250Кб компресирани данни.

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

В крайна сметка, от моите тестови данни получих 3-4 байта на запис, коефициентът на компресия се оказа над 6:1. Честно казано: не очаквах такъв резултат, според мен всичко, което е по-добро от 2:1 — вече е резултат, оправдаващ използването на компресия.

Всичко е чудесно, но zlib (deflate) — все пак е архаичен и малко старомоден алгоритъм за компресия. Самото това, че като речник се използват последните 32Кб от потока на нес compressed данни, днес изглежда странно (тоест, ако някой блок данни е много подобен на това, което е било в входния поток преди 40Кб, той ще започне да се архивира отново, а не да се позова на миналото вхождане). В съвременните архиватори размерът на речника често се измерва в мегабайти, а не в килобайти.

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

Следващият, който пробвах, беше bzip2 (напомням, без FLUSH показа фантастична степен на компресия, почти 100:1). Уви, с FLUSH се представи много зле, размерът на компресираните данни се оказа по-голям от нес compressed данните.

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

Libbz2 предлага само един вариант за flush, който, изглежда, изчиства речника (аналог на Z_FULL_FLUSH в zlib), говоренето за някаква ефективна компресия след това не може да е актуално.

И последният, който пробвах, беше zstd. В зависимост от параметрите, той компресира или на ниво gzip, но много по-бързо, или пък по-добре от gzip.

Уви, с FLUSH и той не се представи „много добре“: размерът на компресираните данни стана около 700Кб.

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

На това реших да спра експериментите с архиваторите (припомням, xz, lzip, lzo, lz4 не се показаха на етапа на тестване без FLUSH, а не исках да разглеждам по-екзотични алгоритми за компресия).

Връщаме се към проблемите с архивирането.

Вторият проблем (както се казва, по ред, а не по значение) е, че компресираните данни представляват единен поток, в който постоянно има препратки към предишни участъци. Така, при повреждане на някой участък от компресираните данни, ние губим не само свързания с него блок некомутирани данни, но и всички последващи.

Има подходи за решаване на този проблем:

1. Да се предотврати появата на проблема — да се добави излишна информация в компресираните данни, която да позволи определяне и поправяне на грешки; за това ще говорим по-късно;
2. Да се минимизира въздействието в случай на възникване на проблема.
   Вече споменахме, че можем да компресираме всеки блок данни независимо, при което проблемът ще изчезне сам по себе си (повредата на един блок ще доведе до загуба на данни само от този блок). Въпреки това, това е крайно решение, при което компресирането на данни ще бъде неефективно. Обратната крайност е: да използваме всичките 4MB на нашия чип като единен архив, което ще ни осигури отлично компресиране, но катастрофални последици в случай на повреждане на данни.
   Да, нужен е компромис от гледна точка на надеждността. Но трябва да помним, че разработваме формат за съхранение на данни за неенергийна памет с изключително нисък BER и деклариран срок на съхранение на данните от 20 години.

В процеса на експерименти установих, че по-очевидните загуби на нивото на компресия започват на блокове с компресирани данни с размер под 10KB.
По-рано се споменаваше, че използваната памет има странична организация, не виждам причини, поради които не трябва да използваме съответствието "една страница — един блок с компресирани данни".

Така минималният разумен размер на страницата е равен на 16KB (с запас за служебна информация). Въпреки това, толкова малкият размер на страницата налага съществени ограничения върху максималния размер на записа.

Въпреки че засега не предвиждам записи, по-големи от единичен килобайт в компресиран вид, реших да използвам страници с размер 32KB (всичко общо е 128 страници на чип).

Резюме:

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

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

Съхранение на заглавията на данните

Тъй като нашите записи са с променлива дължина, трябва да определим по някакъв начин разположението/границите на записите.

Зная три подхода:

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

Ще илюстрирам.

Вариант 1:

Тук всичко е много просто: знаейки дължината на записа, можем да изчислим адреса на следващото заглавие. Така преминаваме през заглавията, докато не срещнем област, запълнена с 0xff (свободна област) или края на страницата.

Вариант 2:

Поради променливата дължина на записа, не можем предварително да кажем колко много записи (а следователно и заглавия) ще ни трябват на страницата. Можем да разнесем заглавията и самите данни по различни страници, но ми харесва друг подход: и заглавията, и данните се разполагат на една и съща страница, но заглавията (с постоянен размер) са от началото на страницата, а данните (с променлива дължина) — от края. Веднага щом те „се срещнат“ (няма да имаме достатъчно свободно място за нов запис) — считаме, че тази страница е запълнена.

Вариант 3:

Тук няма нужда да се съхранява дължината или друга информация за разположението на данните в заглавието, достатъчно са маркерите, означаващи границите на записите. Обаче данните трябва да се обработват при записване/читене.
Като маркер бих използвал 0xff (с който страницата е запълнена след изтриване), по този начин свободната област със сигурност няма да се интерпретира като данни.

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

Вариант 1
Вариант 2
Вариант 3

Устойчивост на грешки
—
+
+

Компактност
+
—
+

Сложност на реализиране
*
**
**

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

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

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

Първоначално разглеждах втория вариант като основен (и дори написах имплементация). Отказах се от него чак когато окончателно реших да използвам компресия.

Възможно е, някога все пак да използвам подобен вариант. Например, ако трябва да се занимавам с съхранение на данни за кораб, който пътува между Земята и Марс — изискванията за надеждност са съвсем различни, космическа радиация, …

Що се отнася до третия вариант: сложил съм му две звездички за сложността на реализиране просто защото не обичам да се занимавам с екрантиране, промяна на дължината в процеса и т.н. Да, възможно е да съм предубеден, но кода трябва да пиша аз — защо да се натискам да правя нещо, което не харесвам.

Резюме: избираме варианта за съхранение под формата на вериги "заглавие с дължина — данни с променлива дължина" заради ефективността и простотата на реализиране.

Използването на битови полета за контрол на успешността на записите

Вече не помня къде видях идеята, но изглежда всичко горе-долу така:
За всеки запис отделяме няколко бита за съхранение на флагове.
Както споменахме по-рано, след erase всички битове са запълнени с 1, и можем да променяме 1 на 0, но не и обратно. Така че за 'флаг не е зададен' използваме 1, за 'флаг е зададен' — 0.

Ето как може да изглежда мястото за запис на променлива дължина в флаш:

1. Задаваме флага 'запис на дължината започна';
2. Записваме дължината;
3. Задаваме флага 'запис на данните започна';
4. Записваме данните;
5. Задаваме флага 'записът приключи'.

Освен това, ще имаме флаг 'възникна грешка', което прави общо 4 битови флага.

В този случай имаме две стабилни състояния '1111' — записът не е започнал и '1000' — записът е успешен; при неочаквано прекъсване на процеса на запис ще получим междинни състояния, които по-късно можем да открием и обработим.

Подходът е интересен, но той защитава само от внезапно прекъсване на захранването и подобни неща, което, разбира се, е важно, но това далеч не е единствената (и дори не основната) причина за възможни проблеми.

Резюме: Продължаваме в търсене на добро решение.

Контролни суми

Контролни сумите също дават възможност да се уверим (с достатъчна вероятност), че четем точно това, което трябва да бъде записано. И, за разлика от разгледаните по-горе битови полета, те работят винаги.

Ако разгледаме списъка с потенциални източници на проблеми, за които говорихме по-горе, контролна сума може да разпознае грешка независимо от произхода й (с изключение, може би, на злонамерени извънземни — те могат да фалшифицират и контролна сума).

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

Изборът на алгоритъм за изчисление на контролна сума не поставя въпроси — CRC. От една страна, математическите свойства му позволяват да улавя 100% от грешките от определени типове, а освен това — при случайни данни обикновено този алгоритъм показва вероятността за колизии, незначително по-висока от теоретичния предел. Нека това не е най-бързият алгоритъм и не винаги е минимален по брой колизии, но той притежава много важно качество: в срещаните тестове не попаднах на шаблони, при които той явно да се провали. Стабилността е основното качество в този случай.

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

Въпреки това, задачата за избор на контролна сума не е завършена, CRC е цяло семейство от контролни суми. Нужно е да се определи дължината и след това да се избере полином.

Изборът на дължината на контролна сума не е толкова прост въпрос, колкото изглежда на пръв поглед.

Нека илюстрирам:
Нека имаме вероятност за грешка във всеки байт и идеална контролна сума, да изчислим средния брой грешки на милион записи:

Данни, байт
Контролна сума, байт
Неоткритите грешки
Лъжливи открития на грешки
Общо неправилни срабатывания

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 байта (доста често срещан случай за нас), 4 битови грешки в пакети до 655 байта (също често срещан случай за нас), 2 или всяко нечетно число битови грешки в пакети с всякаква разумна дължина.

Ако някого го интересуват детайлите

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

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

В в неговата статия има още един интересен код, който осигурява малко по-добри параметри за актуалните за нас дължини на пакетите, но не сметнах разликата за съществена, а и себе си за достатъчно компетентен, за да избера персонализиран код вместо стандартния и добре проучен.

Освен това, тъй като данните ни са компресирани, възниква въпросът: дали да се изчисли контролна сума на компресираните или на некомпресираните данни?

Аргументи "за" изчисляването на контролна сума на некомпресираните данни:

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

Аргументи "против" изчисляването на контролна сума на некомпресираните данни:

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

В този проект реших да се откажа от общоприетата практика за съхранение на контролна сума на некомпресираните данни.

Резюме: използваме CRC-32C, контролна сумата се изчислява от данните в състоянието, в което се записват във флаш (след компресия).

Излишък

Използването на излишно кодиране не може, разбира се, да изключи загубата на данни, но може значително (често с много порядъка) да намали вероятността от необратима загуба на данни.

Можем да използваме различни видове излишност, за да коригираме грешки.
Кодовете на Хamming могат да коригират единични битови грешки, кодовете на Reed-Solomon символни, няколко копия на данни в комбинация с контролните суми или кодиране като RAID-6 могат да помогнат за възстановяване на данни дори при масивни повреди.
Първоначално бях решен на широко използване на кодиране с устойчивост на смущения, но после разбрах, че първо трябва да имаме представа от какви грешки искаме да се защитим, а след това да изберем кодиране.

Говорихме по-рано, че грешките трябва да се откриват възможно най-бързо. В кои моменти можем да се срещнем с грешки?

1. Несфомирана запис (поради някакви причини по време на запис захранването е прекъснато, Raspberry е заключен, ...)
   За съжаление, в случай на такава грешка остава само да игнорираме невалидните записи и да считаме данните за загубени;
2. Грешки при запис (поради някакви причини в флаш паметта е записано не това, което трябваше да се запише)
   Тези грешки можем да открием веднага, ако направим контролно четене непосредствено след записа;
3. Изкривяване на данните в паметта по време на съхранение;
4. Грешки при четене
   За коригиране е достатъчно в случай на несъответствие на контролната сума да повторим четенето няколко пъти.

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

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

Други

Разбира се, форматът на статията не позволява обосноваване на всеки бит в формата (и вече се изчерпахме от сили), затова ще преминам накратко през някои моменти, които не бяха засегнати по-рано.

• Решено е да се направят всички страници «равноправни»
  Т.е. няма да има специални страници с метаданни, отделни потоци и т.н., вместо това ще има единен поток, който последователно записва всички страници.
  Това осигурява равномерно износване на страниците, отсъствие на единна точка на повреда, и просто харесва.
• Нужно е задължително да се предвиди версия на формата.
  Формат без номер на версия в заглавието е зло!
  Достатъчно е да добавите в заглавието на страницата поле с някакъв Magic Number (сигнатура), което ще указва използваната версия на формата. (не мисля, че в практиката ще бъдат дори десет);
• Използвайте за записите (които са много) заглавие с променлива дължина, стремейки се повечето случаи да го направите с дължина 1 байт.
• За кодиране на дължината на заглавието и дължината на отрязания елемент от сжатия запис използвайте бинарни кодове с променлива дължина.

Много помогна онлайн генератор на Хъфмън кодове. Буквално за няколко минути успяхме да подберем необходимите кодове с променлива дължина.

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

Ред на байтовете

Полета с размер, надвишаващ един байт, се съхраняват в big-endian формат (мрежов ред на байтовете), т.е. 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 на всички предишни байтове на заглавията и данните на тази страница.

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

Заглавието е конструирано по такъв начин, че първият му байт винаги да е различен от 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 флаш, SD, MicroSD и др. (за такава памет създадох формат с размер на страница от 512 байта, сигнатура в началото на всяка страница и уникални номера на записи — понякога успявах да възстановя всички данни чрез просто последователно четене от „глюкнала“ флашка.).

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

Ако на някого форматът му се е сторил интересен, и иска да го използва в открит проект — пишете, ще се постарая да намеря време, да причесам кода и да го кача в github.

Заключение

Както виждаме, форматът в крайна сметка се оказа прост. и дори скучен..

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

Може ли да се окаже, че съм се заблудил? Да, разбира се. Може да се окаже, например, че сме закупили партида некачествени чипове. Или по друга причина оборудването да не оправдае очакванията за надеждност.

Имам ли план за този случай? Мисля, че след прочитането на статията не се съмнявате, че план има. И дори не един.

Ако бъдем малко по-сериозни, форматът е разработен едновременно и като работен вариант, и като „пробен топ“.

В момента всичко на бюрото работи нормално, буквално след няколко дни решението ще бъде развёрнато. (приблизително) на стотици устройства, ще видим какво ще стане в "бойна" експлоатация (слава богу, се надявам, че формата позволява надеждно откриване на повреди; така че ще може да се събере пълна статистика). След няколко месеца ще можем да направим изводи (а ако не ни провърви — и по-рано).

Ако в края на използването се установят сериозни проблеми и са необходими допълнителни разработки, определено ще пиша за това.

Литература

Не бях искал да съставям дълъг скучен списък с използвани работи, накрая всеки може да ползва Google.

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

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

Източник: habr.com