sa naunang kasaysayan

Adunay mga vending machine sa among kaugalingong disenyo. Sa sulod sa Raspberry Pi ug pipila ka mga kable sa usa ka bulag nga board. Ang usa ka tigdawat sa sensilyo, usa ka tigdawat sa bill, usa ka terminal sa bangko ang konektado... Ang tanan kontrolado sa usa ka programa nga gisulat sa kaugalingon. Ang tibuok nga kasaysayan sa trabaho gisulat sa usa ka log sa usa ka flash drive (MicroSD), nga dayon gipasa pinaagi sa Internet (gamit ang USB modem) ngadto sa server, diin kini gitipigan sa usa ka database. Ang kasayuran sa pagbaligya gikarga sa 1c, adunay usa usab ka yano nga interface sa web alang sa pag-monitor, ug uban pa.

Sa ato pa, ang journal hinungdanon - alang sa accounting (kita, halin, ug uban pa), pag-monitor (tanang klase sa mga kapakyasan ug uban pang mga kahimtang sa force majeure); Kini, tingali isulti sa usa, mao ang tanan nga kasayuran nga naa kanamo bahin sa kini nga makina.

problema

Gipakita sa mga flash drive ang ilang kaugalingon nga dili kasaligan nga mga aparato. Napakyas sila uban ang makanunayon nga makanunayon. Kini modala ngadto sa duha nga machine downtime ug (kon sa pipila ka rason ang log dili mabalhin online) ngadto sa data pagkawala.

Dili kini ang una nga kasinatian sa paggamit sa mga flash drive, sa wala pa kini adunay lain nga proyekto nga adunay kapin sa usa ka gatos nga mga aparato, diin ang magasin gitipigan sa mga USB flash drive, adunay usab mga problema sa pagkakasaligan, usahay ang gidaghanon sa mga napakyas sa. ang usa ka bulan diha sa mga dosena. Gisulayan namon ang lainlaing mga flash drive, lakip ang mga branded nga adunay memorya sa SLC, ug ang pipila nga mga modelo mas kasaligan kaysa sa uban, apan ang pag-ilis sa mga flash drive wala gyud makasulbad sa problema.

Pasidaan Taas nga pagbasa! Kung dili ka interesado sa "ngano", apan sa "unsaon" lamang, mahimo kang diretso Sa katapusan mga artikulo.

desisyon

Ang una nga butang nga naa sa hunahuna mao ang: biyai ang MicroSD, pag-install, pananglitan, usa ka SSD, ug pag-boot gikan niini. Sa teoriya nga posible, tingali, apan medyo mahal, ug dili kaayo kasaligan (usa ka USB-SATA adapter gidugang; ang mga istatistika sa kapakyasan alang sa mga SSD sa badyet dili usab makapadasig).

Ang USB HDD dili usab ingon usa ka labi ka madanihon nga solusyon.

Busa, miabut kami niini nga kapilian: biyai ang pag-booting gikan sa MicroSD, apan gamita kini sa read-only mode, ug tipigi ang log sa operasyon (ug uban pang impormasyon nga talagsaon sa usa ka partikular nga piraso sa hardware - serial number, sensor calibrations, ug uban pa) sa laing dapit. .

Ang hilisgutan sa read-only FS alang sa mga raspberry gitun-an na sa sulod ug gawas, dili ako maghisgot sa mga detalye sa pagpatuman niini nga artikulo (apan kung adunay interes, tingali magsulat ako usa ka mini nga artikulo bahin niini nga hilisgutan). Ang bugtong punto nga gusto nakong timan-an mao nga gikan sa personal nga kasinatian ug gikan sa mga pagrepaso sa mga nagpatuman na niini, adunay usa ka ganansya sa pagkakasaligan. Oo, imposible nga hingpit nga makuha ang mga pagkaguba, apan posible nga makunhuran ang ilang frequency. Ug ang mga kard nagkahiusa, nga naghimo sa pagpuli nga labi kadali alang sa mga kawani sa serbisyo.

Hardware

Walay partikular nga pagduhaduha mahitungod sa pagpili sa matang sa panumduman - NOR Flash.
Mga argumento:

yano nga koneksyon (kasagaran ang SPI bus, nga nasinati na nimo nga gigamit, mao nga wala’y nakita nga mga problema sa hardware);
kataw-anan nga presyo;
standard operating protocol (ang pagpatuman naa na sa Linux kernel, kung gusto nimo, mahimo nimong kuhaon ang ikatulo nga partido, nga anaa usab, o bisan pagsulat sa imong kaugalingon, maayo na lang ang tanan yano);
kasaligan ug kapanguhaan:
gikan sa usa ka tipikal nga datasheet: ang data gitipigan sulod sa 20 ka tuig, 100000 ka erase cycle alang sa matag block;
gikan sa ikatulong partido nga mga tinubdan: hilabihan ka ubos nga BER, postulates dili kinahanglan alang sa sayop correction code (gikonsiderar sa ubang mga buhat ang ECC para sa NOR, apan kasagarang nagpasabot gihapon sila sa MLC NOR; mahitabo usab kini).

Atong banabanaon ang mga kinahanglanon alang sa gidaghanon ug kahinguhaan.

Gusto nako nga ang datos masiguro nga maluwas sa daghang mga adlaw. Kinahanglanon kini aron sa kaso sa bisan unsang mga problema sa komunikasyon, ang kasaysayan sa pagbaligya dili mawala. Magpokus kami sa 5 ka adlaw, sa kini nga panahon (bisan pag-isip sa katapusan sa semana ug mga holiday) masulbad ang problema.

Kami karon nangolekta og mga 100kb nga mga troso kada adlaw (3-4 ka libo nga mga entries), apan sa hinay-hinay kini nga numero nagkadako - ang detalye nagdugang, ang mga bag-ong panghitabo gidugang. Dugang pa, usahay adunay mga pagbuto (ang ubang mga sensor nagsugod sa pag-spam sa mga sayup nga positibo, pananglitan). Among kuwentahon ang 10 ka libo nga mga rekord 100 ka bytes matag usa - megabytes kada adlaw.

Sa kinatibuk-an, ang 5MB nga limpyo (maayong pagka-compress) nga datos mogawas. Dugang pa kanila (grabe nga banabana) 1MB nga datos sa serbisyo.

Sa ato pa, kinahanglan namon ang 8MB chip kung dili kami mogamit sa compression, o 4MB kung gamiton namon kini. Talagsaon nga mga numero alang sa kini nga matang sa memorya.

Sama sa alang sa kapanguhaan: kung nagplano kami nga ang tibuuk nga panumduman isulat pag-usab dili molapas sa kausa sa matag 5 ka adlaw, nan sa sobra sa 10 ka tuig nga serbisyo nakakuha kami wala’y usa ka libo nga mga siklo sa pagsulat pag-usab.
Tugoti ako nga pahinumdoman ka nga ang tiggama nagsaad og usa ka gatos ka libo.

Usa ka gamay bahin sa NOR vs NAND

Karon, siyempre, ang panumduman sa NAND labi ka sikat, apan dili nako kini gamiton alang sa kini nga proyekto: Ang NAND, dili sama sa NOR, kinahanglan nga kinahanglan ang paggamit sa mga code sa pagtul-id sa sayup, usa ka lamesa sa dili maayo nga mga bloke, ug uban pa, ug usab ang mga bitiis sa Ang mga NAND chips kasagaran daghan pa.

Ang mga disadvantages sa NOR naglakip sa:

gamay nga gidaghanon (ug, sa ingon, taas nga presyo matag megabyte);
ubos nga gikusgon sa komunikasyon (kadaghanan tungod sa kamatuoran nga gigamit ang serial interface, kasagaran SPI o I2C);
hinay nga pagtangtang (depende sa gidak-on sa block, kini molungtad gikan sa usa ka bahin sa usa ka segundo hangtod sa pipila ka segundo).

Morag walay kritikal alang kanamo, busa nagpadayon kami.

