Prehistorya

Öz dizaynımız olan avtomatlar var. Raspberry Pi içərisində və ayrı bir lövhədə bəzi naqillər. Qəpik qəbul edən, veksel qəbul edən, bank terminalı qoşulub... Hər şey öz-özünə yazılmış proqramla idarə olunur. Bütün iş tarixi bir flash sürücüdə (MicroSD) bir jurnala yazılır, daha sonra İnternet vasitəsilə (USB modemdən istifadə etməklə) verilənlər bazasında saxlanılan serverə ötürülür. Satış məlumatları 1c-ə yüklənir, monitorinq üçün sadə veb interfeysi də var və s.

Yəni jurnal həyati əhəmiyyət kəsb edir - mühasibat uçotu (gəlir, satış və s.), monitorinq (hər cür uğursuzluqlar və digər fors-major hallar); Bu, demək olar ki, bu maşın haqqında əlimizdə olan bütün məlumatlardır.

problem

Flash disklər özlərini çox etibarsız cihazlar kimi göstərirlər. Onlar həsəd aparan müntəzəmliklə uğursuzluğa düçar olurlar. Bu, həm maşının dayanmasına, həm də (əgər nədənsə jurnal onlayn olaraq ötürülə bilmədisə) məlumat itkisinə gətirib çıxarır.

Bu, fleş disklərdən istifadənin ilk təcrübəsi deyil, bundan əvvəl jurnalın USB flash sürücülərdə saxlandığı yüzdən çox cihazdan ibarət başqa bir layihə var idi, etibarlılıq problemləri də var idi, bəzən uğursuz olanların sayı. bir ay onlarla idi. SLC yaddaşlı markalı olanlar da daxil olmaqla, müxtəlif fləş sürücüləri sınadıq və bəzi modellər digərlərindən daha etibarlıdır, lakin fləş sürücülərin dəyişdirilməsi problemi kökündən həll etmədi.

Diqqət! Uzun oxu! Əgər sizi “niyə” deyil, yalnız “necə” maraqlandırırsa, düz gedə bilərsiniz Sonda məqalələr.

qərar

Ağla gələn ilk şey budur: MicroSD-dən imtina edin, məsələn, SSD quraşdırın və ondan yükləyin. Nəzəri cəhətdən mümkündür, ehtimal ki, lakin nisbətən bahalı və o qədər də etibarlı deyil (USB-SATA adapteri əlavə olunur; büdcə SSD-lər üçün uğursuzluq statistikası da ürəkaçan deyil).

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

Buna görə də, biz bu seçimə gəldik: MicroSD-dən yükləməni buraxın, lakin onları yalnız oxumaq rejimində istifadə edin və əməliyyat jurnalını (və müəyyən bir aparat parçasına xas olan digər məlumatları - seriya nömrəsi, sensorun kalibrləmələri və s.) başqa yerdə saxlayın. .

Moruq üçün yalnız oxunan FS mövzusu artıq içəridə və xaricdə öyrənilmişdir, mən bu məqalədə tətbiq detalları üzərində dayanmayacağam. (amma maraq varsa, bəlkə bu mövzuda mini məqalə yazacam). Qeyd etmək istədiyim yeganə məqam odur ki, həm şəxsi təcrübədən, həm də bunu artıq həyata keçirənlərin rəylərindən etibarlılıq qazanılır. Bəli, nasazlıqlardan tamamilə qurtulmaq mümkün deyil, lakin onların tezliyini əhəmiyyətli dərəcədə azaltmaq olduqca mümkündür. Kartlar birləşir ki, bu da xidmət işçilərinin dəyişdirilməsini xeyli asanlaşdırır.

Avadanlıqlar

Yaddaş növünün seçimində xüsusi şübhə yox idi - NOR Flash.
Arqumentlər:

• sadə əlaqə (çox vaxt istifadə təcrübəniz olan SPI avtobusu, buna görə də heç bir hardware problemi gözlənilmir);
• gülünc qiymət;
• standart əməliyyat protokolu (tətbiq artıq Linux nüvəsindədir, istəsəniz, üçüncü tərəfi götürə bilərsiniz, bu da mövcuddur və ya hətta özünüzü yaza bilərsiniz, xoşbəxtlikdən hər şey sadədir);
• etibarlılıq və resurs:
  tipik məlumat vərəqindən: məlumatlar 20 il saxlanılır, hər blok üçün 100000 silmə dövrü;
  üçüncü tərəf mənbələrindən: son dərəcə aşağı BER, səhvlərin düzəldilməsi kodlarına ehtiyac olmadığını güman edir (bəzi əsərlər NOR üçün ECC hesab edir, lakin adətən onlar yenə də MLC NOR deməkdir; bu da olur).

Həcm və resurs tələblərini təxmin edək.

Mən məlumatların bir neçə gün ərzində saxlanmasına zəmanət verilməsini istərdim. Bu, hər hansı bir ünsiyyət problemi halında satış tarixinin itirilməməsi üçün lazımdır. Bu müddət ərzində 5 günə diqqət edəcəyik (hətta həftə sonları və bayram günləri nəzərə alınmaqla) problemi həll etmək olar.

Hazırda biz gündə təxminən 100kb log toplayırıq (3-4 min giriş), lakin tədricən bu rəqəm artır - detal artır, yeni hadisələr əlavə olunur. Üstəlik, bəzən partlayışlar olur (bəzi sensorlar, məsələn, yanlış pozitivlərlə spam göndərməyə başlayır). Hər biri 10 bayt olan 100 min qeyd üçün hesablayacağıq - gündə meqabayt.

Ümumilikdə 5 MB təmiz (yaxşı sıxılmış) məlumat çıxır. Onlara daha çox (təxmini hesablama) 1 MB xidmət məlumatı.

Yəni sıxılmadan istifadə etmiriksə 8MB, istifadə ediriksə 4MB çip lazımdır. Bu tip yaddaş üçün olduqca real rəqəmlər.

Mənbəyə gəlincə: bütün yaddaşın hər 5 gündə bir dəfədən çox olmamaqla yenidən yazılacağını planlaşdırsaq, onda 10 illik xidmət müddətində mindən az təkrar yazma dövrü alırıq.
Xatırladım ki, istehsalçı yüz min söz verir.

NOR vs NAND haqqında bir az

Bu gün, əlbəttə ki, NAND yaddaşı daha populyardır, amma mən onu bu layihə üçün istifadə etməzdim: NAND, NOR-dan fərqli olaraq, mütləq səhvlərin düzəldilməsi kodlarından, pis bloklar cədvəlindən və s., həmçinin ayaqlarının istifadəsini tələb edir. NAND çipləri adətən daha çoxdur.

NOR-un çatışmazlıqlarına aşağıdakılar daxildir:

• kiçik həcm (və müvafiq olaraq meqabayt üçün yüksək qiymət);
• aşağı rabitə sürəti (əsasən serial interfeysindən istifadə edildiyinə görə, adətən SPI və ya I2C);
• yavaş silmə (blokun ölçüsündən asılı olaraq, saniyənin bir hissəsindən bir neçə saniyəyə qədər davam edir).

Görünür, bizim üçün kritik bir şey yoxdur, ona görə də davam edirik.

Detallar maraqlıdırsa, mikrosxem seçilmişdir at25df321a (lakin bu əhəmiyyətsizdir, bazarda pinout və komanda sistemində uyğun gələn çoxlu analoqlar var; hətta fərqli istehsalçıdan və/və ya fərqli ölçüdə mikrosxem quraşdırmaq istəsək də, hər şey dəyişdirilmədən işləyəcək. kod).

