AizvÄsture
Ir mÅ«su paÅ”u dizaina tirdzniecÄ«bas automÄti. Raspberry Pi iekÅ”pusÄ un daži vadi uz atseviŔķas plates. Ir pieslÄgts monÄtu pieÅÄmÄjs, vekseļu akceptors, bankas terminÄlis... Visu vada paÅ”u rakstÄ«ta programma. Visa darba vÄsture tiek ierakstÄ«ta žurnÄlÄ zibatmiÅas diskÄ (MicroSD), kas pÄc tam tiek pÄrsÅ«tÄ«ta caur internetu (izmantojot USB modemu) uz serveri, kur tÄ tiek saglabÄta datu bÄzÄ. PÄrdoÅ”anas informÄcija tiek ielÄdÄta 1c, ir arÄ« vienkÄrÅ”s tÄ«mekļa interfeiss uzraudzÄ«bai utt.
Tas ir, žurnÄls ir vitÄli svarÄ«gs - grÄmatvedÄ«bai (ieÅÄmumi, pÄrdoÅ”ana utt.), UzraudzÄ«bai (visa veida neveiksmes un citi nepÄrvaramas varas apstÄkļi); TÄ, varÄtu teikt, ir visa informÄcija, kas mums ir par Å”o iekÄrtu.
problÄma
ZibatmiÅas diski parÄda sevi kÄ Ä¼oti neuzticamas ierÄ«ces. ViÅiem neizdodas ar apskaužamu regularitÄti. Tas noved gan pie maŔīnas dÄ«kstÄves, gan (ja kÄda iemesla dÄļ žurnÄlu nevarÄja pÄrsÅ«tÄ«t tieÅ”saistÄ) pie datu zuduma.
Å Ä« nav pirmÄ pieredze ar zibatmiÅu lietoÅ”anu, pirms tam bija vÄl viens projekts ar vairÄk nekÄ simts ierÄ«cÄm, kur žurnÄls tika glabÄts USB zibatmiÅÄs, bija arÄ« problÄmas ar uzticamÄ«bu, brīžiem to skaits, kas neizdevÄs mÄnesis bija desmitos. MÄs izmÄÄ£inÄjÄm dažÄdus zibatmiÅas diskus, tostarp zÄ«molus ar SLC atmiÅu, un daži modeļi ir uzticamÄki nekÄ citi, taÄu zibatmiÅas disku nomaiÅa problÄmu radikÄli neatrisinÄja.
UzmanÄ«bu! Ilgi lasÄ«ts! Ja jÅ«s neinteresÄ ākÄpÄcā, bet tikai ākÄā, varat iet taisni raksti.
Å Ä·Ä«dums
PirmÄ lieta, kas nÄk prÄtÄ, ir: atsakieties no MicroSD, instalÄjiet, piemÄram, SSD un sÄknÄjiet no tÄ. TeorÄtiski iespÄjams, iespÄjams, bet salÄ«dzinoÅ”i dÄrgs un ne tik uzticams (pievienots USB-SATA adapteris; budžeta SSD kļūmju statistika arÄ« nav iepriecinoÅ”a).
USB HDD arÄ« neizskatÄs Ä«paÅ”i pievilcÄ«gs risinÄjums.
TÄpÄc mÄs nonÄcÄm pie Å”Ädas iespÄjas: atstÄjiet sÄknÄÅ”anu no MicroSD, bet izmantojiet tos tikai lasÄ«Å”anas režīmÄ un saglabÄjiet operÄciju žurnÄlu (un citu informÄciju, kas ir unikÄla konkrÄtai aparatÅ«ras daļai - sÄrijas numuru, sensoru kalibrÄÅ”anu utt.) kaut kur citur. .
TÄma par tikai lasÄmu FS avenÄm jau ir pÄtÄ«ta gan iekÅ”pusÄ, gan ÄrpusÄ, Å”ajÄ rakstÄ es nekavÄÅ”os pie ievieÅ”anas detaļÄm (bet ja bÅ«s interese, varbÅ«t uztaisÄ«Å”u kÄdu mini rakstu par Å”o tÄmu). VienÄ«gais, ko es vÄlÄtos atzÄ«mÄt, ir tas, ka gan no personÄ«gÄs pieredzes, gan no to lietotÄju atsauksmÄm, kuri to jau ir ieviesuÅ”i, ir palielinÄta uzticamÄ«ba. JÄ, nav iespÄjams pilnÄ«bÄ atbrÄ«voties no bojÄjumiem, taÄu ir pilnÄ«gi iespÄjams ievÄrojami samazinÄt to biežumu. Un kartes kļūst vienotas, kas ievÄrojami atvieglo nomaiÅu apkalpojoÅ”ajam personÄlam.
Aparatūra
ÄŖpaÅ”u Å”aubu par atmiÅas veida izvÄli - NOR Flash - nebija.
Argumenti:
- vienkÄrÅ”s savienojums (visbiežÄk SPI kopne, kuras lietoÅ”anÄ jau ir pieredze, tÄpÄc aparatÅ«ras problÄmas nav paredzÄtas);
- smieklīga cena;
- standarta darbÄ«bas protokols (ievieÅ”ana jau ir Linux kodolÄ, ja vÄlaties, varat paÅemt treÅ”Äs puses, kas arÄ« ir klÄt, vai pat uzrakstÄ«t savu, par laimi viss ir vienkÄrÅ”i);
- uzticamība un resursi:
no tipiskas datu lapas: dati tiek glabÄti 20 gadus, 100000 XNUMX dzÄÅ”anas ciklu katram blokam;
no treÅ”o puÅ”u avotiem: ÄrkÄrtÄ«gi zems BER, postulÄ, ka nav nepiecieÅ”ami kļūdu laboÅ”anas kodi (dažos darbos ECC tiek uzskatÄ«ts par NOR, bet parasti tie joprojÄm nozÄ«mÄ MLC NOR; tas arÄ« notiek).
NovÄrtÄsim prasÄ«bas apjomam un resursiem.
Es vÄlÄtos, lai dati tiktu garantÄti saglabÄti vairÄkas dienas. Tas nepiecieÅ”ams, lai jebkÄdu komunikÄcijas problÄmu gadÄ«jumÄ netiktu zaudÄta pÄrdoÅ”anas vÄsture. Å ajÄ periodÄ mÄs koncentrÄsimies uz 5 dienÄm (pat Åemot vÄrÄ nedÄļas nogales un svÄtku dienas) problÄmu var atrisinÄt.
Å obrÄ«d savÄcam ap 100kb žurnÄlu dienÄ (3-4 tÅ«kstoÅ”i ierakstu), bet pamazÄm Å”is skaitlis aug - pieaug detalizÄcija, tiek pievienoti jauni notikumi. TurklÄt dažreiz ir pÄrrÄvumi (piemÄram, daži sensori sÄk surogÄtpasta ziÅojumus ar viltus pozitÄ«viem rezultÄtiem). MÄs aprÄÄ·inÄsim 10 tÅ«kstoÅ”iem ierakstu pa 100 baiti katram - megabaiti dienÄ.
KopumÄ iznÄk 5 MB tÄ«ru (labi saspiestu) datu. VairÄk viÅiem (aptuvens aprÄÄ·ins) 1 MB pakalpojumu datu.
Tas nozÄ«mÄ, ka mums ir nepiecieÅ”ama 8 MB mikroshÄma, ja neizmantojam saspieÅ”anu, vai 4 MB, ja to izmantojam. Diezgan reÄli skaitļi Å”Äda veida atmiÅai.
Kas attiecas uz resursu: ja plÄnojam, ka visa atmiÅa tiks pÄrrakstÄ«ta ne biežÄk kÄ reizi 5 dienÄs, tad 10 gadu kalpoÅ”anas laikÄ mÄs saÅemam mazÄk par tÅ«kstoti pÄrrakstÄ«Å”anas ciklu.
AtgÄdinÄÅ”u, ka ražotÄjs sola simts tÅ«kstoÅ”us.
Mazliet par NOR vs NAND
MÅ«sdienÄs, protams, NAND atmiÅa ir daudz populÄrÄka, taÄu es to neizmantotu Å”im projektam: NAND, atŔķirÄ«bÄ no NOR, obligÄti pieprasa kļūdu laboÅ”anas kodus, sliktu bloku tabulu utt., kÄ arÄ« kÄjas NAND mikroshÄmas parasti ir daudz vairÄk.
NOR trūkumi ietver:
- mazs apjoms (un attiecīgi augsta cena par megabaitu);
- zems sakaru Ätrums (lielÄkoties tÄpÄc, ka tiek izmantots seriÄlais interfeiss, parasti SPI vai I2C);
- lÄna dzÄÅ”ana (atkarÄ«bÄ no bloka lieluma tas aizÅem no sekundes daļas lÄ«dz vairÄkÄm sekundÄm).
Å Ä·iet, ka mums nekÄ kritiska nav, tÄpÄc turpinÄm.
Ja detaļas ir interesantas, mikroshÄma ir izvÄlÄta (tomÄr tas nav svarÄ«gi, tirgÅ« ir daudz analogu, kas ir savietojams ar pinout un komandu sistÄmu; pat ja mÄs vÄlamies instalÄt cita ražotÄja un/vai cita izmÄra mikroshÄmu, viss darbosies, nemainot kods).
Es izmantoju Linux kodolÄ iebÅ«vÄto draiveri, Raspberry, pateicoties ierÄ«Äu koka pÄrklÄjuma atbalstam, viss ir ļoti vienkÄrÅ”i - jums ir jÄievieto kompilÄtais pÄrklÄjums /boot/overlays un nedaudz jÄpÄrveido /boot/config.txt.
Dts faila piemÄrs
GodÄ«gi sakot, es neesmu pÄrliecinÄts, ka tas ir uzrakstÄ«ts bez kļūdÄm, bet tas darbojas.
/*
* 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?";
};
};Un vÄl viena rindiÅa failÄ config.txt
dtoverlay=at25:spimaxfrequency=50000000Es izlaidÄ«Å”u aprakstu par mikroshÄmas savienoÅ”anu ar Raspberry Pi. No vienas puses, es neesmu elektronikas eksperts, no otras puses, viss Å”eit ir banÄls pat man: mikroshÄmai ir tikai 8 kÄjas, no kurÄm mums ir nepiecieÅ”ams zemÄjums, jauda, āāSPI (CS, SI, SO, SCK ); lÄ«meÅi ir tÄdi paÅ”i kÄ Raspberry Pi, nav nepiecieÅ”ama papildu elektroinstalÄcija - vienkÄrÅ”i pievienojiet norÄdÄ«tos 6 kontaktus.
ProblÄmas paziÅojums
KÄ parasti, problÄmas paziÅojums iziet cauri vairÄkÄm iterÄcijÄm, un man Ŕķiet, ka ir pienÄcis laiks nÄkamajam. TÄpÄc apstÄsimies, saliksim kopÄ jau uzrakstÄ«to un precizÄsim detaļas, kas paliek ÄnÄ.
TÄtad, mÄs esam nolÄmuÅ”i, ka žurnÄls tiks saglabÄts SPI NOR Flash.
Kas ir NOR Flash tiem, kas nezina?
Å Ä« ir nemainÄ«ga atmiÅa, ar kuru varat veikt trÄ«s darbÄ«bas:
- LasīŔana:
VisizplatÄ«tÄkais lasÄ«jums: mÄs pÄrsÅ«tÄm adresi un nolasÄm tik daudz baitu, cik mums nepiecieÅ”ams; - Ieraksts:
RakstÄ«Å”ana uz NOR zibspuldzi izskatÄs kÄ parasta, taÄu tai ir viena Ä«patnÄ«ba: jÅ«s varat mainÄ«t tikai no 1 uz 0, bet ne otrÄdi. PiemÄram, ja mums atmiÅas ŔūnÄ bija 0x55, tad pÄc 0x0f ierakstÄ«Å”anas tajÄ jau tiks saglabÄts 0x05 (skatiet tabulu tieÅ”i zemÄk); - DzÄst:
Protams, mums ir jÄspÄj veikt pretÄju darbÄ«bu - mainiet 0 uz 1, tieÅ”i tam ir paredzÄta dzÄÅ”anas darbÄ«ba. AtŔķirÄ«bÄ no pirmajiem diviem, tas darbojas nevis ar baitiem, bet ar blokiem (minimÄlais dzÄÅ”anas bloks izvÄlÄtajÄ mikroshÄmÄ ir 4kb). DzÄÅ”ana iznÄ«cina visu bloku un ir vienÄ«gais veids, kÄ mainÄ«t 0 uz 1. TÄpÄc, strÄdÄjot ar zibatmiÅu, bieži ir jÄsaskaÅo datu struktÅ«ras ar dzÄÅ”anas bloka robežu.
Ieraksts NOR Flash:
BinÄrie dati
Bija
01010101
Ierakstīts
00001111
Kļuvis
00000101
Pats žurnÄls ir mainÄ«ga garuma ierakstu secÄ«ba. Tipisks ieraksta garums ir aptuveni 30 baiti (lai gan dažkÄrt gadÄs ieraksti, kuru garums ir vairÄki kilobaiti). Å ajÄ gadÄ«jumÄ mÄs strÄdÄjam ar tiem vienkÄrÅ”i kÄ baitu kopu, bet, ja jÅ«s interesÄ, ierakstos tiek izmantots CBOR
Papildus žurnÄlam mums ir jÄsaglabÄ zinÄma āiestatÄ«jumaā informÄcija, gan atjauninÄta, gan ne: noteikts ierÄ«ces ID, sensoru kalibrÄÅ”ana, karodziÅÅ” āierÄ«ce ir Ä«slaicÄ«gi atspÄjotaā utt.
Å Ä« informÄcija ir atslÄgas vÄrtÄ«bu ierakstu kopa, kas tiek glabÄta arÄ« CBOR. Mums nav daudz Ŕīs informÄcijas (ne vairÄk kÄ daži kilobaiti), un tÄ tiek reti atjauninÄta.
TÄlÄk mÄs to sauksim par kontekstu.
Ja atceramies, kur Å”is raksts sÄkÄs, ļoti svarÄ«gi ir nodroÅ”inÄt uzticamu datu uzglabÄÅ”anu un, ja iespÄjams, nepÄrtrauktu darbÄ«bu pat aparatÅ«ras kļūmju/datu bojÄjumu gadÄ«jumÄ.
KÄdus problÄmu avotus var uzskatÄ«t?
- IzslÄdziet rakstÄ«Å”anas/dzÄÅ”anas darbÄ«bu laikÄ. Tas ir no kategorijas ānav nekÄda trika pret lauzniā.
InformÄcija no stackexchange: kad strÄva tiek izslÄgta, strÄdÄjot ar zibspuldzi, gan dzÄÅ”ana (iestatÄ«ts uz 1), gan rakstÄ«Å”ana (iestatÄ«ts uz 0) noved pie nedefinÄtas darbÄ«bas: datus var rakstÄ«t, daļÄji rakstÄ«t (teiksim, mÄs pÄrsÅ«tÄ«jÄm 10 baitus/80 bitus , bet vÄl nevar ierakstÄ«t tikai 45 bitus), iespÄjams, ka daži biti bÅ«s āstarpÄjÄā stÄvoklÄ« (lasot var iegÅ«t gan 0, gan 1); - Kļūdas paÅ”Ä zibatmiÅÄ.
BER, lai arÄ« ļoti zems, nevar bÅ«t vienÄds ar nulli; - Autobusu kļūdas
Dati, kas tiek pÄrraidÄ«ti, izmantojot SPI, netiek nekÄdÄ veidÄ aizsargÄti, var rasties gan viena bita kļūdas, gan sinhronizÄcijas kļūdas - bitu pazaudÄÅ”ana vai ievietoÅ”ana (kas noved pie masveida datu kropļojumiem); - Citas kļūdas/kļūmes
Kļūdas kodÄ, Raspberry kļūmes, citplanÄtieÅ”u iejaukÅ”anÄs...
Esmu formulÄjis prasÄ«bas, kuru izpilde, manuprÄt, ir nepiecieÅ”ama uzticamÄ«bas nodroÅ”inÄÅ”anai:
- ierakstiem nekavÄjoties jÄiet zibatmiÅÄ, aizkavÄtie ieraksti netiek Åemti vÄrÄ; - ja rodas kļūda, tÄ ir jÄatklÄj un jÄapstrÄdÄ pÄc iespÄjas ÄtrÄk; - sistÄmai pÄc iespÄjas jÄatgÅ«stas no kļūdÄm.
(piemÄrs no dzÄ«ves ākÄ tam nevajadzÄtu bÅ«tā, ar ko, manuprÄt, ir nÄcies sastapties: pÄc avÄrijas atsÄknÄÅ”anas failu sistÄma ir āsalauztaā un operÄtÄjsistÄma neboot)
Idejas, pieejas, pÄrdomas
Kad sÄku domÄt par Å”o problÄmu, manÄ galvÄ pavÄ«dÄja daudzas idejas, piemÄram:
- izmantot datu kompresiju;
- izmantot gudras datu struktÅ«ras, piemÄram, ierakstu galvenes glabÄt atseviŔķi no paÅ”iem ierakstiem, lai, ja kÄdÄ ierakstÄ ir kļūda, pÄrÄjos varÄtu nolasÄ«t bez problÄmÄm;
- izmantojiet bitu laukus, lai kontrolÄtu ierakstÄ«Å”anas pabeigÅ”anu, kad baroÅ”ana ir izslÄgta;
- uzglabÄt kontrolsummas par visu;
- izmantojiet kÄda veida trokÅ”Åu izturÄ«gu kodÄÅ”anu.
Dažas no Ŕīm idejÄm tika izmantotas, bet citas tika nolemtas atteikties. Ejam kÄrtÄ«bÄ.
Datu saspieŔana
PaÅ”i notikumi, ko mÄs ierakstÄm žurnÄlÄ, ir diezgan lÄ«dzÄ«gi un atkÄrtojami (āiemeta 5 rubļu monÄtuā, ānospieda naudas doÅ”anas poguā, ...). TÄpÄc kompresijai vajadzÄtu bÅ«t diezgan efektÄ«vai.
Kompresijas slodze ir nenozÄ«mÄ«ga (mÅ«su procesors ir diezgan jaudÄ«gs, pat pirmajam Pi bija viens kodols ar frekvenci 700 MHz, paÅ”reizÄjiem modeļiem ir vairÄki kodoli ar frekvenci virs gigaherciem), maiÅas kurss ar krÄtuvi ir zems (vairÄki megabaiti sekundÄ), ierakstu izmÄrs ir mazs. KopumÄ, ja saspieÅ”ana ietekmÄ veiktspÄju, tÄ bÅ«s tikai pozitÄ«va. (pilnÄ«gi nekritiski, tikai paziÅoju). TurklÄt mums nav Ä«sts iegultais, bet parasts Linux - tÄpÄc ievieÅ”anai nevajadzÄtu prasÄ«t daudz pūļu (pietiek tikai saistÄ«t bibliotÄku un izmantot vairÄkas no tÄs funkcijas).
ŽurnÄla gabals tika izÅemts no darba ierÄ«ces (1.7 MB, 70 tÅ«kstoÅ”i ierakstu) un vispirms tika pÄrbaudÄ«ta saspiežamÄ«ba, izmantojot datorÄ pieejamos gzip, lz4, lzop, bzip2, xz, zstd.
- gzip, xz, zstd uzrÄdÄ«ja lÄ«dzÄ«gus rezultÄtus (40Kb).
Biju pÄrsteigts, ka modÄ«gais xz Å”eit sevi parÄdÄ«ja gzip vai zstd lÄ«menÄ«; - lzip ar noklusÄjuma iestatÄ«jumiem sniedza nedaudz sliktÄkus rezultÄtus;
- lz4 un lzop uzrÄdÄ«ja ne pÄrÄk labus rezultÄtus (150Kb);
- bzip2 uzrÄdÄ«ja pÄrsteidzoÅ”i labu rezultÄtu (18Kb).
TÄtad dati ir ļoti labi saspiesti.
TÄtad (ja neatradÄ«sim liktenÄ«gus trÅ«kumus) bÅ«s saspieÅ”ana! VienkÄrÅ”i tÄpÄc, ka tajÄ paÅ”Ä zibatmiÅas diskÄ var ievietot vairÄk datu.
PadomÄsim par trÅ«kumiem.
PirmÄ problÄma: mÄs jau esam vienojuÅ”ies, ka katram ierakstam nekavÄjoties jÄiet uz mirgoÅ”anu. Parasti arhivÄtÄjs apkopo datus no ievades straumes, lÄ«dz nolemj, ka ir pienÄcis laiks rakstÄ«t nedÄļas nogalÄ. Mums nekavÄjoties jÄsaÅem saspiests datu bloks un jÄsaglabÄ tas nemainÄ«gÄ atmiÅÄ.
Es redzu trīs veidus:
- Saspiediet katru ierakstu, izmantojot vÄrdnÄ«cas saspieÅ”anu, nevis iepriekÅ” aprakstÄ«tos algoritmus.
Tas ir pilnÄ«gi strÄdÄjoÅ”s variants, bet man tas nepatÄ«k. Lai nodroÅ”inÄtu vairÄk vai mazÄk pienÄcÄ«gu saspieÅ”anas lÄ«meni, vÄrdnÄ«cai jÄbÅ«t āpielÄgotaiā konkrÄtiem datiem; jebkuras izmaiÅas novedÄ«s pie saspieÅ”anas lÄ«meÅa katastrofÄlas pazeminÄÅ”anÄs. JÄ, problÄmu var atrisinÄt, izveidojot jaunu vÄrdnÄ«cas versiju, taÄu tas sagÄdÄ galvassÄpes ā mums bÅ«s jÄsaglabÄ visas vÄrdnÄ«cas versijas; katrÄ ierakstÄ mums bÅ«s jÄnorÄda, ar kuru vÄrdnÄ«cas versiju tÄ tika saspiesta... - Saspiest katru ierakstu, izmantojot āklasiskosā algoritmus, taÄu neatkarÄ«gi no citiem.
ApskatÄmie saspieÅ”anas algoritmi nav paredzÄti darbam ar Å”Äda izmÄra ierakstiem (desmitiem baitu), saspieÅ”anas pakÄpe nepÄrprotami bÅ«s mazÄka par 1 (tas ir, datu apjoma palielinÄÅ”ana, nevis saspieÅ”ana); - PÄc katra ieraksta veiciet FLUSH.
Daudzas saspieÅ”anas bibliotÄkas atbalsta FLUSH. Å Ä« ir komanda (vai saspieÅ”anas procedÅ«ras parametrs), pÄc kuras saÅemÅ”anas arhivÄtÄjs veido saspiestu straumi, lai to varÄtu izmantot atjaunoÅ”anai viss nesaspiesti dati, kas jau ir saÅemti. TÄds analogssyncfailu sistÄmÄs vaicommitSQL formÄtÄ.
SvarÄ«gi ir tas, ka turpmÄkajÄs saspieÅ”anas operÄcijÄs varÄs izmantot uzkrÄto vÄrdnÄ«cu un saspieÅ”anas pakÄpe necietÄ«s tik daudz kÄ iepriekÅ”ÄjÄ versijÄ.
Es domÄju, ka ir skaidrs, ka es izvÄlÄjos treÅ”o iespÄju, apskatÄ«sim to sÄ«kÄk.
Atrasts par FLUSH zlib.
Es veicu ceļgala pÄrbaudi, pamatojoties uz rakstu, paÅÄmu 70 tÅ«kstoÅ”us žurnÄla ierakstu no reÄlas ierÄ«ces ar lapas izmÄru 60Kb (pie lapas izmÄra atgriezÄ«simies vÄlÄk) saÅÄma:
NeapstrÄdÄti dati
SaspieŔana gzip -9 (bez FLUSH)
zlib ar Z_PARTIAL_FLUSH
zlib ar Z_SYNC_FLUSH
Apjoms, KB
1692
40
352
604
No pirmÄ acu uzmetiena FLUSH piedÄvÄtÄ cena ir pÄrmÄrÄ«gi augsta, bet patiesÄ«bÄ mums ir maz izvÄles - vai nu nesaspiest vispÄr, vai arÄ« saspiest (un ļoti efektÄ«vi) ar FLUSH. MÄs nedrÄ«kstam aizmirst, ka mums ir 70 tÅ«kstoÅ”i ierakstu, Z_PARTIAL_FLUSH ieviestÄ dublÄÅ”ana ir tikai 4-5 baiti uz ierakstu. Un kompresijas pakÄpe izrÄdÄ«jÄs gandrÄ«z 5: 1, kas ir vairÄk nekÄ lielisks rezultÄts.
Tas var bÅ«t pÄrsteigums, taÄu Z_SYNC_FLUSH patiesÄ«bÄ ir efektÄ«vÄks veids, kÄ veikt FLUSH
Izmantojot Z_SYNC_FLUSH, katra ieraksta pÄdÄjie 4 baiti vienmÄr bÅ«s 0x00, 0x00, 0xff, 0xff. Un, ja mÄs tos zinÄm, tad mums tie nav jÄuzglabÄ, tÄpÄc galÄ«gais izmÄrs ir tikai 324 Kb.
Rakstam, uz kuru es pievienoju saiti, ir paskaidrojums:
Tiek pievienots jauns 0 tipa bloks ar tukŔu saturu.
0 tipa bloks ar tukÅ”u saturu sastÄv no:
- trīs bitu bloka galvene;
- 0 lÄ«dz 7 biti, kas vienÄdi ar nulli, lai panÄktu baitu izlÄ«dzinÄÅ”anu;
- Äetru baitu secÄ«ba 00 00 FF FF.
KÄ jÅ«s viegli varat redzÄt, pÄdÄjÄ blokÄ pirms Å”iem 4 baitiem ir no 3 lÄ«dz 10 nulles bitiem. TomÄr prakse ir parÄdÄ«jusi, ka patiesÄ«bÄ ir vismaz 10 nulles biti.
IzrÄdÄs, ka Å”Ädi Ä«si datu bloki parasti (vienmÄr?) tiek kodÄti, izmantojot 1. tipa bloku (fiksÄto bloku), kas obligÄti beidzas ar 7 nulles bitiem, kopÄ dodot 10-17 garantÄtus nulles bitus (un pÄrÄjie bÅ«s bÅ«t nulle ar varbÅ«tÄ«bu aptuveni 50%).
TÄtad testa datos 100% gadÄ«jumu pirms 0x00, 0x00, 0xff, 0xff ir viens nulles baits, un vairÄk nekÄ treÅ”daÄ¼Ä gadÄ«jumu ir divi nulles baiti. (iespÄjams, fakts ir tÄds, ka es izmantoju binÄro CBOR, un, izmantojot teksta JSON, biežÄk bÅ«tu 2. tipa bloki - dinamiskais bloks, attiecÄ«gi, tiktu sastapti bloki bez papildu nulles baitiem pirms 0x00, 0x00, 0xff, 0xff).
KopumÄ, izmantojot pieejamos testa datus, iespÄjams iekļauties mazÄk nekÄ 250Kb saspiestos datos.
Nedaudz vairÄk var ietaupÄ«t, veicot bitu žonglÄÅ”anu: pagaidÄm mÄs ignorÄjam dažu nulles bitu klÄtbÅ«tni bloka beigÄs, daži biti bloka sÄkumÄ arÄ« nemainÄs...
Bet tad es pieÅÄmu stingru lÄmumu apstÄties, pretÄjÄ gadÄ«jumÄ Å”ÄdÄ tempÄ es varÄtu izstrÄdÄt savu arhivÄtÄju.
KopumÄ no maniem testa datiem es saÅÄmu 3-4 baitus vienÄ ierakstÄ, saspieÅ”anas pakÄpe izrÄdÄ«jÄs lielÄka par 6:1. TeikÅ”u godÄ«gi: nebiju gaidÄ«jis tÄdu rezultÄtu, manuprÄt, viss labÄks par 2:1 jau ir rezultÄts, kas attaisno kompresijas lietoÅ”anu.
Viss ir kÄrtÄ«bÄ, bet zlib (deflate) joprojÄm ir arhaisks, pelnÄ«ts un nedaudz vecmodÄ«gs kompresijas algoritms. Tas vien, ka pÄdÄjie 32 Kb nesaspiestÄs datu straumes tiek izmantoti kÄ vÄrdnÄ«ca, Å”odien izskatÄs dÄ«vaini (tas ir, ja kÄds datu bloks ir ļoti lÄ«dzÄ«gs tam, kas bija ievades straumÄ pirms 40 Kb, tad to atkal sÄks arhivÄt, un neattieksies uz iepriekÅ”Äju notikumu). Modernajos arhivÄtajos vÄrdnÄ«cas lielums bieži tiek mÄrÄ«ts megabaitos, nevis kilobaitos.
TÄpÄc mÄs turpinÄm savu arhivÄtÄju mini pÄtÄ«jumu.
TÄlÄk mÄs pÄrbaudÄ«jÄm bzip2 (atcerieties, bez FLUSH tas uzrÄdÄ«ja fantastisku kompresijas pakÄpi gandrÄ«z 100:1). DiemžÄl ar FLUSH tas darbojÄs ļoti slikti; saspiesto datu izmÄrs izrÄdÄ«jÄs lielÄks nekÄ nesaspiesto.
Mani pieÅÄmumi par neveiksmes iemesliem
Libbz2 piedÄvÄ tikai vienu skaloÅ”anas opciju, kas, Ŕķiet, notÄ«ra vÄrdnÄ«cu (analogs Z_FULL_FLUSH zlib); pÄc tam nav runas par efektÄ«vu saspieÅ”anu.
Un pÄdÄjais, kas tika pÄrbaudÄ«ts, bija zstd. AtkarÄ«bÄ no parametriem tas saspiež vai nu gzip lÄ«menÄ«, bet daudz ÄtrÄk vai labÄk nekÄ gzip.
DiemžÄl ar FLUSH tas nedarbojÄs Ä«paÅ”i labi: saspiesto datu apjoms bija aptuveni 700 Kb.
ŠÆ projekta github lapÄ saÅÄmu atbildi, ka katram saspiesto datu blokam jÄrÄÄ·inÄs ar lÄ«dz 10 baitiem servisa datu, kas ir tuvu iegÅ«tajiem rezultÄtiem; deflÄciju nevar panÄkt.
Es nolÄmu pie Ŕī punkta apstÄties savos eksperimentos ar arhivÄtÄjiem (atgÄdinÄÅ”u, ka xz, lzip, lzo, lz4 pat testÄÅ”anas stadijÄ bez FLUSH neparÄdÄ«jÄs, un es neuzskatÄ«ju par eksotiskÄkiem kompresijas algoritmiem).
AtgriezÄ«simies pie arhivÄÅ”anas problÄmÄm.
Otra (kÄ saka secÄ«bÄ, nevis vÄrtÄ«bÄ) problÄma ir tÄ, ka saspiestie dati ir viena straume, kurÄ pastÄvÄ«gi ir atsauces uz iepriekÅ”ÄjÄm sadaļÄm. TÄdÄjÄdi, ja tiek bojÄta saspiesto datu sadaļa, mÄs zaudÄjam ne tikai saistÄ«to nesaspiesto datu bloku, bet arÄ« visus nÄkamos.
Å Ä«s problÄmas risinÄÅ”anai ir Å”Äda pieeja:
- NovÄrsiet problÄmas raÅ”anos ā pievienojiet saspiestajiem datiem dublÄÅ”anos, kas ļaus identificÄt un labot kļūdas; mÄs par to runÄsim vÄlÄk;
- Samaziniet sekas, ja rodas problÄma
MÄs jau teicÄm iepriekÅ”, ka jÅ«s varat saspiest katru datu bloku neatkarÄ«gi, un problÄma pazudÄ«s pati (viena bloka datu bojÄjums novedÄ«s pie datu zuduma tikai Å”im blokam). TomÄr Å”is ir ÄrkÄrtÄjs gadÄ«jums, kad datu saspieÅ”ana bÅ«s neefektÄ«va. PretÄja galÄjÄ«ba: izmantojiet visus 4 MB mÅ«su mikroshÄmas kÄ vienotu arhÄ«vu, kas dos mums lielisku saspieÅ”anu, bet katastrofÄlas sekas datu bojÄjumu gadÄ«jumÄ.
JÄ, ir nepiecieÅ”ams kompromiss attiecÄ«bÄ uz uzticamÄ«bu. TaÄu jÄatceras, ka mÄs izstrÄdÄjam datu uzglabÄÅ”anas formÄtu nemainÄ«gai atmiÅai ar ÄrkÄrtÄ«gi zemu BER un deklarÄto datu glabÄÅ”anas periodu 20 gadi.
Eksperimentu laikÄ es atklÄju, ka vairÄk vai mazÄk pamanÄmi kompresijas lÄ«meÅa zudumi sÄkas saspiestu datu blokos, kuru izmÄrs ir mazÄks par 10 KB.
IepriekÅ” tika minÄts, ka izmantotÄ atmiÅa ir lappuse, es neredzu iemeslu, kÄpÄc nevajadzÄtu izmantot korespondenci āviena lapa - viens saspiestu datu bloksā.
Tas ir, minimÄlais pieÅemamais lapas izmÄrs ir 16 Kb (ar rezervi pakalpojuma informÄcijai). TomÄr tik mazs lapas izmÄrs uzliek ievÄrojamus ierobežojumus maksimÄlajam ieraksta izmÄram.
Lai gan es vÄl negaidu, ka saspiestÄ veidÄ ieraksti bÅ«s lielÄki par dažiem kilobaitiem, es nolÄmu izmantot 32 Kb lapas (kopÄ 128 lappuses vienÄ mikroshÄmÄ).
Kopsavilkums:
- MÄs uzglabÄjam datus, kas saspiesti, izmantojot zlib (deflate);
- Katram ierakstam mÄs iestatÄm Z_SYNC_FLUSH;
- Katram saspiestajam ierakstam mÄs apgriežam beigu baitus (piemÄram, 0x00, 0x00, 0xff, 0xff); galvenÄ norÄdÄm, cik baitu nogriezÄm;
- MÄs glabÄjam datus 32Kb lapÄs; lapas iekÅ”pusÄ ir viena saspiestu datu plÅ«sma; KatrÄ lapÄ mÄs atkal sÄkam saspieÅ”anu.
Un pirms saspieÅ”anas pabeigÅ”anas vÄlos vÄrst jÅ«su uzmanÄ«bu uz to, ka mums ir tikai daži baiti saspiestu datu uz vienu ierakstu, tÄpÄc ir ÄrkÄrtÄ«gi svarÄ«gi nepalielinÄt pakalpojuma informÄciju, jo katrs baits Å”eit ir svarÄ«gs.
Datu galvenes glabÄÅ”ana
TÄ kÄ mums ir mainÄ«ga garuma ieraksti, mums kaut kÄ jÄnosaka ierakstu izvietojums/robežas.
Es zinu trīs pieejas:
- Visi ieraksti tiek saglabÄti nepÄrtrauktÄ straumÄ, vispirms ir ieraksta galvene ar garumu un pÄc tam pats ieraksts.
Å ajÄ iemiesojumÄ gan galvenes, gan dati var bÅ«t dažÄda garuma.
BÅ«tÄ«bÄ mÄs iegÅ«stam atseviŔķi saistÄ«tu sarakstu, kas tiek izmantots visu laiku; - Galvenes un paÅ”i ieraksti tiek glabÄti atseviŔķÄs plÅ«smÄs.
Izmantojot nemainÄ«ga garuma galvenes, mÄs nodroÅ”inÄm, ka vienas galvenes bojÄjumi neietekmÄ pÄrÄjÄs.
LÄ«dzÄ«ga pieeja tiek izmantota, piemÄram, daudzÄs failu sistÄmÄs; - Ieraksti tiek glabÄti nepÄrtrauktÄ plÅ«smÄ, ieraksta robežu nosaka noteikts marÄ·ieris (rakstzÄ«me/rakstzÄ«mju secÄ«ba, kas ir aizliegta datu blokos). Ja ieraksta iekÅ”pusÄ ir marÄ·ieris, mÄs to aizstÄjam ar kÄdu secÄ«bu (aizveram to).
LÄ«dzÄ«ga pieeja tiek izmantota, piemÄram, PPP protokolÄ.
Es ilustrÄÅ”u.
Variants 1:
Å eit viss ir ļoti vienkÄrÅ”i: zinot ieraksta garumu, mÄs varam aprÄÄ·inÄt nÄkamÄs galvenes adresi. TÄtad mÄs virzÄmies pa virsrakstiem, lÄ«dz sastopam apgabalu, kas piepildÄ«ts ar 0xff (brÄ«vÄ zona) vai lapas beigÄm.
Variants 2:
MainÄ«ga ieraksta garuma dÄļ mÄs nevaram iepriekÅ” pateikt, cik ierakstu (un lÄ«dz ar to arÄ« galvenes) mums bÅ«s nepiecieÅ”ams vienÄ lapÄ. JÅ«s varat izkliedÄt galvenes un paÅ”us datus dažÄdÄs lapÄs, bet es dodu priekÅ”roku citai pieejai: mÄs ievietojam gan galvenes, gan datus vienÄ lapÄ, bet galvenes (konstanta izmÄra) nÄk no lapas sÄkuma, un dati (mainÄ«ga garuma) nÄk no beigÄm. TiklÄ«dz viÅi āsatiekasā (nav pietiekami daudz brÄ«vas vietas jaunam ierakstam), mÄs uzskatÄm, ka Ŕī lapa ir pabeigta.
Variants 3:
GalvenÄ nav nepiecieÅ”ams saglabÄt datu garumu vai citu informÄciju par datu atraÅ”anÄs vietu, pietiek ar marÄ·ieriem, kas norÄda ierakstu robežas. TaÄu dati ir jÄapstrÄdÄ rakstot/lasot.
Es izmantotu 0xff kÄ marÄ·ieri (kas pÄc dzÄÅ”anas aizpilda lapu), tÄpÄc brÄ«vÄ zona noteikti netiks uzskatÄ«ta par datiem.
SalÄ«dzinÄjuma tabula:
iespÄja 1
iespÄja 2
iespÄja 3
Kļūdu tolerance
SÄkot no
+
+
Kompaktums
+
SÄkot no
+
ÄŖstenoÅ”anas sarežģītÄ«ba
*
**
**
1. variantam ir liktenÄ«gs trÅ«kums: ja kÄda no galvenÄm ir bojÄta, tiek iznÄ«cinÄta visa nÄkamÄ Ä·Äde. AtlikuÅ”Äs opcijas ļauj atgÅ«t dažus datus pat lielu bojÄjumu gadÄ«jumÄ.
Bet Å”eit der atcerÄties, ka mÄs nolÄmÄm datus glabÄt saspiestÄ formÄ, un tÄpÄc mÄs zaudÄjam visus lapas datus pÄc āsalauztaā ieraksta, tÄpÄc, lai arÄ« tabulÄ ir mÄ«nuss, mÄs to nedarÄm. Åemt to vÄrÄ.
Kompaktums:
- pirmajÄ variantÄ galvenÄ jÄsaglabÄ tikai garums, ja izmantojam mainÄ«ga garuma veselus skaitļus, tad vairumÄ gadÄ«jumu varam iztikt ar vienu baitu;
- otrajÄ variantÄ mums jÄsaglabÄ sÄkuma adrese un garums; ierakstam jÄbÅ«t nemainÄ«gam izmÄram, es lÄÅ”u, ka katram ierakstam ir 4 baiti (divi baiti nobÄ«dei un divi baiti garumam);
- treÅ”ajai opcijai nepiecieÅ”ama tikai viena rakstzÄ«me, lai norÄdÄ«tu ieraksta sÄkumu, kÄ arÄ« pats ieraksts palielinÄsies par 1-2% ekranÄÅ”anas dÄļ. KopumÄ aptuveni paritÄte ar pirmo variantu.
SÄkotnÄji es uzskatÄ«ju otro variantu par galveno (un pat uzrakstÄ«ju ievieÅ”anu). Es to pametu tikai tad, kad beidzot nolÄmu izmantot kompresiju.
VarbÅ«t kÄdreiz es joprojÄm izmantoÅ”u lÄ«dzÄ«gu iespÄju. PiemÄram, ja man ir jÄnodarbojas ar datu glabÄÅ”anu kuÄ£im, kas ceļo starp Zemi un Marsu, bÅ«s pavisam citas prasÄ«bas attiecÄ«bÄ uz uzticamÄ«bu, kosmisko starojumu, ...
Kas attiecas uz treÅ”o variantu: es tam pieŔķīru divas zvaigznes par ievieÅ”anas grÅ«tÄ«bÄm vienkÄrÅ”i tÄpÄc, ka man nepatÄ«k jaukties ar vairogu, mainÄ«t garumu procesÄ utt. JÄ, iespÄjams, esmu neobjektÄ«vs, bet man bÅ«s jÄieraksta kods ā kÄpÄc piespiest sevi darÄ«t kaut ko, kas jums nepatÄ«k.
Kopsavilkums: MÄs izvÄlamies uzglabÄÅ”anas iespÄju Ä·Äžu veidÄ āgalvene ar garumu - mainÄ«ga garuma datiā efektivitÄtes un ievieÅ”anas vienkÄrŔības dÄļ.
Bitu lauku izmantoÅ”ana, lai uzraudzÄ«tu rakstÄ«Å”anas darbÄ«bu panÄkumus
Es tagad neatceros, kur man radÄs ideja, bet tas izskatÄs apmÄram Å”Ädi:
Katram ierakstam mÄs pieŔķiram vairÄkus bitus, lai saglabÄtu karogus.
KÄ jau teicÄm iepriekÅ”, pÄc dzÄÅ”anas visi biti tiek aizpildÄ«ti ar 1, un mÄs varam mainÄ«t 1 uz 0, bet ne otrÄdi. TÄtad ākarogs nav iestatÄ«tsā mÄs izmantojam 1, bet ākarogs ir iestatÄ«tsā mÄs izmantojam 0.
LÅ«k, kÄ varÄtu izskatÄ«ties mainÄ«ga garuma ieraksta ievietoÅ”ana zibatmiÅÄ:
- Iestatiet karogu āgaruma ieraksts ir sÄktsā;
- Pierakstiet garumu;
- Iestatiet karogu ādatu ierakstÄ«Å”ana ir sÄkusiesā;
- MÄs ierakstÄm datus;
- Iestatiet karodziÅu āierakstÄ«Å”ana beigusiesā.
TurklÄt mums bÅ«s karodziÅÅ” ānotikusi kļūdaā, kopumÄ 4 bitu karodziÅiem.
Å ajÄ gadÄ«jumÄ mums ir divi stabili stÄvokļi "1111" - ierakstÄ«Å”ana nav sÄkta un "1000" - ierakstÄ«Å”ana bija veiksmÄ«ga; neparedzÄta ierakstÄ«Å”anas procesa pÄrtraukuma gadÄ«jumÄ mÄs saÅemsim starpstÄvokli, kurus pÄc tam varÄsim atklÄt un apstrÄdÄt.
Pieeja ir interesanta, taÄu tÄ pasargÄ tikai no pÄkÅ”Åiem elektrÄ«bas padeves pÄrtraukumiem un lÄ«dzÄ«gÄm kļūmÄm, kas, protams, ir svarÄ«gi, taÄu tas nebÅ«t nav vienÄ«gais (vai pat galvenais) iespÄjamo kļūmju cÄlonis.
Kopsavilkums: Dosimies tÄlÄk, meklÄjot labu risinÄjumu.
Kontrolsummas
Kontrolsummas arÄ« ļauj pÄrliecinÄties (ar saprÄtÄ«gu varbÅ«tÄ«bu), ka mÄs lasÄm tieÅ”i to, kas bija rakstÄ«ts. Un atŔķirÄ«bÄ no iepriekÅ” apskatÄ«tajiem bitu laukiem tie vienmÄr darbojas.
Ja Åemam vÄrÄ iespÄjamo problÄmu avotu sarakstu, par kuru mÄs runÄjÄm iepriekÅ”, tad kontrolsumma spÄj atpazÄ«t kļūdu neatkarÄ«gi no tÄs izcelsmes. (izÅemot, iespÄjams, ļaunprÄtÄ«gos citplanÄtieÅ”us - viÅi var arÄ« viltot kontrolsummu).
TÄtad, ja mÅ«su mÄrÄ·is ir pÄrbaudÄ«t, vai dati ir neskarti, kontrolsummas ir lieliska ideja.
Kontrolsummas aprÄÄ·inÄÅ”anas algoritma izvÄle neradÄ«ja jautÄjumus - CRC. No vienas puses, matemÄtiskÄs Ä«paŔības ļauj 100% uztvert noteikta veida kļūdas, no otras puses, uz nejauÅ”iem datiem Å”is algoritms parasti parÄda sadursmju iespÄjamÄ«bu, kas nav daudz lielÄka par teorÄtisko robežu. . Tas var nebÅ«t ÄtrÄkais algoritms, ne vienmÄr tas ir minimÄlais sadursmju skaita ziÅÄ, taÄu tam ir ļoti svarÄ«ga kvalitÄte: testos, ar kuriem es saskÄros, nebija neviena modeļa, kurÄ tas nepÄrprotami bÅ«tu neveiksmÄ«gs. StabilitÄte Å”ajÄ gadÄ«jumÄ ir galvenÄ kvalitÄte.
Tilpuma pÄtÄ«juma piemÄrs: , (saites uz narod.ru, atvainojiet).
TomÄr kontrolsummas atlases uzdevums nav pabeigts; CRC ir vesela kontrolsummu saime. Jums jÄizlemj par garumu un pÄc tam jÄizvÄlas polinoms.
Kontrolsummas garuma izvÄle nav tik vienkÄrÅ”s jautÄjums, kÄ Å”Ä·iet no pirmÄ acu uzmetiena.
Ä»aujiet man ilustrÄt:
Noskaidrosim kļūdas iespÄjamÄ«bu katrÄ baitÄ un ideÄla kontrolsumma, aprÄÄ·inÄsim vidÄjo kļūdu skaitu uz miljonu ierakstu:
Dati, baits
Kontrolsumma, baits
NeatklÄtas kļūdas
Viltus kļūdu noteikŔana
KopÄjais viltus pozitÄ«vais rÄdÄ«tÄjs
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
Å Ä·iet, ka viss ir vienkÄrÅ”i - atkarÄ«bÄ no aizsargÄjamo datu garuma izvÄlieties kontrolsummas garumu ar minimÄlu nepareizu pozitÄ«vu skaitu - un triks ir maisÄ.
TomÄr problÄma rodas ar Ä«sÄm kontrolsummÄm: lai gan tÄs labi atklÄj viena bita kļūdas, tÄs ar diezgan lielu varbÅ«tÄ«bu var pieÅemt pilnÄ«gi nejauÅ”us datus kÄ pareizus. Par HabrÄ jau bija raksts, kurÄ bija aprakstÄ«ts .
TÄpÄc, lai nejauÅ”as kontrolsummas sakritÄ«ba bÅ«tu gandrÄ«z neiespÄjama, jums jÄizmanto kontrolsummas, kuru garums ir 32 biti vai ilgÄk. (ja garums ir lielÄks par 64 bitiem, parasti tiek izmantotas kriptogrÄfiskÄs jaucÄjfunkcijas).
Neskatoties uz to, ka iepriekÅ” rakstÄ«ju, ka mums ir nepiecieÅ”ams ietaupÄ«t vietu, mÄs joprojÄm izmantosim 32 bitu kontrolsummu (16 biti ir par maz, sadursmes iespÄjamÄ«ba ir lielÄka par 0.01% un 24 biti, jo tie saki, nav ne Å”eit, ne tur).
Å eit var rasties iebildums: vai, izvÄloties kompresiju, mÄs saglabÄjÄm katru baitu, lai tagad dotu 4 baitus uzreiz? Vai nebÅ«tu labÄk nesaspiest vai pievienot kontrolsummu? Protams, nÄ, bez kompresijas nenozÄ«mÄ, ka mums nav nepiecieÅ”ama integritÄtes pÄrbaude.
IzvÄloties polinomu, mÄs neizgudrosim riteni no jauna, bet Åemsim tagad populÄro CRC-32C.
Å is kods nosaka 6 bitu kļūdas paketÄs lÄ«dz 22 baitiem (iespÄjams, mums tas ir visizplatÄ«tÄkais gadÄ«jums), 4 bitu kļūdas paketÄs lÄ«dz 655 baitiem (pie mums arÄ« bieži), 2 vai jebkuru nepÄra skaitu bitu kļūdu paketÄs. jebkura saprÄtÄ«ga garuma.
Ja kÄdu interesÄ detaļas
par CRC.
par ā iespÄjams, vadoÅ”ais CRC speciÄlists uz planÄtas.
Š tur ir , kas nodroÅ”ina nedaudz labÄkus parametrus mums aktuÄlajiem pakeÅ”u garumiem, taÄu atŔķirÄ«bu neuzskatÄ«ju par bÅ«tisku un biju pietiekami kompetenta, lai izvÄlÄtos pielÄgotu kodu standarta un labi izpÄtÄ«tÄ koda vietÄ.
TurklÄt, tÄ kÄ mÅ«su dati ir saspiesti, rodas jautÄjums: vai mums jÄaprÄÄ·ina saspiesto vai nesaspiesto datu kontrolsumma?
Argumenti par labu nesaspiestu datu kontrolsummas aprÄÄ·inÄÅ”anai:
- Mums beigu beigÄs ir jÄpÄrbauda datu glabÄÅ”anas droŔība - tÄtad pÄrbaudÄm to tieÅ”i (vienlaikus tiks pÄrbaudÄ«tas iespÄjamÄs kļūdas kompresijas/dekompresijas realizÄcijÄ, bojÄtas atmiÅas radÄ«tie bojÄjumi utt.);
- DeflÄcijas algoritmam zlib ir diezgan nobriedusi ievieÅ”ana un nevajadzÄtu krÄ«t ar āgreiziemā ievades datiem; turklÄt bieži vien spÄj patstÄvÄ«gi atklÄt kļūdas ievades straumÄ, samazinot kopÄjo kļūdas neatklÄÅ”anas varbÅ«tÄ«bu (veikta pÄrbaude ar viena bita invertÄÅ”anu Ä«sajÄ ierakstÄ, zlib atklÄja kļūdu apmÄram treÅ”daÄ¼Ä gadÄ«jumu).
Argumenti pret nesaspiestu datu kontrolsummas aprÄÄ·inÄÅ”anu:
- CRC ir Ä«paÅ”i āpielÄgotsā dažÄm bitu kļūdÄm, kas raksturÄ«gas zibatmiÅai (bitu kļūda saspiestÄ straumÄ var izraisÄ«t lielas izmaiÅas izvades straumÄ, kurÄ tÄ«ri teorÄtiski mÄs varam ānoÄ·ertā sadursmi);
- Man ļoti nepatÄ«k ideja nodot potenciÄli bojÄtus datus dekompresoram, kÄ viÅÅ” reaÄ£Äs.
Å ajÄ projektÄ es nolÄmu atkÄpties no vispÄrpieÅemtÄs nesaspiestu datu kontrolsummas glabÄÅ”anas prakses.
Kopsavilkums: MÄs izmantojam CRC-32C, mÄs aprÄÄ·inÄm kontrolsummu no datiem tÄdÄ formÄ, kÄdÄ tie ir rakstÄ«ti uz flash (pÄc saspieÅ”anas).
AtlaiŔana
Liekas kodÄÅ”anas izmantoÅ”ana, protams, nenovÄrÅ” datu zudumu, tomÄr tÄ var ievÄrojami (bieži vien par daudzÄm kÄrtÄm) samazinÄt neatgriezeniska datu zuduma iespÄjamÄ«bu.
MÄs varam izmantot dažÄda veida dublÄÅ”anu, lai labotu kļūdas.
Hamminga kodi var labot viena bita kļūdas, RÄ«da-ZÄlamana rakstzÄ«mju kodus, vairÄkas datu kopijas apvienojumÄ ar kontrolsummÄm vai kodÄjumus, piemÄram, RAID-6, var palÄ«dzÄt atgÅ«t datus pat lielas korupcijas gadÄ«jumÄ.
SÄkotnÄji es biju apÅÄmies plaÅ”i izmantot kļūdÄm izturÄ«gu kodÄÅ”anu, bet tad es sapratu, ka mums vispirms ir nepiecieÅ”ams priekÅ”stats par to, no kÄdÄm kļūdÄm mÄs vÄlamies sevi pasargÄt, un pÄc tam izvÄlÄties kodÄÅ”anu.
IepriekÅ” teicÄm, ka kļūdas ir jÄnovÄrÅ” pÄc iespÄjas ÄtrÄk. KÄdos gadÄ«jumos mÄs varam saskarties ar kļūdÄm?
- Nepabeigts ieraksts (kÄdu iemeslu dÄļ ierakstÄ«Å”anas laikÄ strÄva tika izslÄgta, Raspberry sastinga, ...)
DiemžÄl Å”Ädas kļūdas gadÄ«jumÄ atliek tikai ignorÄt nederÄ«gos ierakstus un uzskatÄ«t, ka dati ir zaudÄti; - RakstÄ«Å”anas kļūdas (kÄdu iemeslu dÄļ tas, kas tika ierakstÄ«ts zibatmiÅÄ, nebija tas, kas tika ierakstÄ«ts)
MÄs varam nekavÄjoties atklÄt Å”Ädas kļūdas, ja mÄs veicam testa nolasÄ«Å”anu tÅ«lÄ«t pÄc ierakstÄ«Å”anas; - Datu sagrozÄ«Å”ana atmiÅÄ uzglabÄÅ”anas laikÄ;
- LasīŔanas kļūdas
Lai to labotu, ja kontrolsumma nesakrÄ«t, pietiek ar rÄdÄ«jumu atkÄrtot vairÄkas reizes.
Tas ir, tikai treÅ”Ä veida kļūdas (spontÄna datu sabojÄÅ”ana uzglabÄÅ”anas laikÄ) nevar labot bez kļūdÄm izturÄ«gas kodÄÅ”anas. Å Ä·iet, ka Å”Ädas kļūdas joprojÄm ir ÄrkÄrtÄ«gi maz ticamas.
Kopsavilkums: tika nolemts atteikties no liekÄs kodÄÅ”anas, bet, ja darbÄ«ba uzrÄda Ŕī lÄmuma kļūdu, tad atgriezties pie jautÄjuma izskatÄ«Å”anas (ar jau uzkrÄto statistiku par kļūmÄm, kas ļaus izvÄlÄties optimÄlo kodÄÅ”anas veidu).
Cits
Protams, raksta formÄts neļauj mums attaisnot katru formÄta bitu (un spÄki jau ir beiguÅ”ies), tÄpÄc es Ä«sumÄ apskatÄ«Å”u dažus punktus, kas iepriekÅ” netika skarti.
- Tika nolemts visas lapas padarÄ«t āvienÄdasā
Tas ir, nebÅ«s Ä«paÅ”u lapu ar metadatiem, atseviŔķiem pavedieniem utt., bet gan viens pavediens, kas pÄrraksta visas lapas pÄc kÄrtas.
Tas nodroÅ”ina vienmÄrÄ«gu lapu nodilumu, neviena neveiksmes punkta, un man tas vienkÄrÅ”i patÄ«k; - Ir obligÄti jÄnodroÅ”ina formÄta versija.
FormÄts bez versijas numura galvenÄ ir ļauns!
Pietiek lapas galvenÄ pievienot lauku ar noteiktu burvju numuru (parakstu), kas norÄdÄ«s izmantotÄ formÄta versiju (NedomÄju, ka praksÄ tÄdu bÅ«s pat ducis); - Ierakstiem (kuru ir daudz) izmantojiet mainÄ«ga garuma galveni, vairumÄ gadÄ«jumu mÄÄ£inot padarÄ«t to 1 baitu garu;
- Lai kodÄtu saspiestÄ ieraksta galvenes garumu un apgrieztÄs daļas garumu, izmantojiet mainÄ«ga garuma binÄros kodus.
Ä»oti palÄ«dzÄja Hafmena kodi. Tikai dažu minÅ«Å”u laikÄ mÄs varÄjÄm atlasÄ«t nepiecieÅ”amos mainÄ«ga garuma kodus.
Datu uzglabÄÅ”anas formÄta apraksts
Baitu secība
Lauki, kas ir lielÄki par vienu baitu, tiek saglabÄti lielÄ formÄtÄ (tÄ«kla baitu secÄ«bÄ), tas ir, 0x1234 tiek rakstÄ«ts kÄ 0x12, 0x34.
Lapu ŔķiroŔana
Visa zibatmiÅa ir sadalÄ«ta vienÄda izmÄra lapÄs.
NoklusÄtais lapas izmÄrs ir 32Kb, bet ne vairÄk kÄ 1/4 no kopÄjÄ atmiÅas mikroshÄmas izmÄra (4MB mikroshÄmai tiek iegÅ«tas 128 lapas).
Katra lapa glabÄ datus neatkarÄ«gi no pÄrÄjÄm (tas ir, dati vienÄ lapÄ neatsaucas uz datiem citÄ lapÄ).
Visas lapas ir numurÄtas dabiskÄ secÄ«bÄ (adreÅ”u augoÅ”Ä secÄ«bÄ), sÄkot ar numuru 0 (nulles lapa sÄkas ar adresi 0, pirmÄ lapa sÄkas ar 32Kb, otrÄ lapa sÄkas ar 64Kb utt.)
AtmiÅas mikroshÄma tiek izmantota kÄ ciklisks buferis (zvana buferis), tas ir, vispirms tiek rakstÄ«ts uz 0 lappusi, pÄc tam numuru 1, ..., kad mÄs aizpildÄm pÄdÄjo lapu, sÄkas jauns cikls un ierakstÄ«Å”ana turpinÄs no nulles lapas. .
Lapas iekÅ”pusÄ
Lapas sÄkumÄ tiek saglabÄta 4 baitu lapas galvene, pÄc tam galvenes kontrolsumma (CRC-32C), pÄc tam ieraksti tiek saglabÄti formÄtÄ āgalvenes, dati, kontrolsummaā.
Lapas virsraksts (shÄmÄ netÄ«ri zaļŔ) sastÄv no:
- divu baitu burvju numura lauks (arÄ« formÄta versijas zÄ«me)
paÅ”reizÄjai formÄta versijai tas tiek aprÄÄ·inÄts kÄ0xed00 ā Š½Š¾Š¼ŠµŃ ŃŃŃŠ°Š½ŠøŃŃ; - divu baitu skaitÄ«tÄjs āLapas versijaā (atmiÅas pÄrrakstÄ«Å”anas cikla numurs).
Lapas ieraksti tiek saglabÄti saspiestÄ formÄ (tiek izmantots deflÄcijas algoritms). Visi ieraksti vienÄ lapÄ tiek saspiesti vienÄ pavedienÄ (tiek izmantota parastÄ vÄrdnÄ«ca), un katrÄ jaunÄ lapÄ saspieÅ”ana sÄkas no jauna. Tas ir, lai atspiestu jebkuru ierakstu, ir nepiecieÅ”ami visi iepriekÅ”Äjie ieraksti no Ŕīs lapas (un tikai Å”is).
Katrs ieraksts tiks saspiests ar karogu Z_SYNC_FLUSH, un saspiestÄs straumes beigÄs bÅ«s 4 baiti 0x00, 0x00, 0xff, 0xff, pirms kuriem, iespÄjams, bÅ«s vÄl viens vai divi nulles baiti.
MÄs atmetam Å”o secÄ«bu (4, 5 vai 6 baitus garu), rakstot zibatmiÅÄ.
Ieraksta galvene ir 1, 2 vai 3 baiti, kurÄ tiek glabÄta:
- viens bits (T), kas norÄda ieraksta veidu: 0 - konteksts, 1 - žurnÄls;
- mainÄ«ga garuma lauks (S) no 1 lÄ«dz 7 bitiem, kas nosaka galvenes un āastesā garumu, kas jÄpievieno ierakstam dekompresijas nolÅ«kÄ;
- rekorda garums (L).
S vÄrtÄ«bu tabula:
S
Galvenes garums, baiti
Atmests rakstÄ«Å”anas laikÄ, baits
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)
Es mÄÄ£inÄju ilustrÄt, es nezinu, cik skaidri tas izrÄdÄ«jÄs:
Dzeltens Å”eit apzÄ«mÄ T lauku, balts S lauku, zaļŔ L (saspiesto datu garums baitos), zils saspiestos datus, sarkans saspiesto datu pÄdÄjos baitus, kas netiek ierakstÄ«ti zibatmiÅÄ.
TÄdÄjÄdi vienÄ baitÄ varam ierakstÄ«t visizplatÄ«tÄka garuma ierakstu galvenes (lÄ«dz 63+5 baitiem saspiestÄ veidÄ).
PÄc katra ieraksta tiek saglabÄta CRC-32C kontrolsumma, kurÄ kÄ sÄkotnÄjÄ vÄrtÄ«ba (init) tiek izmantota iepriekÅ”ÄjÄs kontrolsummas apgrieztÄ vÄrtÄ«ba.
CRC ir Ä«paŔība āilgumsā, darbojas Å”Äda formula (plus vai mÄ«nus bitu inversija procesÄ): .
Tas nozÄ«mÄ, ka mÄs aprÄÄ·inÄm CRC visiem iepriekÅ”Äjiem Ŕīs lapas galveÅu un datu baitiem.
TieÅ”i aiz kontrolsummas ir nÄkamÄ ieraksta galvene.
Galvene ir veidota tÄ, lai tÄs pirmais baits vienmÄr atŔķirtos no 0x00 un 0xff (ja galvenes pirmÄ baita vietÄ mÄs sastopamies ar 0xff, tas nozÄ«mÄ, ka tas ir neizmantots apgabals; 0x00 signalizÄ par kļūdu).
Algoritmu piemÄri
LasÄ«Å”ana no zibatmiÅas
JebkurÅ” lasÄ«jums nÄk ar kontrolsummas pÄrbaudi.
Ja kontrolsumma nesakrÄ«t, nolasÄ«jumu atkÄrto vairÄkas reizes, cerot nolasÄ«t pareizos datus.
(tas ir loÄ£iski, Linux neglabÄ keÅ”atmiÅÄ nolasÄ«jumus no NOR Flash, pÄrbaudÄ«ts)
Ierakstiet zibatmiÅÄ
MÄs ierakstÄm datus.
Lasīsim tos.
Ja nolasÄ«tie dati nesakrÄ«t ar rakstÄ«tajiem, laukumu aizpildÄm ar nullÄm un signalizÄ par kļūdu.
Jaunas mikroshÄmas sagatavoÅ”ana darbam
InicializÄcijai galvene ar versiju 1 tiek ierakstÄ«ta pirmajÄ (vai drÄ«zÄk nulles) lapÄ.
PÄc tam Å”ajÄ lapÄ tiek ierakstÄ«ts sÄkotnÄjais konteksts (satur iekÄrtas UUID un noklusÄjuma iestatÄ«jumus).
Tas arÄ« viss, zibatmiÅa ir gatava lietoÅ”anai.
MaŔīnas ielÄde
IelÄdÄjot, tiek nolasÄ«ti katras lapas pirmie 8 baiti (galvene + CRC), lapas ar nezinÄmu maÄ£isko numuru vai nepareizu CRC tiek ignorÄtas.
No āpareizajÄmā lapÄm tiek atlasÄ«tas lapas ar maksimÄlo versiju, un no tÄm tiek Åemta lapa ar lielÄko skaitu.
Tiek nolasÄ«ts pirmais ieraksts, tiek pÄrbaudÄ«ta CRC pareizÄ«ba un ākontekstaā karoga klÄtbÅ«tne. Ja viss ir kÄrtÄ«bÄ, Ŕī lapa tiek uzskatÄ«ta par aktuÄlu. Ja nÄ, mÄs atgriežamies pie iepriekÅ”ÄjÄs lapas, lÄ«dz atrodam ādzÄ«vuā lapu.
un atrastajÄ lapÄ lasÄm visus ierakstus, tos, kurus lietojam ar ākontekstaā karogu.
SaglabÄjiet zlib vÄrdnÄ«cu (tÄ bÅ«s nepiecieÅ”ama, lai pievienotu Å”o lapu).
Tas ir viss, lejupielÄde ir pabeigta, konteksts ir atjaunots, jÅ«s varat strÄdÄt.
ŽurnÄla ieraksta pievienoÅ”ana
MÄs saspiežam ierakstu ar pareizo vÄrdnÄ«cu, norÄdot Z_SYNC_FLUSH. MÄs redzam, vai saspiestais ieraksts iederas paÅ”reizÄjÄ lapÄ.
Ja tÄ neatbilst (vai lapÄ bija CRC kļūdas), sÄciet jaunu lapu (skatiet tÄlÄk).
MÄs pierakstÄm ierakstu un CRC. Ja rodas kļūda, sÄciet jaunu lapu.
Jauna lapa
MÄs izvÄlamies bezmaksas lapu ar minimÄlo skaitu (par bezmaksas lapu uzskatÄm lapu, kuras galvenÄ ir nepareiza kontrolsumma vai kuras versija ir mazÄka par paÅ”reizÄjo). Ja Å”Ädu lapu nav, atlasiet lapu ar minimÄlo skaitu no tÄm, kuru versija ir vienÄda ar paÅ”reizÄjo.
MÄs izdzÄÅ”am atlasÄ«to lapu. MÄs pÄrbaudÄm saturu ar 0xff. Ja kaut kas nav kÄrtÄ«bÄ, paÅemiet nÄkamo bezmaksas lapu utt.
IzdzÄstajÄ lapÄ ierakstÄm galveni, pirmais ieraksts ir paÅ”reizÄjais konteksta stÄvoklis, nÄkamais ir nerakstÄ«tais žurnÄla ieraksts (ja tÄds ir).
FormÄta pielietojamÄ«ba
ManuprÄt, tas izrÄdÄ«jÄs labs formÄts jebkÄdu vairÄk vai mazÄk saspiežamu informÄcijas plÅ«smu (plain text, JSON, MessagePack, CBOR, iespÄjams, protobuf) glabÄÅ”anai NOR Flash.
Protams, formÄts ir āpielÄgotsā SLC NOR Flash.
To nevajadzÄtu izmantot ar augstu BER datu nesÄju, piemÄram, NAND vai MLC NOR (vai Å”Äda atmiÅa vispÄr ir pieejama pÄrdoÅ”anÄ? Esmu redzÄjis, ka tÄ tiek pieminÄta tikai laboÅ”anas kodu darbos).
TurklÄt to nevajadzÄtu izmantot ierÄ«cÄm, kurÄm ir savs FTL: USB zibatmiÅa, SD, MicroSD utt (Å”Ädai atmiÅai es izveidoju formÄtu ar lapas izmÄru 512 baiti, parakstu katras lapas sÄkumÄ un unikÄlos ierakstu numurus - dažkÄrt bija iespÄjams atgÅ«t visus datus no āsagrautÄā zibatmiÅas diska ar vienkÄrÅ”u secÄ«gu lasÄ«Å”anu).
AtkarÄ«bÄ no uzdevumiem formÄtu var izmantot bez izmaiÅÄm zibatmiÅas diskos no 128Kbit (16Kb) lÄ«dz 1Gbit (128MB). Ja vÄlaties, varat to izmantot lielÄkÄm mikroshÄmÄm, taÄu, iespÄjams, jums ir jÄpielÄgo lapas izmÄrs (Bet Å”eit jau rodas jautÄjums par ekonomisko iespÄjamÄ«bu; cena par liela apjoma NOR Flash nav iepriecinoÅ”a).
Ja kÄdam formÄts Ŕķiet interesants un vÄlas to izmantot atvÄrtÄ projektÄ, rakstiet, mÄÄ£inÄÅ”u atrast laiku, noslÄ«pÄÅ”u kodu un ievietoÅ”u github.
SecinÄjums
KÄ redzat, beigÄs formÄts izrÄdÄ«jÄs vienkÄrÅ”s un pat garlaicÄ«gi.
Ir grÅ«ti atspoguļot mana viedokļa attÄ«stÄ«bu rakstÄ, bet ticiet man: sÄkotnÄji es gribÄju izveidot kaut ko izsmalcinÄtu, neiznÄ«cinÄmu, kas spÄj pÄrdzÄ«vot pat kodolsprÄdzienu tieÅ”Ä tuvumÄ. TomÄr saprÄts (es ceru) tomÄr uzvarÄja un pakÄpeniski prioritÄtes pÄrcÄlÄs uz vienkÄrŔību un kompaktumu.
Vai varÄtu bÅ«t, ka es kļūdÄ«jos? JÄ, protams. PiemÄram, var izrÄdÄ«ties, ka mÄs iegÄdÄjÄmies zemas kvalitÄtes mikroshÄmu partiju. Vai arÄ« kÄda cita iemesla dÄļ iekÄrta neatbilst uzticamÄ«bas prasÄ«bÄm.
Vai man ir plÄns Å”im nolÅ«kam? Es domÄju, ka pÄc raksta izlasÄ«Å”anas jums nav Å”aubu, ka plÄns ir. Un pat ne vienatnÄ.
Nedaudz nopietnÄk sakot, formÄts tika izstrÄdÄts gan kÄ darba iespÄja, gan kÄ āizmÄÄ£inÄjuma balonsā.
Å obrÄ«d viss uz galda darbojas labi, burtiski citu dienu risinÄjums tiks izvietots (aptuveni) simtiem ierÄ«Äu, redzÄsim, kas notiek ākaujasā darbÄ«bÄ (par laimi, es ceru, ka formÄts ļauj droÅ”i noteikt kļūmes; lai jÅ«s varÄtu apkopot pilnu statistiku). PÄc dažiem mÄneÅ”iem varÄs izdarÄ«t secinÄjumus (un, ja jums nepaveicas, pat agrÄk).
Ja, pamatojoties uz lietoÅ”anas rezultÄtiem, tiks atklÄtas nopietnas problÄmas un nepiecieÅ”ami uzlabojumi, tad noteikti par to uzrakstÄ«Å”u.
Literatūra
Es negribÄju izveidot garu un garlaicÄ«gu lietoto darbu sarakstu; galu galÄ visiem ir Google.
Å eit es nolÄmu atstÄt sarakstu ar atradumiem, kas man Ŕķita Ä«paÅ”i interesanti, taÄu pamazÄm tie migrÄja tieÅ”i raksta tekstÄ, un sarakstÄ palika viens vienums:
- LietderÄ«ba no autora zlib. Var skaidri parÄdÄ«t deflate/zlib/gzip arhÄ«vu saturu. Ja jums ir jÄrisina deflÄcijas (vai gzip) formÄta iekÅ”ÄjÄ struktÅ«ra, es to ļoti iesaku.
Avots: www.habr.com