Kung ang mga detalye makapaikag, gipili ang microcircuit sa25df321a (bisan pa, kini dili hinungdanon, adunay daghang mga analogue sa merkado nga nahiuyon sa pinout ug command system; bisan kung gusto namon mag-install usa ka microcircuit gikan sa usa ka lainlaing tiggama ug / o usa ka lahi nga gidak-on, ang tanan molihok nga wala’y pagbag-o sa Code).

Gigamit nako ang drayber nga gitukod sa kernel sa Linux; sa Raspberry, salamat sa suporta sa overlay sa punoan sa aparato, ang tanan yano ra - kinahanglan nimo ibutang ang giipon nga overlay sa /boot/overlays ug gamay nga usbon ang /boot/config.txt.

Pananglitan nga dts file

Sa tinuud, dili ako sigurado nga kini gisulat nga wala’y mga sayup, apan kini molihok.

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

Ug laing linya sa config.txt

dtoverlay=at25:spimaxfrequency=50000000

Akong laktawan ang paghulagway sa pagkonektar sa chip sa Raspberry Pi. Sa usa ka bahin, dili ako usa ka eksperto sa elektroniko, sa laing bahin, ang tanan dinhi banal bisan alang kanako: ang microcircuit adunay 8 ra ka tiil, diin kinahanglan namon ang yuta, gahum, SPI (CS, SI, SO, SCK ); ang mga lebel parehas sa mga Raspberry Pi, wala’y kinahanglan nga dugang nga mga kable - ikonektar lang ang gipakita nga 6 pin.

Pagbuot sa problema

Sama sa naandan, ang pahayag sa problema moagi sa daghang mga pag-uli, ug ingon nako nga oras na alang sa sunod. Busa hunongon nato, hiusahon ang nasulat na, ug klarohon ang mga detalye nga nagpabilin sa mga anino.

Busa, nakahukom kami nga ang log itago sa SPI NOR Flash.

Unsa ang NOR Flash para sa mga wala kahibalo?

Kini mao ang non-volatile memory nga imong mahimo sa tulo ka mga operasyon:

Pagbasa:
Ang labing kasagaran nga pagbasa: among ipadala ang adres ug basahon ang daghang mga byte nga among gikinahanglan;
Pagrekord:
Ang pagsulat sa NOR flash morag usa ka regular, apan kini adunay usa ka peculiarity: mahimo ra nimo usbon ang 1 ngadto sa 0, apan dili vice versa. Pananglitan, kung kita adunay 0x55 sa usa ka memory cell, unya pagkahuman sa pagsulat sa 0x0f niini, ang 0x05 itago na didto (tan-awa ang lamesa sa ubos);
Papasa:
Siyempre, kinahanglan natong mahimo ang kaatbang nga operasyon - usba ang 0 ngadto sa 1, mao gayud kini ang para sa pagpapas nga operasyon. Dili sama sa unang duha, kini naglihok dili sa mga byte, apan sa mga bloke (ang minimum nga erase block sa pinili nga chip mao ang 4kb). Ang erase makaguba sa tibuok block ug mao lamang ang paagi sa pag-usab sa 0 ngadto sa 1. Busa, sa diha nga nagtrabaho uban sa flash memory, kasagaran kinahanglan nimo nga ipahiangay ang mga istruktura sa datos ngadto sa erase block boundary.
Pagrekord sa NOR Flash:

Binary nga datos

Gibuhat
01010101

Natala
00001111

Nahimong
00000101

Ang log mismo nagrepresentar sa usa ka han-ay sa mga rekord nga lainlain ang gitas-on. Ang kasagarang gitas-on sa usa ka rekord maoy mga 30 ka bytes (bisan tuod ang mga rekord nga pipila ka kilobytes ang gitas-on usahay mahitabo). Sa kini nga kaso, nagtrabaho kami uban kanila ingon usa ka hugpong sa mga byte, apan, kung interesado ka, gigamit ang CBOR sa sulod sa mga rekord.

Agi og dugang sa log, kinahanglan natong tipigan ang pipila ka impormasyon sa "setting", pareho nga na-update ug dili: usa ka ID sa device, mga pag-calibrate sa sensor, usa ka "device temporaryo nga gi-disable" nga bandila, ug uban pa.
Kini nga impormasyon usa ka set sa key-value records, nga gitipigan usab sa CBOR. Wala kami daghan niini nga impormasyon (pinakadaghang kilobytes), ug kini panagsa ra nga gi-update.
Sa mosunod tawgon nato kini nga konteksto.

Kung mahinumduman nato kung diin nagsugod kini nga artikulo, hinungdanon kaayo nga masiguro ang kasaligan nga pagtipig sa datos ug, kung mahimo, padayon nga operasyon bisan kung adunay mga kapakyasan sa hardware / korapsyon sa datos.

Unsang mga tinubdan sa mga problema ang makonsiderar?

Pagpatay sa panahon sa pagsulat/pagpapas nga mga operasyon. Kini gikan sa kategorya nga "wala’y limbong batok sa crowbar."
Impormasyon gikan sa mga diskusyon sa stackexchange: kung ang gahum gipalong samtang nagtrabaho gamit ang flash, ang duha papason (i-set sa 1) ug isulat (i-set sa 0) mosangpot sa dili matino nga kinaiya: ang data mahimong isulat, partially written (ingon, gibalhin namo ang 10 bytes/80 bits , apan dili pa lang 45 ka tipik ang mahimong isulat), posible usab nga ang pipila sa mga tipik anaa sa “intermediate” nga kahimtang (ang pagbasa makapatunghag 0 ug 1);
Mga sayop sa flash memory mismo.
BER, bisan tuod ubos kaayo, dili mahimong katumbas sa sero;
Mga sayop sa bus
Ang datos nga gipasa pinaagi sa SPI dili protektado sa bisan unsang paagi; ang duha ka single bit errors ug synchronization errors mahimong mahitabo - pagkawala o pagsal-ot sa mga bits (nga mosangpot sa dako nga data distortion);
Ubang mga sayop/glitches
Mga sayop sa code, Raspberry glitches, alien interference...

Giporma nako ang mga kinahanglanon, ang katumanan nga, sa akong opinyon, gikinahanglan aron masiguro ang kasaligan:

Ang mga rekord kinahanglan nga moadto dayon sa flash memory, ang mga nalangan nga pagsulat wala gikonsiderar; - kung adunay mahitabo nga sayup, kinahanglan kini mahibal-an ug maproseso sa labing sayo nga mahimo; - ang sistema kinahanglan, kung mahimo, makabawi gikan sa mga sayup.
(usa ka panig-ingnan gikan sa kinabuhi nga "unsaon kini dili kinahanglan", nga sa akong hunahuna ang tanan nakatagbo: pagkahuman sa usa ka emerhensya nga pag-reboot, ang file system "nabuak" ug ang operating system wala mag-boot)

Mga ideya, pamaagi, pamalandong

Sa dihang nagsugod ko sa paghunahuna mahitungod niini nga problema, daghang mga ideya ang mikidlap sa akong ulo, pananglitan:

paggamit sa data compression;
gamita ang maalamon nga mga istruktura sa datos, pananglitan, pagtago sa mga ulohan sa rekord nga gilain gikan sa mga rekord mismo, aron kung adunay sayup sa bisan unsang rekord, mahimo nimong basahon ang nahabilin nga wala’y mga problema;
gamita ang mga bit field aron makontrol ang pagkompleto sa pagrekord kung ang gahum gipalong;
tindahan checksum alang sa tanan;
gamita ang pipila ka matang sa noise-resistant coding.

Ang pipila niini nga mga ideya gigamit, samtang ang uban nakahukom nga biyaan. Magsunod-sunod ta.

Ang pag-compress sa datos

Ang mga panghitabo mismo nga among girekord sa journal parehas ug balikbalik ("gilabay ang 5 ruble nga sensilyo", "gipindot ang buton alang sa paghatag pagbag-o", ...). Busa, ang compression kinahanglan nga epektibo kaayo.