Mən Linux nüvəsinə quraşdırılmış sürücüdən istifadə edirəm; Raspberry-də, cihaz ağacının üst-üstə düşməsi dəstəyi sayəsində hər şey çox sadədir - tərtib edilmiş örtüyü /boot/overlays-a yerləşdirmək və /boot/config.txt-i bir az dəyişdirmək lazımdır.

Misal dts faylı

Düzünü desəm, səhvsiz yazıldığından ə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-də başqa bir xətt

dtoverlay=at25:spimaxfrequency=50000000

Çipin Raspberry Pi-yə qoşulmasının təsvirini buraxacağam. 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 belə banaldır: mikrosxemin cəmi 8 ayağı var, bunlardan bizə torpaq, güc, SPI (CS, SI, SO, SCK) lazımdır. ); səviyyələr Raspberry Pi ilə eynidir, heç bir əlavə naqil tələb olunmur - sadəcə olaraq göstərilən 6 sancağı birləşdirin.

Problem problemi

Həmişə olduğu kimi, problem bəyanatı bir neçə təkrarlamadan keçir və mənə elə gəlir ki, növbəti birinə keçmək vaxtıdır. Odur ki, gəlin dayanaq, artıq yazılanları bir yerə toplayaq və kölgədə qalan detallara aydınlıq gətirək.

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

Bilməyənlər üçün NOR Flash nədir?

Bu, üç əməliyyatı yerinə yetirə biləcəyiniz uçucu olmayan yaddaşdır:

1. Oxu:
   Ən çox yayılmış oxu: biz ünvanı ötürürük və lazım olan qədər bayt oxuyuruq;
2. Qeyd:
   NOR flash-a yazmaq adi olan kimi görünür, lakin onun bir özəlliyi var: siz yalnız 1-i 0-a dəyişə bilərsiniz, əksinə deyil. Məsələn, yaddaş hüceyrəsində 0x55 varsa, ona 0x0f yazdıqdan sonra 0x05 artıq orada saxlanacaq. (aşağıdakı cədvələ baxın);
3. Silin:
   Əlbəttə ki, əks əməliyyatı edə bilməliyik - 0-ı 1-ə dəyişdirin, silmə əməliyyatı məhz bunun üçündür. İlk ikisindən fərqli olaraq, baytlarla deyil, bloklarla işləyir (seçilmiş çipdə minimum silmə bloku 4kb-dir). Silinmə bütün bloku məhv edir və 0-dan 1-ə dəyişmək üçün yeganə yoldur. Buna görə də, flash yaddaşla işləyərkən siz tez-tez məlumat strukturlarını silmək blokunun sərhədinə uyğunlaşdırmalısınız.
   NOR Flash-da qeyd:

Binar verilənlər

Oldu
01010101

Qeydə alınıb
00001111

Oldu
00000101

Jurnalın özü dəyişən uzunluqlu qeydlər ardıcıllığını təmsil edir. Yazının tipik uzunluğu təxminən 30 baytdır (baxmayaraq ki, uzunluğu bir neçə kilobayt olan qeydlər bəzən olur). Bu halda, biz onlarla sadəcə bayt dəsti kimi işləyirik, lakin əgər maraqlanırsınızsa, qeydlər içərisində CBOR istifadə olunur.

Jurnaldan əlavə, həm yenilənmiş, həm də olmayan bəzi "parametrlər" məlumatlarını saxlamalıyıq: müəyyən bir cihaz identifikatoru, sensor kalibrləmələri, "cihaz müvəqqəti olaraq söndürüldü" bayrağı və s.
Bu məlumat həm də CBOR-da saxlanılan əsas dəyər qeydləri toplusudur. Bizdə bu məlumatların çoxu yoxdur (ən çoxu bir neçə kilobayt) və o, nadir hallarda yenilənir.
Bundan sonra biz bunu kontekst adlandıracağıq.

Bu məqalənin haradan başladığını xatırlasaq, məlumatların etibarlı saxlanmasını və mümkünsə, hətta hardware nasazlıqları/məlumatların pozulması halında da davamlı işləməyi təmin etmək çox vacibdir.

Problemlərin hansı mənbələri hesab edilə bilər?

• Yazma/silmə əməliyyatları zamanı enerjini söndürün. Bu, "ləyinə qarşı hiylə yoxdur" kateqoriyasındandır.
  Məlumat müzakirələr stackexchange-də: flaşla işləyərkən enerji söndürüldükdə, həm silmək (1-ə təyin edilmiş), həm də yazmaq (0-a təyin edilmiş) qeyri-müəyyən davranışa gətirib çıxarır: verilənlər yazıla bilər, qismən yazıla bilər (məsələn, 10 bayt/80 bit köçürdük. , lakin hələ yalnız 45 bit yazıla bilməz), bəzi bitlərin “aralıq” vəziyyətdə olması da mümkündür (oxumaq həm 0, həm də 1-i yarada bilər);
• Fləş yaddaşın özündə səhvlər.
  BER çox aşağı olsa da, sıfıra bərabər ola bilməz;
• Avtobus xətaları
  SPI vasitəsilə ötürülən məlumatlar heç bir şəkildə qorunmur, həm tək bit xətaları, həm də sinxronizasiya xətaları baş verə bilər - bitlərin itirilməsi və ya daxil edilməsi (bu, məlumatların kütləvi təhrifinə səbəb olur);
• Digər səhvlər/glitches
  Koddakı səhvlər, Moruq səhvləri, yadplanetlilərin müdaxiləsi...

Tələbləri tərtib etdim, onların yerinə yetirilməsi, mənim fikrimcə, etibarlılığı təmin etmək üçün zəruridir:

• qeydlər dərhal flash yaddaşa daxil olmalıdır, gecikmiş yazılar nəzərə alınmır; - xəta baş verərsə, o, mümkün qədər tez aşkar edilməli və işlənməlidir; - sistem, mümkünsə, xətaları bərpa etməlidir.
  (hər kəsin qarşılaşdığını düşündüyüm həyatdan "necə olmamalıdır" nümunəsi: təcili rebootdan sonra fayl sistemi "sındırılır" və əməliyyat sistemi açılmır)

İdeyalar, yanaşmalar, düşüncələr

Bu problem haqqında düşünməyə başlayanda beynimdən çoxlu fikirlər keçdi, məsələn:

• məlumatların sıxılmasından istifadə edin;
• ağıllı məlumat strukturlarından istifadə edin, məsələn, qeyd başlıqlarını qeydlərin özündən ayrı saxlayın ki, hər hansı bir qeyddə xəta olarsa, qalanını heç bir problem olmadan oxuya biləsiniz;
• enerji söndürüldükdə qeydin tamamlanmasına nəzarət etmək üçün bit sahələrindən istifadə edin;
• hər şey üçün yoxlama məbləğlərini saxlamaq;
• bəzi növ səs-küyə davamlı kodlaşdırmadan istifadə edin.

Bu ideyaların bəzilərindən istifadə olundu, digərlərindən isə imtina edilməsinə qərar verildi. Gəlin qaydada gedək.

Məlumatların sıxılması

Jurnalda qeyd etdiyimiz hadisələrin özləri olduqca oxşar və təkrarlanır ("5 rubl sikkə atdı", "dəyişiklik etmək üçün düyməni basdı", ...). Buna görə sıxılma kifayət qədər təsirli olmalıdır.

