Tarixçə

Özəl hazırlanmış avtomatlarımız var. İçində Raspberry Pi və biraz əlavə dövrə var. Qəbul cihazları, bank terminalı… Bütün bunları yazılmış proqram idarə edir. İş tarixçəsi bir flaş kartda (MicroSD) yazılır, daha sonra internet üzərindən (USB-modem vasitəsilə) serverə göndərilir və orada verilənlər bazasına yığılır. Satış məlumatları 1C-yə yüklənir, həmçinin monitorinq və s. üçün sadə bir veb-interfeys var.

Yəni jurnal həyati əhəmiyyət daşıyır — uçot üçün (orada gəlir, satış və s.), monitorinq üçün (hər cür nasazlıq və digər fövqəladə hallar); bu, demək olar ki, avtomat haqqında sahib olduğumuz bütün məlumatdır.

Problema

Flaş kartlar çox etibarsız qurğular kimi özlərini göstərirlər. Onlar gözəl bir müntəzəmliklə baş verirlər. Bu, həm avtomatların dayanmasına, həm də (jurnal onlayn ötürülə bilmədiyi hallarda) məlumat itkilərinə səbəb olur.

Bu artıq flaş kartların istifadəsi ilə bağlı ilk təcrübəmiz deyil, əvvəllər yüzdən çox qurğu olan başqa bir layihə var idi, orada jurnal USB-flaş kartlarında saxlanılırdı, orada da etibarlılıq problemləri yaşanırdı, bəzən bir ay ərzində çıxa bilənlərin sayı onlarla ölçülürdü. Müxtəlif flaş kartlar sınanmışdır, o cümlədən SLC yaddaşlı brend modelləri, bəli, bəzi modellər digərindən daha etibarlıdır, lakin flaş kartların dəyişdirilməsi problemi həll etmədi.

Dikkat! Longrid! Əgər sizə "nəyə" deyil, yalnız "nəcə" maraqlıdırsa, dərhal sona gedə bilərsiniz. sonuna məqaləsiylə tanış olun.

Həll

Ağlıma gələn ilk şey: MicroSD-dən imtina etmək, məsələn, SSD qoymaq və ondan yüklənmək. Teorik cəhətdən mümkündür, amma nisbətən bahalıdır və o qədər də etibarlı deyil (USB-SATA adapteri əlavə olunur; büdcə SSD-lərinin də uğursuzluq statistikası sevindirici deyil).

USB HDD də xüsusilə cəlbedici bir həll kimi görünmür.

Buna görə belə bir variantla gəldik: yüklənməni MicroSD-dən saxlamaq, lakin onları read-only rejimində istifadə etmək, iş jurnalı (və spesifik avadanlığa aid olan digər unikal məlumatlar — serial nömrəsi, sensor kalibrləri və s.) haradasa başqa bir yerdə saxlamaq.

Raspberry üçün read-only FS mövzusu artıq hərtərəfli araşdırılıb, mən bu məqalədə tətbiqinizin detalları ilə dayanmayacam. (Amma maraq olarsa — bəlkə də bu mövzuda kiçik bir məqalə yazaram). Yeganə qeyd etmək istədiyim bir məqam: həm şəxsi təcrübələrim, həm də artıq tətbiq edənlərin rəyləri ilə etibarlılıqda irəliləyiş var. Bəli, pozulmalardan tamamilə qurtulmaq mümkün deyil, lakin onların tezliyini əhəmiyyətli dərəcədə azaltmaq tamamilə realdır. Həmçinin, kartlar standartlaşdırılır, bu da qulluq heyəti üçün dəyişdirməyi xeyli asanlaşdırır.

Avadanlıq

Yaddaş növü seçərkən xüsusi şübhələrimiz yox idi — NOR Flash.
Arqumentlər:

• sadə qoşulma (ən çox SPI interfeysi, artıq istifadə təcrübəsi var, beləliklə, "dəmir" problemlərinin yaranması gözlənilmir);
• gülünc qiymət;
• standart iş protokolu (Linux nüvəsində artıq tətbiq edilmişdir, istəsəniz xarici variantları ala bilərsiniz, bunlar da mevcuddur, ya da hətta özünüz yaza bilərsiniz, çünki hər şey sadədir);
• etibarlılıq və resurs:
  tipik datasheetdən: məlumatlar 20 il saxlanılır, hər blok üçün 100000 erase dövrü;
  xarici mənbələrdən: son dərəcə aşağı BER, səhv düzəltmə kodlarına ehtiyacın olmadığı iddia edilir (bəzi işlərdə NOR üçün ECC müzakirə edilir, amma adətən burada MLC NOR nəzərdə tutulur, belə bir hal da olur).

Tələbləri həcminə və resursuna nəzər salaq.

Məlumatların bir neçə gün ərzində qorunmasını istəyirik. Bu, əlaqə problemləri baş verdikdə satış tarixçəsinin itməməsi üçün lazımdır. 5 gün ərzində nəzərdən keçirəcəyik, bu müddət ərzində (hətta həftə sonları və bayramlar da daxil olmaqla) problemi həll etmək olar.

Hazırda gündə təxminən 100 kB jurnal toplanır (3-4 min qeydlər), lakin bu rəqəm tədricən artır — detallılığı artır, yeni hadisələr əlavə olunur. Üstəlik, bəzən artma hallar olur (hansısa sensor saxta reaksiyalarla spam gönderməyə başlayır, məsələn). 10 min qeyd üçün 100 bayt hesablayacayıq — gündə 1 MB.

Nəticədə 5 MB təmiz (yaxşı sıxılan) məlumat olur. Bunlara əlavə olaraq (aşkar qiymətləndirmə) 1 MB xidmət məlumatları.

Yəni, sıxılma tətbiq edilmədiyi halda, 8 MB çip lazımdır, ya da sıxılma istifadə edildikdə 4 MB. Bu tip yaddaş üçün real rəqəmlərdir.

Resursa gəldikdə: əgər yaddaşın tamamilə 5 gündən tez yazılmayacağını planlaşdırırıqsa, o zaman 10 illik xidmət müddətində 1000-dən az yenidən yazma dövrü alırıq.
Xatırladıram ki, istehsalçı yüz min vəd edir.

NOR vs NAND haqqında biraz

Bu gün, əlbəttə, NAND yaddaşı daha populyardır, lakin bu layihə üçün onu istifadə etməyi düşünmürəm: NAND, NOR-dan fərqli olaraq, mütləq səhv düzəltmə kodlarının, qüsurlu blok cədvələlərinin istifadəsini tələb edir və s., eyni zamanda NAND çiplərinin pinlərinin sayı adətən daha çoxdur.

NOR-un çatışmazlıqları olaraq aşağıdakıları qeyd etmək olar:

• kiçik həcmi (və müvafiq olaraq, megabayt üçün yüksək qiymət);
• orta sürətdə məlumat mübadiləsi (çox hallarda ardıcıl interfeys istifadə olunduğu üçün, adətən SPI və ya I2C);
• yavaş erase (blok ölçüsünə görə, bir neçə saniyədən, bir neçə saniyəyə qədər davam edir).

Bizim üçün kritik görünmür, ona görə də davam edirik.

Ətraflı məlumat maraqlıdırsa, seçilmiş çipdir at25df321a (lakin bu əhəmiyyətsizdir, bazarda pin və komandalar üzrə uyğun olan çoxlu analoqlar var; əgər başqa istehsalçıdan və/və ya başqa həcmlə çip qoymaq istəsək, hər şey kodu dəyişdirmədən işə düşəcək).