Ang compression overhead dili kaayo hinungdanon (ang among processor kusog kaayo, bisan ang una nga Pi adunay usa ka core nga adunay frequency nga 700 MHz, ang karon nga mga modelo adunay daghang mga cores nga adunay frequency nga labaw sa usa ka gigahertz), ang exchange rate nga adunay pagtipig gamay (daghang megabytes matag segundo), ang gidak-on sa mga rekord gamay ra. Sa kinatibuk-an, kung ang compression adunay epekto sa pasundayag, kini mahimong positibo. (hingpit nga dili kritikal, nagsulti lang). Dugang pa, wala kami'y tinuod nga naka-embed, apan regular nga Linux - mao nga ang pagpatuman dili kinahanglan nga magkinahanglan og daghang paningkamot (igo ra nga i-link ang librarya ug gamiton ang daghang mga function gikan niini).

Ang usa ka piraso sa log gikuha gikan sa usa ka nagtrabaho nga device (1.7 MB, 70 ka libo nga mga entry) ug una nga gisusi alang sa compressibility gamit ang gzip, lz4, lzop, bzip2, xz, zstd nga anaa sa computer.

gzip, xz, zstd nagpakita sa susama nga mga resulta (40Kb).
Natingala ko nga ang uso nga xz nagpakita sa iyang kaugalingon dinhi sa lebel sa gzip o zstd;
Ang lzip nga adunay default nga mga setting naghatag gamay nga labi ka daotan nga mga sangputanan;
Ang lz4 ug lzop nagpakita nga dili kaayo maayo nga mga resulta (150Kb);
Ang bzip2 nagpakita sa usa ka katingad-an nga maayong resulta (18Kb).

Busa, ang data gi-compress kaayo.
Mao nga (kung wala kita makit-an nga makamatay nga mga sayup) adunay pag-compress! Tungod lang kay mas daghang datos ang mahimong mohaum sa samang flash drive.

Atong hunahunaon ang mga disbentaha.

Unang problema: nagkasinabot na kami nga ang matag rekord kinahanglang moadto dayon sa flash. Kasagaran, ang archiver nagkolekta sa datos gikan sa input stream hangtod nga kini nakahukom nga panahon na sa pagsulat sa katapusan sa semana. Kinahanglan nga makadawat dayon kita og usa ka compressed block sa data ug tipigan kini sa non-volatile memory.

Nakita nako ang tulo ka paagi:

I-compress ang matag rekord gamit ang compression sa diksyonaryo imbes sa mga algorithm nga gihisgutan sa ibabaw.
Kini usa ka hingpit nga magamit nga kapilian, apan dili ko ganahan niini. Aron masiguro ang usa ka labi o dili kaayo disente nga lebel sa compression, ang diksyonaryo kinahanglan nga "ipahaum" sa piho nga datos; bisan unsang pagbag-o magdala sa lebel sa compression nga mahulog sa katalagman. Oo, ang problema mahimong masulbad pinaagi sa paghimo sa usa ka bag-ong bersyon sa diksyonaryo, apan kini usa ka sakit sa ulo - kinahanglan namon nga tipigan ang tanan nga mga bersyon sa diksyonaryo; sa matag entry kinahanglan namong ipakita kung unsang bersyon sa diksyonaryo ang gi-compress...
I-compress ang matag rekord gamit ang "klasikal" nga mga algorithm, apan independente sa uban.
Ang mga algorithm sa compression nga gikonsiderar wala gidesinyo aron magtrabaho uban ang mga rekord sa kini nga gidak-on (napulo ka mga byte), ang ratio sa compression klaro nga dili moubos sa 1 (nga mao, pagdugang sa gidaghanon sa datos imbis nga pag-compress);
Buhata ang FLUSH pagkahuman sa matag pagrekord.
Daghang mga librarya sa compression adunay suporta alang sa FLUSH. Kini usa ka sugo (o usa ka parametro sa pamaagi sa pag-compress), sa pagkadawat nga ang archiver nagporma og usa ka compressed stream aron kini magamit sa pagpasig-uli. sa tanan nga mga wala ma-compress nga datos nga nadawat na. Ang ingon nga analogue sync sa mga file system o commit sa sql.
Ang importante mao nga ang sunod nga mga operasyon sa compression makahimo sa paggamit sa natipon nga diksyonaryo ug ang compression ratio dili mag-antus sama sa miaging bersyon.

Sa akong hunahuna klaro nga gipili nako ang ikatulo nga kapilian, tan-awon naton kini sa mas detalyado.

Nakaplagan maayong artikulo mahitungod sa FLUSH sa zlib.

Naghimo ako usa ka pagsulay sa tuhod base sa artikulo, gikuha ang 70 ka libo nga mga entry sa log gikan sa usa ka tinuud nga aparato, nga adunay gidak-on sa panid nga 60Kb (mobalik kami sa gidak-on sa panid sa ulahi) nakadawat:

Raw data
Compression gzip -9 (walay FLUSH)
zlib uban sa Z_PARTIAL_FLUSH
zlib uban sa Z_SYNC_FLUSH

Tomo, KB
1692
40
352
604

Sa una nga pagtan-aw, ang presyo nga giamot sa FLUSH sobra ka taas, apan sa tinuud wala kami’y kapilian - kung dili gyud mag-compress, o mag-compress (ug epektibo kaayo) gamit ang FLUSH. Dili nato kalimtan nga kita adunay 70 ka libo nga mga rekord, ang redundancy nga gipaila sa Z_PARTIAL_FLUSH kay 4-5 bytes lang kada rekord. Ug ang compression ratio nahimo nga hapit 5: 1, nga labaw pa sa usa ka maayo kaayo nga resulta.

Mahimong usa ka katingala, apan ang Z_SYNC_FLUSH sa tinuud usa ka mas episyente nga paagi sa pagbuhat sa FLUSH

Kung gamiton ang Z_SYNC_FLUSH, ang katapusan nga 4 bytes sa matag entry kanunay nga 0x00, 0x00, 0xff, 0xff. Ug kung nahibal-an nato sila, nan dili na nato kinahanglan nga tipigan sila, mao nga ang katapusang gidak-on kay 324Kb ra.

Ang artikulo nga akong gi-link adunay katin-awan:

Usa ka bag-ong tipo nga 0 block nga adunay walay sulod nga sulod gidugang.

Ang tipo nga 0 block nga adunay walay sulod nga sulod naglangkob sa:

ang tulo ka bit block header;

0 ngadto sa 7 bits nga katumbas sa zero, aron makab-ot ang byte alignment;

ang upat ka byte nga han-ay 00 00 FF FF.

Sama sa dali nimong makita, sa katapusan nga bloke sa wala pa kini nga 4 bytes adunay gikan sa 3 hangtod 10 zero bits. Bisan pa, gipakita sa praktis nga adunay labing menos 10 ka zero bits.

Mopatim-aw nga ang ingon nga mubu nga mga bloke sa datos kasagaran (kanunay?) Gi-encode gamit ang usa ka bloke sa tipo 1 (fixed block), nga kinahanglan matapos sa 7 zero bits, nga naghatag usa ka kinatibuk-an nga 10-17 nga garantiya nga zero bits (ug ang nahabilin mahimong sero nga adunay posibilidad nga mga 50%).

Busa, sa datos sa pagsulay, sa 100% sa mga kaso adunay usa ka zero byte sa wala pa ang 0x00, 0x00, 0xff, 0xff, ug sa labaw sa ikatulo nga mga kaso adunay duha ka zero bytes. (tingali ang kamatuoran mao nga naggamit ako og binary CBOR, ug kung naggamit sa teksto nga JSON, ang mga bloke sa tipo nga 2 - dinamikong block mahimong mas komon, matag usa, mga bloke nga walay dugang nga zero bytes sa wala pa ang 0x00, 0x00, 0xff, 0xff ang masugatan).

Sa kinatibuk-an, gamit ang magamit nga datos sa pagsulay, posible nga mohaum sa ubos sa 250Kb nga compressed data.