Sıxılma yükü əhəmiyyətsizdir (prosessorumuz kifayət qədər güclüdür, hətta ilk Pi-də 700 MHz tezliyi olan bir nüvə var idi, indiki modellərdə bir gigahertz-dən çox olan bir neçə nüvə var), saxlama ilə mübadilə məzənnəsi aşağıdır (bir neçə saniyədə meqabayt), qeydlərin ölçüsü kiçikdir. Ümumiyyətlə, sıxılma performansa təsir edərsə, bu, yalnız müsbət olacaqdır. (tamamilə tənqidi deyil, sadəcə ifadə edirəm). Üstəlik, bizdə həqiqi quraşdırılmış, lakin adi Linux yoxdur - buna görə də həyata keçirmək çox səy tələb etməməlidir (sadəcə kitabxananı əlaqələndirmək və ondan bir neçə funksiyadan istifadə etmək kifayətdir).

Jurnalın bir hissəsi işləyən cihazdan götürülüb (1.7 MB, 70 min giriş) və əvvəlcə kompüterdə mövcud olan gzip, lz4, lzop, bzip2, xz, zstd istifadə edərək sıxılma qabiliyyəti yoxlanılıb.

• gzip, xz, zstd oxşar nəticələr göstərdi (40Kb).
  Dəbli xz-nin burada gzip və ya zstd səviyyəsində özünü göstərməsinə təəccübləndim;
• standart parametrlərlə lzip bir az daha pis nəticələr verdi;
• lz4 və lzop çox yaxşı nəticələr göstərmədi (150Kb);
• bzip2 təəccüblü dərəcədə yaxşı nəticə göstərdi (18Kb).

Beləliklə, məlumatlar çox yaxşı sıxılır.
Beləliklə (ölümcül qüsurlar tapmasaq) sıxılma olacaq! Sadəcə ona görə ki, eyni flash sürücüyə daha çox məlumat sığa bilər.

Mənfi cəhətləri haqqında düşünək.

Birinci problem: biz artıq razılaşmışıq ki, hər bir qeyd dərhal flasha keçməlidir. Tipik olaraq, arxivçi həftə sonu yazmaq vaxtının gəldiyinə qərar verənə qədər giriş axınından məlumatları toplayır. Biz dərhal sıxılmış məlumat blokunu qəbul etməliyik və onu dəyişkən yaddaşda saxlamalıyıq.

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

1. Yuxarıda müzakirə olunan alqoritmlər əvəzinə lüğət sıxışdırmadan istifadə edərək hər bir qeydi sıxın.
   Tamamilə işlək variantdır, amma xoşuma gəlmir. Sıxılmanın az və ya çox layiqli səviyyəsini təmin etmək üçün lüğət xüsusi məlumatlara "uyğunlaşdırılmalıdır"; hər hansı dəyişiklik sıxılma səviyyəsinin fəlakətli şəkildə aşağı düşməsinə səbəb olacaq. Bəli, problemi lüğətin yeni versiyasını yaratmaqla həll etmək olar, lakin bu, baş ağrısıdır - lüğətin bütün versiyalarını saxlamalı olacağıq; hər girişdə lüğətin hansı versiyası ilə sıxıldığını göstərməliyik...
2. "Klassik" alqoritmlərdən istifadə edərək hər bir qeydi sıxışdırın, lakin digərlərindən asılı olmayaraq.
   Baxılan sıxılma alqoritmləri bu ölçülü (onlarla bayt) qeydlərlə işləmək üçün nəzərdə tutulmamışdır, sıxılma nisbəti aydın şəkildə 1-dən az olacaqdır (yəni sıxılma əvəzinə məlumat həcmini artırmaq);
3. Hər qeyddən sonra FLUSH edin.
   Bir çox sıxılma kitabxanası FLUSH dəstəyinə malikdir. Bu əmrdir (və ya sıxılma prosedurunun parametri), onu aldıqdan sonra arxivçi sıxılmış axın əmələ gətirir ki, onu bərpa etmək üçün istifadə olunsun. bütün artıq qəbul edilmiş sıxılmamış məlumatlar. Belə bir analoq sync fayl sistemlərində və ya commit sql-də.
   Əhəmiyyətli olan odur ki, sonrakı sıxılma əməliyyatları yığılmış lüğətdən istifadə edə biləcək və sıxılma nisbəti əvvəlki versiyada olduğu kimi çox əziyyət çəkməyəcək.

Düşünürəm ki, üçüncü variantı seçdiyim aydındır, gəlin ona daha ətraflı baxaq.

tapıldı əla məqalə zlib-də FLUSH haqqında.

Məqalə əsasında diz testi etdim, səhifə ölçüsü 70Kb olan real cihazdan 60 min log girişi götürdüm (səhifə ölçüsünə daha sonra qayıdacağıq) qəbul:

Xam data
Sıxılma gzip -9 (FLUSH yoxdur)
Z_PARTIAL_FLUSH ilə zlib
Z_SYNC_FLUSH ilə zlib

Həcmi, KB
1692
40
352
604

İlk baxışdan FLUSH-un verdiyi qiymət həddən artıq yüksəkdir, lakin əslində bizim seçimimiz azdır - ya ümumiyyətlə sıxmamaq, ya da FLUSH ilə sıxmaq (və çox effektiv) etmək. Unutmamalıyıq ki, 70 min qeydimiz var, Z_PARTIAL_FLUSH tərəfindən təqdim edilən artıqlıq hər qeyd üçün cəmi 4-5 baytdır. Və sıxılma nisbəti demək olar ki, 5: 1 oldu, bu əla nəticədən daha çoxdur.

Bu sürpriz ola bilər, lakin Z_SYNC_FLUSH əslində FLUSH etmək üçün daha səmərəli bir yoldur

Z_SYNC_FLUSH istifadə edərkən, hər girişin son 4 baytı həmişə 0x00, 0x00, 0xff, 0xff olacaqdır. Əgər biz onları tanıyırıqsa, onda onları saxlamağa ehtiyac yoxdur, buna görə də son ölçü cəmi 324 Kb-dir.

Əlaqələndirdiyim məqalənin izahı var:

Boş məzmunu olan yeni tip 0 bloku əlavə olunur.

Boş məzmunu olan 0 tipli blok aşağıdakılardan ibarətdir:

• üç bitlik blok başlığı;
• 0-dan 7-yə qədər bit sıfıra bərabərdir, bayt hizalanmasına nail olmaq üçün;
• dörd bayt ardıcıllığı 00 00 FF FF.

Asanlıqla gördüyünüz kimi, bu 4 baytdan əvvəlki son blokda 3-dən 10-a qədər sıfır bit var. Bununla belə, təcrübə göstərdi ki, əslində ən azı 10 sıfır bit var.

