праистория

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

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

проблем

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

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

Внимание! Лонгрид! Ако не се интересувате от „защо“, а само от „как“, можете да отидете направо в нишката статия.

Решение

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

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

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

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

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

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

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

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

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

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

Общо излизат 5MB чисти (добре компресирани) данни. Повече за тях (груба оценка) 1MB сервизни данни.

Тоест имаме нужда от 8MB чип, ако не използваме компресия, или 4MB, ако го използваме. Доста реалистични числа за този тип памет.

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

Малко за NOR срещу NAND

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

Недостатъците на NOR включват:

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

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

Ако подробностите са интересни, микросхемата е избрана at25df321a (това обаче не е важно, на пазара има много аналози, които са съвместими по щифтове и командна система; дори ако искаме да инсталираме микросхема от различен производител и/или различен размер, всичко ще работи без промяна на код).

Използвам драйвера, вграден в ядрото на Linux; на Raspberry, благодарение на поддръжката на наслагване на дървото на устройствата, всичко е много просто - трябва да поставите компилираното наслагване в /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 флаш изглежда като обикновено, но има една особеност: можете да промените само 1 на 0, но не и обратното. Например, ако имаме 0x55 в клетка от паметта, тогава след като напишем 0x0f в нея, 0x05 вече ще се съхранява там (вижте таблицата точно по-долу);
3. Изтрива:
   Разбира се, трябва да можем да направим и обратната операция - да променим 0 на 1, точно за това е операцията за изтриване. За разлика от първите два, той работи не с байтове, а с блокове (минималният блок за изтриване в избрания чип е 4kb). Изтриването унищожава целия блок и е единственият начин да промените 0 на 1. Следователно, когато работите с флаш памет, често трябва да подравнявате структурите от данни към границата на блока за изтриване.
   Запис в NOR Flash:

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

това е
01010101

Записано
00001111

Е станал
00000101

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

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

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

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

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

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

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

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

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

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

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

Компресиране на данни

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

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

Част от дневника беше взета от работещо устройство (1.7 MB, 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. Това е команда (или параметър към процедурата за компресиране), при получаването на която архиваторът формира компресиран поток, за да може да се използва за възстановяване всички некомпресирани данни, които вече са получени. Такъв аналог sync във файлови системи или commit в sql.
   Важното е, че следващите операции за компресиране ще могат да използват натрупания речник и степента на компресия няма да пострада толкова много, колкото в предишната версия.

Мисля, че е очевидно, че избрах третия вариант, нека го разгледаме по-подробно.

Намерени страхотна статия относно FLUSH в zlib.

Направих тест на коляното въз основа на статията, взех 70 хиляди записа в журнал от реално устройство с размер на страницата 60 Kb (ще се върнем към размера на страницата по-късно) получено:

Сурови данни
Компресия gzip -9 (без FLUSH)
zlib с Z_PARTIAL_FLUSH
zlib с Z_SYNC_FLUSH

Обем, KB
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 Kb.

Статията, към която дадох връзка, има обяснение:

Добавен е нов блок тип 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).

Общо, като се използват наличните тестови данни, е възможно да се поберат в по-малко от 250Kb компресирани данни.

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

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

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

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

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

Моите предположения за причините за неуспеха

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

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

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

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

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

Да се ​​върнем на проблемите с архивирането.

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

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

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

По време на експериментите открих, че повече или по-малко забележими загуби в нивото на компресия започват при блокове от компресирани данни с размер под 10 KB.
По-рано беше споменато, че използваната памет е странирана; не виждам причина защо не трябва да се използва кореспонденцията „една страница - един блок от компресирани данни“.

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

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

Резюме:

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

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

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

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

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

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

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

Вариант 1:

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

Вариант 2:

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

Вариант 3:

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

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

Опция 1
Опция 2
Опция 3

Толерантност към грешки
-
+
+

плътност
+
-
+

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

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

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

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

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

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

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

Резюме: Избираме опцията за съхранение под формата на вериги „заглавие с дължина - данни с променлива дължина“ поради ефективност и лекота на изпълнение.

Използване на битови полета за наблюдение на успеха на операциите за запис