Makadaginot ka og gamay pinaagi sa pagbuhat og gamay nga juggling: kay karon wala na namo gibalewala ang presensya sa pipila ka mga zero bits sa katapusan sa block, ang pipila ka mga bits sa sinugdanan sa block dili usab mausab...
Apan pagkahuman nakahimo ako usa ka kusgan nga desisyon nga mohunong, kung dili sa kini nga rate mahimo nako nga mapauswag ang akong kaugalingon nga archiver.

Sa kinatibuk-an, gikan sa akong data sa pagsulay nakadawat ako og 3-4 bytes kada pagsulat, ang compression ratio nahimong labaw pa sa 6:1. Magmatinud-anon ko: Wala ko magdahom nga ingon niana ang resulta; sa akong opinyon, ang bisan unsa nga mas maayo pa sa 2:1 kay resulta na nga nagpakamatarong sa paggamit sa compression.

Maayo ang tanan, apan ang zlib (deflate) usa gihapon ka karaan, angayan ug medyo karaan nga algorithm sa compression. Ang kamatuoran nga ang katapusan nga 32Kb sa wala ma-compress nga stream sa datos gigamit ingon nga usa ka diksyonaryo nga tan-awon nga katingad-an karon (nga mao, kung ang pipila nga bloke sa datos parehas kaayo sa kung unsa ang naa sa input stream 40Kb ang milabay, nan kini magsugod sa pag-archive pag-usab, ug dili magtumong sa usa ka miaging panghitabo). Sa uso nga moderno nga mga archiver, ang gidak-on sa diksyonaryo sagad gisukod sa megabytes kaysa kilobytes.

Busa gipadayon namo ang among mini nga pagtuon sa mga archiver.

Sunod gisulayan namon ang bzip2 (hinumdomi, kung wala ang FLUSH nagpakita kini usa ka maayo nga ratio sa compression nga hapit 100: 1). Ikasubo, kini dili maayo nga nahimo sa FLUSH; ang gidak-on sa gi-compress nga datos nahimo nga mas dako kaysa sa wala ma-compress nga datos.

Ang akong mga pangagpas bahin sa mga hinungdan sa kapakyasan

Ang Libbz2 nagtanyag lamang og usa ka flush nga opsyon, nga daw nag-clear sa diksyonaryo (kaamgid sa Z_FULL_FLUSH sa zlib); wala'y paghisgot sa bisan unsang epektibo nga compression pagkahuman niini.

Ug ang katapusan nga gisulayan mao ang zstd. Depende sa mga parameter, nag-compress kini sa lebel sa gzip, apan mas paspas, o mas maayo kaysa sa gzip.

Alaut, sa FLUSH kini dili kaayo maayo: ang gidak-on sa compressed data mao ang mahitungod sa 700Kb.

Я nangutana sa github page sa proyekto, nakadawat ko og tubag nga kinahanglan nimong isalig hangtod sa 10 bytes nga data sa serbisyo alang sa matag bloke sa compressed data, nga duol sa mga resulta nga nakuha; wala'y paagi nga makaapas sa deflate.

Nakahukom ko nga mohunong niining puntoha sa akong mga eksperimento sa mga archiver (pahinumdoman ko ikaw nga ang xz, lzip, lzo, lz4 wala magpakita sa ilang kaugalingon bisan sa yugto sa pagsulay nga walay FLUSH, ug wala nako isipa ang mas exotic nga compression algorithm).

Balikan nato ang mga problema sa pag-archive.

Ang ikaduha (ingon sa ilang giingon sa han-ay, dili sa bili) nga problema mao nga ang compressed data mao ang usa ka sapa, diin adunay kanunay nga mga pakisayran sa miaging mga seksyon. Busa, kon ang usa ka seksyon sa compressed data nadaot, kita mawad-an dili lamang sa mga kauban block sa wala ma-compress data, apan usab sa tanan nga mga sunod-sunod nga.

Adunay usa ka paagi sa pagsulbad niini nga problema:

Pugngi ang problema nga mahitabo - idugang ang redundancy sa compressed data, nga magtugot kanimo sa pag-ila ug pagtul-id sa mga sayup; ato kining hisgotan unya;
Pagmenos sa mga sangputanan kung adunay problema
Gisulti na namo sa sayo pa nga mahimo nimong i-compress ang matag bloke sa datos nga independente, ug ang problema mawala sa iyang kaugalingon (ang kadaot sa datos sa usa ka block mosangpot sa pagkawala sa datos alang lamang niini nga block). Bisan pa, kini usa ka grabe nga kaso diin ang data compression dili epektibo. Ang kaatbang nga grabe: gamita ang tanan nga 4MB sa among chip isip usa ka archive, nga maghatag kanamo maayo kaayo nga pag-compress, apan mga katalagman nga sangputanan kung adunay korapsyon sa datos.
Oo, gikinahanglan ang pagkompromiso bahin sa pagkakasaligan. Apan kinahanglan natong hinumdoman nga nag-ugmad kita og format sa pagtipig sa datos alang sa dili-volatile nga panumduman nga adunay hilabihan ka ubos nga BER ug gideklarar nga panahon sa pagtipig sa datos nga 20 ka tuig.

Atol sa mga eksperimento, akong nadiskobrehan nga mas daghan o dili kaayo mamatikdan nga pagkawala sa lebel sa compression nagsugod sa mga bloke sa compressed data nga ubos sa 10 KB ang gidak-on.
Gihisgotan na kaniadto nga ang panumduman nga gigamit kay paged; Wala koy nakitang rason nganong dili gamiton ang "usa ka panid - usa ka bloke sa compressed data" nga mga sulat.

Kana mao, ang minimum nga makatarunganon nga gidak-on sa panid mao ang 16Kb (nga adunay reserba alang sa impormasyon sa serbisyo). Bisan pa, ang ingon ka gamay nga gidak-on sa panid nagpahamtang ug hinungdanon nga mga pagdili sa labing taas nga gidak-on sa rekord.

Bisan tuod wala pa ako magdahom nga ang mga rekord mas dako pa kay sa pipila ka kilobytes sa compressed nga porma, nakahukom ko nga mogamit ug 32Kb nga mga panid (alang sa total nga 128 ka panid matag chip).

Katingbanan:

Gitipigan namon ang datos nga gi-compress gamit ang zlib (deflate);
Alang sa matag entry among gibutang ang Z_SYNC_FLUSH;
Alang sa matag compressed record, among putlon ang trailing bytes (pananglitan 0x00, 0x00, 0xff, 0xff); sa header among gipakita kung pila ka byte ang among giputol;
Gitipigan namo ang datos sa 32Kb nga mga panid; adunay usa ka sapa sa compressed data sa sulod sa panid; Sa matag panid magsugod kami pag-usab sa compression.

Ug, sa dili pa mahuman ang compression, gusto nako nga ipunting ang imong atensyon sa kamatuoran nga kami adunay pipila ra nga mga byte sa compressed data matag rekord, mao nga hinungdanon kaayo nga dili madugangan ang kasayuran sa serbisyo, ang matag byte maihap dinhi.

Pagtipig sa Mga Header sa Data

Tungod kay kita adunay mga rekord sa lain-laing mga gitas-on, kita kinahanglan nga sa usa ka paagi sa pagtino sa pagbutang/mga utlanan sa mga rekord.

Nahibal-an ko ang tulo ka pamaagi:

Ang tanan nga mga rekord gitipigan sa usa ka padayon nga sapa, una adunay usa ka header sa rekord nga adunay gitas-on, ug dayon ang rekord mismo.
Niini nga embodiment, ang mga header ug data mahimong lainlain ang gitas-on.
Sa tinuud, nakakuha kami usa ka lista nga na-link nga usa nga gigamit sa tanan nga oras;
Ang mga ulohan ug ang mga rekord mismo gitipigan sa bulag nga mga sapa.
Pinaagi sa paggamit sa mga header nga kanunay ang gitas-on, among gisiguro nga ang kadaot sa usa ka header dili makaapekto sa uban.
Ang susama nga pamaagi gigamit, pananglitan, sa daghang mga sistema sa file;
Ang mga rekord gitipigan sa usa ka padayon nga sapa, ang utlanan sa rekord gitino pinaagi sa usa ka piho nga marker (usa ka kinaiya / han-ay sa mga karakter nga gidili sulod sa mga bloke sa datos). Kung adunay usa ka marker sa sulod sa rekord, dayon among ilisan kini sa pipila ka han-ay (escap kini).
Ang susama nga pamaagi gigamit, pananglitan, sa PPP protocol.