Belə çıxır ki, belə qısa məlumat blokları adətən (həmişə?) tip 1 blokundan (sabit blok) istifadə edilməklə kodlaşdırılır, bu blok mütləq 7 sıfır bitlə bitir və cəmi 10-17 zəmanətli sıfır bit verir (qalanları isə təxminən 50% ehtimalı ilə sıfır olmalıdır.

Beləliklə, test məlumatlarında 100% hallarda 0x00, 0x00, 0xff, 0xff-dən əvvəl bir sıfır bayt, halların üçdə birindən çoxunda isə iki sıfır bayt var. (bəlkə də fakt budur ki, mən ikili CBOR-dan istifadə edirəm və JSON mətnindən istifadə edərkən 2-dinamik blok tipli bloklar daha çox yayılmışdır, müvafiq olaraq 0x00, 0x00, 0xff, 0xff-dan əvvəl əlavə sıfır bayt olmayan bloklara rast gəlinəcək).

Ümumilikdə, mövcud test məlumatlarından istifadə edərək, 250 Kb-dən az sıxılmış məlumatlara sığdırmaq mümkündür.

Siz bit hoqqası etməklə bir az daha qənaət edə bilərsiniz: hələlik biz blokun sonunda bir neçə sıfır bitin olmasına məhəl qoymuruq, blokun əvvəlindəki bir neçə bit də dəyişmir...
Ancaq sonra dayanmaq üçün iradəli bir qərar verdim, əks halda bu sürətlə öz arxivçimi inkişaf etdirə bilərdim.

Ümumilikdə, test məlumatlarımdan hər yazmağa 3-4 bayt aldım, sıxılma nisbəti 6: 1-dən çox oldu. Düzünü desəm: belə bir nəticə gözləmirdim; mənim fikrimcə, 2:1-dən daha yaxşı bir şey artıq sıxılmanın istifadəsinə haqq qazandıran nəticədir.

Hər şey yaxşıdır, lakin zlib (deflate) hələ də arxaik, layiqli və bir qədər köhnə sıxılma alqoritmidir. Sıxılmamış məlumat axınının son 32Kb-nin lüğət kimi istifadə edilməsi bu gün qəribə görünür (yəni bəzi verilənlər bloku 40Kb əvvəl giriş axınında olana çox bənzəyirsə, o zaman yenidən arxivləşdirilməyə başlayacaq, və əvvəlki hadisəyə istinad etməyəcək). Dəbli müasir arxivçilərdə lüğət ölçüsü çox vaxt kilobaytlarla deyil, meqabaytlarla ölçülür.

Beləliklə, biz arxivçilərlə bağlı mini-tədqiqatımızı davam etdiririk.

Sonra bzip2-ni sınaqdan keçirdik (unutmayın ki, FLUSH olmadan demək olar ki, 100:1 fantastik sıxılma nisbəti göstərdi). Təəssüf ki, FLUSH ilə çox zəif çıxış etdi; sıxılmış məlumatın ölçüsü sıxılmamış məlumatdan daha böyük oldu.

Uğursuzluğun səbəbləri ilə bağlı fərziyyələrim

Libbz2 lüğəti təmizləyən yalnız bir flush variantını təklif edir (zlib-də Z_FULL_FLUSH-un analoqu); bundan sonra hər hansı effektiv sıxılma haqqında söhbət yoxdur.

Və sonuncu sınaqdan keçirilməli olan zstd idi. Parametrlərdən asılı olaraq ya gzip səviyyəsində sıxılır, lakin gzip-dən daha sürətli və ya daha yaxşı.

Təəssüf ki, FLUSH ilə o, çox yaxşı işləmədi: sıxılmış məlumatın ölçüsü təxminən 700 Kb idi.

Я sual verdi layihənin github səhifəsində, əldə edilən nəticələrə yaxın olan sıxılmış məlumatların hər bloku üçün 10 bayta qədər xidmət məlumatına güvənməli olduğunuz cavabını aldım; deflate ilə çatmağın heç bir yolu yoxdur.

Arxivçilər ilə apardığım təcrübələrdə bu nöqtədə dayanmaq qərarına gəldim (xatırlatmaq istəyirəm ki, xz, lzip, lzo, lz4 hətta FLUSH olmadan sınaq mərhələsində də özünü göstərmədi və mən daha ekzotik sıxılma alqoritmlərini nəzərə almadım).

Arxiv problemlərinə qayıdaq.

İkinci (dəyərlə deyil, sıra ilə dedikləri kimi) problem, sıxılmış məlumatların əvvəlki bölmələrə davamlı istinadların olduğu bir axın olmasıdır. Beləliklə, sıxılmış məlumatların bir hissəsi zədələnərsə, biz yalnız sıxılmamış məlumatların əlaqəli blokunu deyil, həm də bütün sonrakıları itiririk.

Bu problemi həll etmək üçün bir yanaşma var:

1. Problemin baş verməsinin qarşısını almaq - sıxılmış məlumatlara artıqlıq əlavə edin, bu da səhvləri müəyyən etməyə və düzəltməyə imkan verəcəkdir; bu haqda sonra danışacağıq;
2. Problem baş verərsə, nəticələri minimuma endir
   Daha əvvəl dedik ki, hər bir məlumat blokunu müstəqil şəkildə sıxışdıra bilərsiniz və problem öz-özünə yox olacaq (bir blokun məlumatlarının zədələnməsi yalnız bu blok üçün məlumatların itirilməsinə səbəb olacaq). Bununla belə, bu, məlumatların sıxılmasının təsirsiz olacağı ekstremal haldır. Əks ekstremal: çipimizin bütün 4MB-ni vahid arxiv kimi istifadə edin, bu bizə əla sıxılma, lakin məlumatların pozulması halında fəlakətli nəticələr verəcəkdir.
   Bəli, etibarlılıq baxımından kompromis lazımdır. Ancaq yadda saxlamalıyıq ki, biz son dərəcə aşağı BER və 20 il elan edilmiş məlumatların saxlanma müddəti ilə qeyri-uçucu yaddaş üçün məlumat saxlama formatını inkişaf etdiririk.

Təcrübələr zamanı mən aşkar etdim ki, sıxılma səviyyəsində az və ya çox nəzərə çarpan itkilər ölçüsü 10 KB-dən az olan sıxılmış məlumat bloklarında başlayır.
Əvvəllər qeyd olundu ki, istifadə olunan yaddaş səhifələnir; “bir səhifə - sıxılmış məlumatların bir bloku” yazışmalarının istifadə edilməməsi üçün heç bir səbəb görmürəm.

Yəni minimum ağlabatan səhifə ölçüsü 16Kb-dir (xidmət məlumatı üçün ehtiyatla). Bununla belə, belə kiçik səhifə ölçüsü maksimum rekord ölçüsünə əhəmiyyətli məhdudiyyətlər qoyur.

Sıxılmış formada bir neçə kilobaytdan böyük qeydləri hələ gözləməsəm də, 32Kb səhifələrdən istifadə etmək qərarına gəldim (bir çip üçün cəmi 128 səhifə).

Xülasə:

• Biz zlib (deflate) istifadə edərək sıxılmış məlumatları saxlayırıq;
• Hər bir giriş üçün biz Z_SYNC_FLUSH;
• Hər sıxılmış qeyd üçün biz arxa baytları kəsirik (məsələn, 0x00, 0x00, 0xff, 0xff); başlıqda neçə baytı kəsdiyimizi göstəririk;
• Biz məlumatları 32 Kb səhifələrdə saxlayırıq; səhifənin içərisində sıxılmış məlumatların vahid axını var; Hər səhifədə yenidən sıxılmaya başlayırıq.

Sıxılma ilə bitirməzdən əvvəl diqqətinizi ona yönəltmək istərdim ki, bizdə yalnız bir qeyd üçün bir neçə bayt sıxılmış məlumat var, buna görə də xidmət məlumatlarını şişirtməmək son dərəcə vacibdir, burada hər bayt sayılır.

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

Dəyişən uzunluqlu qeydlərimiz olduğundan, qeydlərin yerləşdirilməsini/sərhədlərini müəyyən etmək lazımdır.

Mən üç yanaşma bilirəm:

1. Bütün qeydlər davamlı bir axın içində saxlanılır, əvvəlcə uzunluğu ehtiva edən bir qeyd başlığı, sonra isə qeydin özü var.
   Bu təcəssümdə həm başlıqlar, həm də məlumatlar dəyişən uzunluqda ola bilər.
   Əslində, biz hər zaman istifadə olunan tək-tək əlaqəli siyahı alırıq;
2. Başlıqlar və qeydlərin özləri ayrı axınlarda saxlanılır.
   Sabit uzunluqlu başlıqlardan istifadə etməklə, bir başlığın zədələnməsinin digərlərinə təsir etməməsini təmin edirik.
   Bənzər bir yanaşma, məsələn, bir çox fayl sistemlərində istifadə olunur;
3. Qeydlər davamlı axınla saxlanılır, qeyd sərhədi müəyyən bir marker (məlumat blokları daxilində qadağan edilmiş simvol/simvollar ardıcıllığı) ilə müəyyən edilir. Əgər qeydin içərisində marker varsa, o zaman onu hansısa ardıcıllıqla əvəz edirik (ondan qaçırıq).
   Bənzər bir yanaşma, məsələn, PPP protokolunda istifadə olunur.

Mən təsvir edəcəyəm.

Variantları 1:

Burada hər şey çox sadədir: qeydin uzunluğunu bilməklə növbəti başlığın ünvanını hesablaya bilərik. Beləliklə, 0xff (sərbəst sahə) və ya səhifənin sonu ilə dolu bir sahə ilə qarşılaşana qədər başlıqlar arasında hərəkət edirik.

Variantları 2:

Dəyişən qeyd uzunluğuna görə hər səhifəyə neçə qeyd (və buna görə də başlıqlar) lazım olacağını əvvəlcədən deyə bilmərik. Siz başlıqları və məlumatları müxtəlif səhifələr arasında yaya bilərsiniz, lakin mən fərqli yanaşmaya üstünlük verirəm: biz həm başlıqları, həm də məlumatları bir səhifəyə yerləşdiririk, lakin başlıqlar (sabit ölçülü) səhifənin əvvəlindən gəlir və verilənlər (dəyişən uzunluqda) sondan gəlir. Onlar “görüşdükləri” kimi (yeni giriş üçün kifayət qədər boş yer yoxdur), biz bu səhifəni tamamlanmış hesab edirik.

Variantları 3:

Başlıqda məlumatların uzunluğunu və ya yeri ilə bağlı digər məlumatları saxlamağa ehtiyac yoxdur, qeydlərin sərhədlərini göstərən markerlər kifayətdir. Bununla belə, məlumat yazarkən/oxunarkən emal edilməlidir.
Mən 0xff-dən marker kimi istifadə edərdim (silindikdən sonra səhifəni doldurur), buna görə də boş sahə mütləq məlumat kimi qəbul edilməyəcək.

Müqayisə cədvəli:

Seçim 1
Seçim 2
Seçim 3

Səhv tolerantlığı
-
+
+

Kompaktlıq
+
-
+

İcra mürəkkəbliyi
*
**
**

Seçim 1-də ölümcül bir qüsur var: başlıqlardan hər hansı biri zədələnərsə, bütün sonrakı zəncir məhv edilir. Qalan seçimlər hətta kütləvi zədələnmə halında bəzi məlumatları bərpa etməyə imkan verir.
Ancaq burada xatırlamaq yerinə düşər ki, biz məlumatları sıxılmış formada saxlamağa qərar verdik və buna görə də "sınıq" qeyddən sonra səhifədəki bütün məlumatları itiririk, buna görə də cədvəldə mənfi olsa da, biz bunu etmirik. nəzərə alın.

Kompaktlıq:

• birinci variantda başlıqda yalnız uzunluğu saxlamalıyıq, əgər dəyişən uzunluqlu tam ədədlərdən istifadə etsək, onda əksər hallarda bir baytla əldə edə bilərik;
• ikinci seçimdə başlanğıc ünvanını və uzunluğu saxlamalıyıq; qeyd sabit ölçüdə olmalıdır, mən hər qeyd üçün 4 bayt hesab edirəm (ofset üçün iki bayt və uzunluq üçün iki bayt);
• üçüncü seçimə qeydin başlandığını göstərmək üçün yalnız bir simvol lazımdır, üstəlik qeydin özü qorunma səbəbindən 1-2% artacaq. Ümumiyyətlə, birinci seçimlə təxminən paritet.

Əvvəlcə ikinci variantı əsas hesab etdim (hətta həyata keçirilməsini də yazdım). Yalnız nəhayət sıxılmadan istifadə etmək qərarına gələndə ondan imtina etdim.

Ola bilsin ki, nə vaxtsa yenə də oxşar variantdan istifadə edəcəyəm. Məsələn, mən Yer və Mars arasında səyahət edən bir gəmi üçün məlumatların saxlanması ilə məşğul olmalı olsam, etibarlılıq, kosmik radiasiya, ... üçün tamamilə fərqli tələblər olacaq.

Üçüncü seçimə gəlincə: Mən ona iki ulduz verdim ki, həyata keçirməyin çətinliyi, sadəcə olaraq, ekranlaşdırma ilə qarışmağı, prosesdə uzunluğu dəyişdirməyi və s. sevmirəm. Bəli, bəlkə qərəzliyəm, amma kodu yazmalı olacağam - niyə özünüzü bəyənmədiyiniz bir şeyi etməyə məcbur edəsiniz.

Xülasə: Səmərəlilik və icra asanlığı səbəbindən "uzunluğu olan başlıq - dəyişən uzunluqlu məlumatlar" zəncirləri şəklində saxlama variantını seçirik.

Yazı Əməliyyatlarının Müvəffəqiyyətinə Nəzarət etmək üçün Bit Sahələrindən İstifadə

Fikrimi haradan aldığımı indi xatırlamıram, amma belə görünür:
Hər bir giriş üçün bayraqları saxlamaq üçün bir neçə bit ayırırıq.
Daha əvvəl dediyimiz kimi, sildikdən sonra bütün bitlər 1-lərlə doldurulur və biz 1-i 0-a dəyişə bilərik, lakin əksinə deyil. Beləliklə, “bayraq qoyulmayıb” üçün 1-dən, “bayraq qoyulub” üçün isə 0-dan istifadə edirik.

Dəyişən uzunluqlu qeydi flaşa yerləşdirmək belə görünə bilər:

1. “Uzunluq qeydi başladı” bayrağını təyin edin;
2. Uzunluğu qeyd edin;
3. “Məlumatların qeydiyyatı başladı” bayrağını təyin edin;
4. Biz məlumatları qeyd edirik;
5. “Qeydiyyat bitdi” bayrağını təyin edin.

Bundan əlavə, cəmi 4 bitlik bayraq üçün "xəta baş verdi" bayrağımız olacaq.

Bu halda, iki sabit vəziyyətimiz var "1111" - qeyd başlamadı və "1000" - qeyd uğurlu oldu; qeyd prosesinin gözlənilmədən kəsilməsi halında biz aralıq vəziyyətləri alacağıq, sonra onları aşkar edib emal edə bilərik.

Yanaşma maraqlıdır, lakin o, yalnız elektrik enerjisinin qəfil kəsilməsi və oxşar nasazlıqlardan qoruyur, bu, əlbəttə ki, vacibdir, lakin bu, mümkün uğursuzluqların yeganə (və ya hətta əsas) səbəbi deyil.

Xülasə: Yaxşı bir həll axtarışına davam edək.

Yoxlama məbləğləri

Yoxlama məbləğləri həmçinin (ağlabatan ehtimalla) yazılmalı olanı oxuduğumuza əmin olmağa imkan verir. Və yuxarıda müzakirə olunan bit sahələrindən fərqli olaraq, onlar həmişə işləyirlər.

Yuxarıda müzakirə etdiyimiz problemlərin potensial mənbələrinin siyahısını nəzərdən keçirsək, yoxlama cəmi mənşəyindən asılı olmayaraq səhvi tanıya bilər. (bəlkə, zərərli əcnəbilər istisna olmaqla - onlar da yoxlama məbləğini saxtalaşdıra bilərlər).

Beləliklə, əgər məqsədimiz məlumatların bütöv olduğunu yoxlamaqdırsa, yoxlama məbləğləri əla fikirdir.

Yoxlama məbləğinin hesablanması üçün alqoritm seçimi heç bir sual yaratmadı - CRC. Bir tərəfdən, riyazi xüsusiyyətlər müəyyən növ səhvləri 100% tutmağa imkan verir; digər tərəfdən, təsadüfi məlumatlarda bu alqoritm adətən nəzəri hədddən çox olmayan toqquşma ehtimalını göstərir. . O, ən sürətli alqoritm olmaya bilər, nə də toqquşmaların sayı baxımından həmişə minimum deyil, lakin çox vacib keyfiyyətə malikdir: qarşılaşdığım sınaqlarda onun açıq şəkildə uğursuz olduğu nümunələr yox idi. Bu vəziyyətdə sabitlik əsas keyfiyyətdir.

Həcmli tədqiqat nümunəsi: 1 hissəsi, 2 hissəsi (narod.ru-ya keçidlər, üzr istəyirik).

Bununla belə, yoxlama məbləğinin seçilməsi tapşırığı tamamlanmayıb; CRC yoxlama məbləğlərinin bütün ailəsidir. Uzunluğa qərar verməlisiniz və sonra bir polinom seçin.

Yoxlama məbləğinin uzunluğunu seçmək ilk baxışdan göründüyü qədər sadə bir sual deyil.

İcazə verin təsvir edim:
Gəlin hər baytda xəta olma ehtimalımız olsun və ideal yoxlama cəmi, gəlin milyon qeydə düşən səhvlərin orta sayını hesablayaq:

Məlumat, bayt
Yoxlama məbləği, bayt
Aşkar edilməmiş səhvlər
Yanlış səhv aşkarlamaları
Ümumi yanlış pozitivlər

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əlumatların uzunluğundan asılı olaraq, minimum səhv müsbət ilə yoxlama məbləğinin uzunluğunu seçin - və hiylə çantadadır.

Bununla belə, qısa yoxlama məbləğləri ilə bağlı problem yaranır: onlar tək bit səhvləri aşkar etməkdə yaxşı olsalar da, kifayət qədər yüksək ehtimalla tamamilə təsadüfi məlumatları doğru kimi qəbul edə bilərlər. Artıq Habré-ni təsvir edən bir məqalə var idi real həyatda problem.

Buna görə də, təsadüfi yoxlama cəmini demək olar ki, qeyri-mümkün etmək üçün uzunluğu 32 bit və ya daha uzun olan yoxlama məbləğlərindən istifadə etməlisiniz. (64 bitdən çox uzunluqlar üçün adətən kriptoqrafik hash funksiyalarından istifadə olunur).

Əvvəllər yazmağıma baxmayaraq, hər vasitə ilə yerə qənaət etmək lazımdır, biz yenə də 32 bitlik yoxlama məbləğindən istifadə edəcəyik (16 bit kifayət deyil, toqquşma ehtimalı 0.01% -dən çoxdur; və 24 bit, çünki onlar deyin, nə burada, nə də orada) .

Burada bir etiraz yarana bilər: indi birdən 4 bayt vermək üçün sıxılma seçərkən hər baytı saxladıqmı? Yoxlama məbləğini sıxmamaq və ya əlavə etməmək daha yaxşı olmazdımı? Əlbəttə ki, yox, sıxılma yoxdur demək deyil, bizim dürüstlüyün yoxlanılmasına ehtiyacımız yoxdur.

Polinom seçərkən biz təkəri yenidən kəşf etməyəcəyik, lakin indi məşhur olan CRC-32C-ni götürəcəyik.
Bu kod 6 bayta qədər paketlərdə 22 bit səhvləri (bəlkə də bizim üçün ən ümumi haldır), 4 bayta qədər paketlərdə 655 bit xətaları (bizim üçün də ümumi hal), paketlərdə 2 və ya hər hansı tək sayda bit səhvini aşkar edir. istənilən ağlabatan uzunluqda.

Kimsə təfərrüatları ilə maraqlanırsa

Vikipediya məqaləsi CRC haqqında.

Kod parametrləri crc-32c haqqında Koopman veb saytı — bəlkə də planetin aparıcı CRC mütəxəssisi.

В onun məqaləsi yoxdur başqa bir maraqlı kod, bu, bizə uyğun olan paket uzunluqları üçün bir qədər daha yaxşı parametrlər təqdim edir, lakin fərqi əhəmiyyətli hesab etmədim və standart və yaxşı araşdırılmış kodun əvəzinə xüsusi kodu seçmək üçün kifayət qədər bacarıqlı idim.

Həmçinin, məlumatlarımız sıxıldığı üçün sual yaranır: sıxılmış və ya sıxılmamış məlumatların yoxlama məbləğini hesablamalıyıq?

Sıxılmamış məlumatların yoxlama məbləğinin hesablanması lehinə arqumentlər:

• Biz son nəticədə məlumatların saxlanmasının təhlükəsizliyini yoxlamaq məcburiyyətindəyik - ona görə də biz onu birbaşa yoxlayırıq (eyni zamanda sıxılma/dekompressiyanın həyata keçirilməsində mümkün səhvlər, yaddaşın pozulması nəticəsində yaranan zədələr və s. yoxlanılacaq);
• Zlib-də deflasiya alqoritmi kifayət qədər yetkin icraya malikdir və olmamalıdır "əyri" giriş məlumatları ilə düşür; üstəlik, o, tez-tez giriş axınındakı səhvləri müstəqil olaraq aşkar edə bilir, səhvin aşkar edilməməsinin ümumi ehtimalını azaldır (qısa bir qeyddə bir biti çevirməklə bir sınaq keçirdi, zlib bir səhv aşkar etdi halların təxminən üçdə birində).

Sıxılmamış məlumatların yoxlama məbləğinin hesablanmasına qarşı arqumentlər:

• CRC xüsusi olaraq flaş yaddaşa xas olan bir neçə bit xətaları üçün “uyğunlaşdırılıb” (sıxılmış axındakı bir az səhv çıxış axınında kütləvi dəyişikliyə səbəb ola bilər ki, bunun əsasında sırf nəzəri olaraq toqquşmanı “tuta” bilərik);
• Potensial pozulmuş məlumatları dekompressora ötürmək fikrini həqiqətən sevmirəm, Kim bilirnecə reaksiya verəcək.

Bu layihədə mən sıxılmamış məlumatların yoxlama məbləğini saxlamaq üçün ümumi qəbul edilmiş təcrübədən yayınmağa qərar verdim.

Xülasə: Biz CRC-32C-dən istifadə edirik, yoxlama məbləğini flaş üçün yazıldıqları formada (sıxılmadan sonra) məlumatlardan hesablayırıq.

Artıqlıq

Lazımsız kodlaşdırmanın istifadəsi, əlbəttə ki, məlumat itkisini aradan qaldırmır, lakin o, bərpa olunmayan məlumat itkisi ehtimalını əhəmiyyətli dərəcədə azalda bilər (çox vaxt bir çox miqyasda).

Səhvləri düzəltmək üçün müxtəlif növ ehtiyatlardan istifadə edə bilərik.
Hamming kodları tək bit səhvlərini düzəldə bilər, Reed-Solomon simvol kodları, yoxlama məbləğləri ilə birləşdirilmiş məlumatların çoxsaylı nüsxələri və ya RAID-6 kimi kodlaşdırmalar hətta kütləvi korrupsiya halında belə məlumatların bərpasına kömək edə bilər.
Əvvəlcə səhvlərə davamlı kodlaşdırmanın geniş tətbiqinə sadiq idim, lakin sonra başa düşdüm ki, əvvəlcə özümüzü hansı səhvlərdən qorumaq istədiyimiz barədə təsəvvürümüz olmalıdır, sonra isə kodlaşdırmanı seçməliyik.

Daha əvvəl dedik ki, səhvləri mümkün qədər tez tutmaq lazımdır. Hansı məqamlarda səhvlərlə qarşılaşa bilərik?

1. Yarımçıq çəkiliş (yazı zamanı nədənsə enerji söndürüldü, Moruq dondu, ...)
   Təəssüf ki, belə bir səhv baş verdikdə, yalnız etibarsız qeydlərə məhəl qoymamaq və məlumatların itirilmiş hesab edilməsi qalır;
2. Yazma xətaları (nədənsə flash yaddaşa yazılanlar yazılanlar deyildi)
   Qeydiyyatdan dərhal sonra test oxunması etsək, bu cür səhvləri dərhal aşkar edə bilərik;
3. Saxlama zamanı yaddaşdakı məlumatların təhrif edilməsi;
4. Oxuma səhvləri
   Onu düzəltmək üçün yoxlama məbləği uyğun gəlmirsə, oxunu bir neçə dəfə təkrarlamaq kifayətdir.

Yəni, yalnız üçüncü növ səhvlər (saxlama zamanı məlumatların kortəbii pozulması) səhvlərə davamlı kodlaşdırma olmadan düzəldilə bilməz. Görünür, bu cür səhvlər hələ də çox azdır.

Xülasə: lazımsız kodlaşdırmadan imtina etmək qərara alındı, lakin əməliyyat bu qərarın səhvini göstərirsə, problemin nəzərdən keçirilməsinə qayıdın (uğursuzluqlar haqqında artıq yığılmış statistika ilə, bu kodlaşdırmanın optimal növünü seçməyə imkan verəcəkdir).

Digər

Təbii ki, məqalənin formatı formatda hər biti əsaslandırmağa imkan vermir (və gücüm artıq tükəndi), buna görə də əvvəllər toxunulmamış bəzi məqamları qısaca nəzərdən keçirəcəyəm.

• Bütün səhifələrin “bərabər” edilməsi qərara alındı.
  Yəni, metadata, ayrı-ayrı mövzular və s.-li xüsusi səhifələr olmayacaq, bunun əvəzinə bütün səhifələri növbə ilə yenidən yazan tək başlıq olacaq.
  Bu, səhifələrin bərabər aşınmasını təmin edir, heç bir uğursuzluq nöqtəsi yoxdur və mən bunu bəyənirəm;
• Formatın versiyasını təmin etmək vacibdir.
  Başlıqda versiya nömrəsi olmayan format pisdir!
  Səhifənin başlığına müəyyən bir Sehrli Nömrə (imza) olan bir sahə əlavə etmək kifayətdir ki, bu da istifadə olunan formatın versiyasını göstərəcəkdir. (Praktikada onlardan hətta onlarla olacağını düşünmürəm);
• Əksər hallarda onu 1 bayt uzunluğunda etməyə çalışaraq qeydlər üçün dəyişən uzunluqlu başlıqdan istifadə edin (bunlardan çoxu var);
• Başlığın uzunluğunu və sıxılmış qeydin kəsilmiş hissəsinin uzunluğunu kodlaşdırmaq üçün dəyişən uzunluqlu ikili kodlardan istifadə edin.

Çox kömək etdi onlayn generator Huffman kodları. Cəmi bir neçə dəqiqə ərzində biz tələb olunan dəyişən uzunluqlu kodları seçə bildik.

Məlumat saxlama formatının təsviri

Bayt sırası

Bir baytdan böyük sahələr big-endian formatında (şəbəkə bayt sırası) saxlanılır, yəni 0x1234 0x12, 0x34 kimi yazılır.

Səhifələmə

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

Standart səhifə ölçüsü 32Kb-dir, lakin yaddaş çipinin ümumi ölçüsünün 1/4-dən çox deyil (4MB çip üçün 128 səhifə alınır).

Hər bir səhifə məlumatları digərlərindən asılı olmayaraq saxlayır (yəni bir səhifədəki məlumatlar digər səhifədəki məlumatlara istinad etmir).

Bütün səhifələr natural qaydada (ünvanların artan sırası ilə) 0 rəqəmindən başlayaraq nömrələnir (sıfır səhifə 0 ünvanından başlayır, birinci səhifə 32Kb-dan başlayır, ikinci səhifə 64Kb-dan başlayır və s.)

Yaddaş çipi tsiklik bufer (ring bufer) kimi istifadə olunur, yəni əvvəlcə yazı 0 nömrəli səhifəyə, sonra 1 nömrəyə, ..., sonuncu səhifəni doldurduqda yeni dövr başlayır və sıfır səhifədən qeyd davam edir. .

Səhifənin içərisində

Səhifənin əvvəlində 4 baytlıq səhifə başlığı, sonra başlıq yoxlama məbləği (CRC-32C), sonra qeydlər “başlıq, məlumat, yoxlama cəmi” formatında saxlanılır.

Səhifənin başlığı (diaqramda çirkli yaşıl) aşağıdakılardan ibarətdir:

• iki baytlıq Magic Number sahəsi (həmçinin format versiyasının işarəsi)
  formatın cari versiyası üçün bu kimi hesablanır 0xed00 ⊕ номер страницы;
• iki baytlıq sayğac "Səhifə versiyası" (yaddaşın yenidən yazma dövrünün nömrəsi).

Səhifədəki qeydlər sıxılmış formada saxlanılır (deflasiya alqoritmi istifadə olunur). Bir səhifədəki bütün qeydlər bir mövzuda sıxılır (ümumi lüğət istifadə olunur) və hər yeni səhifədə sıxılma yenidən başlayır. Yəni, hər hansı bir qeydi açmaq üçün bu səhifədəki bütün əvvəlki qeydlər (və yalnız bu) tələb olunur.

Hər bir qeyd Z_SYNC_FLUSH bayrağı ilə sıxılacaq və sıxılmış axının sonunda 4 bayt 0x00, 0x00, 0xff, 0xff, ola bilsin ki, bir və ya iki sıfır baytdan əvvəl olacaq.
Fləş yaddaşa yazarkən bu ardıcıllığı (4, 5 və ya 6 bayt uzunluğunda) atırıq.

Qeyd başlığı 1, 2 və ya 3 baytdır:

• qeydin növünü göstərən bir bit (T): 0 - kontekst, 1 - log;
• 1-dən 7 bitə qədər dəyişən uzunluq sahəsi (S), başlığın uzunluğunu və dekompressiya üçün qeydə əlavə edilməli olan “quyruq”u müəyyən edir;
• rekord uzunluq (L).

S dəyər cədvəli:

S
Başlıq 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)