Linux nüvəsində olan sürücünü istifadə edirəm, Raspberry-də cihaz ağacının üst-üstə qoyulması dəstəyi sayəsində hər şey çox asandır - yalnız /boot/overlays-ə tərtib edilmiş overlayi yerləşdirmək və /boot/config.txt faylını biraz dəyişdirmək lazımdır.

Dts faylının nümunəsi

Düzü, burada səhvsiz yazıldığına əmin deyiləm, amma işləyir.

/*
 * 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?";
    };
};

Və config.txt faylında bir sətir daha

dtoverlay=at25:spimaxfrequency=50000000

Raspberry Pi-yə mikroçipin bağlantısının təsvirini buraxıram. Bir tərəfdən, mən elektronika üzrə mütəxəssis deyiləm, digər tərəfdən - burada hər şey mənim üçün də sadədir: mikroçipin cəmi 8 ayağı var, bunlardan bizə yer, enerji, SPI (CS, SI, SO, SCK) lazımdır; səviyyələr Raspberry Pi ilə üst-üstə düşür, əlavə bağlantı lazım deyil - sadəcə olaraq göstərilmiş 6 kontaktı birləşdirmək kifayətdir.

Məsələnin qoyulması

Adətən, məsələnin qoyulması bir neçə iterasiyadan keçir, məncə, birinə daha ehtiyac var. Beləliklə, gəlin dayanıb, artıq yazılmışları bir yerə toplayaq və qaranlıqda qalan detalar üzərində aydınlıq gətirək.

Beləliklə, artıq SPI NOR Flash-da jurnalın saxlanacağına qərar verdik.

NOR Flash nədir bilmeyənlər üçün

Bu, üç əməliyyat icra edə bildiyimiz enerji müstəqil yaddaşdır:

1. Oxuma:
   Ən adi oxuma: ünvanı ötürürük və nə qədər bayt lazımdırsa, oxuyuruq;
2. Yazma:
   NOR flash-a yazmaq adi kimi görünür, amma bunun bir özəlliyi var: yalnız 1-i 0-a dəyişə bilərsiniz, əksinə isə deyil. Məsələn, əgər yaddaş hüceyrəsində 0x55 varsa, oraya 0x0f yazdıqdan sonra artıq 0x05 olar. (aşağıdakı cədvələ baxın);
3. Silinmə:
   Təbii ki, biz 0-ı 1-ə dəyişmək əməliyyatını da icra edə bilmək üçün - silinmə əməliyyatı var. İlk iki əməliyyatdan fərqli olaraq, bu, baytlarla deyil, bloklarla işləyir (seçilmiş mikroçipdə minimal silinmə bloku - 4kb). Silinmə bütün bloku tamamilə məhv edir və bu, 0-ı 1-ə dəyişdirmək üçün yeganə yoldur. Buna görə, flash yaddaşla işləyərkən tez-tez məlumatların strukturlarını silinmə bloku sərhədinə uyğunlaşdırmaq lazım gəlir.
   NOR Flash-da yazma:

İkili məlumatlar

Oldu
01010101

Yazdıq
00001111

Oldu
00000101

Jurnalın özü dəyişkən uzunluqda yazılardan ibarətdir. Tipik yazı uzunluğu təxminən 30 baytdır (bəzən bir neçə kilobayt uzunluğunda yazılar da baş verir). Bu halda, onlarla sadəcə olaraq bayt qrupuna bənzər bir şəkildə işləyirik, amma, əgər maraqlıdırsa, yazıların içərisində CBOR istifadə edilir.

Jurnalın yanında, bizə bəziləri yeniləməli, bəziləri isə bəyənməli 'tənzimləmə' məlumatlarını saxlamaq lazımdır: bir növ aparatın ID-si, sensorların kalibrləndirilməsi, 'aparat müvəqqəti olaraq söndürüldü' bayrağı və s.
Bu məlumatlar key-value yazılardan ibarətdir, həmçinin CBOR-da saxlanılır. Bizim bu məlumatlar çox deyil (maksimum bir neçə kilobayt), nadir hallarda yenilənir.
Gələcəkdə buna kontekst deyəcəyik.

Məqalənin necə başladığını xatırladıqda, məlumatların saxlanmasının etibarlılığını təmin etmək və mümkün olduqda, hardware nasazlıqları/dəyişikliklər halında belə fasiləsiz işin təmin edilməsi çox önəmlidir.

Hansı problem mənbələrini nəzərdən keçirmək olar?

• Yazma/silme əməliyyatları zamanı enerji kəsilməsi. Bu, "qırılmış zənciri sındırmağın" bir formasıdır.
  Məlumatlar müzakirələri stackexchange-dən: elektrik kəsiləndə flash ilə işləyərkən silmə (1-ə təyin edilməsi) və ya yazma (0-a təyin edilməsi) undefined davranışa gətirib çıxarır: məlumatlar tam yazıla bilər, qismən yazıla bilər (məsələn, biz 10 bayt/80 bit ötürdük, amma yalnız 45 bit yazdıra bildik), bəzən isə bitlərin "ara vəziyyətlə" olması da istisna deyil (oxuma 0 ya da 1 verə bilər);
• Flash yaddaşının öz səhvləri.
  BER çox aşağı olsa da, sıfıra bərabər ola bilməz;
• Şin üzərindəki səhvlər
  SPI vasitəsilə ötürülən məlumatlar heç bir şəkildə qorunmur, tək bit səhvlərindən, həmçinin sinxronizasiya səhvləri ilə - bitlərin itməsi və ya əlavə olunması (bu, geniş miqyasda məlumatların pozulmasına gətirib çıxarır) baş verə bilər;
• Digər səhvlər/dəfələr
  Kod səhvləri, Raspberry'nin "əyri yanları", yadplanetlilərin müdaxiləsi...

Mən etibarlılığın təmin edilməsi üçün zəruri olan tələbləri müəyyən etdim:

• yazılar dərhal flash yaddaşına çatmalıdır, gecikdirilmiş yazma nəzərə alınmır; - əgər səhv baş verərsə, mümkün olduğu qədər tez aşkar edilməli və emal edilməlidir; - sistem mümkün olduğunca səhvlərdən sonra işini bərpa etməlidir.
  ("olmaz" nümunəsi, hər kəsin rastlaşdığı: qəza yenidən başladıkda "fayl sistemi pozuldu" və əməliyyat sistemi açılmır)

Fikirlər, yanaşmalar, düşüncələr

Bu məsələyə yanaşmağa başladığımda, beynimdə bir çox fikir cirit atırdı, məsələn:

• məlumat sıxılmasından istifadə etmək;
• məsələn, qeydlərin başlıqlarını qeydlərin özündən ayrı saxlamaq üçün mürəkkəb məlumat strukturlarından istifadə etmək, beləliklə hər hansı bir qeyddə səhv olduqda digər qeydləri problem olmadan oxumaq mümkün olsun;
• enerji kəsilməsi zamanı yazmanın tamamlanmasını izləmək üçün bit sahələrindən istifadə etmək;
• hər şeyin, hər birinin üçün yoxlama cəmləri saxlamaq;
• hər hansı bir növ maneə dözümlü kodlamadan istifadə etmək.

Bu fikirlərdən bəziləri istifadə olundu, bəzilərini isə istifadə etməkdən imtina edildi. Gəlin ardıcıllıqla baxaq.

Məlumat sıxılması

Jurnalımızda qeydə alınan hadisələr kifayət qədər eyni növ və təkrarlanan («5 manatlıq əskinə atıldı», «qaytarma düyməsinə basıldı», ...). Ən səmərəli sıxılma olmalıdır.

Sıxma ilə bağlı xərclər əhəmiyyətli dərəcədə azdır (prosessorumuz kifayət qədər güclüdür; hətta ilk Pi-də 700MHz tezlikli bir nüvəmiz var idi, indiki modellərdə isə bir neçə nüvə 1 gigahertzdən yüksək tezlikdə işləyir), saxlama sürəti aşağıdır (bir neçə megabayt saniyədə), qeydlərin ölçüsü isə kiçikdir. Ümumilikdə, əgər sıxma performansa təsir edəcəksə, bu yalnız müsbət olacaq. (tamamilə kritik deyil, sadəcə qeyd edirəm). Üstəlik, bizdə real embedded yox, adi Linux var — buna görə icra çox çətin olmamalıdır (sadəcə kitabxananı bağlamaq və ondan bir neçə funksiyanı istifadə etmək kifayətdir).

İşləyən bir cihazın logunun bir hissəsi götürüldü (1.7MB, 70 min qeyd) və əvvəlcə komputerimdə olan gzip, lz4, lzop, bzip2, xz, zstd ilə sıxıla biləcəyinə baxıldı.

• gzip, xz, zstd oxşar nəticələr göstərdi (40KB).
  Məni təəccübləndirdi ki, məşhur xz burada gzip ya da zstd səviyyəsində çıxdı;
• lzip standart parametrlərlə bir az pis nəticə verdi;
• lz4 və lzop isə çox yaxşı bir nəticə göstərmədi (150KB);
• bzip2 isə təəccüblü şəkildə yaxşı bir nəticə verdi (18KB).

Beləliklə, məlumatlar çox yaxşı sıxılır.
Beləliklə, (əgər biz fundamental çatışmazlıqlar tapmasaq) sıxma olacaq! Sadəcə, çünki eyni flaşda daha çox məlumat saxlanıla bilər.

Gəlin çatışmazlıqları düşünək.

Birinci problem: biz artıq razılaşdıq ki, hər bir qeyd dərhal flaşa düşməlidir. Adətən arxivator, çıxışa yazma vaxtının gəldiyini düşünənə qədər giriş axınından məlumatları toplar. Bizə isə sıxılmış məlumat bloku dərhal əldə etmək və onu enerji ilə mühafizə olunan yaddaşda saxlamaq lazımdır.

Mən üç yol görürəm:

1. Hər bir qeydi yuxarıda müzakirə olunan algoritmlardan fərqli olaraq leksik sıxma ilə sıxmaq.
   Tamamilə işlək bir variant, amma mənim üçün xoş deyil. Müqayisəli bir sıxma səviyyəsi təmin etmək üçün leksik cədvəl konkret məlumatlara uyğun olmalıdır, hər hansı bir dəyişiklik sıxma səviyyəsinin kəskin şəkildə düşməsinə gətirib çıxarır. Bəli, problem yeni bir cədvəl versiyası yaradılması ilə həll edilə bilər, amma bu baş ağrısıdır — biz hər bir cədvəl versiyasını saxlamağa məcburuq; hər bir qeydimizdə hansı cədvəl versiyası ilə sıxıldığını göstərməliyik...
2. Hər bir qeydi «klassik» algoritmlarla sıxmaq, lakin bir-birindən asılı olmayaraq.
   Müzakirə olunan sıxma algoritmları belə ölçüdə (onlarla bayt) qeydlərlə işləmək üçün nəzərdə tutulmayıb; sıxma əmsalı açıq şəkildə 1-dən az olacaq (yəni, sıxma əvəzinə məlumatların həcminin artması);
3. Hər bir qeyddən sonra FLUSH etmək.
   Çox sayda sıxma kitabxanasında FLUSH dəstəyi var. Bu, sıxma proseduruna verilən bir komanda (ya da parametr)dir ki, arxivator bu komandanı aldığında sıxılmış axını belə formalaşdırır ki, onun əsasında artıq alınmış tüm sıxılmamış məlumatları bərpa etmək mümkündür. Belə bir analog sync fayl sistemlərində və ya commit sql-də.
   Əsas odur ki, sonrakı sıxılma əməliyyatları toplanmış lüğətdən istifadə edə biləcək və sıxılma dərəcəsi əvvəlki variantda olduğu kimi o qədər də ziyan görməyəcək.

Məncə, üçüncü variantı seçdiyim açıqdır, ona daha ətraflı baxaq.

Tapa bildim əla məqalə zlib-də FLUSH ilə bağlı.

Məqalə əsasında bir test həyata keçirdim, gerçək bir cihazdan 70 min giriş qeydi topladım, səhifə ölçüsü 60Kb olan sistemlə (səhifə ölçüsü ilə biz hələ geri dönəcəyik) aldım:

Məlumatlar
gzip sıxılması -9 (FLUSH olmadan)
zlib Z_PARTIAL_FLUSH ilə
zlib Z_SYNC_FLUSH ilə

Həcm, Kb
1692
40
352
604

İlk baxışda FLUSH-un gətirdiyi qiymət həddindən artıq yüksək görünə bilər, amma əslində bizim seçimimiz çox zəifdir - ya heç sıxmamaq, ya da FLUSH ilə (və çox effektiv şəkildə) sıxmaq. Unutmayaq ki, bizdə 70 min qeyd var, Z_PARTIAL_FLUSH tərəfindən yaradılan artıqlıq hər qeyd üçün yalnız 4-5 baytdır. Və sıxılma dərəcəsi 5:1-dən çox çıxdı, bu da mükəmməl nəticədir.

Gözlənilməz görünsə də, əslində Z_SYNC_FLUSH daha effektiv FLUSH anlayışını təqdim edir

Z_SYNC_FLUSH istifadə edildikdə hər qeyd üçün son dörd bayt daim 0x00, 0x00, 0xff, 0xff olacaq. Əgər bu baytları bilsək - onları saxlaya bilmərik, beləliklə nəticədəki ölçü yalnız 324Kb olur.

Mənim istinad etdiyim məqalədə izah var:

Boş məzmunlu yeni tip 0 bloku əlavə edilir.

Boş məzmunlu tip 0 bloku aşağıdakılardan ibarətdir:

• üçbitlik blok başlığı;
• 0-dan 7 bitə qədər sıfır, bayt hizalaması əldə etmək üçün;
• dörd baytlıq 00 00 FF FF sırası.

Son bloka qədər olan 4 baytdan əvvəl 3-dən 10-a qədər sıfır bit olduğunu asanlıqla görə bilərsiniz. Ancaq praktikada, sıfır bitlərinin əslində minimum 10 olduğunu göstərdi.

Məlum oldu ki, bu qədər qısa məlumat blokları ümumiyyətlə (həmişə?) tip 1 (sabit blok) istifadə edərək kodlaşdırılır ki, bu da mütləq 7 sıfır bitlə bitməlidir, beləliklə 10-17 mütləq sıfır bit əldə etmiş oluruq (qalanları isə təxminən 50% ehtimalı ilə sıfır olacaq).

Buna görə, test məlumatlarında 0x00, 0x00, 0xff, 0xff-dən əvvəl 100% hallarda bir sıfır bayt, daha çox hallarda isə — iki sıfır bayt var (bəlkə də, mən binary CBOR istifadə edirəm, amma mətn JSON istifadə edildikdə daha çox bloklar tip 2 - dinamik blok görünərdi, müvafiq olaraq 0x00, 0x00, 0xff, 0xff-dən əvvəl əlavə sıfır baytları olan bloklar görünərdi).

Beləliklə, mövcud test məlumatlarına əsasən, sıxılmış məlumatlarda 250Kb-dan az yer tutmaq mümkündür.

Biraz daha qənaət edə bilərik, bitləri dizmək ilə məşğul olaraq: indiki halda biz blokun sonundakı bir neçə sıfır bit olduğunu göz ardı edirik, blokun əvvəlində bir neçə bit də eyni qalmır...
Amma burada mən sərt bir qərar qəbul etdim, çünki bu cür temp ilə öz arxivatorumu inkişaf etdirməyə başlaya bilərdim.

Nəticədə, test məlumatlarıma əsasən, 3-4 bayt yazmağı əldə etdim, sıxılma dərəcəsi 6:1-dən çox oldu. Düzünü desəm, belə bir nəticəyə ümid etmirdim, mənim fikrimcə 2:1-dən yaxşı olan hər şey sıxılmanın istifadə olunmasına dəyər.

Hər şey mükəmməl, amma zlib (deflate) yenə də köhnə, lakin hörmətli və bir az köhnəlmiş sıxılma alqoritmidir. Son 32Kb sıxılmamış verilənlərinin axını, lüğət olaraq istifadə edilməsi belə bir vəziyyətdə qəribə görünür (yəni əgər bir blok verilənləri 40Kb əvvəlki axından çox oxşar olursa, o, yenidən arxivləşdiriləcək, keçmiş daxilolmaya istinad etməyəcəkdir). Müasir arxivatorlarda lüğət ölçüsü daha çox megabaytlarla ölçülür, kilobaytlardan deyil.

Beləliklə, arxivatorlarla mini araşdırmamıza davam edirik.

Növbəti bzip2 alınıb (xatırladım, FLUSH olmadan fantastik sıxılma dərəcəsi 100:1ə yaxın oldu). Təəssüf ki, FLUSH ilə çox pis nəticələr göstərdi, sıxılmış verilənlərin ölçüsü, sıxılmamışdan böyük çıxdı.

Mənim uğursuzluğun səbəbləri ilə bağlı düşüncələrim

Libbz2, görünür, yalnız bir flush variantı təqdim edir, bu, lüğəti təmizləyir (zlib-dakı Z_FULL_FLUSH analoqu), bundan sonra hər hansı səmərəli sıxılmadan danışmaq mümkün deyil.

Sonuncusu zstd oldu. Parametrlərdən asılı olaraq, ya gzip səviyyəsində sıxır, lakin daha sürətli, ya da gzipdən daha yaxşı.

Təəssüf ki, FLUSH ilə də «çox yaxşı» nəticələr vermədi: sıxılmış verilənlərin ölçüsü təxminən 700Kb oldu.

Mən sual verdim github layihə səhifəsində, sıxılmış verilənlər üçün hər blok üzrə 10 bayta qədər idarəetmə verilənlərə gözləmək lazım olduğu cavabını aldım, bu, əldə edilən nəticələrə yaxındır, deflate-ni keçmək mümkün olmayacaq.

Bununla, arxivatorlarla eksperimentlərimi dayandırmağa qərar verdim (xatırlayıram ki, xz, lzip, lzo, lz4 hələ FLUSH olmadan test mərhələsində özlərini yaxşı göstərmədi, daha ekzotik sıxılma alqoritmləri nəzərdən keçirilmədi).

Arxivləşdirmə problemlərinə qayıdırıq.

İkincisi (deyildiyi kimi, ardıcıllıqla, lakin əhəmiyyətinə görə deyil) problem - sıxılmış verilənlər birdəfəlik axın təşkil edir, burada daim əvvəlki hissələrə istinad edilir. Beləliklə, sıxılmış verilənlərin bir hissəsinin zədələnməsi ilə yalnız ona bağlı sıxılmamış verilən blokunu itirmirik, həm də bütün sonrakıları.

Bu problemin həllinə yanaşmalar var:

1. Problemin yaranmasının qarşısını almaq — sıxılmış verilənlərə artıqlıq əlavə etmək, bu, xətaları tanımağa və düzəltməyə imkan verəcək; bununla daha sonra danışacağıq;
2. Problemin baş verməsi halında nəticələri minimuma endirmək
   Daha əvvəl də qeyd etdiyimiz kimi, hər bir məlumat blokunu müstəqil sıxmaq mümkündür, bu zaman problemin özü ortadan qalxır (bir blokun zədələnməsi yalnız həmin blokun məlumatlarının itirilməsinə səbəb olacaq). Ancaq bu, məlumatların sıxılmasının effektiv olmadığı ekstremal bir haldır. Tərsinə, 4MB-lıq çipimizin hamısını bir arxiv kimi istifadə etmək, bizə əla sıxılma verəcək, lakin məlumatların zədələnməsi halında fəlakətli nəticələrə səbəb olacaq.
   Bəli, etibarlılıq baxımından bir kompromis lazımdır. Ancaq unutmaq olmaz ki, biz 20 illik saxlama müddəti ilə son dərəcə aşağı BER-ə malik enerji müstəqil yaddaş üçün məlumat saxlama formatı inkişaf edirik.

Eksperimentlər zamanı gördüm ki, sıxılmış məlumat bloklarında sıxılma səviyyəsinin daha çox nəzərəçarpan itkiləri 10KB-dən aşağı olan bloklarda başlayır.
Əvvəlcə istifadə olunan yaddaşın səhifə təşkilinə malik olduğu qeyd edilib, "bir səhifə - bir sıxılmış məlumat bloku" uyğunluğunu istifadə etməyə qarşı bir səbəb görmürəm.

Yəni, minimal makul səhifə ölçüsü 16KB-dir (xidmət məlumatı üçün ehtiyatı da nəzərə alaraq). Ancaq bu qədər kiçik səhifə ölçüsü qeyd etmək üçün maksimum ölçüyə ciddi məhdudiyyətlər qoyur.

Hal-hazırda sıxılmış şəkildə bir kilobaytdan böyük qeyd gözləmədiyim üçün 32KB-lıq səhifələrdən istifadə etməyə qərar verdim (yəni çip başına ümumilikdə 128 səhifədir).

Xülasə:

• Məlumatları zlib (deflate) ilə sıxılmış şəkildə saxlayırıq;
• Hər bir qeyd üçün Z_SYNC_FLUSH müəyyən edirik;
• Hər sıxılmış qeyddən son baytları kəsirik (məsələn, 0x00, 0x00, 0xff, 0xff); başlıqda neçənin bayt olduğunu göstəririk;
• Məlumatları 32KB-lıq səhifələrdə saxlayırıq; səhifə daxilində sıxılmış məlumatların ardıcıl axını var; hər səhifədə sıxılmanı yenidən başlayırıq.

Və sıxılma ilə işimizi bitirmədən öncə diqqət çəkmək istərdim ki, sıxılmış məlumatların hər qeydə cəmi bir neçə bayt olması, xidmət məlumatını artırmamağın son dərəcə vacib olduğu anlamına gəlir, burada hər bir bayt məhsuldardır.

Məlumat başlıqlarının saxlanması

Çünki bizdə dəyişkən uzunluqlu qeydlər var, ona görə də qeydlərin yeri/hüdudlarını müəyyən etməyin bir yolu olmalıdır.

Üç yanaşmanı tanıyıram:

1. Bütün qeydlər davamlı axında saxlanılır, əvvəlcə qeydin uzunluğunu artıran başlıq, sonra isə özü qeyddir.
   Bu variantda həm başlıqlar, həm də məlumatlar dəyişkən uzunluğa malik ola bilər.
   Əslində, bizdə daim istifadə olunan bir bağlı siyahı yaranır;
2. Başlıqlar və qeydlər ayrı-ayrı axınlarda saxlanılır.
   Daimi uzunluqlu başlıqlar istifadə edərək, bir başlığın zədələnməsi digər başlıqlara təsir etmir.
   Belə yanaşma, məsələn, bir çox fayl sistemlərində istifadə olunur;
3. Yazılar kesintisiz bir akışta saklanıyor, kayıt sınırı belirli bir işaretçi (sembol/dizi semboller) tarafından belirleniyor, bu işaretçi veri blokları içinde yasaklıdır. Kayıt içinde bir işaretçi varsa, onu belirli bir dizi ile değiştiriyoruz (kaçış karakteri kullanarak).
   Böyle bir yaklaşım, örneğin PPP protokolünde kullanılmaktadır.

Göstereyim.

Variant 1:

Burada her şey çok basit: Kaydın uzunluğunu bilerek bir sonraki başlığın adresini hesaplayabiliriz. Başlıkların arasında hareket ederiz, ta ki 0xff ile doldurulmuş bir alan (boş alan) ya da sayfanın sonunu bulana dek.

Variant 2:

Kayıtların değişken uzunluğu nedeniyle, sayfada ne kadar kayıt (yani başlık) gerektiğini önceden söyleyemeyiz. Başlıkları ve verileri farklı sayfalara yerleştirebiliriz, ama benim için daha hoş bir yaklaşım var: hem başlıkları hem de verileri aynı sayfada tutuyoruz, ancak başlıklar (sabit boyutlu) sayfanın başından, veriler (değişken uzunlukta) ise sonundan başlıyor. Onlar 'karşılaştığında' (yeni bir kayıt için boş yer yetmediğinde) bu sayfayı dolu sayıyoruz.

Seçenek 3:

Burada başlıkta veri uzunluğunu veya başka bilgilere yer ayırmaya gerek yok, sadece kayıt sınırlarını belirten işaretçilere ihtiyacımız var. Ancak verileri yazma/okuma sırasında işlememiz gerekiyor.
Bir işaretçi olarak 0xff kullanmayı öneririm (silme işleminden sonra sayfa bu değerle doldurulur), bu şekilde boş alan kesin olarak veri olarak algılanmaz.

Karşılaştırmalı tablo:

Variant 1
Variant 2
Variant 3

Hata toleransı
—
+
+

Kompaktlık
+
—
+

Uygulama karmaşıklığı
*
**
**

Seçenek 1'in kritik bir dezavantajı var: herhangi bir başlığın hasar görmesi durumunda, tüm sonraki zincir yok oluyor. Diğer seçenekler, kitlesel hasar durumunda bile verilerin bir kısmını kurtarmayı sağlıyor.
Ama burada, verileri sıkıştırılmış halde saklamaya karar verdiğimizi hatırlamakta fayda var, bu nedenle 'bozuk' kayıttan sonra sayfadaki tüm verileri kaybediyoruz, bu yüzden tabloda bir eksi olsa da dikkate almıyoruz.

Kompaktlık:

• ilk seçenekte başlıkta sadece uzunluğu saklamamız gerekiyor, eğer değişken genişlikte tam sayılar kullanırsak, çoğu durumda sadece bir baytla yetinebiliriz;
• ikinci seçenekte başlangıç adresini ve uzunluğu saklamamız gerekiyor; kayıt sabit boyutta olmalı, yazım başına 4 bayt olarak değerlendiriyorum (iki bayt yer değiştirme, iki bayt uzunluk için);
• üçüncü seçenekte sadece bir sembol kaydın başlangıcını belirtmek için yeterlidir, ayrıca kaçış işlemi nedeniyle kaydın %1-2 daha büyümesine neden olacaktır. Genel olarak, birinci seçenekle yaklaşık eşdeğer.

Başlangıçta ikinci seçeneği ana seçenek olarak değerlendirmiştim (hatta bir uygulama yazdım). Bunu, sıkıştırmayı kullanmaya tamamen karar verene kadar terk ettim.

Bəlkə, bir gün belə bir variantı istifadə edəcəyəm. Məsələn, əgər mənə Yer ilə Mars arasında gedən bir gəminin məlumatlarının saxlanmasıyla məşğul olmağım lazım olsa — tamamilə fərqli etibarlılıq tələbləri, kosmik radiasiya, ...

Üçüncü variantla bağlı: tətbiqinin çətiniyi üçün ona iki ulduz qoydum, sadəcə ekranlaşdırma, prosesdə uzunluğun dəyişməsi və s. kimi şeylərlə başa çıxmağı sevmədiyim üçün. Bəli, bəlkə, subyektivdir, amma kodu yazmalı olacağam — niyə sevmədiyim bir şeylə özümü əziyyətə salım?

Xülasə: Səmərəlilik və tətbiqinin sadəliyi səbəbindən "başlıq uzunluğu - dəyişən uzunluqlu məlumatlar" zəncirləri formasında saxlamanı seçirik.

Yazma əməliyyatlarının müvəffəqiyyətini izləmək üçün bit sahələrinin istifadəsi

İndi hara baxdığımı xatırlamıram, amma hər şey təxminən belə görünür:
Hər qeyd üçün bayraqları saxlamaq üçün bir neçə bit ayırırıq.
Daha əvvəl dediyimiz kimi, erase-dan sonra bütün bitlər 1 ilə doldurulur, biz isə 1-i 0-a dəyişə bilərik, lakin əksinə mümkün deyil. Beləliklə, "bayraq quraşdırılmayıb" üçün 1, "bayraq quraşdırılmışdır" üçün isə 0 istifadə edirik.

Beləliklə, dəyişən uzunluqlu bir qeyd flash-dakı görünüşü belə ola bilər:

1. “Yazma uzunluğunun başladığını” göstərən bayrağı qoyuruq;
2. Uzunluğu yazırıq;
3. “Məlumat yazmağın başladığını” göstərən bayrağı qoyuruq;
4. Məlumatı yazırıq;
5. “Yazmanın başa çatdığını” göstərən bayrağı qoyuruq.

Bundan əlavə, bizim “səhv baş verdi” bayrağımız olacak, nəticədə 4 bit bayrağı olacaq.

Bu durumda iki sabit vəziyyətimiz var: “1111” — yazma başlamayıb və “1000” — yazma müvəffəqiyyətlə keçib; gözlənilməz yazma prosesinin kəsilmə halında, biz müvəqqəti vəziyyətlər əldə edəcəyik ki, bunları sonra aşkar edib müalicə edə biləcəyik.

Yanaşma maraqlıdır, amma o yalnız gözlənilməz enerji təchizatı kəsilməsi və belə uğursuzluqlardan qoruyur, bu, əlbəttə ki, əhəmiyyətlidir, ancaq bu, mümkünsüzlük səbəblərinin tək başına (həm də əsas) səbəbi deyil.

Xülasə: Yaxşı bir həll axtarışında irəliləyirik.

Yoxlama cəmləri

Yoxlama cəmləri də bizə (kafi ehtimalla) hansı ki, yazılmalı olanı oxuduğumuzu təsdiq etməyə imkan tanıyır. Və, yuxarıda müzakirə olunan bit sahələrindən fərqli olaraq, onlar hər zaman işləyirlər.

Yuxarıda qeyd edilən problem mənbələrinin siyahısına nəzər saldıqda, yoxlama cəmimiz səhvi onun mənşəyindən asılı olmayaraq tanımaq mümkündür. (bəlkə də zərərli yadplanetliləri istisna etməklə — onlar yoxlama cəmini də saxtalaşdıra bilərlər).

Beləliklə, əgər məqsədimiz məlumatların sağlamlığını yoxlamaqdırsa, yoxlama cəmləri — mükəmməl bir fikirdir.

Nəzarət toplamı hesablama alqoritmini seçmək problemi yaranmadı — CRC. Bir tərəfdən, riyazi xüsusiyyətlər bəzi növ xətaları tam 100% tutmağa imkan verir, digər tərəfdən isə təsadüfi məlumatlarda bu alqoritmin çarpaz gəzmə ehtimalı adətən nəzəri limitdən artıq olmur. . Bu, bəlkə də ən sürətli alqoritm deyil, həmişə daha az çarpaz qurtarma sayına malik deyil, lakin onun çox vacib bir keyfiyyəti var: mənim rastlaşdığım testlərdə onun açıq şəkildə uğursuz olduğu nümunələr tapılmadı. Sabitlik — bu halda ən vacib keyfiyyətdir.

Həcmli tədqiqat nümunəsi: hissə 1, hissə 2 (narod.ru saytına bağlantılar, bağışlayın).

Ancaq nəzarət toplamını seçmək vəzifəsi tamamlanmadı, CRC — bu, tam bir nəzarət toplamları ailəsidir. Uzunluğu müəyyənləşdirmək və sonra polinom seçmək lazımdır.

Nəzarət toplamının uzunluğunu seçmək birinci görünüşdə olduğu qədər sadə bir sual deyil.

İllüstrasiya edim:
Gəlin qəbul edək ki, hər baytda xətta olma ehtimalı və ideal nəzarət toplamı, bir milyon qeyddə orta xəta sayını hesablayaq:

Məlumat, bayt
Nəzarət toplamı, bayt
Aşkar olunmamış xətalar
Yanlış aşkarlanan xətalar
Ümumilikdə yanlış siqnallar

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

Görünür ki, hər şey sadədir — qorunan məlumatın uzunluğuna uyğun olaraq nəzarət toplamının uzunluğunu seçin ki, yanlış siqnallar minimum olsun — və iş bitir.

Ancaq, qısa nəzarət toplamları ilə problem yaranır: onlar, tək bit xətalarını yaxşı aşkarlasalar da, kifayət qədər böyük ehtimalla tamamilə təsadüfi məlumatı doğru qəbul edə bilərlər. Habr-da artıq bir məqalə var idi, burada həyatda olan problemi.

mısa düşməsinə qarşı, nəzarət toplamının təsadüfi uyğunluğunu demək olar ki, mümkünsüz etmək üçün 32 bitdən uzun nəzarət toplamı istifadə etmək lazımdır (64 bitdən uzun üçün adətən kriptoqrafik hash funksiyalarından istifadə olunur).

Buna baxmayaraq, əvvəllər yazmışdım ki, hər bir baytı qorumaq üçün yerə qənaət etməliyik, yenə də 32 bitlik nəzarət toplamı istifadə edəcəyik (16 bit azdır, çarpaz gəlmə ehtimalı 0.01%-dən çoxdur; 24 bit isə, dediyimiz kimi, nə ora, nə bura).

Burada bir etiraz yarana bilər: sıxma seçərkən hər baytı sərf etməkdə idik ki, indi 4 bayt bir anda verək? Sıxma etmədən və nəzarət toplamı əlavə etmədən daha yaxşı olmazdı? Əlbəttə, sıxmanın olmaması demək deyil ki,başlanğıcın yoxlanması bizə lazım deyil.

Polinom seçimi ilə bağlı yeni bir şey icad etməyəcəyik, indiki dövrdə populyar olan CRC-32C alaq.
Bu kod 22 bayta qədər olan paketlərdə 6 bit xəta aşkar edir (bəlkə də ən tez-tez rastlaşdığımız haldır), 655 bayta qədər olan paketlərdə 4 bit xəta aşkar edir (bu da bizim üçün tez-tez rastlaşan bir haldır), 2 və ya hər hansı tək ədədlə bit xətaları isə hər cür məqbul uzunluqdakı paketlərdə aşkar edir.

Kimin detallarla maraqlandığı varsa

Vikipediya məqaləsi CRC haqqında.

crc-32c kodunun parametrləri buna Küpmana saytında — yəqin ki, dünyada CRC üzrə ən aparıcı mütəxəssis.

İ onun məqaləsində So, let's start the step-by-step implementation bir maraqlı kod daha, bizim üçün aktual paket uzunluqları üçün bir az daha yaxşı parametr təmin edir, amma fərqi əhəmiyyətli hesab etmədim, özümü standart və yaxşı araşdırılmış kod əvəzinə xüsusi kod seçməyə kifayət qədər kompetent hesab edirəm.

Həmçinin, bizim verilənlər sıxıldığı üçün, sıxılmış və ya sıxılmamış verilənlərlə nəzarət cəminin hesablanması məsələsi yaranır?

Sıxılmamış verilənlərin kontrol cəminin hesablanmasının "yaxşı" arqumentləri:

• nəticədə, verilənlərin saxlanmasının təhlükəsizliyini yoxlamaq lazımdır - bunu birbaşa yoxlayırıq (bu zaman sıxma/dəcompressiya icrasında baş verə biləcək səhvlər, yarıqları səbəb olan xətalar və s. bir daha yoxlanacaq);
• zlib-dəki deflate alqoritminin kifayət qədər yetkin tərtibatı var və düşməməlidir sorğulanan verilənlərdə "səhv" nəticəsində, daha da çox, çox vaxt, o, daxil olan axında xətaları öz-özünə aşkar etmək bacarığına malikdir, tamamilə səhv tapılma ehtimalını azaldır (bir qısa qeyd içində bir bitin tərsinə çevrilməsi ilə test apardım, zlib xətası təxminən üçdə bir halda aşkar etdi).

Sıxılmamış verilənlərin kontrol cəminin hesablanmasının "əleyhinə" arqumentləri:

• CRC tam olaraq flash yaddaş üçün xarakterik olan nadir bit xətalarına yönəlib (sıxılmış axında bit xətti, çıxış axınında bizim "tutduğumuz" bir toqquşmaya səbəb ola bilər);
• mən, dekombressora potensial olaraq qırılmış verilənləri ötürmək fikrini sevmirəm, kim bilir, o, necə reaksiya verəcək.

Bu layihədə mən sıxılmamış verilənlərin kontrol cəmini saxlamaq ümumi təcrübəsindən uzaqlaşmağı qərara aldım.

Xülasə: biz CRC-32C istifadə edirik, kontrol cəmini verilənlərin flash-a yazıldığı formada hesablayırıq (sıxılma sonrası).

Artıqlıq

Artıq kodlaşdırmanın məlumatların itkisini istisna etməsinə imkan verməsə də, bu, bərpa olunmaz məlumat itkisi ehtimalını Substantially (çox vaxt bir neçə dəfə) azalda bilər.

Xətaları düzəltmək üçün fərqli növ artıqlıqları istifadə edə bilərik.
Hamming kodları tək bit xətalarını düzəldə bilir, Reed-Solomon kodları simvolları, bir neçə verilən nüsxəsi, nəzarət cəmiləri ilə birlikdə və RAID-6 kimi kodlaşdırma, kütləvi xətalar baş verdikdə belə, verilənləri bərpa etməyə kömək edə bilər.
İlk növbədə, mühafizəedici kodlaşdırmanın geniş istifadə edilməsinə hazır idim, amma sonra başa düşdüm ki, əvvəlcə hansı xətalardan qorunmaq istədiyimizi başa düşmək lazımdır, sonra isə kodlaşdırma seçməliyik.

Daha əvvəl dediyimiz kimi, xətaları mümkün qədər tez aşkar etmək lazımdır. Hangi anlarda xətalarla qarşılaşa bilərik?

1. Tamamlanmamış qeyd (hansısa səbəbdən qeyd zamanı enerji kəsilir, Raspberry donur, …)
   Təəssüf ki, belə bir xəta baş verdikdə qeyri-valid qeydləri gözardı etmək və məlumatların itmiş sayıldığını qəbul etmək lazımdır;
2. Qeyd etmə xətaları (hansısa səbəbdən flash yaddaşda qeydə alınan başqadır)
   Bu cür xətaları qeyd etdikdən sonra birbaşa kontrol oxumağı həyata keçirərək dərhal aşkar edə bilərik;
3. Yaddaşda saxlanma prosesi zamanı məlumatların pozulması;
4. Oxuma xətaları
   Hesablanan cəmin uyğunsuzluğu halında bir neçə dəfə oxumağı təkrarlamaq kifayətdir.

Yəni yalnız üçüncü növ xətalar (məlumatların saxlanılmasında öz-özünə pozulması) düzgün mühafizə kodlaması olmadan düzəldilə bilməz. Belə xətaların çox az ehtimal olduğuna inanıram.

Xülasə: artıq artıqlama kodlamadan imtina edilməsi qərara alındı, amma əgər istismar bu qərarın səhv olduğunu göstərəcəksə, problemə qayıtmaq olar (artıq toplanmış uğursuzluq statistikası ilə, optimal kodlama növünü seçmək üçün).

Digər

Təbii ki, məqalənin formatı hər bir bitin əsaslandırılmasına imkan vermir (və mənim üçün artıq güc tükənib), ona görə də əvvəllər toxunulmamış bəzi məqamlardan qısa keçəcəyəm.

• Bütün səhifələrin "bərabər hüquqlu" olması qərara alındı
  Yəni bəzi xüsusi səhifələr metadatalarla, ayrı axınlarla və s. olmayacaq, bunun əvəzinə bütün səhifələri növbə ilə yenidən yazan tək bir axın olacaq.
  Bu, səhifələrin bərabər aşınmasını təmin edir, tək bir uğursuzluq nöqtəsinin olmadığını, həmçinin sadəcə xoşuma gəlir;
• Formatın versiyonunun təmin olunması mütləq olmalıdır.
  Versiya nömrəsi olmayan bir format - çox pisdir!
  Səhifə başlığına istifadə olunan format versiyasını göstərəcək bir Magic Number (imza) sahəsini əlavə etmək kifayətdir (praktikada onların on dənədən çox olacağını düşünmürəm);
• Çox sayda qeydlər üçün (çox sayda) dəyişən uzunluqda başlıq istifadə edin, əksər hallarda onun uzunluğunu 1 bayta gətirməyə çalışaraq;
• Başlığın uzunluğunu və sıxılmış qeydin kəsilmiş hissəsinin uzunluğunu kodlamaq üçün dəyişən uzunluqda ikili kodlardan istifadə edin.

Çox kömək oldu onlayn generator Huffman kodlarının. Sadəcə bir neçə dəqiqə ərzində lazım olan dəyişən uzunluqda kodları tapmaq mümkün oldu.

Məlumatların saxlanma formatının təsviri

Bayt sırası

Bir baytdan çox olan sahələr big-endian formatında (şəbəkə bayt sırası) saxlanılır, yəni 0x1234 0x12, 0x34 kimi qeyd olunur.

Səhifələrə bölmə

Bütün flash yaddaş bərabər ölçülü səhifələrə bölünüb.

Səhifənin ölçüsü əvvəlcə 32Kb, amma yaddaş çipinin ümumi ölçüsünün 1/4-dən artıq olmadan (4Mb-lıq çip üçün 128 səhifə hasil olur).

Hər bir səhifə digərindən müstəqil məlumat saxlayır (yəni bir səhifənin məlumatları digər səhifənin məlumatlarına istinad etmir).

Bütün səhifələr təbii ardıcıllıqla (ünvanların artan sırası ilə) nömrələnir, 0 (sıfırıncı səhifə 0 ünvanından başlayır, birinci səhifə 32K, ikinci səhifə 64K və s.) nömrəsindən başlayaraq.

Yaddaş çipi dövri tampon (ring buffer) kimi işlədilir, yəni əvvəlcə yazı 0 nömrəli səhifəyə, sonra 1 nömrəli səhifəyə və s. gedir; biz son səhifəni doldurduqdan sonra yeni dövr başlayır və yazı sıfırıncı səhifədən davam edir.

Səhifənin içində

Səhifənin əvvəlində 4 baytlıq səhifə başlığı, sonra başlıqın kontrol cəmi (CRC-32C), daha sonra "başlıq, məlumat, kontrol cəmi" formatında qeydlər saxlanılır.

Səhifə başlığı (şemada çirkli-yaşıl) bunlardan ibarətdir:

• iki baytlıq Magic Number sahəsindən (həmçinin - format versiyasının göstəricisi)
  mövcud format versiyası üçün bu hesablanır 0xed00 ⊕ səhifə nömrəsi;
• iki baytlıq "Səhifə Versiyası" sayğacından (yaddaşın yeniden yazılma dövrünün nömrəsi).

Səhifədəki qeydlər sıxılmış formada saxlanılır (deflate alqoritmi istifadə olunur). Bütün qeydlər eyni səhifədə bir axında sıxılır (ümumi lüğət istifadə olunur), hər yeni səhifədə sıxılma yenidən başlayır. Yəni hər hansı bir qeydin dekompresiyası üçün bu səhifənin bütün əvvəlki qeydləri (və yalnız bunlar) tələb olunur.

Hər bir qeydə Z_SYNC_FLUSH flaqı ilə sıxılacaq, bu zaman sıxılmış axının sonunda 4 bayt 0x00, 0x00, 0xff, 0xff olacaq, bunlar bəlkə də bir və ya iki sıfır baytı ilə əvvəlcədən gəlir.
Bu ardıcıllığı (4, 5 və ya 6 bayt uzunluğunda) flash yaddaşa yazarkən atırıq.

Qeydin başlığı 1, 2 və ya 3 baytdan ibarətdir ki, burada:

• bir bit (T) qeyd növünü göstərir: 0 - kontekst, 1 - jurnal;
• qalınlığı 1-dən 7 bitə qədər olan dəyişən uzunluqlu (S) sahəsi, başlığın uzunluğunu və dekompressiya üçün qeydə əlavə edilməli olan "ayaq" sahəsini müəyyən edir;
• qeydin uzunluğu (L).

S dəyərləri cədvəli:

S
Başlığın uzunluğu, bayt
Yazarkən atılır, bayt

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)

Aydınlaşdırmağa çalışdım, nə qədər aydın olduğunu bilmirəm:

Sarı ilə burada T sahəsi, ağ ilə S sahəsi, yaşıl ilə L (sıxılmış məlumatların uzunluğu baytlarda), mavi ilə sıxılmış məlumatlar, qırmızı ilə yazılmayan sıxılmış məlumatların son baytları işarələnmişdir.

Beləliklə, ən geniş yayılmış uzunluqda (sıxılmış formada 63+5 bayta qədər) qeydlərin başlıqlarını bir baytla yaza bilərik.

Hər bir qeyddən sonra CRC-32C kontrol cəmi saxlanılır ki, bunun başlanğıc dəyəri (init) əvvəlki kontrol cəminin tərs dəyəridir.

CRC «davamlılıq» xüsusiyyətinə malikdir, beləliklə (bitlərin prosesi zamanı tərsi olmaqla) belə bir formula işləyir: .
Yəni, faktiki olaraq, biz bu səhifədəki əvvəlki başlıqların və məlumatların bütün baytlarının CRC-ni hesablayırıq.

Nəzarət cəmi ilə birbaşa növbəti qeydin başlığı yerləşir.

Başlıq belə şəkildə qurulub ki, onun ilk baytı həmişə 0x00 və 0xff-dən fərqli olur (əgər başlığın ilk baytı 0xff-dirsə, deməli, bu istifadə olunmamış sahədir; 0x00 isə səhv olduğunu bildirir).

Təxmini alqoritmlər

Flash yaddaşından oxuma

Hər hansı bir oxuma nəzarət cəmini yoxlamaqla həyata keçirilir.
Əgər nəzarət cəmi uyğun gəlmirsə - oxuma bir neçə dəfə təkrarlanır, düzgün məlumatları oxumağı ümid edərək.

(bu mənası var, Linux NOR Flash-dan oxumağı yaddaşda saxlamaq etmir, yoxlanılıb)

Flash yaddaşına yazma

Məlumatları yazırıq.
Onları oxuyuruq.

Əgər oxunan məlumatlar yazılanlarla uyğun gəlmirsə – sahəni sıfırlarla doldururuq və səhvi bildiririk.

Yeni mikrosxemanın işə hazırlanması

İnkişaf üçün birinci (dəqiq desək, sıfır) səhifəyə versiya 1 olan başlıq yazılır.
Bundan sonra bu səhifəyə başlanğıc konteksti yazılır (UUID avtomatını və standart parametrləri ehtiva edir).

Bütün bunlar olduqdan sonra, flash yaddaş işləməyə hazırdır.

Avtomatın yüklənməsi

Yükləmə zamanı hər səhifənin ilk 8 baytı (başlıq + CRC) oxunur, bilinməyən Magic Number və ya yanlış CRC olan səhifələr nəzərə alınmır.
«Düzgün» səhifələrdən maksimum versiyalı səhifələr seçilir, onlardan ən yüksək nömrəli səhifə götürülür.
İlk qeydi oxuyuruq, CRC-nin düzgünlüyünü və «kontekst» bayrağının mövcudluğunu yoxlayırıq. Əgər hər şey qaydasındadırsa - bu səhifə cari hesab olunur. Əks halda - əvvəlki səhifəyə geri dönürük, «canlı» səhifə tapana qədər.
Və tapılan səhifədə bütün qeydləri oxuyuruq, «kontekst» bayrağı olanları tətbiq edirik.
Zlib lüğətini saxlayırıq (bu, bu səhifəyə əlavə yazmaq üçün lazım olacaq).

Bütün bunlar, yükləmə tamamlandı, kontekst bərpa edildi, işə başlaya bilərik.

Jurnala qeydin əlavə edilməsi

Doğru lüğət ilə qeydi sıxışdırırıq, Z_SYNC_FLUSH-i göstərərək. Sıxılmış qeydin cari səhifəyə sığması üçün yer olduğuna baxırıq.
Əgər sığmırsa (və ya səhifədə CRC xətası olubsa) - yeni səhifə açırıq (aşağıya baxın).
Qeydi və CRC-ni yazırıq. Əgər səhv baş verərsə - yeni səhifə açmağa başlayırıq.

Yeni səhifə

Minimum nömrəyə malik boş səhifəni seçirik (boş olaraq, başlığında yanlış nəzarət cəmi olan və ya cari versiyadan az olan səhifəni hesab edirik). Əgər belə səhifələr yoxdursa - cari versiyaya bərabər olan minimum nömrəli səhifəni seçirik.
Seçilmiş səhifəni erase edirik. Məzmunu 0xff ilə müqayisə edirik. Əgər bir şey düzgün deyilsə - növbəti boş səhifəni alırıq, və s.
Silinmiş səhifəyə başlıq yazırıq, ilkin qeyd kimi cari kontekstin vəziyyətini, sonrakı kimi isə yazılmamış jurnal qeydi (əgər varsa) yazırıq.

Formatın tətbiqi

Mənim fikrimcə, hər hansı bir şəkildə sıxıla bilən informasiya axınlarını (sadə mətn, JSON, MessagePack, CBOR, bəlkə də, protobuf) NOR Flash-da saxlamaq üçün yaxşı bir format alınmışdır.

Əlbəttə, format SLC NOR Flash-a yönəldilib.

Yüksək BER olan daşıyıcılarla istifadə olunmamalıdır, məsələn, NAND və ya MLC NOR ilə. (Belə yaddaşlar bazarda varmı? Yalnız düzəldici kodlarla bağlı işlərdə rast gəlmişəm.).

Həmçinin, öz FTL-si olan cihazlarla, USB flash, SD, MicroSD və s. ilə istifadə olunmamalıdır. (Belə yaddaş üçün mən, hər səhifənin əvvəlinə imza və unik nümunə nömrələri ilə 512 baytlıq səhifə ölçüsü olan bir format yaratmışdım; bəzən "sözsüz" flash-dan sadə ardıcıl oxumaqla bütün məlumatları bərpa etmək mümkün olmuşdu.).

Tapşırıqlara bağlı olaraq, formatı 128 KBit-dən (16 Kb) 1 GBit-ə (128 Mb) qədər flash-larda dəyişməz istifadə etmək olar. İstəsəniz, daha böyük ölçülü çiplərdə də istifadə edə bilərsiniz, yalnız, ehtimal ki, səhifə ölçüsünü düzəltmək lazım olacaq. (Amma burada iqtisadi səmərəlilik məsələsi ortaya çıxır, NOR Flash-ın böyük ölçüsü üçün qiymət məni qane etmir.).

Format kiminsə maraqlı gəlsə və açıq layihədə istifadə etmək istəyirsə - yazın, vaxt ayırmağa çalışaram, kodu əlavə edib github-a qoyaram.

Nəticə

Gördüyümüz kimi, nəticədə format sadə oldu. və hətta darıxdırıcı..

Məqalədə öz baxışımın təkamülünü əks etdirmək çətindir, amma inanın ki, əvvəllər mürəkkəb, məhv edilə bilməyən, hətta nüvə partlayışından sağ çıxan bir şey yaratmaq istəyirdim. Lakin, şüurum (ümid edirəm) nəhayət ki, qalib gəldi və tədricən prioritetlər sadəlik və kompaktlığa dəyişdi.

Belə ola bilərmi ki, mən yanıldım? Bəli, əlbəttə. Mümkün ola bilər ki, məsələn, keyfiyyətsiz çip almışıq. Və ya başqa bir səbəbdən avadanlıq gözləntiləri doğrultmaya bilər.

Bunun üçün planım varmı? Mən düşünürəm ki, məqaləni oxuduqdan sonra planımın olduğu ilə şübhə etmirsiniz. Və hətta bir neçə.

Bir az daha ciddi desək, format eyni anda həm işləyən variant, həm də "sınaq" məqsədilə hazırlanmışdır.

Hazırda masada hər şey normal çalışır, yaxın günlərdə qərar genişlənəcək. (təxminən) bu, yüzlərlə cihazda olacaq, 'müharibə' istismarı zamanı nə olacağını görə bilərik (şükür ki, formatın təhlükəsiz şəkildə uğursuzluqları aşkarlamağa imkan verdiyinə ümid edirəm; beləliklə, tam statistikalar toplamaq mümkün olacaq). Bir neçə ay sonra nəticələr əldə etmək olar. (bəlkə də şanssızlıq olarsa, daha əvvəl).

İstifadənin nəticələrinə əsasən ciddi problemlər aşkar edilərsə və düzəlişlər tələb olunarsa, bunun barədə mütləq yazacağam.

Edebiyat

İstifadə olunan işlərin uzun, sıxıntılı siyahısını tərtib etmək istəmədim, axı, google hər kəsdə var.

Bura qərara aldım ki, mənə xüsusilə maraqlı görünən tapıntıların siyahısını burada saxlayım, lakin tədricən bunlar məqalənin tekstinə daxil oldu və siyahıda yalnız bir maddə qaldı:

1. Araç infgen yazarı zlib. deflate/zlib/gzip arxivlərinin məzmununu anlaşıqlı şəkildə göstərmək qabiliyyətinə malikdir. Əgər deflate (və ya gzip) formatının daxili quruluşunu başa düşmək məcburiyyətində qalsanız — mütləq tövsiyə edirəm.

Mənbə: habr.com