Akong i-ilustrar.

Pagpili 1:

Ang tanan yano ra kaayo dinhi: nahibal-an ang gitas-on sa rekord, mahimo natong kuwentahon ang adres sa sunod nga header. Mao nga gibalhin namon ang mga ulohan hangtod nga makasugat kami usa ka lugar nga puno sa 0xff (libre nga lugar) o katapusan sa panid.

Pagpili 2:

Tungod sa lainlain nga gitas-on sa rekord, dili kami makasulti daan kung pila ang mga rekord (ug busa mga ulohan) ang among kinahanglan matag panid. Mahimo nimong ipakaylap ang mga ulohan ug ang datos mismo sa lainlaing mga panid, apan gusto nako ang usa ka lahi nga pamaagi: gibutang namon ang mga ulohan ug ang datos sa usa ka panid, apan ang mga ulohan (kanunay nga gidak-on) gikan sa sinugdanan sa panid, ug ang data (sa variable nga gitas-on) gikan sa katapusan. Sa diha nga sila "magkita" (walay igo nga libre nga luna alang sa usa ka bag-ong entry), among giisip kini nga panid nga kompleto.

Pagpili 3:

Dili kinahanglan nga tipigan ang gitas-on o uban pang impormasyon bahin sa lokasyon sa datos sa header; igo na ang mga marka nga nagpakita sa mga utlanan sa mga rekord. Bisan pa, ang datos kinahanglan nga iproseso kung nagsulat / nagbasa.
Akong gamiton ang 0xff isip usa ka marker (nga mopuno sa panid human mapapas), mao nga ang libre nga lugar siguradong dili isipon nga datos.

Talaan sa pagtandi:

Pagpili 1
Pagpili 2
Pagpili 3

Sayop nga pagtugot
-
+
+

Compactness
+
-
+

Pagkakomplikado sa pagpatuman
*
**
**

Ang kapilian 1 adunay usa ka makamatay nga sayup: kung adunay bisan unsang mga ulohan nga nadaot, ang tibuuk nga sunod-sunod nga kadena maguba. Ang nahabilin nga mga kapilian nagtugot kanimo sa pagbawi sa pipila ka mga datos bisan kung adunay daghang kadaot.
Apan dinhi angay nga hinumdoman nga nakahukom kami nga tipigan ang datos sa usa ka compressed nga porma, ug busa nawala ang tanan nga datos sa panid pagkahuman sa usa ka "nabuak" nga rekord, mao nga bisan kung adunay minus sa lamesa, wala kami tagda kini.

Pagkakomplikado:

sa unang kapilian, kinahanglan natong tipigan lamang ang gitas-on sa header; kon kita mogamit sa variable-length integers, nan sa kadaghanang mga kaso kita makakuha sa usa ka byte;
sa ikaduha nga kapilian kinahanglan namon nga tipigan ang pagsugod nga adres ug gitas-on; ang rekord kinahanglan nga usa ka makanunayon nga gidak-on, akong gibanabana nga 4 ka byte matag rekord (duha ka byte alang sa offset, ug duha ka byte alang sa gitas-on);
ang ikatulo nga kapilian nagkinahanglan lamang og usa ka karakter aron ipahibalo ang pagsugod sa pagrekord, ug ang pagrekord mismo motaas sa 1-2% tungod sa panagang. Sa kinatibuk-an, gibana-bana nga parity sa unang kapilian.

Sa sinugdan, akong gikonsiderar ang ikaduha nga kapilian ingon nga nag-una (ug bisan gisulat ang pagpatuman). Gibiyaan ra nako kini sa diha nga sa katapusan nakahukom ako sa paggamit sa compression.

Tingali sa umaabot nga adlaw mogamit gihapon ako usa ka parehas nga kapilian. Pananglitan, kung kinahanglan nako nga atubangon ang pagtipig sa datos alang sa usa ka barko nga nagbiyahe tali sa Yuta ug Mars, adunay hingpit nga lainlaing mga kinahanglanon alang sa kasaligan, kosmiko nga radiation, ...

Mahitungod sa ikatulo nga kapilian: Gihatagan nako kini og duha ka bituon alang sa kalisud sa pagpatuman tungod lang kay dili ko ganahan nga magsamok-samok sa panagang, pagbag-o sa gitas-on sa proseso, ug uban pa. Oo, tingali gipihig ako, apan kinahanglan nako nga isulat ang code - nganong pugson ang imong kaugalingon sa pagbuhat sa usa ka butang nga dili nimo gusto.

Katingbanan: Gipili namon ang kapilian sa pagtipig sa porma sa mga kadena nga "header nga adunay gitas-on - data sa variable nga gitas-on" tungod sa kahusayan ug kadali sa pagpatuman.

Paggamit sa Bit Fields aron Pag-monitor sa Kalampusan sa Pagsulat nga mga Operasyon

Wala ko kahinumdom karon kung diin nako nakuha ang ideya, apan ingon niini ang hitsura:
Alang sa matag entry, naggahin kami og daghang mga piraso aron tipigan ang mga bandila.
Sama sa giingon namon kaniadto, pagkahuman sa pagtangtang ang tanan nga mga piraso napuno sa 1s, ug mahimo naton usbon ang 1 hangtod 0, apan dili vice versa. Busa alang sa "ang bandila wala ibutang" atong gamiton ang 1, kay "ang bandila gitakda" atong gamiton ang 0.

Ania kung unsa ang hitsura sa pagbutang sa usa ka variable nga gitas-on nga rekord sa flash:

Ibutang ang bandila nga "nagsugod na ang pagrekord sa gitas-on";
Irekord ang gitas-on;
Ibutang ang bandila nga "nagsugod na ang pagrekord sa datos";
Girekord namon ang datos;
Ibutang ang bandila nga "natapos na ang pagrekord".

Dugang pa, kita adunay usa ka "nahitabo nga sayup" nga bandila, alang sa kinatibuk-an nga 4 bit nga mga bandila.

Sa kini nga kaso, kami adunay duha ka lig-on nga estado "1111" - wala pa magsugod ang pagrekord ug "1000" - malampuson ang pagrekord; kung adunay wala damha nga pagkabalda sa proseso sa pagrekord, makadawat kami mga intermediate nga estado, nga mahimo namong mahibal-an ug maproseso.

Ang pamaagi makapaikag, apan kini nanalipod lamang batok sa kalit nga pagkawala sa kuryente ug susama nga mga kapakyasan, nga, siyempre, importante, apan kini layo sa bugtong (o bisan ang nag-unang) rason sa posible nga mga kapakyasan.

Katingbanan: Magpadayon ta sa pagpangita og maayong solusyon.

Mga checksum

Ang mga checksum naghimo usab nga posible aron masiguro (uban ang makatarunganon nga posibilidad) nga among gibasa kung unsa gyud ang kinahanglan nga isulat. Ug, dili sama sa gamay nga mga natad nga gihisgutan sa ibabaw, sila kanunay nga nagtrabaho.

Kung atong tagdon ang lista sa mga potensyal nga tinubdan sa mga problema nga atong gihisgutan sa ibabaw, nan ang checksum makahimo sa pag-ila sa usa ka sayup bisan unsa pa ang gigikanan niini. (gawas, tingali, alang sa mga malisyosong langyaw - mahimo usab nila nga panday ang checksum).

Mao nga kung ang among katuyoan mao ang pag-verify nga ang datos wala’y labot, ang mga checksum usa ka maayong ideya.