Təsvir etməyə çalışdım, bunun nə qədər aydın olduğunu bilmirəm:

Burada sarı T sahəsini, ağ S sahəsini, yaşıl L (sıxılmış verilənlərin baytlarda uzunluğu), mavi sıxılmış məlumatları, qırmızı sıxılmış məlumatların flash yaddaşa yazılmayan son baytlarını göstərir.

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

Hər qeyddən sonra CRC-32C yoxlama məbləği saxlanılır, burada əvvəlki yoxlama məbləğinin ters çevrilmiş dəyəri ilkin dəyər (init) kimi istifadə olunur.

CRC "müddət" xüsusiyyətinə malikdir, aşağıdakı düstur işləyir (prosesdə əlavə və ya mənfi bit inversiya): .
Yəni, əslində biz bu səhifədəki bütün əvvəlki bayt başlıqların və məlumatların CRC-ni hesablayırıq.

Yoxlama məbləğindən birbaşa sonra gələn qeydin başlığıdır.

Başlıq elə qurulmuşdur ki, onun ilk baytı həmişə 0x00 və 0xff-dən fərqli olsun (əgər başlığın ilk baytı əvəzinə 0xff ilə qarşılaşırıqsa, bu, istifadə olunmayan sahədir; 0x00 xəta haqqında siqnal verir).

