praistorija

Постоје аутомати нашег дизајна. Унутар Распберри Пи и мало ожичења на посебној плочи. Прикључени су акцептор новчића, акцептор новчаница, банковни терминал... Све се контролише помоћу самописног програма. Целокупна радна историја се уписује у дневник на флеш диску (МицроСД), који се затим преноси преко Интернета (помоћу УСБ модема) на сервер, где се чува у бази података. Информације о продаји се учитавају у 1ц, постоји и једноставан веб интерфејс за праћење итд.

Односно, дневник је од виталног значаја - за рачуноводство (приходи, продаја, итд.), праћење (све врсте кварова и друге околности више силе); Ово су, могло би се рећи, све информације које имамо о овој машини.

проблем

Флеш дискови се показују као веома непоуздани уређаји. Не успевају са завидном редовношћу. Ово доводи до застоја машине и (ако из неког разлога дневник није могао да се пренесе на мрежу) до губитка података.

Ово није прво искуство коришћења флеш дискова, пре овога је постојао још један пројекат са више од сто уређаја, где је часопис чуван на УСБ флеш дисковима, било је и проблема са поузданошћу, на моменте већи број оних који су отказали у месец дана је било на десетине. Пробали смо различите флеш дискове, укључујући и оне брендиране са СЛЦ меморијом, и неки модели су поузданији од других, али замена флеш дискова није радикално решила проблем.

Упозорење! Лонгреад! Ако вас не занима „зашто“, већ само „како“, можете ићи право у нит чланци.

одлука

Прво што вам пада на памет је: напустите МицроСД, инсталирајте, на пример, ССД и покрените систем са њега. Теоретски могуће, вероватно, али релативно скупо и не тако поуздано (додат је УСБ-САТА адаптер; статистика кварова за буџетске ССД дискове такође није охрабрујућа).

УСБ ХДД такође не изгледа као посебно атрактивно решење.

Стога смо дошли до ове опције: оставите покретање са МицроСД-а, али их користите у режиму само за читање и сачувајте дневник рада (и друге информације јединствене за одређени комад хардвера - серијски број, калибрације сензора, итд.) негде другде .

Тема ФС-а само за читање за малине је већ проучавана изнутра и споља, нећу се задржавати на детаљима имплементације у овом чланку (али ако постоји интересовање, можда ћу написати мини чланак на ову тему). Једина ствар коју бих желео да приметим је да и из личног искуства и из прегледа оних који су га већ применили, постоји добитак у поузданости. Да, немогуће је потпуно се отарасити кварова, али је сасвим могуће значајно смањити њихову учесталост. И картице постају обједињене, што сервисерима знатно олакшава замену.

Хардвер

Није било посебне сумње у избор типа меморије - НОР Фласх.
Аргументи:

• једноставно повезивање (најчешће СПИ магистрала, коју већ имате искуства у коришћењу, тако да се не предвиђају хардверски проблеми);
• смешна цена;
• стандардни оперативни протокол (имплементација је већ у језгру Линука, ако желите, можете узети неки треће стране, који је такође присутан, или чак написати свој, на срећу све је једноставно);
• поузданост и ресурс:
  из типичног листа са подацима: подаци се чувају 20 година, 100000 циклуса брисања за сваки блок;
  из извора трећих страна: изузетно низак БЕР, постулира да нема потребе за кодовима за исправљање грешака (неки радови сматрају ЕЦЦ за НОР, али обично и даље значе МЛЦ НОР; ово се такође дешава).

Хајде да проценимо захтеве за обимом и ресурсима.

Желео бих да се подаци гарантовано чувају неколико дана. Ово је неопходно да се у случају било каквих проблема у комуникацији не изгуби историја продаје. Фокусираћемо се на 5 дана, током овог периода (чак и узимајући у обзир викенде и празнике) проблем се може решити.

Тренутно прикупљамо око 100 кб дневника дневно (3-4 хиљаде уноса), али постепено ова цифра расте - детаљи се повећавају, додају се нови догађаји. Осим тога, понекад има рафала (неки сензор почиње да шаље нежељену пошту са лажним позитивним резултатима, на пример). Израчунаћемо за 10 хиљада записа по 100 бајтова - мегабајта дневно.

Укупно излази 5МБ чистих (добро компресованих) података. Више њима (груба процена) 1МБ сервисних података.

То јест, потребан нам је чип од 8МБ ако не користимо компресију, или 4МБ ако га користимо. Сасвим реални бројеви за ову врсту меморије.

Што се тиче ресурса: ако планирамо да се целокупна меморија преписује не више од једном у 5 дана, онда за 10 година рада добијамо мање од хиљаду циклуса преписивања.
Да вас подсетим да произвођач обећава сто хиљада.

Мало о НОР-у против НАНД-а

Данас је, наравно, НАНД меморија много популарнија, али је не бих користио за овај пројекат: НАНД, за разлику од НОР-а, нужно захтева употребу кодова за исправљање грешака, табелу лоших блокова, итд., а такође и ноге НАНД чипови обично много више.

Недостаци НОР-а укључују:

• мали волумен (и, сходно томе, висока цена по мегабајту);
• мала брзина комуникације (у великој мери због чињенице да се користи серијски интерфејс, обично СПИ или И2Ц);
• споро брисање (у зависности од величине блока, потребно је од делића секунде до неколико секунди).

Изгледа да за нас нема ништа критично, па настављамо даље.

Ако су детаљи занимљиви, одабрано је микро коло ат25дф321а (међутим, ово је неважно, на тржишту постоји много аналога који су компатибилни у пиноут и командном систему; чак и ако желимо да уградимо микроколо другог произвођача и/или друге величине, све ће радити без промене код).