Ang pagpili sa algorithm alang sa pagkalkula sa checksum wala nagpatunghag bisan unsang pangutana - CRC. Sa usa ka bahin, ang mga kabtangan sa matematika nagpaposible sa pagdakop sa pipila ka mga matang sa mga kasaypanan nga 100%; sa laing bahin, sa random nga datos kini nga algorithm kasagaran nagpakita sa kalagmitan sa pagbangga nga dili labaw pa kay sa teoretikal nga limitasyon. . Mahimong dili kini ang pinakapaspas nga algorithm, ni kini kanunay nga minimum sa mga termino sa gidaghanon sa mga bangga, apan kini adunay usa ka importante kaayo nga kalidad: sa mga pagsulay nga akong nasugatan, walay mga sumbanan diin kini klaro nga napakyas. Ang kalig-on mao ang nag-unang kalidad niini nga kaso.

Pananglitan sa usa ka volumetric nga pagtuon: bahin 1, bahin 2 (mga link sa narod.ru, sorry).

Bisan pa, ang tahas sa pagpili sa usa ka checksum dili kompleto; Ang CRC usa ka tibuuk nga pamilya sa mga checksum. Kinahanglan ka nga magdesisyon sa gitas-on, ug dayon pagpili og polynomial.

Ang pagpili sa gitas-on sa checksum dili ingon ka yano nga pangutana sama sa una nga pagtan-aw.

Tugoti ako sa pag-ilustrar:
Himoa nga kita adunay kalagmitan sa usa ka sayop sa matag byte ug usa ka sulundon nga checksum, atong kuwentahon ang kasagarang gidaghanon sa mga sayop kada milyon nga mga rekord:

Data, byte
Checksum, byte
Wala mamatikdi nga mga sayop
Sayop nga pag-ila sa sayop
Kinatibuk-ang bakak nga mga positibo

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

Ingon og yano ra ang tanan - depende sa gitas-on sa datos nga giprotektahan, pilia ang gitas-on sa checksum nga adunay labing gamay nga dili husto nga mga positibo - ug ang lansis naa sa bag.

Bisan pa, usa ka problema ang mitungha sa mugbo nga mga checksum: bisan kung maayo sila sa pag-ila sa usa ka gamay nga sayup, mahimo nila nga adunay taas nga posibilidad nga makadawat sa hingpit nga random nga datos ingon husto. Adunay na usa ka artikulo sa Habré nga naghulagway problema sa tinuod nga kinabuhi.

Busa, aron mahimo ang usa ka random checksum match nga hapit imposible, kinahanglan nimo nga gamiton ang mga checksum nga 32 bit o mas taas ang gitas-on. (alang sa mga gitas-on nga labaw sa 64 ka bit, ang cryptographic hash functions kasagarang gigamit).

Bisan pa sa kamatuoran nga ako misulat sa sayo pa nga kita kinahanglan nga sa pagluwas sa luna sa tanan nga paagi, kita sa gihapon mogamit sa usa ka 32-bit checksum (16 bits dili igo, ang kalagmitan sa usa ka bangga mao ang labaw pa kay sa 0.01%; ug 24 bits, ingon nga sila ingna, wala dinhi o didto).

Mahimong motungha ang usa ka pagsupak dinhi: gitipigan ba namo ang matag byte sa dihang nagpili sa compression aron makahatag na karon ug 4 ka byte sa usa ka higayon? Dili ba mas maayo nga dili mag-compress o magdugang usa ka checksum? Siyempre dili, walay compression wala magpasabot, nga dili nato kinahanglan ang pagsusi sa integridad.

Kung nagpili usa ka polynomial, dili naton usbon ang ligid, apan kuhaon ang karon nga sikat nga CRC-32C.
Kini nga code nakamatikod sa 6 ka gamay nga mga sayup sa mga pakete hangtod sa 22 ka bytes (tingali ang labing kasagaran nga kaso alang kanamo), 4 ka gamay nga mga sayup sa mga pakete hangtod sa 655 ka byte (usa usab ka kasagaran nga kaso alang kanamo), 2 o bisan unsang katingad-an nga gidaghanon sa mga gamay nga sayup sa mga pakete sa bisan unsa nga makatarunganon nga gitas-on.

Kung kinsa ang interesado sa mga detalye

Artikulo sa Wikipedia mahitungod sa CRC.

Mga parametro sa code crc-32c sa Koopman nga website - tingali ang nanguna nga espesyalista sa CRC sa planeta.

В iyang artikulo mao laing makapaikag nga code, nga naghatag og gamay nga mas maayo nga mga parameter alang sa mga gitas-on sa pakete nga may kalabutan kanato, apan wala nako isipa ang kalainan nga mahinungdanon, ug ako adunay igo nga katakus sa pagpili sa custom code imbes sa standard ug maayo nga gi-research.

Usab, tungod kay ang among datos gi-compress, ang pangutana mitungha: kinahanglan ba natong kuwentahon ang checksum sa compressed o uncompressed data?

Mga argumento pabor sa pagkalkula sa checksum sa wala ma-compress nga datos:

Sa katapusan kinahanglan natong susihon ang kaluwasan sa pagtipig sa datos - busa atong susihon kini direkta (sa samang higayon, posible nga mga sayup sa pagpatuman sa compression/decompression, kadaot nga gipahinabo sa nabuak nga memorya, ug uban pa.)
Ang deflate algorithm sa zlib adunay medyo hamtong nga pagpatuman ug dili nahulog uban ang "baliko" nga data sa pag-input; dugang pa, kini kanunay nga makahimo nga independente nga makit-an ang mga sayup sa input stream, nga makunhuran ang kinatibuk-ang posibilidad nga dili makit-an ang usa ka sayup (naghimo usa ka pagsulay nga adunay pagbag-o sa usa ka gamay sa usa ka mubo nga rekord, nakit-an ni zlib ang usa ka sayup sa mga un-tersiya sa mga kaso).

Mga argumento batok sa pagkalkula sa checksum sa wala ma-compress nga datos:

Ang CRC "gipahaum" ilabi na alang sa pipila ka gamay nga mga sayup nga kinaiya sa flash memory (usa ka gamay nga sayup sa usa ka compressed stream mahimong hinungdan sa usa ka dako nga pagbag-o sa output stream, diin, sa teoriya lamang, kita "makadakop" sa usa ka bangga);
Dili gyud ko ganahan sa ideya sa pagpasa sa posibleng mabungkag nga datos ngadto sa decompressor, Kinsay nasayodunsay iyang reaksyon.

Niini nga proyekto, nakahukom ko nga motipas gikan sa kasagarang gidawat nga praktis sa pagtipig og checksum sa wala ma-compress nga datos.

Katingbanan: Gigamit namon ang CRC-32C, among gikalkulo ang checksum gikan sa datos sa porma diin kini gisulat sa flash (pagkahuman sa compression).

Redundancy

Ang paggamit sa sobra nga coding dili, siyempre, pagwagtang sa pagkawala sa datos, bisan pa, kini mahimo nga kamahinungdanon (kasagaran sa daghang mga order sa magnitude) makapakunhod sa kalagmitan sa dili mabawi nga pagkawala sa datos.

Mahimo natong gamiton ang lain-laing matang sa redundancy aron matul-id ang mga sayop.
Ang mga code sa hamming mahimong magtul-id sa usa ka gamay nga sayup, ang mga code sa karakter sa Reed-Solomon, daghang mga kopya sa datos nga gihiusa sa mga checksum, o mga pag-encode sama sa RAID-6 makatabang sa pagbawi sa datos bisan kung adunay daghang korapsyon.
Sa sinugdan, ako mipasalig sa kaylap nga paggamit sa error-resistant coding, apan unya akong naamgohan nga kita kinahanglan una nga adunay usa ka ideya sa unsa nga mga sayop nga gusto natong panalipdan ang atong kaugalingon gikan sa, ug unya pagpili sa coding.

Giingon namon kaniadto nga ang mga sayup kinahanglan nga madakpan sa labing madali. Sa unsa nga mga punto kita makasugat og mga sayop?