Вече не помня откъде ми хрумна идеята, но изглежда така:
За всеки запис ние разпределяме няколко бита за съхранение на флагове.
Както казахме по-рано, след изтриване всички битове се запълват с 1s и можем да променим 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-32c на Уеб сайт на Koopman — може би водещият специалист по CRC на планетата.

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

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

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

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

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

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

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

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

Съкращаване

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

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

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

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

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

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

Друг

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

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

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

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

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

Полетата, по-големи от един байт, се съхраняват във формат big-endian (мрежов ред на байтовете), тоест 0x1234 се записва като 0x12, 0x34.

Пагинация

Цялата флаш памет е разделена на страници с еднакъв размер.

Размерът на страницата по подразбиране е 32Kb, но не повече от 1/4 от общия размер на чипа с памет (за 4MB чип се получават 128 страници).

Всяка страница съхранява данни независимо от другите (т.е. данните на една страница не препращат към данни на друга страница).

Всички страници са номерирани в естествен ред (във възходящ ред на адресите), започвайки с номер 0 (нулевата страница започва от адрес 0, първата страница започва от 32Kb, втората страница започва от 64Kb и т.н.)

Чипът с памет се използва като цикличен буфер (рингов буфер), тоест първо записът отива на страница номер 0, след това номер 1, ..., когато запълним последната страница, започва нов цикъл и записът продължава от страница нула .

Вътре в страницата

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

Заглавието на страницата (мръсно зелено в диаграмата) се състои от:

• двубайтово поле Magic Number (също знак за версията на формата)
  за текущата версия на формата се изчислява като 0xed00 ⊕ номер страницы;
• двубайтов брояч „Версия на страницата“ (номер на цикъла на презапис на паметта).

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

Всеки запис ще бъде компресиран с флага 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), страници с неизвестно магическо число или неправилен CRC се игнорират.
От „правилните“ страници се избират страници с максимална версия и от тях се взема страницата с най-голям номер.
Прочита се първият запис, проверява се коректността на CRC и наличието на флага „контекст“. Ако всичко е наред, тази страница се счита за актуална. Ако не, връщаме се към предишната, докато намерим „жива“ страница.
и на намерената страница четем всички записи, тези, които използваме с флага „контекст“.
Запазете zlib речника (ще е необходим за добавяне към тази страница).

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

Добавяне на запис в дневник

Компресираме записа с правилния речник, посочвайки Z_SYNC_FLUSH.Виждаме дали компресираният запис пасва на текущата страница.
Ако не пасва (или има CRC грешки на страницата), започнете нова страница (вижте по-долу).
Записваме записа и CRC. Ако възникне грешка, започнете нова страница.

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

Избираме безплатна страница с минималния брой (за безплатна считаме страница с неправилна контролна сума в хедъра или с версия по-малка от текущата). Ако няма такива страници, изберете страницата с минималния брой от тези, които имат версия, равна на текущата.
Изтриваме избраната страница. Проверяваме съдържанието с 0xff. Ако нещо не е наред, вземете следващата безплатна страница и т.н.
Пишем заглавка на изтритата страница, първият запис е текущото състояние на контекста, следващият е ненаписаният запис в дневника (ако има такъв).

Приложимост на формата

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

Разбира се, форматът е „пригоден“ за SLC NOR Flash.

Не трябва да се използва с носители с висок BER като NAND или MLC NOR (такава памет предлага ли се дори за продажба? Виждал съм да се споменава само в работи върху коригиращи кодове).

Освен това не трябва да се използва с устройства, които имат собствен FTL: USB флаш, SD, MicroSD и др (за такава памет създадох формат с размер на страницата от 512 байта, подпис в началото на всяка страница и уникални номера на записи - понякога беше възможно да се възстановят всички данни от „сбъркано“ флаш устройство чрез просто последователно четене).

В зависимост от задачите форматът може да се използва без промени на флашки от 128Kbit (16Kb) до 1Gbit (128MB). Ако желаете, можете да го използвате на по-големи чипове, но вероятно трябва да коригирате размера на страницата (Но тук вече възниква въпросът за икономическата осъществимост; цената за голям обем NOR Flash не е обнадеждаваща).

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

Заключение

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

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

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

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

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

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

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

Литература

Не исках да правя дълъг досаден списък с използвани произведения; в крайна сметка всеки има Google.

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

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

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