Користим драјвер уграђен у језгро Линука; на Распберри-ју, захваљујући подршци за преклапање стабла уређаја, све је врло једноставно – потребно је да ставите компајлирани преклоп у /боот/оверлаис и мало измените /боот/цонфиг.ткт.

Пример дтс датотеке

Да будем искрен, нисам сигуран да је написано без грешака, али ради.

/*
 * 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

Изоставићу опис повезивања чипа на Распберри Пи. С једне стране, нисам стручњак за електронику, с друге стране, овде је све банално чак и за мене: микроколо има само 8 кракова, од којих нам је потребно уземљење, напајање, СПИ (ЦС, СИ, СО, СЦК ); нивои су исти као код Распберри Пи, није потребно додатно ожичење - само повежите назначених 6 пинова.

Проблем статемент

Као и обично, изјава проблема пролази кроз неколико итерација и чини ми се да је време за следећу. Па хајде да станемо, да саставимо оно што је већ написано и да разјаснимо детаље који остају у сенци.

Дакле, одлучили смо да се дневник чува у СПИ НОР Фласх-у.

Шта је НОР Фласх за оне који не знају?

Ово је непроменљива меморија са којом можете да урадите три операције:

1. Читање:
   Најчешће читање: преносимо адресу и читамо онолико бајтова колико нам је потребно;
2. Рецорд:
   Писање у НОР флеш изгледа као обично, али има једну посебност: можете променити само 1 у 0, али не и обрнуто. На пример, ако смо имали 0к55 у меморијској ћелији, онда ће након уписивања 0к0ф у њу, 0к05 већ бити ускладиштен тамо (погледајте табелу испод);
3. Избриши:
   Наравно, морамо бити у могућности да урадимо супротну операцију - променимо 0 у 1, управо томе служи операција брисања. За разлику од прва два, не ради са бајтовима, већ са блоковима (минимални блок за брисање у изабраном чипу је 4 кб). Брисање уништава цео блок и то је једини начин да промените 0 у 1. Због тога, када радите са флеш меморијом, често морате да поравнате структуре података са границом блока за брисање.
   Снимање у НОР Фласх-у:

Бинарни подаци

Вас
01010101

Снимљено
00001111

Је постао
00000101

Сам дневник представља низ записа променљиве дужине. Типична дужина записа је око 30 бајтова (иако се понекад јављају записи дужине неколико килобајта). У овом случају радимо са њима једноставно као скуп бајтова, али, ако сте заинтересовани, ЦБОР се користи унутар записа

Поред евиденције, потребно је да ускладиштимо неке информације о „подешавању“, како ажуриране, тако и не: одређени ИД уређаја, калибрације сензора, ознаку „уређај је привремено онемогућен“ итд.
Ове информације су скуп записа кључ/вредност, такође ускладиштени у ЦБОР-у. Немамо много ових информација (највише неколико килобајта) и ретко се ажурирају.
У наставку ћемо то звати контекстом.

Ако се сетимо одакле је почео овај чланак, веома је важно обезбедити поуздано складиштење података и, ако је могуће, континуиран рад чак и у случају кварова на хардверу/оштећења података.

Који извори проблема се могу узети у обзир?

• Искључите напајање током операција писања/брисања. Ово је из категорије „нема трика против пајсера“.
  Informacije iz дискусије на стацкекцханге-у: када се напајање искључи док радите са флешом, и брисање (подешено на 1) и писање (подешено на 0) доводе до недефинисаног понашања: подаци се могу писати, делимично уписивати (рецимо, пренели смо 10 бајтова/80 битова , али још увек не може да се упише само 45 битова), такође је могуће да ће неки од битова бити у „средњем“ стању (читање може да произведе и 0 и 1);
• Грешке у самој флеш меморији.
  БЕР, иако веома низак, не може бити једнак нули;
• Бус грешке
  Подаци који се преносе преко СПИ-а нису ни на који начин заштићени, могу се појавити и појединачне грешке и грешке у синхронизацији – губитак или уметање битова (што доводи до великог изобличења података);
• Друге грешке/недостаци
  Грешке у коду, малине кварови, сметње ванземаљаца...

Формулисао сам захтеве чије је испуњење, по мом мишљењу, неопходно да би се обезбедила поузданост:

• записи морају одмах да оду у флеш меморију, одложено уписивање се не узима у обзир; - ако дође до грешке, она мора бити откривена и обрађена што је пре могуће; - систем мора, ако је могуће, да се опорави од грешака.
  (пример из живота „како не би требало“, са којим се, мислим, сви сусрели: након хитног поновног покретања, систем датотека је „покварен“ и оперативни систем се не покреће)

Идеје, приступи, размишљања

Када сам почео да размишљам о овом проблему, кроз главу ми је прошло много идеја, на пример:

• користите компресију података;
• користите паметне структуре података, на пример, чување заглавља записа одвојено од самих записа, тако да ако постоји грешка у било ком запису, можете да прочитате остатак без икаквих проблема;
• користите битна поља за контролу завршетка снимања када је напајање искључено;
• чувајте контролне суме за све;
• користите неку врсту кодирања отпорног на буку.

Неке од ових идеја су искоришћене, док је од других одлучено да се одустану. Идемо редом.

Компресија података

Сами догађаји које бележимо у дневнику су прилично слични и поновљиви („бацио новчић од 5 рубаља”, „притиснуо дугме за давање кусур”,...). Према томе, компресија би требала бити прилично ефикасна.

Трошкови компресије су безначајни (наш процесор је прилично моћан, чак је и први Пи имао једно језгро са фреквенцијом од 700 МХз, тренутни модели имају неколико језгара са фреквенцијом преко гигахерца), курс размене са складиштем је низак (неколико мегабајта у секунди), величина записа је мала. Генерално, ако компресија има утицај на перформансе, то ће бити само позитивно. (апсолутно некритички, само изјављујем). Осим тога, немамо прави уграђени, већ обичан Линук - тако да имплементација не би требало да захтева много труда (довољно је само повезати библиотеку и користити неколико функција из ње).

Део дневника је узет са радног уређаја (1.7 МБ, 70 хиљада уноса) и прво проверен компресибилност помоћу гзип, лз4, лзоп, бзип2, кз, зстд доступних на рачунару.

• гзип, кз, зстд су показали сличне резултате (40Кб).
  Изненадило ме је што се помодни кз овде показао на нивоу гзип или зстд;
• лзип са подразумеваним подешавањима дао је нешто лошије резултате;
• лз4 и лзоп су показали не баш добре резултате (150Кб);
• бзип2 је показао изненађујуће добар резултат (18Кб).

Дакле, подаци су компримовани веома добро.
Дакле (ако не пронађемо фаталне недостатке) доћи ће до компресије! Једноставно зато што више података може стати на исти флеш диск.

Хајде да размислимо о недостацима.

Први проблем: већ смо се договорили да сваки запис мора одмах ићи у флеш. Типично, архиватор прикупља податке из улазног тока док не одлучи да је време за писање викендом. Морамо одмах да примимо компримовани блок података и ускладиштимо га у непроменљивој меморији.

Видим три начина:

1. Компримујте сваки запис користећи компресију речника уместо алгоритама о којима смо горе говорили.
   То је потпуно функционална опција, али ми се не свиђа. Да би се обезбедио мање-више пристојан ниво компресије, речник мора бити „прилагођен“ одређеним подацима; свака промена ће довести до катастрофалног пада нивоа компресије. Да, проблем се може решити креирањем нове верзије речника, али ово је главобоља – мораћемо да ускладиштимо све верзије речника; у сваком уносу ћемо морати да назначимо са којом верзијом речника је компримован...
2. Компримирајте сваки запис користећи „класичне“ алгоритаме, али независно од осталих.
   Алгоритми компресије који се разматрају нису дизајнирани да раде са записима ове величине (десетине бајтова), однос компресије ће очигледно бити мањи од 1 (то јест, повећање обима података уместо компресије);
3. Урадите ФЛУСХ након сваког снимања.
   Многе библиотеке компресије имају подршку за ФЛУСХ. Ово је команда (или параметар процедуре компресије), по пријему које архиватор формира компримовани ток тако да се може користити за враћање све некомпримовани подаци који су већ примљени. Такав аналог sync у системима датотека или commit у скл.
   Оно што је важно је да ће накнадне операције компресије моћи да користе нагомилани речник и да однос компресије неће трпети толико као у претходној верзији.

Мислим да је очигледно да сам изабрао трећу опцију, погледајмо је детаљније.

Нашао сјајан чланак о ФЛУСХ у злиб.

Урадио сам тест колена на основу чланка, узео 70 хиљада уноса у дневник са стварног уређаја, са величином странице од 60Кб (на величину странице ћемо се вратити касније) примљен:

Необрађени подаци
Компресија гзип -9 (без ФЛУСХ)
злиб са З_ПАРТИАЛ_ФЛУСХ
злиб са З_СИНЦ_ФЛУСХ

Обим, КБ
1692
40
352
604

На први поглед, цена коју доприноси ФЛУСХ је превисока, али у стварности имамо мало избора - или да уопште не компресујемо, или да компресујемо (и веома ефикасно) са ФЛУСХ-ом. Не смемо заборавити да имамо 70 хиљада записа, редундантност коју је увео З_ПАРТИАЛ_ФЛУСХ је само 4-5 бајтова по запису. А однос компресије се показао скоро 5:1, што је више него одличан резултат.

Можда је изненађење, али З_СИНЦ_ФЛУСХ је заправо ефикаснији начин за ФЛУСХ

Када користите З_СИНЦ_ФЛУСХ, последња 4 бајта сваког уноса ће увек бити 0к00, 0к00, 0кфф, 0кфф. А ако их знамо, онда не морамо да их чувамо, тако да је коначна величина само 324Кб.

Чланак на који сам повезао има објашњење:

Додат је нови блок типа 0 са празним садржајем.

Блок типа 0 са празним садржајем састоји се од:

• тробитно заглавље блока;
• 0 до 7 битова једнако нули, да би се постигло поравнање бајтова;
• четворобајтна секвенца 00 00 ФФ ФФ.

Као што можете лако видети, у последњем блоку пре ова 4 бајта има од 3 до 10 нула битова. Међутим, пракса је показала да заправо постоји најмање 10 битова нула.

Испоставило се да се такви кратки блокови података обично (увек?) кодирају коришћењем блока типа 1 (фиксни блок), који се обавезно завршава са 7 нултих битова, дајући укупно 10-17 гарантованих нултих битова (а остатак ће бити нула са вероватноћом од око 50%).

Дакле, на тест подацима, у 100% случајева постоји један нула бајт испред 0к00, 0к00, 0кфф, 0кфф, ау више од трећине случајева постоје два нула бајта (можда је чињеница да користим бинарни ЦБОР, а када користим текстуални ЈСОН блокови типа 2 - динамички блок би били чешћи, односно наишли би блокови без додатних нула бајтова пре 0к00, 0к00, 0кфф, 0кфф).

Укупно, користећи доступне тестне податке, могуће је уклопити мање од 250Кб компресованих података.

Можете уштедети мало више жонглирањем: за сада игноришемо присуство неколико нула битова на крају блока, неколико битова на почетку блока се такође не мења...
Али онда сам донео чврсту одлуку да прекинем, иначе бих овом брзином могао да завршим са развојем сопственог архиватора.

Укупно, из мојих тест података сам добио 3-4 бајта по запису, испоставило се да је однос компресије већи од 6:1. Да будем искрен: нисам очекивао такав резултат; по мом мишљењу, све боље од 2:1 је већ резултат који оправдава употребу компресије.

Све је у реду, али злиб (дефлате) је и даље архаичан, заслужени и помало старомодан алгоритам компресије. Сама чињеница да се последњих 32Кб некомпримованог тока података користи као речник данас изгледа чудно (то јест, ако је неки блок података веома сличан ономе што је био у улазном току пре 40Кб, онда ће поново почети да се архивира, и неће се односити на претходну појаву). У модерним модерним архивама, величина речника се често мери у мегабајтима, а не у килобајтима.

Дакле, настављамо нашу мини студију о архиварима.

Затим смо тестирали бзип2 (запамтите, без ФЛУСХ-а је показао фантастичан однос компресије од скоро 100:1). Нажалост, са ФЛУСХ-ом се показао веома лоше; испоставило се да је величина компресованих података већа од некомпримованих података.

Моје претпоставке о разлозима неуспеха

Либбз2 нуди само једну опцију за испирање, која изгледа да брише речник (аналогно З_ФУЛЛ_ФЛУСХ у злиб-у); нема говора о било каквој ефикасној компресији након овога.

А последњи који је тестиран био је зстд. У зависности од параметара, компримује се или на нивоу гзип-а, али много брже, или боље од гзип-а.

Нажалост, са ФЛУСХ-ом није добро радио: величина компресованих података била је око 700Кб.

Я поставио питање на гитхуб страници пројекта добио сам одговор да треба рачунати на до 10 бајтова сервисних података за сваки блок компресованих података, што је близу добијеним резултатима; не постоји начин да се сустигне дефлате.

Одлучио сам да на овом месту зауставим своје експерименте са архиваторима (да вас подсетим да се кз, лзип, лзо, лз4 нису показали чак ни у фази тестирања без ФЛУСХ-а, и нисам разматрао егзотичније алгоритме компресије).

Вратимо се проблемима архивирања.

Други (како кажу по реду, а не по вредности) проблем је то што су компримовани подаци један ток, у коме се стално налазе референце на претходне одељке. Дакле, ако је део компримованих података оштећен, губимо не само повезани блок некомпримованих података, већ и све наредне.

Постоји приступ за решавање овог проблема:

1. Спречите појаву проблема - додајте редундантност компримованим подацима, што ће вам омогућити да идентификујете и исправите грешке; о томе ћемо касније;
2. Смањите последице ако дође до проблема
   Већ смо раније рекли да сваки блок података можете компримовати независно, а проблем ће нестати сам од себе (оштећење података једног блока ће довести до губитка података само за овај блок). Међутим, ово је екстреман случај у којем ће компресија података бити неефикасна. Супротан екстрем: искористити свих 4МБ нашег чипа као једну архиву, што ће нам дати одличну компресију, али катастрофалне последице у случају оштећења података.
   Да, потребан је компромис у погледу поузданости. Али морамо имати на уму да развијамо формат за складиштење података за непроменљиву меморију са изузетно ниским БЕР-ом и декларисаним периодом складиштења података од 20 година.

Током експеримената, открио сам да мање-више приметни губици у нивоу компресије почињу на блоковима компресованих података мањим од 10 КБ.
Раније је поменуто да се меморија која се користи је страница; не видим разлог зашто не би требало да се користи кореспонденција „једна страница - један блок компресованих података“.

То јест, минимална разумна величина странице је 16Кб (са резервом за сервисне информације). Међутим, тако мала величина странице намеће значајна ограничења на максималну величину записа.

Иако још не очекујем записе веће од неколико килобајта у компримованом облику, одлучио сам да користим странице од 32Кб (за укупно 128 страница по чипу).

Резиме:

• Чувамо податке компримоване помоћу злиб (дефлате);
• За сваки унос постављамо З_СИНЦ_ФЛУСХ;
• За сваки компримовани запис скраћујемо задње бајтове (нпр. 0к00, 0к00, 0кфф, 0кфф); у заглављу означавамо колико бајтова смо одсекли;
• Податке чувамо на страницама од 32Кб; унутар странице постоји један ток компримованих података; На свакој страници поново почињемо компресију.

И, пре него што завршимо са компресијом, желео бих да вам скренем пажњу на чињеницу да имамо само неколико бајтова компресованих података по запису, тако да је изузетно важно да не надувавате сервисне информације, сваки бајт се овде рачуна.

Чување заглавља података

Пошто имамо записе променљиве дужине, морамо некако да одредимо положај/границе записа.

Знам три приступа:

1. Сви записи се чувају у континуираном току, прво постоји заглавље записа које садржи дужину, а затим и сам запис.
   У овој реализацији, и заглавља и подаци могу бити променљиве дужине.
   У суштини, добијамо једноструко повезану листу која се користи све време;
2. Заглавља и сами записи се чувају у одвојеним токовима.
   Коришћењем заглавља константне дужине обезбеђујемо да оштећење једног заглавља не утиче на друге.
   Сличан приступ се користи, на пример, у многим системима датотека;
3. Записи се чувају у континуираном току, граница записа је одређена одређеним маркером (знаком/секвенцијом знакова који је забрањен у блоковима података). Ако постоји маркер унутар записа, онда га замењујемо неком секвенцом (избегнемо га).
   Сличан приступ се користи, на пример, у ППП протоколу.

ја ћу илустровати.

Опција КСНУМКС:

Овде је све врло једноставно: знајући дужину записа, можемо израчунати адресу следећег заглавља. Дакле, крећемо се кроз наслове док не наиђемо на област испуњену 0кфф (слободна област) или крај странице.

Опција КСНУМКС:

Због променљиве дужине записа, не можемо унапред рећи колико записа (а самим тим и заглавља) ће нам требати по страници. Можете ширити заглавља и саме податке на различите странице, али ја више волим другачији приступ: постављамо и заглавља и податке на једну страницу, али заглавља (сталне величине) долазе са почетка странице, а подаци (променљиве дужине) долазе са краја. Чим се „састану“ (нема довољно слободног простора за нови унос), сматрамо ову страницу завршеном.

Опција КСНУМКС:

Нема потребе да складиштите дужину или друге информације о локацији података у заглављу; довољни су маркери који указују на границе записа. Међутим, подаци се морају обрадити приликом писања/читања.
Користио бих 0кфф као маркер (који испуњава страницу након брисања), тако да слободна област дефинитивно неће бити третирана као подаци.

Табела поређења:

Опција КСНУМКС
Опција КСНУМКС
Опција КСНУМКС

Толеранција грешке
-
+
+

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

Сложеност имплементације
*
**
**

Опција 1 има фаталну грешку: ако је неко од заглавља оштећено, цео наредни ланац је уништен. Преостале опције вам омогућавају да повратите неке податке чак и у случају велике штете.
Али овде је прикладно запамтити да смо одлучили да податке ускладиштимо у компримованом облику, и тако губимо све податке на страници након „поквареног“ записа, па иако постоји минус у табели, не узети у обзир.

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

• у првој опцији потребно је да сачувамо само дужину у заглављу; ако користимо целе бројеве променљиве дужине, онда у већини случајева можемо да прођемо са једним бајтом;
• у другој опцији треба да сачувамо почетну адресу и дужину; запис мора бити константне величине, ја процењујем 4 бајта по запису (два бајта за помак и два бајта за дужину);
• трећој опцији је потребан само један знак да означи почетак снимања, плус сам снимак ће се повећати за 1-2% због заштите. Генерално, приближно паритет са првом опцијом.

У почетку сам другу опцију сматрао главном (и чак сам написао имплементацију). Напустио сам га тек када сам коначно одлучио да користим компресију.

Можда ћу једног дана и даље користити сличну опцију. На пример, ако морам да се бавим складиштењем података за брод који путује између Земље и Марса, биће потпуно другачији захтеви за поузданост, космичко зрачење, ...

Што се тиче треће опције: дао сам јој две звездице због тежине имплементације једноставно зато што не волим да се петљам са заштитом, мењањем дужине у процесу итд. Да, можда сам пристрасан, али мораћу да напишем шифру - зашто се присиљавате да радите нешто што вам се не свиђа.

Резиме: Ми бирамо опцију складиштења у облику ланаца „заглавље са дужином - подаци променљиве дужине“ због ефикасности и лакоће имплементације.

Коришћење битних поља за праћење успеха операција писања

Не сећам се сада одакле ми идеја, али изгледа отприлике овако:
За сваки унос додељујемо неколико битова за чување заставица.
Као што смо раније рекли, након брисања сви битови се попуњавају 1с, и ​​можемо променити 1 у 0, али не и обрнуто. Дакле, за „застава није постављена“ користимо 1, за „застава је постављена“ користимо 0.

Ево како би стављање записа променљиве дужине у флеш могло изгледати:

1. Поставите заставицу „дужина снимања је почела“;
2. Запишите дужину;
3. Поставите ознаку „снимање података је почело“;
4. Ми бележимо податке;
5. Поставите ознаку „снимање је завршено“.

Поред тога, имаћемо ознаку „дошло је до грешке“, за укупно 4-битне заставице.

У овом случају имамо два стабилна стања “1111” – снимање није почело и “1000” – снимање је успешно; у случају неочекиваног прекида процеса снимања, добићемо међустања која потом можемо открити и обрадити.

Приступ је интересантан, али штити само од изненадних нестанка струје и сличних кварова, што је, наравно, важно, али то није једини (па чак ни главни) разлог могућих кварова.

Резиме: Идемо даље у потрагу за добрим решењем.

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

Контролне суме такође омогућавају да будемо сигурни (са разумном вероватноћом) да читамо тачно оно што је требало да буде написано. И, за разлику од битних поља о којима смо горе говорили, она увек раде.

Ако узмемо у обзир листу потенцијалних извора проблема о којој смо горе говорили, онда је контролни збир у стању да препозна грешку без обзира на њено порекло (осим, ​​можда, за злонамерне ванземаљце - и они могу да кривотворе контролни збир).

Дакле, ако је наш циљ да проверимо да ли су подаци нетакнути, контролни суми су одлична идеја.

Избор алгоритма за израчунавање контролне суме није изазвао никаква питања - ЦРЦ. С једне стране, математичка својства омогућавају да се одређене врсте грешака ухвати 100%, с друге стране, на случајним подацима овај алгоритам обично показује вероватноћу судара која није много већа од теоријске границе. . Можда није најбржи алгоритам, нити је увек минималан у смислу броја судара, али има веома важан квалитет: у тестовима на које сам наишао није било шаблона у којима је очигледно пао. Стабилност је главни квалитет у овом случају.

Пример волуметријске студије: Део КСНУМКС, Део КСНУМКС (линкови ка народ.ру, извини).

Међутим, задатак одабира контролне суме није завршен; ЦРЦ је читава породица контролних сума. Морате одлучити о дужини, а затим одабрати полином.

Одабир дужине контролног збира није тако једноставно питање као што изгледа на први поглед.

Дозволите ми да илуструјем:
Хајде да имамо вероватноћу грешке у сваком бајту и идеалан контролни збир, хајде да израчунамо просечан број грешака на милион записа:

Подаци, бајт
Контролна сума, бајт
Неоткривене грешке
Откривање лажних грешака
Тотални лажни позитивни резултати

1
0
1000
0
1000

1
1
4
999
1003

1
2
≈КСНУМКС
1997
1997

1
4
≈КСНУМКС
3990
3990

10
0
9955
0
9955

10
1
39
990
1029

10
2
≈КСНУМКС
1979
1979

10
4
≈КСНУМКС
3954
3954

1000
0
632305
0
632305

1000
1
2470
368
2838

1000
2
10
735
745

1000
4
≈КСНУМКС
1469
1469

Чини се да је све једноставно - у зависности од дужине података који се штите, изаберите дужину контролне суме са минимумом нетачних позитива - и трик је у торби.

Међутим, проблем настаје са кратким контролним збировима: иако су добри у откривању грешака у једном биту, могу са прилично великом вероватноћом да прихвате потпуно насумичне податке као тачне. Већ је постојао чланак о Хабреу који описује проблем у стварном животу.

Због тога, да би случајно подударање контролне суме било готово немогуће, потребно је да користите контролне суме дужине 32 бита или дуже. (за дужине веће од 64 бита, обично се користе криптографске хеш функције).

Упркос чињеници да сам раније писао да морамо свакако да уштедимо простор, ипак ћемо користити 32-битну контролну суму (16 бита није довољно, вероватноћа колизије је већа од 0.01%; а 24 бита, јер рецимо, нису ни овде ни тамо).

Овде се може појавити примедба: да ли смо сачували сваки бајт када смо бирали компресију да бисмо сада дали 4 бајта одједном? Зар не би било боље да не компримујете или не додате контролни збир? Наравно да не, нема компресије не значи, да нам није потребна провера интегритета.

Када бирамо полином, нећемо поново измишљати точак, већ ћемо узети сада популарни ЦРЦ-32Ц.
Овај код открива 6-битне грешке на пакетима до 22 бајта (можда најчешћи случај за нас), 4-битне грешке на пакетима до 655 бајтова (такође уобичајен случај за нас), 2 или било који непаран број грешака у биту на пакетима било које разумне дужине.

Ако некога занимају детаљи

Чланак на Википедији о ЦРЦ.

Параметри кода црц-32ц на Коопман вебсите — можда водећи специјалиста ЦРЦ на планети.

В његов чланак ту је још један занимљив код, који обезбеђује нешто боље параметре за дужине пакета које су нам релевантне, али разлику нисам сматрао значајном, и био сам довољно компетентан да одаберем прилагођени код уместо стандардног и добро истраженог.

Такође, пошто су наши подаци компримовани, поставља се питање: да ли да израчунамо контролни збир компримованих или некомпримованих података?

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

• У крајњој линији треба да проверимо безбедност складиштења података – па га проверавамо директно (истовремено ће се проверавати могуће грешке у имплементацији компресије/декомпресије, оштећења изазвана поквареном меморијом итд.);
• Алгоритам дефлате у злиб-у има прилично зрелу имплементацију и не би требало пада са „кривим“ улазним подацима; штавише, често је у стању да независно открије грешке у улазном току, смањујући укупну вероватноћу да се грешка не открије (спроведен тест са инвертовањем једног бита у кратком запису, злиб је открио грешку у око трећини случајева).

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

• ЦРЦ је „скројен“ посебно за неколико битних грешака које су карактеристичне за флеш меморију (грешка бита у компримованом току може да изазове огромну промену у излазном току, на коме, чисто теоретски, можемо „ухватити“ колизију);
• Не свиђа ми се идеја да се потенцијално покварени подаци прослеђују декомпресору, Ко знакако ће реаговати.

У овом пројекту одлучио сам да одступим од опште прихваћене праксе чувања контролне суме некомпримованих података.

Резиме: Користимо ЦРЦ-32Ц, израчунавамо контролну суму из података у облику у којем су записани у флеш (након компресије).

Сувишност

Употреба редундантног кодирања, наравно, не елиминише губитак података, али може значајно (често за много редова величине) да смањи вероватноћу непоправљивог губитка података.

Можемо користити различите врсте редундансе да исправимо грешке.
Хемингови кодови могу да исправе грешке у једном биту, Рид-Соломонови знаковни кодови, вишеструке копије података у комбинацији са контролним сумама или кодирања као што је РАИД-6 могу помоћи у опоравку података чак и у случају велике оштећења.
У почетку сам био посвећен широкој употреби кодирања отпорног на грешке, али онда сам схватио да прво треба да имамо идеју од којих грешака желимо да се заштитимо, а затим да изаберемо кодирање.

Раније смо рекли да грешке морају бити ухваћене што је пре могуће. У којим тачкама можемо наићи на грешке?

1. Недовршено снимање (из неког разлога у време снимања је искључено напајање, малина се смрзла, ...)
   Авај, у случају такве грешке, остаје само да се игноришу неважећи записи и да се подаци сматрају изгубљеним;
2. Грешке у писању (из неког разлога, оно што је уписано у флеш меморију није оно што је написано)
   Такве грешке можемо одмах открити ако урадимо пробно очитавање одмах након снимања;
3. Изобличење података у меморији током складиштења;
4. Грешке у читању
   Да бисте то исправили, ако се контролни збир не поклапа, довољно је поновити читање неколико пута.

То јест, само грешке трећег типа (спонтано оштећење података током складиштења) не могу се исправити без кодирања отпорног на грешке. Чини се да су такве грешке и даље веома мало вероватне.

Резиме: одлучено је да се одустане од сувишног кодирања, али ако операција покаже грешку ове одлуке, онда се вратимо на разматрање питања (са већ акумулираном статистиком о кваровима, што ће омогућити одабир оптималног типа кодирања).

Други

Наравно, формат чланка нам не дозвољава да оправдамо свако мало у формату (а моја снага је већ понестала), па ћу укратко прећи на неке тачке које раније нису биле дотакнуте.

• Одлучено је да све странице буду „једнаке“
  То јест, неће бити посебних страница са метаподацима, одвојеним нитима, итд., већ уместо једне нити која редом преписује све странице.
  Ово осигурава равномерно хабање страница, без једне тачке квара, и једноставно ми се свиђа;
• Неопходно је обезбедити верзију формата.
  Формат без броја верзије у заглављу је зао!
  Довољно је додати поље са одређеним Магичним бројем (потписом) у заглавље странице, које ће указати на верзију формата који се користи (Мислим да их у пракси неће бити ни десетак);
• Користите заглавље променљиве дужине за записе (којих има много), покушавајући да у већини случајева буде дугачко 1 бајт;
• Да бисте кодирали дужину заглавља и дужину исеченог дела компримованог записа, користите бинарне кодове променљиве дужине.

Помогао много онлине генератор Хафманови кодови. За само неколико минута успели смо да изаберемо потребне кодове променљиве дужине.

Опис формата складиштења података

Редослед бајтова

Поља већа од једног бајта се чувају у биг-ендиан формату (мрежни поредак бајтова), то јест, 0к1234 се записује као 0к12, 0к34.

Пагинација

Сва флеш меморија је подељена на странице једнаке величине.

Подразумевана величина странице је 32Кб, али не више од 1/4 укупне величине меморијског чипа (за чип од 4МБ добија се 128 страница).

Свака страница складишти податке независно од других (то јест, подаци на једној страници не упућују на податке на другој страници).

Све странице су нумерисане природним редоследом (узлазним редоследом адреса), почевши од броја 0 (нула страница почиње од адресе 0, прва страница почиње од 32Кб, друга страница почиње од 64Кб, итд.)

Меморијски чип се користи као циклични бафер (ринг бафер), односно прво уписивање иде на страницу број 0, затим број 1, ..., када попунимо последњу страницу, почиње нови циклус и снимање се наставља од нулте странице .

Унутар странице

На почетку странице се чува заглавље странице од 4 бајта, затим контролни збир заглавља (ЦРЦ-32Ц), а затим се записи чувају у формату „заглавље, подаци, контролна сума“.

Наслов странице (прљаво зелена на дијаграму) се састоји од:

• двобајтно поље Магиц Нумбер (такође знак верзије формата)
  за тренутну верзију формата израчунава се као 0xed00 ⊕ номер страницы;
• двобајтни бројач „Верзија странице“ (број циклуса преписивања меморије).

Уноси на страници се чувају у компримованом облику (користи се алгоритам дефлате). Сви записи на једној страници се компримују у једну нит (користи се заједнички речник), а на свакој новој страници компресија почиње изнова. То јест, за декомпресију било ког записа потребни су сви претходни записи са ове странице (и само овај).

Сваки запис ће бити компримован са З_СИНЦ_ФЛУСХ заставицом, а на крају компримованог тока биће 4 бајта 0к00, 0к00, 0кфф, 0кфф, којима ће можда претходити још један или два нула бајта.
Одбацујемо ову секвенцу (дужине 4, 5 или 6 бајтова) када пишемо у флеш меморију.

Заглавље записа има 1, 2 или 3 бајта и чува:

• један бит (Т) који означава тип записа: 0 - контекст, 1 - дневник;
• поље променљиве дужине (С) од 1 до 7 бита, које дефинише дужину заглавља и „репа“ који се морају додати запису за декомпресију;
• дужина записа (Л).

Табела С вредности:

S
Дужина заглавља, бајтови
Одбачено при писању, бајт

0
1
КСНУМКС (00 00 00 ff ff)

10
1
КСНУМКС (00 00 00 00 ff ff)

110
2
КСНУМКС (00 00 ff ff)

1110
2
КСНУМКС (00 00 00 ff ff)

11110
2
КСНУМКС (00 00 00 00 ff ff)

1111100
3
КСНУМКС (00 00 ff ff)

1111101
3
КСНУМКС (00 00 00 ff ff)

1111110
3
КСНУМКС (00 00 00 00 ff ff)

Покушао сам да илуструјем, не знам колико је јасно испало:

Жуто овде означава поље Т, бело поље С, зелено Л (дужина компресованих података у бајтовима), плаво компресоване податке, црвено последње бајтове компресованих података који нису уписани у флеш меморију.

Тако можемо уписати заглавља записа најчешће дужине (до 63+5 бајтова у компримованом облику) у један бајт.

После сваког записа, ЦРЦ-32Ц контролна сума се чува, у којој се обрнута вредност претходне контролне суме користи као почетна вредност (инит).

ЦРЦ има својство „трајања“, следећа формула функционише (плус или минус инверзија бита у процесу): .
То јест, у ствари, ми израчунавамо ЦРЦ свих претходних бајтова заглавља и података на овој страници.

Директно иза контролне суме налази се заглавље следећег записа.

Заглавље је дизајнирано тако да се његов први бајт увек разликује од 0к00 и 0кфф (ако уместо првог бајта заглавља наиђемо на 0кфф, то значи да је ово неискоришћено подручје; 0к00 сигнализира грешку).

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

Читање из флеш меморије

Свако читање долази са провером контролне суме.
Ако се контролни збир не поклапа, очитавање се понавља неколико пута у нади да ће се прочитати тачни подаци.

(ово има смисла, Линук не кешује читања са НОР Фласх-а, тестирано)

Упишите у флеш меморију

Записујемо податке.
Хајде да их прочитамо.

Ако се очитани подаци не поклапају са написаним, подручје попуњавамо нулама и сигнализирамо грешку.

Припрема новог микрокола за рад

За иницијализацију, заглавље са верзијом 1 уписује се на прву (или боље речено нулту) страницу.
Након тога, почетни контекст се уписује на ову страницу (садржи УУИД машине и подразумевана подешавања).

То је то, флеш меморија је спремна за употребу.

Учитавање машине

Приликом учитавања, првих 8 бајтова сваке странице (заглавље + ЦРЦ) се читају, странице са непознатим магичним бројем или нетачним ЦРЦ се занемарују.
Са „исправних“ страница бирају се странице са максималном верзијом, а са њих се узима страница са највећим бројем.
Чита се први запис, проверава се исправност ЦРЦ-а и присуство заставице „контекст“. Ако је све у реду, ова страница се сматра актуелном. Ако не, враћамо се на претходну док не пронађемо „живу“ страницу.
и на пронађеној страници читамо све записе, оне које користимо са заставицом „контекст“.
Сачувајте злиб речник (биће потребан за додавање на ову страницу).

То је то, преузимање је завршено, контекст је враћен, можете радити.

Додавање уноса у дневник

Компримујемо запис исправним речником, наводећи З_СИНЦ_ФЛУСХ. Видимо да ли компримовани запис одговара тренутној страници.
Ако се не уклапа (или је било ЦРЦ грешака на страници), покрените нову страницу (погледајте испод).
Записујемо запис и ЦРЦ. Ако дође до грешке, покрените нову страницу.

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

Бирамо бесплатну страницу са минималним бројем (бесплатном страницом сматрамо страницу са нетачним контролним сумом у заглављу или са верзијом мањом од тренутне). Ако таквих страница нема, изаберите страницу са минималним бројем од оних које имају верзију једнаку тренутној.
Избришемо изабрану страницу. Проверавамо садржај са 0кфф. Ако нешто није у реду, узмите следећу бесплатну страницу итд.
На обрисаној страници пишемо заглавље, први унос је тренутно стање контекста, следећи је ненаписани унос дневника (ако га има).

Применљивост формата

По мом мишљењу, испоставило се да је то добар формат за чување било каквих више или мање компресибилних токова информација (обични текст, ЈСОН, МессагеПацк, ЦБОР, евентуално протобуф) у НОР Фласх-у.

Наравно, формат је „скројен“ за СЛЦ НОР Фласх.

Не би требало да се користи са медијима са високим БЕР као што су НАНД или МЛЦ НОР (да ли је таква меморија уопште доступна за продају? Видео сам да се помиње само у радовима на исправним кодовима).

Штавише, не треба га користити са уређајима који имају сопствени ФТЛ: УСБ флеш, СД, МицроСД итд (за такву меморију направио сам формат са величином странице од 512 бајтова, потписом на почетку сваке странице и јединственим бројевима записа - понекад је било могуће опоравити све податке са „поквареног” флеш диска једноставним секвенцијалним читањем).

У зависности од задатака, формат се може користити без промена на флеш дисковима од 128Кбит (16Кб) до 1Гбит (128МБ). Ако желите, можете га користити на већим чиповима, али вероватно ћете морати да прилагодите величину странице (Али овде се већ поставља питање економске изводљивости; цена за НОР Фласх великог обима није охрабрујућа).

Ако некоме буде интересантан формат и жели да га користи у отвореном пројекту, напишите, покушаћу да нађем времена, исполирати код и објавити га на гитхуб-у.

Закључак

Као што видите, на крају се испоставило да је формат једноставан па чак и досадно.

Тешко је одразити еволуцију мог гледишта у чланку, али верујте ми: у почетку сам желео да створим нешто софистицирано, неуништиво, способно да преживи чак и нуклеарну експлозију у непосредној близини. Међутим, разум је (надам се) ипак победио и постепено су се приоритети померили ка једноставности и компактности.

Да ли је могуће да сам погрешио? Да сигуран. Може се испоставити, на пример, да смо купили серију неквалитетних микрокола. Или из неког другог разлога опрема неће испунити очекивања о поузданости.

Да ли имам план за ово? Мислим да након читања чланка немате сумње да постоји план. Па чак ни сама.

Мало озбиљније, формат је развијен и као радна опција и као „пробни балон“.

Тренутно све на столу функционише добро, буквално пре неки дан решење ће бити распоређено (Приближно) на стотинама уређаја, хајде да видимо шта се дешава у „борбеним“ операцијама (на срећу, надам се да вам формат омогућава да поуздано откријете кварове; тако да можете да прикупите пуну статистику). За неколико месеци биће могуће донети закључке (а ако немате среће, чак и раније).

Ако се на основу резултата употребе открију озбиљни проблеми и буду потребна побољшања, онда ћу свакако писати о томе.

Литература

Нисам желео да правим дугу досадну листу коришћених радова; на крају крајева, сви имају Гоогле.

Овде сам одлучио да оставим списак налаза који су ми се чинили посебно занимљиви, али су постепено прешли директно у текст чланка, а једна ставка је остала на листи:

1. Корисност инфген од аутора злиб. Може јасно да прикаже садржај дефлате/злиб/гзип архива. Ако морате да се бавите унутрашњом структуром дефлате (или гзип) формата, топло препоручујем.

Извор: ввв.хабр.цом