Ang wala mahuman nga pagrekord (sa usa ka hinungdan sa panahon sa pagrekord gipalong ang gahum, ang Raspberry nagyelo, ...)
Alaut, kung mahitabo ang ingon nga sayup, ang nahabilin mao ang pagbaliwala sa dili balido nga mga rekord ug ikonsiderar ang nawala nga datos;
Pagsulat og mga sayop (sa pipila ka rason, ang gisulat sa flash memory dili ang gisulat)
Mamatikdan dayon namo ang ingon nga mga sayup kung maghimo kami usa ka pagsulay nga pagbasa dayon pagkahuman sa pagrekord;
Ang pagtuis sa datos sa memorya sa panahon sa pagtipig;
Mga sayop sa pagbasa
Aron matul-id kini, kung ang checksum dili motakdo, igo na nga balikon ang pagbasa sa daghang mga higayon.

Sa ato pa, ang mga sayup lamang sa ikatulo nga tipo (spontaneous corruption of data during storage) dili matul-id nga walay error-resistant coding. Morag ang ingon nga mga kasaypanan dili gihapon posible.

Katingbanan: nakahukom nga biyaan ang sobra nga coding, apan kung ang operasyon nagpakita sa sayup sa kini nga desisyon, unya ibalik ang konsiderasyon sa isyu (nga adunay natipon nga mga istatistika sa mga kapakyasan, nga magtugot sa pagpili sa labing kaayo nga tipo sa coding).

Ang ubang mga

Siyempre, ang pormat sa artikulo wala magtugot kanamo sa paghatag katarungan sa matag gamay sa pormat (ug nahurot na ang akong kusog), mao nga akong hisgotan sa makadiyot ang pipila ka punto nga wala mahisgoti kaniadto.

Nadesisyonan nga himoong “parehas” ang tanang panid
Sa ato pa, wala’y espesyal nga mga panid nga adunay metadata, lahi nga mga hilo, ug uban pa, apan sa baylo usa ka hilo nga nagbag-o sa pagsulat sa tanan nga mga panid.
Kini nagsiguro bisan sa pagsul-ob sa mga panid, walay bisan usa ka punto sa kapakyasan, ug ganahan lang ko niini;
Gikinahanglan ang paghatag ug bersyon sa format.
Ang usa ka format nga walay numero sa bersyon sa ulohan daotan!
Igo na ang pagdugang usa ka uma nga adunay usa ka Magic Number (pirma) sa header sa panid, nga magpakita sa bersyon sa gigamit nga format. (Wala ko maghunahuna nga sa praktis adunay bisan usa ka dosena niini);
Gamita ang usa ka variable-length header alang sa mga rekord (nga adunay daghan), naningkamot nga mahimo kini nga 1 byte ang gitas-on sa kadaghanan nga mga kaso;
Aron ma-encode ang gitas-on sa header ug ang gitas-on sa giputol nga bahin sa compressed record, gamita ang variable-length binary codes.

Nakatabang kaayo online generator Mga kodigo sa Huffman. Sa pipila lang ka minuto nakahimo kami sa pagpili sa gikinahanglan nga variable length codes.

Deskripsyon sa format sa pagtipig sa datos

Pag-order sa byte

Ang mga field nga mas dako pa sa usa ka byte gitipigan sa big-endian nga format (network byte order), nga mao, ang 0x1234 gisulat isip 0x12, 0x34.

Pagination

Ang tanan nga flash memory gibahin sa mga panid nga managsama ang gidak-on.

Ang default nga gidak-on sa panid mao ang 32Kb, apan dili mosobra sa 1/4 sa kinatibuk-ang gidak-on sa memory chip (alang sa 4MB chip, 128 ka panid ang makuha).

Ang matag panid nagtipig sa datos nga independente sa uban (sa ato pa, ang datos sa usa ka panid wala maghisgot sa datos sa laing panid).

Ang tanang panid ginumero sa natural nga pagkahan-ay (sa nagsaka nga han-ay sa mga adres), sugod sa numero 0 (panid zero magsugod sa adres 0, ang unang panid magsugod sa 32Kb, ang ikaduhang panid magsugod sa 64Kb, ug uban pa)

Ang memory chip gigamit isip cyclic buffer (ring buffer), nga mao, ang una nga pagsulat moadto sa numero sa panid 0, dayon numero 1, ..., kung pun-on nato ang katapusang panid, magsugod ang usa ka bag-ong siklo ug ang pagrekord nagpadayon gikan sa panid zero .

Sulod sa panid

Sa sinugdanan sa panid, usa ka 4-byte nga panid sa panid ang gitipigan, dayon usa ka header checksum (CRC-32C), dayon ang mga rekord gitipigan sa "header, data, checksum" nga format.

Ang ulohan sa panid (hugaw nga berde sa dayagram) naglangkob sa:

duha ka byte nga Magic Number field (usa usab ka timaan sa bersyon sa format)
alang sa kasamtangan nga bersyon sa format kini kalkulado ingon nga 0xed00 ⊕ номер страницы;
duha ka byte nga counter "Bersyon sa panid" (gisulat pag-usab nga numero sa siklo sa memorya).

Ang mga entry sa panid gitipigan sa compressed nga porma (ang deflate algorithm gigamit). Ang tanan nga mga rekord sa usa ka panid gi-compress sa usa ka hilo (usa ka sagad nga diksyonaryo ang gigamit), ug sa matag bag-ong panid magsugod ang pag-compress. Sa ato pa, aron ma-decompress ang bisan unsang rekord, gikinahanglan ang tanan nga nangaging mga rekord gikan niini nga panid (ug kini ra).

Ang matag rekord i-compress sa Z_SYNC_FLUSH nga bandera, ug sa katapusan sa compressed stream adunay 4 bytes 0x00, 0x00, 0xff, 0xff, posible nga giunhan sa usa o duha pa ka zero bytes.
Among gilabay kini nga han-ay (4, 5 o 6 bytes ang gitas-on) sa pagsulat sa flash memory.

Ang record header kay 1, 2 o 3 bytes nga pagtipig:

usa ka gamay (T) nga nagpakita sa matang sa rekord: 0 - konteksto, 1 - log;
usa ka variable nga gitas-on nga field (S) gikan sa 1 ngadto sa 7 bits, nga nagtino sa gitas-on sa header ug ang "ikog" nga kinahanglan idugang sa rekord alang sa decompression;
gitas-on sa rekord (L).

S nga bili sa lamesa:

S
Ang gitas-on sa ulohan, bytes
Gilabay sa pagsulat, byte

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)

Gisulayan nako ang pag-ilustrar, wala ko mahibal-an kung unsa kini ka klaro:

Ang yellow dinhi nagpakita sa T field, puti ang S field, berde L (ang gitas-on sa compressed data sa bytes), blue ang compressed data, pula ang final bytes sa compressed data nga wala gisulat sa flash memory.

Sa ingon, mahimo natong isulat ang mga ulohan sa rekord sa labing komon nga gitas-on (hangtod sa 63+5 bytes sa compressed nga porma) sa usa ka byte.

Human sa matag rekord, usa ka CRC-32C checksum ang gitipigan, diin ang balit-ad nga bili sa miaging checksum gigamit isip inisyal nga bili (init).

Ang CRC adunay kabtangan nga "gidugayon", ang mosunod nga pormula molihok (dugang o minus nga pagbag-o sa gamay sa proseso): .
Kana mao, sa tinuud, among gikalkula ang CRC sa tanan nga nangaging mga byte sa mga ulohan ug datos sa kini nga panid.

Direkta nga nagsunod sa checksum mao ang ulohan sa sunod nga rekord.

Ang header gidisenyo sa paagi nga ang una nga byte niini kanunay nga lahi sa 0x00 ug 0xff (kung imbes sa una nga byte sa header ang atong masugatan nga 0xff, nan kini nagpasabut nga kini usa ka wala magamit nga lugar; ang 0x00 nagpahibalo sa usa ka sayup).

Pananglitan nga Algorithm

Pagbasa gikan sa Flash Memory

Ang bisan unsang pagbasa adunay usa ka checksum check.
Kung ang checksum dili motakdo, ang pagbasa gisubli sa daghang mga higayon sa paglaum nga mabasa ang husto nga datos.