Nümunə alqoritmlər

Flash yaddaşdan oxuma

İstənilən oxu yoxlama yoxlaması ilə birlikdə gəlir.
Yoxlama məbləği uyğun gəlmirsə, düzgün məlumatları oxumaq ümidi ilə oxuma bir neçə dəfə təkrarlanır.

(bu məntiqlidir, Linux NOR Flash-dan oxunuşları keş saxlamır, sınaqdan keçirilmişdir)

Fləş yaddaşa yazın

Məlumatları qeyd edirik.
Gəlin onları oxuyaq.

Əgər oxunan məlumatlar yazılı məlumatlara uyğun gəlmirsə, biz sahəni sıfırlarla doldururuq və xəta haqqında siqnal veririk.

Yeni mikrosxemin işləməyə hazırlanması

İnisializasiya üçün birinci (daha doğrusu sıfır) səhifəyə 1-ci versiya ilə başlıq yazılır.
Bundan sonra, ilkin kontekst bu səhifəyə yazılır (maşının UUID-sini və standart parametrləri ehtiva edir).

Budur, flash yaddaş istifadəyə hazırdır.

Maşın yüklənir

Yükləyərkən hər səhifənin ilk 8 baytı (başlıq + CRC) oxunur, naməlum Magic Number və ya səhv CRC olan səhifələr nəzərə alınmır.
“Düzgün” səhifələrdən maksimum versiyaya malik səhifələr seçilir və onlardan ən çox sayı olan səhifələr götürülür.
İlk qeyd oxunur, CRC-nin düzgünlüyü və “kontekst” bayrağının olması yoxlanılır. Hər şey qaydasındadırsa, bu səhifə cari hesab olunur. Əks təqdirdə, "canlı" səhifə tapana qədər əvvəlkinə qayıdırıq.
və tapılan səhifədə biz “kontekst” bayrağı ilə istifadə etdiyimiz bütün qeydləri oxuduq.
Zlib lüğətini yadda saxlayın (bu səhifəyə əlavə etmək üçün lazım olacaq).

