Передісторія
Існують торгові автомати власної розробки. Усередині 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 XNUMX циклів 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Кб.
У статті, на яку я посилаюся, є пояснення:
Новий тип блоку 0 з empty contents is appended.
A type 0 block with empty contents consists of:
- the three-bit block header;
- 0 to 7 bits equal to zero, to achieve byte alignment;
- 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