(Kini makatarunganon, ang Linux wala mag-cache sa mga pagbasa gikan sa NOR Flash, gisulayan)

Pagsulat sa flash memory

Girekord namon ang datos.
Atong basahon sila.

Kung ang gibasa nga datos dili motakdo sa sinulat nga datos, atong pun-on ang lugar og mga zero ug magsenyas og sayop.

Pag-andam sa usa ka bag-ong microcircuit alang sa operasyon

Alang sa pagsugod, usa ka ulohan nga adunay bersyon 1 gisulat sa una (o labi pa nga zero) nga panid.
Pagkahuman niana, ang inisyal nga konteksto gisulat sa kini nga panid (naglangkob sa UUID sa makina ug default nga mga setting).

Mao na, ang flash memory andam na nga gamiton.

Nagkarga sa makina

Kung nagkarga, ang una nga 8 ka byte sa matag panid (header + CRC) gibasa, ang mga panid nga adunay wala mailhi nga Magic Number o usa ka sayup nga CRC gibalewala.
Gikan sa "husto" nga mga panid, ang mga panid nga adunay labing kadaghan nga bersyon gipili, ug ang panid nga adunay labing kataas nga numero gikuha gikan kanila.
Ang unang rekord gibasa, ang pagkahusto sa CRC ug ang presensya sa "konteksto" nga bandila gisusi. Kung maayo ang tanan, kini nga panid giisip nga karon. Kung dili, ibalik namon ang nauna hangtod makit-an namon ang usa ka "live" nga panid.
ug sa nakit-an nga panid among gibasa ang tanan nga mga rekord, kadtong among gigamit sa bandila nga "konteksto".
I-save ang zlib nga diksyonaryo (kini kinahanglan alang sa pagdugang niini nga panid).

Mao ra kana, kompleto na ang pag-download, gipahiuli ang konteksto, mahimo ka magtrabaho.

Pagdugang og Journal Entry

Among gi-compress ang rekord gamit ang saktong diksyonaryo, nga nagpiho sa Z_SYNC_FLUSH. Atong tan-awon kon ang compressed record mohaom ba sa kasamtangan nga panid.
Kung dili kini angay (o adunay mga sayup sa CRC sa panid), pagsugod og bag-ong panid (tan-awa sa ubos).
Gisulat namo ang rekord ug CRC. Kung adunay mahitabo nga sayup, pagsugod og bag-ong panid.

Bag-ong panid

Gipili namo ang usa ka libre nga panid nga adunay minimum nga gidaghanon (among gikonsiderar ang usa ka libre nga panid nga usa ka panid nga adunay dili husto nga checksum sa ulohan o adunay usa ka bersyon nga gamay kaysa sa karon). Kung walay ingon nga mga panid, pilia ang panid nga adunay minimum nga numero gikan sa mga adunay bersyon nga parehas sa karon.
Atong papason ang pinili nga panid. Gisusi namo ang sulod sa 0xff. Kung adunay sayup, kuhaa ang sunod nga libre nga panid, ug uban pa.
Nagsulat kami og usa ka header sa gipapas nga panid, ang una nga entry mao ang kasamtangan nga kahimtang sa konteksto, ang sunod mao ang dili sinulat nga log entry (kung adunay usa).

Format nga magamit

Sa akong opinyon, kini nahimo nga usa ka maayo nga pormat alang sa pagtipig sa bisan unsang labi pa o dili kaayo mapilit nga mga sapa sa kasayuran (plain text, JSON, MessagePack, CBOR, posible nga protobuf) sa NOR Flash.

Siyempre, ang format "gipahaum" alang sa SLC NOR Flash.

Dili kini gamiton sa taas nga BER media sama sa NAND o MLC NOR (mahimo ba nga ibaligya ang ingon nga memorya? Nakita ra nako kini nga gihisgutan sa mga buhat sa mga code sa pagtul-id).

Dugang pa, dili kini angay gamiton sa mga himan nga adunay kaugalingon nga FTL: USB flash, SD, MicroSD, ug uban pa (alang sa ingon nga panumduman naghimo ako usa ka format nga adunay gidak-on sa panid nga 512 bytes, usa ka pirma sa sinugdanan sa matag panid ug talagsaon nga mga numero sa rekord - usahay posible nga mabawi ang tanan nga datos gikan sa usa ka "glitched" nga flash drive pinaagi sa yano nga sunud-sunod nga pagbasa).

Depende sa mga buluhaton, ang format mahimong magamit nga walay mga pagbag-o sa mga flash drive gikan sa 128Kbit (16Kb) ngadto sa 1Gbit (128MB). Kung gusto, mahimo nimo kini gamiton sa mas dagkong mga chip, apan kinahanglan nimo nga ayohon ang gidak-on sa panid (Apan dinhi mitumaw na ang pangutana bahin sa posibilidad sa ekonomiya; dili makapadasig ang presyo sa dako nga volume nga NOR Flash).

Kung adunay usa nga makit-an ang format nga makapaikag ug gusto nga gamiton kini sa usa ka bukas nga proyekto, pagsulat, paningkamutan nako nga makit-an ang oras, polish ang code ug i-post kini sa github.

konklusyon

Sama sa imong nakita, sa katapusan ang format nahimo nga yano ug bisan boring.

Lisud nga ipakita ang ebolusyon sa akong punto sa panglantaw sa usa ka artikulo, apan tuohi ako: sa sinugdan gusto ko nga maghimo usa ka butang nga sopistikado, dili malaglag, nga makalahutay bisan sa usa ka nukleyar nga pagbuto sa duol. Bisan pa, ang katarungan (naglaum ako) midaog gihapon ug anam-anam nga nabalhin ang mga prayoridad padulong sa kayano ug kakomplikado.

Nasayop kaha ko? Oo, sigurado. Mahimong maayo, pananglitan, nga mipalit kami usa ka hugpong sa mga mubu nga kalidad nga microcircuits. O alang sa ubang mga rason nga ang mga ekipo dili makaabot sa kasaligan nga mga gilauman.

Duna ba koy plano niini? Sa akong hunahuna nga pagkahuman sa pagbasa sa artikulo wala ka magduhaduha nga adunay usa ka plano. Ug dili gani nag-inusara.

Sa usa ka gamay nga mas seryoso nga nota, ang pormat gihimo ingon nga usa ka opsyon sa pagtrabaho ug ingon nga usa ka "trial balloon".

Sa pagkakaron ang tanan nga anaa sa lamesa nagtrabaho pag-ayo, sa literal sa laing adlaw ang solusyon ipakatap (gibanabana) sa gatusan ka mga himan, atong tan-awon kon unsa ang mahitabo sa "kombat" nga operasyon (maayo na lang, nanghinaut ko nga ang format nagtugot kanimo nga masaligan nga makamatikod sa mga kapakyasan; aron makolekta nimo ang bug-os nga estadistika). Sa pipila ka mga bulan posible nga maghimo mga konklusyon (ug kung malas ka, mas sayo pa).

Kung, base sa mga resulta sa paggamit, ang mga seryoso nga problema nakit-an ug ang mga pag-uswag gikinahanglan, nan siguradong isulat ko kini.

Literatura

Dili ko gusto nga maghimo usa ka taas nga makapakapoy nga lista sa gigamit nga mga buhat; pagkahuman, ang tanan adunay Google.

Dinhi nakahukom ko nga ibilin ang usa ka lista sa mga nahibal-an nga ingon labi ka makapaikag alang kanako, apan anam-anam nga mibalhin sila direkta sa teksto sa artikulo, ug usa ka butang ang nagpabilin sa lista:

Gamit infgen gikan sa tagsulat zlib. Mahimong tin-aw nga ipakita ang mga sulud sa deflate/zlib/gzip archive. Kung kinahanglan nimo nga atubangon ang internal nga istruktura sa deflate (o gzip) nga format, girekomenda ko kini.

Source: www.habr.com

Ang akong pagpatuman sa usa ka ring buffer sa NOR flash