Budur, yükləmə tamamlandı, kontekst bərpa edildi, işləyə bilərsiniz.

Jurnal Girişinin əlavə edilməsi

Biz qeydi Z_SYNC_FLUSH təyin edərək düzgün lüğətlə sıxırıq.Sıxılmış qeydin cari səhifəyə uyğun olub-olmadığını görürük.
Uyğun gəlmirsə (və ya səhifədə CRC xətaları olubsa), yeni səhifəyə başlayın (aşağıya baxın).
Biz qeyd və CRC yazırıq. Səhv baş verərsə, yeni səhifəyə başlayın.

Yeni səhifə

Biz minimum sayda pulsuz səhifə seçirik (biz pulsuz səhifəni başlıqda səhv yoxlama məbləği olan və ya caridən daha az versiyaya malik səhifə hesab edirik). Əgər belə səhifələr yoxdursa, cari ilə bərabər versiyaya malik olanlar arasından minimum sayda səhifəni seçin.
Seçilmiş səhifəni silirik. Məzmunu 0xff ilə yoxlayırıq. Bir şey səhv olarsa, növbəti pulsuz səhifəni götürün və s.
Silinmiş səhifəyə başlıq yazırıq, ilk giriş kontekstin cari vəziyyəti, sonrakı yazılmamış log girişidir (əgər varsa).

