перадгісторыя
Ёсць гандлёвыя аўтаматы ўласнай распрацоўкі. Усярэдзіне Raspberry Pi і трохі абвязкі на асобнай плаце. Падключаны манетапрыёмнік, купюрапрыёмнік, банкаўскі тэрмінал... Кіруе ўсім самапісная праграма. Уся гісторыя працы пішацца ў часопіс на флэшцы (MicroSD), які потым перадаецца праз інтэрнэт (з дапамогай USB-мадэма) на сервер, там складаецца ў БД. Інфармацыя аб продажах загружаецца ў 1с, таксама ёсць просценькі вэб-інтэрфейс для маніторынгу і да т.п.
Гэта значыць часопіс жыццёва неабходны - для ўліку (там выручка, продажу і г.д.), маніторынгу (разнастайныя збоі і іншыя форс-мажорныя абставіны); гэта, можна сказаць, уся інфармацыя, якая ў нас аб гэтым аўтамаце.
праблема
Флэшкі паказваюць сябе як вельмі ненадзейныя прылады. Яны з зайздроснай рэгулярнасцю выходзяць са строю. Гэта прыводзіць як да прастояў аўтаматаў, так і (калі па нейкіх прычынах часопіс не мог быць перададзены анлайн) да страт дадзеных.
Гэта ўжо не першы досвед выкарыстання флэшак, да гэтага быў іншы праект з больш, чым сотняй прылад, дзе часопіс захоўваўся на USB-флэшках, тамака таксама былі праблемы з надзейнасцю, часам лік якія выйшлі з ладу за месяц вылічалася дзясяткамі. Спрабавалі розныя флэшкі, у тым ліку і брэндавыя на SLC памяці, ды некаторыя мадэлі надзейней за іншых, але замена флэшак не вырашыла праблему кардынальна.
Увага! Лонгрыд! Калі вам нецікава "чаму", а цікава толькі "як", можаце адразу ісці артыкулы.
рашэнне
Першае, што прыходзіць у галаву: адмовіцца ад MicroSD, паставіць, напрыклад, SSD, і грузіцца з яго. Тэарэтычна магчыма, напэўна, але адносна дорага, і не так ужо надзейна (дадаецца перахаднік USB-SATA; па бюджэтных SSD статыстыка адмоў таксама не радуе).
USB HDD таксама не выглядае асоба прывабным рашэннем.
Таму прыйшлі да такога варыянту: пакінуць загрузку з MicroSD, але выкарыстоўваць іх у рэжыме read-only, а часопіс працы (і іншую ўнікальную для канкрэтнай жалязякі інфармацыю - серыйны нумар, каліброўкі датчыкаў, etc) захоўваць дзесьці яшчэ.
Тэма read-only ФС для малінкі ўжо вывучана ўздоўж і папярок, я не буду спыняцца на дэталях рэалізацыі ў гэтым артыкуле (але калі будзе цікавасць - быць можа і напішу міні-артыкул на гэтую тэму). Адзіны момант, які жадаецца адзначыць: і па асабістым досведзе, і па водгуках ужо якія ўкаранілі выйгрыш у надзейнасці ёсць. Так, цалкам пазбавіцца ад паломак немагчыма, аднак істотна знізіць іх частату - цалкам рэальна. Ды і карткі становяцца ўніфікаванымі, што прыкметна спрашчае замену для абслуговага персанала.
апаратная частка
З выбарам тыпу памяці асаблівых сумневаў не было - NOR Flash.
аргументы:
- простае падлучэнне (часцей за ўсё шына SPI, досвед выкарыстання якой ужо ёсць, так што «жалезных» праблем не прадбачыцца);
- смешная цана;
- стандартны пратакол працы (рэалізацыя ёсць ужо ў ядры Linux, пры жаданні можна ўзяць іншую, якія таксама прысутнічаюць, ці нават напісаць сваю, балазе ўсё проста);
- надзейнасць і рэсурс:
з тыповага даташыта: дадзеныя захоўваюцца 20 гадоў, 100000 цыклаў erase для кожнага блока;
з іншых крыніц: вельмі нізкі BER, пастулюецца адсутнасць неабходнасці ў кодах карэкцыі памылак (у некаторых працах разглядаецца ECC для NOR, але звычайна ўсёткі тамака маюць на ўвазе MLC NOR, бывае і такое).
Прыкінем патрабаванні да аб'ёму і рэсурсу.
Жадаецца, каб гарантавана захоўваліся дадзеныя за некалькі дзён. Трэба гэта для таго, каб у выпадку якіх-небудзь праблем са сувяззю гісторыя продажаў не была страчана. Будзем арыентавацца на 5 дзён, за гэты тэрмін (нават з улікам выходных і свят) можна вырашыць праблему.
У нас зараз за суткі набіраецца каля 100кб часопіса (3-4 тысячы запісаў), аднак паступова гэтая лічба расце — павялічваецца дэталізацыя, дадаюцца новыя падзеі. Плюс часам бываюць воплескі (які-небудзь датчык пачынае спаміць ілжывымі спрацоўваннямі, напрыклад). Будзем разлічыць на 10 тысяч запісаў па 100 байт - мегабайт у суткі.
Разам выходзіць 5Мб чыстых (добра сціскаемых) дадзеных. Да іх яшчэ (грубая прыкідка) 1Мб службовых дадзеных.
Гэта значыць, нам патрэбна мікрасхема на 8Мб калі не выкарыстоўваць сціск, або 4Мб калі выкарыстоўваць. Суцэль рэальныя лічбы для гэтага тыпу памяці.
Што ж да рэсурсу: калі мы плануем, што памяць цалкам будзе перапісвацца не часцей, чым раз на 5 дзён, то за 10 гадоў службы мы атрымліваем менш за тысячу цыклаў перазапісу.
Нагадваю, вытворца абяцае сто тысяч.
Трохі пра NOR vs NAND
Сёння, вядома, куды папулярнейшая NAND памяць, аднак для гэтага праекту я бы не стаў яе выкарыстаць: NAND, у адрозненне ад NOR, абавязкова патрабуе выкарыстанні кодаў карэкцыі памылак, табліцы збойных блокаў і т.д., ды і ножак у мікрасхем NAND звычайна куды больш.
У якасці недахопаў NOR можна паказаць:
- малы аб'ём (і, адпаведна, высокая цана за мегабайт);
- невысокая хуткасць абмену (шмат у чым з-за таго, што выкарыстоўваецца паслядоўны інтэрфейс, звычайна SPI ці I2C);
- павольны erase (у залежнасці ад памеру блока, ён займае ад доляй секунды, да некалькіх секунд).
Нібыта нічога крытычнага для нас, так што працягваем.
Калі цікавыя дэталі, была абрана мікрасхема (зрэшты, гэта неістотна, на рынку куча аналагаў, сумяшчальных па распіноўцы і сістэме каманд; нават калі мы захочам паставіць мікрасхему іншага вытворцы і/ці іншага аб'ёму, тое ўсё запрацуе без змены кода).
Я выкарыстоўваю ўбудаваны ў ядро Linux драйвер, на Raspberry дзякуючы падтрымцы device tree overlay усё вельмі проста – трэба пакласці ў /boot/overlays скампіляваны овэрлэй і трохі мадыфікаваць /boot/config.txt.
Прыклад dts файла
Шчыра кажучы, не ўпэўнены, што напісана без памылак, але працуе.
/*
* 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?";
};
};І яшчэ радок у config.txt
dtoverlay=at25:spimaxfrequency=50000000Апісанне самога падлучэння мікрасхемы да Raspberry Pi апушчу. З аднаго боку, я не адмысловец у электроніцы, з іншай – тут усё банальна нават для мяне: у мікрасхемы ўсяго 8 ног, з якіх нам патрэбныя зямля, сілкаванне, SPI (CS, SI, SO, SCK); ўзроўні супадаюць з такімі ў Raspberry Pi, ніякай дадатковай абвязкі не патрабуецца - проста злучыць паказаныя 6 кантактаў.
Пастаноўка задачы
Як звычайна, пастаноўка задачы праходзіць некалькі ітэрацый, мне здаецца, што надышоў час для чарговай. Так што давайце спынімся, збяром разам тое, што ўжо было напісана, і растлумачым пакінутыя ў цені дэталі.
Такім чынам мы вызначыліся з тым, што часопіс будзе захоўвацца ў SPI NOR Flash.
Што такое NOR Flash для тых, хто не ведае
Гэта энерганезалежная памяць, з якой можна рабіць тры аперацыі:
- чытанне:
Самае звычайнае чытанне: перадаем адрас і чытэльны гэтулькі байт, колькі нам трэба; - запіс:
Запіс у NOR flash выглядае як звычайны, але ў яе ёсць адна асаблівасць: можна толькі мяняць 1 на 0, але не наадварот. Напрыклад, калі ў нас у вочку памяці ляжала 0x55, то пасля запісу ў яе 0x0f тамака ўжо будзе захоўвацца 0x05 (гл. табліцу крыху ніжэй); - Сцерці:
Зразумела, нам трэба ўмець рабіць і зваротную аперацыю - мяняць 0 на 1, менавіта для гэтага і існуе аперацыя erase. У адрозненне ад першых двух, яна аперуе не байтамі, а блокамі (мінімальны erase block у абранай мікрасхеме – 4кб). Erase знішчае ўвесь блок цалкам і гэта адзіны спосаб памяняць 0 на 1. Таму, пры працы з флэш-памяццю часта даводзіцца выраўноўваць структуры дадзеных на мяжу erase block.
Запіс у NOR Flash:
Двайковыя дадзеныя
Было
01010101
Запісалі
00001111
стала
00000101
Сам часопіс уяўляе паслядоўнасць запісаў зменнай даўжыні. Тыповая даўжыня запісу каля 30 байт (хоць часам здараюцца і запісы даўжынёй у некалькі кілабайт). У дадзеным выпадку мы працуем з імі проста як з наборам байт, але, калі цікава, усярэдзіне запісаў выкарыстоўваецца CBOR
Акрамя часопіса, нам трэба захоўваць некаторую "наладкавую" інфармацыю, як якая абнаўляецца, так і няма: нейкі ID апарата, каліброўкі датчыкаў, сцяг "апарат часова адключаны", etc.
Гэтая інфармацыя ўяўляе сабой набор запісаў key-value, таксама захоўваецца ў CBOR. Гэтай інфармацыі ў нас не вельмі шмат (максімум некалькі кілабайт), абнаўляецца яна нячаста.
У далейшым будзем называць яе кантэкстам.
Калі ўспомніць з чаго пачынаўся гэты артыкул, тое вельмі важна забяспечыць надзейнасць захоўвання дадзеных і, па магчымасці, бесперапынную працу нават у выпадку апаратных збояў/пашкоджанні дадзеных.
Якія крыніцы праблем можна разгледзець?
- Адключэнне харчавання ў момант аперацый write/erase. Гэта з разраду "супраць лому няма прыёму".
Інфармацыя з на stackexchange: пры адключэнні харчавання ў момант працы з flash што erase (усталёўка ў 1), што write (усталёўка ў 0) прыводзяць да undefined behavior: дадзеныя могуць запісацца, запісацца часткова (скажам, мы перадалі 10 байт/80 біт, а паспелі запісацца толькі 45 біт), не выключана і тое, што частка бітаў апынецца ў "прамежкавым" стане (чытанне можа выдаць як 0, так і 1); - Памылкі самай flash-памяці.
BER хоць і вельмі нізкі, але не можа быць роўным нулю; - Памылкі па шыне
Дадзеныя, якія перадаюцца па SPI ніяк не абаронены, цалкам могуць здарыцца як адзіночныя бітавыя памылкі, так і памылкі сінхранізацыі - страта або ўстаўка біт (што прыводзіць да масавых скажэнняў дадзеных); - Іншыя памылкі/збоі
Памылкі ў кодзе, "глюкі" Raspberry, умяшанне іншапланецян…
Я сфармуляваў патрабаванні, выкананне якіх, на мой погляд, неабходна для забеспячэння надзейнасці:
- запісы павінны трапляць у флэш-памяць адразу, адкладзены запіс не разглядаецца; - калі памылка ўзнікла, то яна павінна выяўляцца і апрацоўвацца як мага раней; - сістэма павінна па магчымасці аднаўляць працу пасля памылак.
(прыклад з жыцця "як не павінна быць", з якім, думаю, усё сустракаліся: пасля аварыйнай перазагрузкі "пабілася" файлавая сістэма і аперацыйная сістэма не грузіцца)
Ідэі, падыходы, разважанні
Калі я пачаў думаць над гэтай задачай, то ў галаве праносілася куча ідэй, напрыклад:
- выкарыстоўваць сціск дадзеных;
- выкарыстоўваць хітрыя структуры дадзеных, напрыклад захоўваць загалоўкі запісаў асобна ад саміх запісаў, каб пры памылцы ў які-небудзь запісы можна было без праблем прачытаць астатнія;
- выкарыстоўваць бітавыя палі для кантролю завершанасці запісу пры адключэнні харчавання;
- захоўваць кантрольныя сумы для ўсяго і ўся;
- выкарыстоўваць якую-небудзь разнавіднасць перашкодаўстойлівага кадавання.
Частка гэтых ідэй была скарыстана, ад часткі было вырашана адмовіцца. Давайце па парадку.
Сціск дадзеных
Самі падзеі, якія мы фіксуем у часопісе, дастаткова аднатыпныя і паўтараныя («кінулі манетку 5 рублёў», «націснулі на кнопку выдачы здачы», …). Таму сціск павінен апынуцца дастаткова эфектыўным.
Накладныя выдаткі на сціск неістотныя (працэсар у нас досыць магутны, нават на першым Pi было адно ядро з частатой 700Мгц, на актуальных мадэлях некалькі ядраў з частатой звыш гігагерца), хуткасць абмену са сховішчам невысокая (некалькі мегабайт у секунду), памер запісаў невялікі. Увогуле, калі сціск і паўплывае на прадукцыйнасць, то толькі станоўчае. (абсалютна некрытычна, проста канстатую). Плюс у нас жа не сапраўдны embedded, а звычайны Linux - так што рэалізацыя не павінна запатрабаваць шмат намаганняў (досыць проста прылінкаваць бібліятэку і выкарыстоўваць некалькі функцый з яе).
Быў узяты кавалак лога з якая працуе прылады (1.7Мб, 70 тысяч запісаў) і для пачатку правераны на сціскальнасць з дапамогай наяўных на кампутары gzip, lz4, lzop, bzip2, xz, zstd.
- gzip, xz, zstd паказалі свае вынікі (40Кб).
Здзівіла, што модны xz паказаў тут сябе на ўзроўні gzip ці zstd; - lzip з наладамі па змаўчанні даў крыху горшы вынік;
- lz4 і lzop паказалі не вельмі добры вынік (150Кб);
- bzip2 паказаў на здзіўленне добры вынік (18Кб).
Такім чынам, дадзеныя сціскаюцца вельмі добрае.
Так што (калі мы не знойдзем фатальных недахопаў) сціску быць! Проста таму, што на тую ж флешку змесціцца больш дадзеных.
Давайце падумаем аб недахопах.
Першая праблема: мы ўжо дамовіліся, што кожны запіс павінен неадкладна патрапіць на флэш. Звычайна архіватар набірае дадзеныя з уваходнага струменя датуль, пакуль не вырашыць, што сітавіна пісаць у выходны. Нам жа трэба адразу атрымаць сціслы блок звестак і захаваць яго ў энерганезалежнай памяці.
Я бачу тры шляхі:
- Сціскаць кожны запіс з дапамогай слоўнікавага сціску замест разгледжаных вышэй алгарытмаў.
Суцэль працоўны варыянт, але мне ён не падабаецца. Для забеспячэння больш-менш прыстойнага ўзроўню сціску слоўнік павінен быць "заменчаны" пад канкрэтныя дадзеныя, любая змена прывядзе да таго, што ўзровень сціску катастрафічна падае. Так, праблема вырашаецца стварэннем новай версіі слоўніка, але гэта ж галаўны боль - нам трэба будзе захоўваць усе версіі слоўніка; у кожным запісе нам трэба будзе ўказваць з якой версіяй слоўніка яна была сціснутая… - Сціскаць кожны запіс "класічнымі" алгарытмамі, але незалежна ад іншых.
Разглядаюцца алгарытмы кампрэсіі не разлічаны на працу з запісамі такога памеру (дзясяткі байт), каэфіцыент сціску будзе відавочна менш 1 (гэта значыць павелічэнне аб'ёму дадзеных замест сціску); - Рабіць FLUSH пасля кожнага запісу.
У шматлікіх бібліятэках сціску ёсць падтрымка FLUSH. Гэта каманда (ці параметр да працэдуры сціску), атрымаўшы якую архіватар фармуе сціслы струмень так, каб каб на яго падставе можна аднавіць ўсё несціснутыя дадзеныя, якія ўжо былі атрыманы. Такі аналагsyncу файлавых сістэмах абоcommitу sql.
Што важна, наступныя аперацыі сціску змогуць выкарыстоўваць назапашаны слоўнік і ступень сціску не будзе пакутаваць так моцна, як у папярэднім варыянце.
Думаю відавочна, што я абраў трэці варыянт, спынімся на ім падрабязней.
Знайшлася пра FLUSH у zlib.
Зрабіў па матывах артыкула накалены тэст, узяў 70 тысяч запісаў часопіса з рэальнай прылады, пры памеры старонкі ў 60Кб (да памеру старонкі мы яшчэ вернемся) атрымаў:
Зыходныя дадзеныя
Сціск gzip -9 (без FLUSH)
zlib з Z_PARTIAL_FLUSH
zlib з Z_SYNC_FLUSH
Аб'ём, Кб
1692
40
352
604
На першы погляд кошт, якая ўносіцца FLUSH празмеру высокая, аднак насамрэч у нас небагаты выбар ці не сціскаць зусім, ці сціскаць (і вельмі эфектыўна) з FLUSH. Не трэба забываць, што ў нас 70 тысяч запісаў, надмернасць, якая ўносіцца Z_PARTIAL_FLUSH складае ўсяго 4-5 байт на запіс. А каэфіцыент сціску аказаўся амаль 5:1, што больш, чым выдатны вынік.
Можа здацца нечаканым, але на самой справе Z_SYNC_FLUSH - больш эфектыўны спосаб рабіць FLUSH
У выпадку выкарыстання Z_SYNC_FLUSH 4 апошнія байта кожнага запісу заўсёды будуць 0x00, 0x00, 0xff, 0xff. А калі яны нам вядомыя - то мы можам іх не захоўваць, такім чынам выніковы памер аказваецца ўсяго 324Кб.
У артыкуле, на які я спасылаюся, ёсць тлумачэнне:
New typ 0 block with empty contents is appended.
A typ 0 block with empty contents consists of:
- the three-bit block header;
- 0 - 7 бітаў эквівалентна XNUMX, мяркуецца, лічыцца;
- the four-byte sequence 00 00 FF FF.
Як нескладана заўважыць, у апошнім блоку перад гэтымі 4 байтамі ідзе ад 3 да 10 нулявых біт. Аднак практыка паказала, што нулявых біт насамрэч мінімум 10.
Апыняецца, гэтак кароткія блокі дадзеных звычайна (заўсёды?) кадуюцца з дапамогай блока тыпу 1 (fixed block), які абавязкова сканчаецца 7 нулявымі бітамі, разам атрымліваем 10-17 гарантавана нулявых біт (а астатнія будуць нулявымі з верагоднасцю каля 50%).
Такім чынам, на тэставых дадзеных у 100% выпадкаў перад 0x00, 0x00, 0xff, 0xff ідзе адзін нулявы байт, а больш, чым у трэці выпадку – два нулявыя байты (магчыма, справа ў тым, што я выкарыстоўваю бінарны CBOR, а пры выкарыстанні тэкставага JSON часцей сустракаліся б блокі тыпу 2 - dynamic block, адпаведна сустракаліся б блокі без дадатковых нулявых байт перад 0x00, 0x00, 0xff, 0xff).
Разам на наяўных тэставых дадзеных можна ўкласціся ў менш за 250Кб сціснутых дадзеных.
Можна зэканоміць яшчэ трохі, заняўшыся жангляваннем бітамі: зараз мы ігнаруем наяўнасць некалькіх нулявых біт у канцы блока, некалькі біт у пачатку блока таксама не змяняюцца…
Але тут я прыняў валявое рашэнне спыніцца, інакш такімі тэмпамі можна дайсці да распрацоўкі свайго архіватара.
Разам, я са сваіх тэставых дадзеных атрымаў 3-4 байта на запіс, каэфіцыент сціску атрымаўся больш за 6:1. Шчыра скажу: я на такі вынік і не разлічваў, на мой погляд усё, што лепш 2:1 – ужо вынік, які апраўдвае выкарыстанне сціску.
Усё выдатна, але zlib (deflate) — усё ж архаічны заслужаны і крыху старамодны алгарытм сціску. Ужо адно тое, што ў якасці слоўніка выкарыстоўваюцца апошнія 32Кб са струменя несціснутых дадзеных, сёння выглядае дзіўным (гэта значыць калі нейкі блок дадзеных вельмі падобны на тое, што было ва ўваходнай плыні 40Кб назад, то ён пачне архівавацца нанова, а не будзе спасылацца на мінулае ўваходжанне). У модных сучасных архіватарах памер слоўніка часцей вымяраецца мегабайтамі, а не кілабайтамі.
Так што працягваем наша міні-даследаванне архіватараў.
Наступным быў апрабаваны bzip2 (нагадаю, без FLUSH ён паказаў фантастычную ступень сціску, амаль 100:1). Нажаль, з FLUSH ён паказаў сябе вельмі дрэнна, памер сціснутых дадзеных аказаўся больш, чым несціснутых.
Мае здагадкі аб прычынах правалу
Libbz2 прапануе ўсяго адзін варыянт flush, які, падобна, чысціць слоўнік (аналаг Z_FULL_FLUSH у zlib), казаць аб нейкім эфектыўным сціску пасля гэтага не прыходзіцца.
І апошнім быў апрабаваны zstd. У залежнасці ад параметраў ён сціскае ці на ўзроўні gzip, але значна хутчэй, ці ж лепш gzip.
Нажаль, з FLUSH і ён паказаў сябе "не вельмі": памер сціснутых дадзеных выйшаў каля 700Кб.
Я на старонцы праекту ў github, атрымаў адказ, што варта разлічваць на да 10 байт службовых дадзеных на кожны блок сціснутых дадзеных, што блізка да атрыманых вынікаў, дагнаць deflate ніяк не атрымаецца.
На гэтым я вырашыў спыніцца ў эксперыментах з архіватарамі (нагадаю, xz, lzip, lzo, lz4 не паказалі сябе яшчэ на этапе тэставання без FLUSH, а разглядаць больш экзатычныя алгарытмы сціску я не стаў).
Вяртаемся да праблем архівацыі.
Другая (як гаворыцца па парадку, а не па значэнні) праблема - сціснутыя дадзеныя ўяўляюць з сябе адзіны паток, у якім пастаянна ідуць дасылкі на папярэднія ўчасткі. Такім чынам, пры пашкоджанні нейкага ўчастку сціснутых дадзеных мы губляем не толькі злучаны з ім блок несціснутых дадзеных, але і ўсё наступныя.
Ёсць падыходу да рашэння гэтай праблемы:
- Папярэджваць з'яўленне праблемы - дадаваць у сціснутыя дадзеныя надмернасць, якая дазволіць вызначаць і выпраўляць памылкі; пра гэта мы пагаворым пазней;
- Мінімізаваць наступствы ў выпадку ўзнікнення праблемы
Мы ўжо казалі раней, што можна кожны блок дадзеных сціскаць незалежна, пры гэтым праблема знікне сама сабой (псаванне дадзеных аднаго блока прывядзе да страты дадзеных толькі гэтага блока). Аднак, гэта крайні выпадак, пры якім сціск дадзеных будзе неэфектыўным. Процілеглая крайнасць: выкарыстоўваць усе 4Мб нашай мікрасхемы як адзіны архіў, што дасць нам выдатны сціск, але катастрафічныя наступствы ў выпадку псуты дадзеных.
Так, патрэбен кампраміс з пункту гледжання надзейнасці. Але трэба памятаць, што мы распрацоўваем фармат захоўвання дадзеных для энерганезалежнай памяці з вельмі нізкім BER і дэклараваным тэрмінам захоўвання дадзеных 20 гадоў.
Падчас эксперыментаў я выявіў, што больш-менш прыкметныя страты ўзроўня сціску пачынаюцца на блоках сціснутых дадзеных рамерам меней 10Кб.
Раней згадвалася, што памяць, якая выкарыстоўваецца, мае старонкавую арганізацыю, я не бачу прычын, па якіх не варта выкарыстоўваць адпаведнасць «адна старонка — адзін блок сціснутых дадзеных».
Гэта значыць мінімальны разумны памер старонкі роўны 16Кб (з запасам на службовую інфармацыю). Аднак такі малы памер старонкі накладвае істотныя абмежаванні на максімальны памер запісу.
Хоць у мяне пакуль і не прадбачыцца запісаў больш адзінак кілабайт у сціснутым выглядзе, я вырашыў выкарыстоўваць старонкі памерам 32Кб (разам атрымліваецца 128 старонак на мікрасхему).
Рэзюмэ:
- Дадзеныя мы захоўваем сціснутымі з дапамогай zlib (deflate);
- Для кожнага запісу ўсталёўваны Z_SYNC_FLUSH;
- У кожным сціснутым запісе абразаем канчатковыя байты. (напрыклад, 0x00, 0x00, 0xff, 0xff); у загалоўку паказваем як шмат байт мы адразалі;
- Дадзеныя захоўваем старонкамі па 32Кб; усярэдзіне старонак ідзе адзіны струмень сціснутых дадзеных; на кожнай старонцы сціск пачынаем нанова.
І, перад тым як скончыць са сціскам, жадалася б звярнуць увагу, што сціснутых дадзеных у нас атрымліваецца ўсяго некалькі байт на запіс, таму вельмі важна не раздзімаць службовую інфармацыю, кожны байт тут на рахунку.
Захоўванне загалоўкаў дадзеных
Так як у нас запісы зменнай даўжыні, то нам трэба неяк вызначаць размяшчэнне/мяжы запісаў.
Я ведаю тры падыходы:
- Усе запісы захоўваюцца ў бесперапынным струмені, спачатку ідзе загаловак запісу, які змяшчае даўжыню, а потым сам запіс.
У гэтым варыянце і загалоўкі, і дадзеныя могуць мець зменную даўжыню.
Па сутнасці, у нас атрымліваецца аднасувязны спіс, які выкарыстоўваецца запар і побач; - Загалоўкі і самі запісы захоўваюцца ў паасобных патоках.
Выкарыстоўваючы загалоўкі сталай даўжыні, мы дамагаемся таго, што псута аднаго загалоўка не ўплывае на астатнія.
Падобны падыход выкарыстоўваецца, напрыклад, у шматлікіх файлавых сістэмах; - Запісы захоўваюцца ў бесперапынным струмені, мяжа запісу вызначаецца па некаторым маркеру (знаку/паслядоўнасці знакаў, які/якая забароненыя ўсярэдзіне блокаў дадзеных). Калі ўсярэдзіне запісу сустракаецца маркер, то мы заменны яго на некаторую паслядоўнасць (экрануем яго).
Падобны падыход выкарыстоўваецца, напрыклад, у пратаколе PPP.
Праілюструю.
Варыянт 1:
Тут усё вельмі проста: ведаючы даўжыню запісу мы можам вылічыць адрас наступнага загалоўка. Так мы перамяшчаемся па загалоўках, пакуль не сустрэнем вобласць, запоўненую 0xff (вольную вобласць) ці канец старонкі.
Варыянт 2:
З-за зменнай даўжыні запісу мы не можам загадзя сказаць як шмат запісаў (а значыць і загалоўкаў) на старонку нам спатрэбіцца. Можна разнесці загалоўкі і самі дадзеныя па розных старонках, але мне сімпотней іншы падыход: і загалоўкі, і дадзеныя размяшчаем на адной старонцы, аднак загалоўкі (пастаяннага памеру) у нас ідуць ад пачатку старонкі, а дадзеныя (пераменнай даўжыні) - ад канца. Як толькі яны “сустрэнюцца” (вольнага месца не хопіць на новы запіс) – лічым гэтую старонку запоўненай.
Варыянт 3:
Тут няма патрэбы захоўваць у загалоўку даўжыню ці іншую інфармацыю аб размяшчэнні дадзеных, дастаткова маркераў, якія азначаюць межы запісаў. Аднак дадзеныя даводзіцца апрацоўваць пры запісе / чытанні.
У якасці маркера я б выкарыстоўваў 0xff (якім запоўненая старонка пасля erase), такім чынам вольная вобласць сапраўды не будзе тлумачыцца як дадзеныя.
Параўнальная табліца:
варыянт 1
варыянт 2
варыянт 3
Устойлівасць да памылак
-
+
+
кампактнасць
+
-
+
Складанасць рэалізацыі
*
**
**
Варыянт 1 мае фатальны недахоп: пры пашкоджанні нейкага з загалоўкаў у нас руйнуецца ўвесь наступны ланцужок. Астатнія варыянты дазваляюць аднавіць частку дадзеных нават пры масавых пашкоджаннях.
Але тут дарэчы ўспомніць, што мы вырашылі захоўваць дадзеныя ў сціснутым выглядзе, так і так мы губляем усе дадзеныя на старонцы пасля "бітага" запісы, так што хоць у табліцы і стаіць мінус, мы яго не ўлічваем.
Кампактнасць:
- у першым варыянце нам трэба захоўваць у загалоўку толькі даўжыню, калі выкарыстоўваць цэлыя зменнай даўжыні, то ў большасці выпадкаў можна абыйсціся адным байтам;
- у другім варыянце нам трэба захоўваць пачатковы адрас і даўжыню; запіс павінен быць пастаяннага памеру, я ацэньваю ў 4 байта на запіс (два байта на зрушэнне, і два байта на даўжыню);
- трэцяму варыянту дастаткова ўсяго аднаго сімвала для абазначэння пачатку запісу, плюс сам запіс з-за экранавання вырасце на 1-2%. У цэлым прыкладны парытэт з першым варыянтам.
Першапачаткова я разглядаў другі варыянт як асноўны (і нават напісаў рэалізацыю). Адмовіўся ад яго я толькі тады, калі канчаткова вырашыў выкарыстоўваць сціск.
Магчыма, калі-небудзь я ўсё ж такі буду выкарыстоўваць падобны варыянт. Напрыклад, калі мне давядзецца займацца захоўваннем дадзеных для карабля, які курсуе паміж Зямлёй і Марсам — зусім іншыя патрабаванні да надзейнасці, касмічнае выпраменьванне, …
Што ж да трэцяга варыянту: я паставіў яму дзве зорачкі за складанасць рэалізацыі проста таму, што не люблю важдацца з экранаваннем, зменай даўжыні ў працэсе і да т.п. Так, магчыма, прадузята, але код пісаць прыйдзецца мне - навошта прымушаць сябе рабіць тое, што не падабаецца.
Рэзюмэ: выбіраемы варыянт захоўвання ў выглядзе ланцужкоў «загаловак з даўжынёй - дадзеныя зменнай даўжыні» з-за эфектыўнасці і прастаты рэалізацыі.
Выкарыстанне бітавых палёў для кантролю паспяховасці аперацый запісу
Ужо зараз не памятаю, дзе я падгледзеў ідэю, але выглядае ўсё прыкладна так:
Для кожнага запісу вылучаем некалькі біт для захоўвання сцягоў.
Як мы казалі раней, пасля erase усе біты запоўненыя 1, і мы можам змяняць 1 на 0, але не наадварот. Так што для "сцяг не ўсталяваны" выкарыстоўваем 1, для "сцяг усталяваны" - 0.
Вось як можа выглядаць памяшканне запісу зменнай даўжыні ва flash:
- Усталёўваны сцяг "запіс даўжыні пачаўся";
- Запісваем даўжыню;
- Усталёўваны сцяг "запіс дадзеных пачаўся";
- Запісваем дадзеныя;
- Усталёўваны сцяг "запіс скончыўся".
Акрамя гэтага, у нас будзе сцяг “адбылася памылка”, разам 4 бітавыя сцягі.
У гэтым выпадку ў нас ёсць два стабільныя станы “1111” – запіс не пачаўся і “1000” – запіс прайшоў паспяхова; у выпадку непрадбачанага перапынення працэсу запісу атрымаем прамежкавыя станы, якія мы потым мы зможам выявіць і апрацаваць.
Падыход цікавы, але ён абараняе толькі ад раптоўнага адключэння харчавання і падобных збояў, што, вядома, важна, аднак гэта далёка не адзіная (і нават не асноўная) прычына магчымых збояў.
Рэзюмэ: ідзем далей у пошуках добрага рашэння.
Кантрольныя сумы
Кантрольныя сумы таксама даюць магчымасць упэўніцца (з дастатковай верагоднасцю) што мы чытаем менавіта тое, што павінна было быць запісана. І, у адрозненне ад разгледжаных вышэй бітавых палёў, яны працуюць заўсёды.
Калі разглядаць спіс патэнцыйных крыніц праблем, пра якія мы казалі вышэй, то кантрольная сума здольная распазнаць памылку незалежна ад яе паходжання (за выключэннем, мабыць, зламысных іншапланецян - тыя могуць падрабіць і кантрольную суму таксама).
Так што, калі наша мэта праверыць, што дадзеныя мэты, кантрольныя сумы - выдатная ідэя.
Выбар алгарытму вылічэння кантрольнай сумы пытанняў не выклікаў - CRC. З аднаго боку, матэматычныя ўласцівасці дазваляюць у 100% лавіць памылкі некаторых тыпаў, з іншай - на выпадковых дадзеных звычайна гэты алгарытм паказвае верагоднасць калізій не моцна больш тэарэтычнай мяжы . Хай гэта не самы хуткі алгарытм, не заўсёды мінімальны па колькасці калізій, але ў яго ёсць вельмі важная якасць: у сустраканых мне тэстах не трапляліся патэрны, на якіх ён бы відавочна правальваўся. Стабільнасць - гэта галоўнае якасць у дадзеным выпадку.
Прыклад аб'ёмнага даследавання: , (спасылкі на narod.ru, прабачце).
Аднак задача выбару кантрольнай сумы не завершана, CRC - гэта цэлае сямейства кантрольных сум. Трэба вызначыцца з даўжынёй, а потым абраць палінам.
Выбар даўжыні кантрольнай сумы не такое простае пытанне, як здаецца з першага погляду.
Праілюструю:
Няхай у нас верагоднасць памылкі ў кожным байце і ідэальная кантрольная сума, палічым сярэднюю колькасць памылак на мільён запісаў:
Дадзеныя, байт
Кантрольная сума, байт
Невыяўленых памылак
Ілжывых выяўленняў памылак
Разам няправільных спрацоўванняў
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
Здавалася б, усё проста - выбірай у залежнасці ад даўжыні абараняемых дадзеных даўжыню кантрольнай сумы з мінімумам няправільных спрацоўванняў - і справа ў капелюшы.
Аднак, з кароткімі кантрольнымі сумамі ўзнікае праблема: яны, хоць і добра выяўляюць адзінкавыя бітавыя памылкі, могуць з дастаткова вялікай верагоднасцю прыняць за дакладныя зусім выпадковыя дадзеныя. На хабры ўжо быў артыкул, які апісвае .
Таму, каб зрабіць выпадковае супадзенне кантрольнай сумы практычна немагчымым, трэба выкарыстоўваць кантрольныя сумы даўжынёй 32 біта і больш (для даўжынь больш за 64 біт звычайна выкарыстоўваюць крыптаграфічныя хэш-функцыі).
Нягледзячы на тое, што раней я пісаў, што трэба эканоміць месца ўсімі сіламі, усё ж такі будзем выкарыстоўваць 32-бітную кантрольную суму (16 біт мала, верагоднасць калізіі больш за 0.01%; а 24 біта, як гаворыцца, ні туды і ні сюды) .
Тут можа паўстаць пярэчанне: ці для таго мы эканомілі кожны байт пры выбары сціску, каб зараз аддаць 4 байта адразу? ці не лепш было не сціскаць і не дадаваць кантрольную суму? Вядома не, адсутнасць сціску не азначае, Што праверка цэласнасці нам не патрэбна.
Па выбары палінома не будзем вынаходзіць ровар, а возьмем папулярны зараз CRC-32C.
Гэты код выяўляе 6 бітавых памылак на пакетах да 22 байт (мабыць, самы часты выпадак для наc), 4 бітавыя памылкі на пакетах да 655 байт (таксама часты выпадак для нас), 2 ці любы няцотны лік бітавых памылак на пакетах любой разумнай даўжыні.
Калі каму цікавыя дэталі
пра CRC.
на - мабыць, галоўнага спецыяліста па CRC на планеце.
В ёсць , Які забяспечвае крыху лепшыя параметры для актуальных для нас даўжынь пакетаў, але я не палічыў розніцу істотнай, а сябе дастаткова кампетэнтным, каб выбраць кастамны код замест стандартнага і добра даследаванага.
Яшчэ, бо ў нас дадзеныя сціснутыя, узнікае пытанне: лічыць кантрольную суму сціснутых ці несціснутых дадзеных?
Аргументы "за" падлік кантрольнай сумы несціснутых дадзеных:
- нам у канчатковым выніку трэба праверыць захаванасць захоўвання дадзеных - вось мы яе напрамую і правяраем (пры гэтым будуць заадно правераны магчымыя памылкі ў рэалізацыі кампрэсіі / дэкампрэсіі, пашкоджанні, выкліканыя бітай памяццю і да т.п.);
- алгарытм deflate у zlib мае дастаткова спелую рэалізацыю і не павінен падаць пры «крывых» уваходных дадзеных, больш за тое, часцяком ён здольны самастойна выявіць памылкі ва ўваходным струмені, знізіўшы агульную верагоднасць невыяўлення памылкі (правёў тэст з інвертаваннем адзіночнага біта ў кароткім запісе, zlib выявіў памылку прыкладна ў траціне выпадкаў).
Аргументы "супраць" падліку кантрольнай сумы несціснутых дадзеных:
- CRC "заменчаны" менавіта пад нешматлікія бітавыя памылкі, якія характэрны для флэш-памяці (бітавая памылка ў сціснутым струмені можа даць масавае змена выходнага струменя, на якім, чыста тэарэтычна, мы можам "злавіць" калізію);
- мне не вельмі падабаецца ідэя перадаваць дэкампрэсару патэнцыйна бітыя дадзеныя, , як ён адрэагуе.
У дадзеным праекце я вырашыў адысці ад агульнапрынятай практыкі захоўвання кантрольнай сумы несціснутых дадзеных.
Рэзюмэ: выкарыстоўваем CRC-32C, кантрольную суму лічым ад дадзеных у тым выглядзе, у якім яны запісваюцца ва flash (пасля сціску).
Надмернасць
Выкарыстанне залішняга кадавання не дазваляе, вядома, выключыць страту дадзеных, аднак, яно можа істотна (часта на шматлікія парадкі) зменшыць верагоднасць невосстановимой страты дадзеных.
Мы можам выкарыстоўваць розныя віды надмернасці для таго, каб выпраўляць памылкі.
Коды Хэмінга могуць выпраўляць адзіночныя бітавыя памылкі, коды Рыда-Саламона знакавыя, некалькі копій дадзеных сумесна з кантрольнымі сумамі або кадаваньне накшталт RAID-6 могуць дапамагчы аднавіць дадзеныя нават у выпадку масавых пашкоджанняў.
Першапачаткова я быў настроены на шырокае выкарыстанне перашкодаўстойлівага кадавання, але потым зразумеў, што спачатку трэба мець уяўленне ад якіх памылак мы жадаем абараніцца, а потым ужо выбіраць кадаванне.
Мы казалі раней, што памылкі трэба выяўляць як мага хутчэй. У якія моманты мы можам сутыкнуцца з памылкамі?
- Няскончаны запіс (па якіх-небудзь прычынах у момант запісу адключылася харчаванне, завіс Raspberry, …)
Нажаль, у выпадку падобнай памылкі застаецца толькі ігнараваць невалідныя запісы і лічыць дадзеныя страчанымі; - Памылкі запісу (па якіх-небудзь чынніках у flash-памяць запісалася не тое, што запісвалася)
Падобныя памылкі мы можам адразу выявіць, калі мы непасрэдна пасля запісу будзем рабіць кантрольнае чытанне; - Скажэнне дадзеных у памяці ў працэсе захоўвання;
- Памылкі чытання
Для выпраўлення дастаткова ў выпадку несупадзення кантрольнай сумы некалькі разоў паўтарыць чытанне.
Гэта значыць толькі памылкі трэцяга тыпу (самаадвольнае псута дадзеных пры захоўванні) не могуць быць выпраўленыя без перашкодаўстойлівага кадавання. Думаецца, падобныя памылкі ўсё ж такі вельмі малаверагодныя.
Рэзюмэ: было вырашана адмовіцца ад залішняга кадавання, але, калі эксплуатацыя пакажа памылковасць гэтага рашэння, то вярнуцца да разгляду пытання (з ужо назапашанай статыстыкай па збоях, якая дазволіць абраць аптымальны выгляд кадавання).
Іншае
Зразумела, фармат артыкула не дазваляе абгрунтаваць кожны біт у фармаце. (ды і ў мяне ўжо скончыліся сілы), таму коратка прабягу па некаторых момантах, не закранутым раней.
- Вырашана рабіць усе старонкі "раўнапраўнымі"
Гэта значыць не будзе нейкіх спецыяльных старонак з метададзенымі, асобнымі патокамі і да т.п., замест гэтага адзіны паток, які перапісвае ўсе старонкі па чарзе.
Гэта забяспечвае раўнамерны знос старонак, астудства адзінай кропкі адмовы, ну і проста падабаецца; - Абавязкова трэба прадугледзець версійнасць фармату.
Фармат без нумара версіі ў загалоўку - зло!
Досыць дадаць у загаловак старонкі поле з нейкім Magic Number (сігнатурай), якое будзе паказваць на выкарыстоўваную версію фармату (не думаю, што іх на практыцы будзе нават дзясятак); - Выкарыстоўваць для запісаў (якіх вельмі шмат) загаловак зменнай даўжыні, імкнучыся для большасці выпадкаў зрабіць яго даўжынёй у 1 байт;
- Для кадавання даўжыні загалоўка і даўжыні якая абразаецца часткі сціснутага запісу выкарыстоўваць бінарныя коды зменнай даўжыні.
Вельмі дапамог кодаў Хафмана. Літаральна за некалькі хвілін удалося падабраць патрэбныя коды зменнай даўжыні.
Апісанне фармату захоўвання дадзеных
Парадак байтаў
Палі, памерам якія перавышаюць адзін байт, захоўваюцца ў big-endian фармаце (network byte order), гэта значыць 0x1234 запісваецца як 0x12, 0x34.
Дзяленне на старонкі
Уся флэш-памяць разбіта на старонкі роўнага памеру.
Памер старонкі па намачэнні 32Кб, але не больш, чым 1/4 ад агульнага памеру мікрасхемы памяці (для мікрасхемы на 4Мб атрымліваецца 128 старонак).
Кожная старонка захоўвае дадзеныя незалежна ад іншых (гэта значыць дадзеныя адной старонкі не спасылаюцца на дадзеныя іншай старонкі).
Усе старонкі пранумараваны ў натуральным парадку (у парадку ўзрастання адрасоў), пачынаючы з нумара 0 (нулявая старонка пачынаецца з адраса 0, першая - з 32Кб, другая - з 64Кб і г.д.)
Мікрасхема памяці выкарыстоўваецца як цыклічны буфер (ring buffer), гэта значыць спачатку запіс ідзе ў старонку з нумарам 0, потым з нумарам 1, …, калі мы запаўняем апошнюю старонку, то пачынаецца новы цыкл і запіс працягваецца з нулявой старонкі.
Унутры старонкі
У пачатку старонкі захоўваецца 4-байтны загаловак старонкі, потым кантрольная сума загалоўка (CRC-32C), далей захоўваюцца запісы ў фармаце "загаловак, дадзеныя, кантрольная сума".
Загаловак старонкі (на схеме брудна-зялёны) складаецца з:
- двухбайтнага поля Magic Number (ён жа – прыкмета версіі фармату)
для бягучай версіі фармату ён лічыцца як0xed00 ⊕ номер страницы; - двухбайтнага лічыльніка «Версія старонкі» (нумар цыклу перазапісу памяці).
Запісы на старонцы захоўваюцца ў сціснутым выглядзе (выкарыстоўваецца алгарытм deflate). Усе запісы на адной старонцы сціскаюцца ў адной плыні (выкарыстоўваецца агульны слоўнік), на кожнай новай старонцы сціск пачынаецца зноўку. Гэта значыць, для дэкампрэсіі любога запісу патрабуюцца ўсе папярэднія запісы з гэтай старонкі (і толькі з гэтага).
Кожны запіс сціскаецца са сцягам Z_SYNC_FLUSH, пры гэтым у канцы сціснутага струменя апыняюцца 4 байта 0x00, 0x00, 0xff, 0xff, папярэднія, магчыма, яшчэ адным ці двума нулявымі байтамі.
Гэтую паслядоўнасць (даўжынёй 4, 5 ці 6 байт) мы адкідаем пры запісе ў флэш-памяць.
Загаловак запісу ўяўляе з сябе 1, 2 ці 3 байта, якія захоўваюць:
- адзін біт (T), які азначае тып запісу: 0 - кантэкст, 1 - часопіс;
- поле зменнай даўжыні (S) ад 1 да 7 біт, якое вызначае даўжыню загалоўка і «хвост», які трэба дадаць да запісу для распакавання;
- даўжыню запісу (L).
Табліца значэнняў S:
S
Даўжыня загалоўка, байт
Адкідаецца пры запісе, байт
0
1
5 (00 00 00 ff ff)
10
1
6 (00 00 00 00 ff ff)
110
2
4 (00 00 ff ff)
1110
2
5 (00 00 00 ff ff)
11110
2
6 (00 00 00 00 ff ff)
1111100
3
4 (00 00 ff ff)
1111101
3
5 (00 00 00 ff ff)
1111110
3
6 (00 00 00 00 ff ff)
Паспрабаваў праілюстраваць, не ведаю, наколькі навочна атрымалася:
Жоўтым тут пазначана поле T, белым - поле S, зялёным L (даўжыня сціснутых дадзеных у байтах), блакітным - сціснутыя дадзеныя, чырвоным - канчатковыя байты сціснутых дадзеных, якія не пішуцца ў флэш-памяць.
Такім чынам, загалоўкі запісаў самай распаўсюджанай даўжыні (да 63+5 байт у сціснутым выглядзе) мы зможам запісаць адным байтам.
Пасля кожнага запісу захоўваецца кантрольная сума CRC-32C, у якой у якасці пачатковага значэння (init) выкарыстоўваецца інвертаваць значэнне папярэдняй кантрольнай сумы.
CRC валодае ўласцівасцю «працягласці», дзейнічае (плюс-мінус инвертирование біт падчас) такая формула: .
Гэта значыць фактычна мы вылічваем CRC усіх папярэдніх байт загалоўкаў і даных на гэтай старонцы.
Непасрэдна за кантрольнай сумай ляжыць загаловак наступнага запісу.
Загаловак сканструяваны такім чынам, каб першы яго байт быў заўсёды адрозны ад 0x00 і 0xff (калі замест першага байта загалоўка мы сустракаем 0xff, то значыць гэта пакуль невыкарыстоўваная вобласць; 0x00 жа сігналізуе пра памылку).
Прыкладныя алгарытмы
Чытанне з флэш-памяці
Любое чытанне ідзе з праверкай кантрольнай сумы.
Калі кантрольная сума не сышлася - чытанне паўтараецца некалькі разоў у надзеі прачытаць-ткі дакладныя дадзеныя.
(гэта мае сэнс, Linux не кэшуе чытанне з NOR Flash, праверана)
Запіс у флэш-памяць
Запісваем дадзеныя.
Чытаем іх.
Калі прачытаныя дадзеныя не супадаюць з запісанымі - запаўняем вобласць нулямі і сігналізуем пра памылку.
Падрыхтоўка новай мікрасхемы да працы
Для ініцыялізацыі ў першую (дакладней нулявую) старонку запісваецца загаловак з версіяй 1.
Пасля гэтага ў гэтую старонку запісваецца пачатковы кантэкст (змяшчае UUID аўтамата і дэфолтныя налады).
Усё, флэш-памяць гатова да працы.
Загрузка аўтамата
Пры загрузцы чытаюцца першыя 8 байт кожнай старонкі (загаловак + CRC), старонкі з невядомым Magic Number ці няслушным CRC ігнаруюцца.
З "правільных" старонак выбіраюцца старонкі з максімальнай версіяй, з іх бярэцца старонка, якая мае найбольшы нумар.
Счытваецца першы запіс, правяраецца карэктнасць CRC, наяўнасць сцяга "кантэкст". Калі ўсё нармальна - гэтая старонка лічыцца бягучай. Калі не - адкочваемся на папярэднюю, пакуль не знойдзем "жывую" старонку.
а знойдзенай старонцы счытваем усе запісы, тыя, якія са сцягам «кантэкст» ужывальны.
Захоўваем слоўнік zlib (патрэбен будзе для дазапісу ў гэтую старонку).
Усё, загрузка завершана, кантэкст адноўлены, можна працаваць.
Даданне запісу ў часопіс
Сціскаем запіс з правільным слоўнікам, паказваючы Z_SYNC_FLUSH.Глядзім, ці змяшчаецца сціснуты запіс на бягучай старонцы.
Калі не змяшчаецца (ці на старонцы былі памылкі CRC) - пачынаем новую старонку (гл. ніжэй).
Запісваем запіс і CRC. Калі адбылася памылка - пачынаем новую старонку.
Новая старонка
Выбіраем свабодную старонку з мінімальным нумарам (свабоднай мы лічым старонку з няправільнай кантрольнай сумай у загалоўку або з версіяй меншай за бягучую). Калі такіх старонак няма - выбіраем старонку з мінімальным нумарам з тых, што маюць версію роўную бягучай.
Які робіцца абранай старонцы erase. Звяраем змесціва з 0xff. Калі нешта не так - бярэм наступную свабодную старонку, і г.д.
На сьцёртую старонку запісваем загаловак, першым запісам бягучы стан кантэксту, наступным — незапісаны запіс часопіса (калі ён ёсць).
Ужывальнасць фармату
На маю думку, атрымаўся нядрэнны фармат для захоўвання любых больш-менш сцісканых патокаў інфармацыі (просты тэкст, JSON, MessagePack, CBOR, магчыма, protobuf) у NOR Flash.
Вядома, фармат "заменчаны" пад SLC NOR Flash.
Яго не варта выкарыстоўваць з носьбітамі з высокім BER, напрыклад NAND ці MLC NOR (а такая памяць наогул ёсць у продажы? сустракаў згадванні толькі ў працах па кодах карэкцыі).
Тым больш, яго не варта выкарыстоўваць з прыладамі, якія маюць свой FTL: USB flash, SD, MicroSD, etc (Для такой памяці я рабіў фармат з памерам старонкі ў 512 байт, сігнатурай у пачатку кожнай старонкі і ўнікальнымі нумарамі запісаў - часам з «глюкнула» флэшкі атрымоўвалася простым паслядоўным чытаннем аднавіць усе дадзеныя).
У залежнасці ад задач фармат без змен можна выкарыстоўваць на флэшках ад 128Кбіт (16Кб) да 1Гбіт (128Мб). Пры жаданні можна выкарыстоўваць і на мікрасхемах большага аб'ёму, толькі, мусіць, трэба скарэктаваць памер старонкі (Але тут ужо ўстае пытанне эканамічнай мэтазгоднасці, кошт на NOR Flash вялікага аб'ёму не цешыць).
Калі камусьці фармат здаўся цікавым, і ён захоча выкарыстоўваць яго ў адкрытым праекце - пішыце, пастараюся знайсці час, прычасаць код і выкласці на github.
Заключэнне
Як бачым, у выніку фармат аказаўся простым. і нават сумным.
У артыкуле складана адлюстраваць эвалюцыю свайго пункта гледжання, але паверце: першапачаткова мне жадалася стварыць нешта наварочанае, неубиваемое, здольнае выжыць нават пасля ядзернага выбуху ў непасрэднай блізкасці. Аднак, розум (спадзяюся) усё ж такі перамог і паступова прыярытэты ссунулася да прастаты і кампактнасці.
Ці можа атрымацца так, што я памыліўся? Так, вядома. Цалкам можа аказацца, напрыклад, што мы закупілі партыю няякасных мікрасхем. Або па нейкім іншым чынніку абсталяванне не апраўдае чаканні па надзейнасці.
Ці ёсць у мяне план на гэты выпадак? Я думаю, што па чытанні артыкула вы не сумняваецеся, што план ёсць. І нават не адзін.
Калі крыху больш сур'ёзна, фармат распрацаваны адначасова і як працоўны варыянт, і як «пробны шар».
На сённяшні момант на стале ўсё працуе нармальна, літаральна на днях рашэнне будзе разгорнута. (прыкладна) на сотні прылад, паглядзім, што будзе ў «баявой» эксплуатацыі (балазе, спадзяюся, фармат дазваляе надзейна дэтэктаваць збоі; так што атрымаецца сабраць паўнавартасную статыстыку). Праз некалькі месяцаў можна будзе рабіць высновы (а калі не павязе - то і раней).
Калі па выніках выкарыстання будуць сур'ёзныя праблемы і спатрэбяцца дапрацоўкі, то я абавязкова пра гэта напішу.
Літаратура
Не жадалася складаць доўгі нудны спіс скарыстаных прац, у выніку гугл ёсць ва ўсіх.
Тут я вырашыў пакідаць спіс знаходак, якія мне падаліся асабліва цікавымі, аднак паступова яны перавандравалі непасрэдна ў тэкст артыкула, і ў спісе застаўся адзін пункт:
- ўтыліта ад аўтара zlib. Умее ў зразумелым выглядзе адлюстроўваць змесціва архіваў deflate/zlib/gzip. Калі вам даводзіцца разбірацца з унутранай прыладай фармату deflate (або gzip) - настойліва рэкамендую.
Крыніца: habr.com