Format tətbiqi

Fikrimcə, NOR Flash-da az və ya çox sıxıla bilən məlumat axınlarını (düz mətn, JSON, MessagePack, CBOR, bəlkə də protobuf) saxlamaq üçün yaxşı format olduğu ortaya çıxdı.

Əlbəttə ki, format SLC NOR Flash üçün “uyğunlaşdırılıb”.

O, NAND və ya MLC NOR kimi yüksək BER media ilə istifadə edilməməlidir (belə yaddaş hətta satışda da varmı? Mən onun yalnız düzəliş kodları üzərində işlərdə qeyd edildiyini görmüşəm).

Üstəlik, öz FTL-si olan cihazlarla istifadə edilməməlidir: USB flash, SD, MicroSD və s (belə yaddaş üçün səhifə ölçüsü 512 bayt olan bir format yaratdım, hər səhifənin əvvəlində bir imza və unikal qeyd nömrələri - bəzən sadə ardıcıl oxumaqla bütün məlumatları "səhv" flash sürücüdən bərpa etmək mümkün idi).

Tapşırıqlardan asılı olaraq, format 128Kbit (16Kb) ilə 1Gbit (128MB) arasında olan fleş disklərdə dəyişdirilmədən istifadə edilə bilər. İstəyirsinizsə, onu daha böyük çiplərdə istifadə edə bilərsiniz, lakin yəqin ki, səhifə ölçüsünü tənzimləməlisiniz (Ancaq burada iqtisadi məqsədəuyğunluq sualı artıq ortaya çıxır; böyük həcmli NOR Flash üçün qiymət ürəkaçan deyil).

Kimsə formatı maraqlı hesab edirsə və onu açıq layihədə istifadə etmək istəyirsə, yazın, mən vaxt tapıb kodu cilalayıb github-da yerləşdirməyə çalışacağam.

Nəticə

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

Fikrimin təkamülünü bir məqalədə əks etdirmək çətindir, amma inanın: əvvəlcə mən mürəkkəb, sarsılmaz, yaxınlıqdakı nüvə partlayışından belə sağ çıxa bilən bir şey yaratmaq istəyirdim. Bununla belə, ağıl (ümid edirəm) yenə də qalib gəldi və tədricən prioritetlər sadəliyə və yığcamlığa doğru dəyişdi.

Səhv etdiyim ola bilərmi? Bəli əminəm. Məsələn, aşağı keyfiyyətli mikrosxemlərin bir dəstini aldığımız məlum ola bilər. Və ya başqa bir səbəbdən avadanlıq etibarlılıq gözləntilərinə cavab verməyəcək.

Bunun üçün bir planım varmı? Düşünürəm ki, məqaləni oxuduqdan sonra bir planın olduğuna şübhə etmirsiniz. Və hətta tək deyil.

Bir az daha ciddi qeyddə, format həm iş variantı, həm də "sınaq balonu" kimi hazırlanmışdır.

Hal-hazırda masada hər şey yaxşı işləyir, sözün əsl mənasında, bu gün həll yerləşdiriləcək (təxminən) yüzlərlə cihazda "döyüş" əməliyyatında nə baş verdiyini görək (xoşbəxtlikdən, ümid edirəm ki, format uğursuzluqları etibarlı şəkildə aşkar etməyə imkan verir; tam statistika toplaya bilərsiniz). Bir neçə aydan sonra nəticə çıxarmaq mümkün olacaq (və əgər bəxtiniz gətirmirsə, hətta əvvəllər).

Əgər istifadənin nəticələrinə əsasən ciddi problemlər aşkar edilərsə və təkmilləşdirmə tələb olunarsa, o zaman bu barədə mütləq yazacağam.

Ədəbiyyat

İstifadə olunmuş işlərin uzun yorucu bir siyahısını tərtib etmək istəmədim; axı, hər kəsin Google-u var.

Burada mənə xüsusilə maraqlı görünən tapıntıların siyahısını tərk etmək qərarına gəldim, lakin tədricən onlar birbaşa məqalənin mətninə köçdü və bir maddə siyahıda qaldı:

1. Kommunal infgen müəllifdən zlib. deflate/zlib/gzip arxivlərinin məzmununu aydın şəkildə göstərə bilər. Əgər siz deflate (və ya gzip) formatının daxili strukturu ilə məşğul olmalısınızsa, mən bunu çox tövsiyə edirəm.

Mənbə: www.habr.com