prasejarah

Ada mesin penjual otomatis dengan desain kami sendiri. Di dalam Raspberry Pi dan beberapa kabel di papan terpisah. Akseptor koin, akseptor tagihan, terminal bank terhubung... Semuanya dikendalikan oleh program yang ditulis sendiri. Seluruh riwayat pekerjaan ditulis ke log pada flash drive (MicroSD), yang kemudian dikirimkan melalui Internet (menggunakan modem USB) ke server, di mana ia disimpan dalam database. Informasi penjualan dimuat ke 1c, ada juga antarmuka web sederhana untuk pemantauan, dll.

Artinya, jurnal sangat penting - untuk akuntansi (pendapatan, penjualan, dll.), pemantauan (segala jenis kegagalan dan keadaan force majeure lainnya); Bisa dikatakan, ini adalah seluruh informasi yang kami miliki tentang mesin ini.

masalah

Flash drive terbukti menjadi perangkat yang sangat tidak dapat diandalkan. Mereka gagal dengan keteraturan yang patut ditiru. Hal ini menyebabkan waktu henti mesin dan (jika karena alasan tertentu log tidak dapat ditransfer secara online) hingga hilangnya data.

Ini bukan pengalaman pertama menggunakan flash drive, sebelumnya ada proyek lain dengan lebih dari seratus perangkat, dimana majalah disimpan di USB flash drive, ada juga masalah dengan keandalan, kadang-kadang jumlah yang gagal di sebulan jumlahnya mencapai puluhan. Kami mencoba berbagai flash drive, termasuk flash drive bermerek dengan memori SLC, dan beberapa model lebih andal dibandingkan yang lain, namun mengganti flash drive tidak menyelesaikan masalah secara radikal.

Peringatan! Bacaan panjang! Jika Anda tidak tertarik pada “mengapa”, tetapi hanya pada “bagaimana”, Anda bisa langsung bertanya Pada akhirnya artikel.

keputusan

Hal pertama yang terlintas dalam pikiran adalah: tinggalkan MicroSD, instal, misalnya, SSD, dan boot darinya. Secara teoritis mungkin, tetapi relatif mahal, dan tidak terlalu dapat diandalkan (adaptor USB-SATA ditambahkan; statistik kegagalan untuk SSD anggaran juga tidak menggembirakan).

USB HDD juga sepertinya bukan solusi yang menarik.

Oleh karena itu, kami sampai pada opsi ini: tinggalkan booting dari MicroSD, tetapi gunakan dalam mode read-only, dan simpan log operasi (dan informasi unik lainnya untuk perangkat keras tertentu - nomor seri, kalibrasi sensor, dll.) di tempat lain. .

Topik FS read-only untuk raspberry telah dipelajari luar dalam, saya tidak akan membahas detail implementasinya di artikel ini (tapi jika ada minat, mungkin saya akan menulis artikel mini tentang topik ini). Satu-satunya hal yang ingin saya catat adalah bahwa baik dari pengalaman pribadi maupun dari ulasan mereka yang telah menerapkannya, ada peningkatan dalam keandalan. Ya, tidak mungkin untuk sepenuhnya menghilangkan kerusakan, tetapi sangat mungkin untuk mengurangi frekuensinya secara signifikan. Dan kartu-kartu tersebut menjadi menyatu, sehingga penggantian menjadi lebih mudah bagi petugas servis.

Perangkat keras

Tidak ada keraguan khusus tentang pilihan jenis memori - NOR Flash.
Argumen:

• koneksi sederhana (paling sering bus SPI, yang sudah pernah Anda gunakan, jadi tidak ada masalah perangkat keras yang diperkirakan);
• harga konyol;
• protokol operasi standar (implementasinya sudah ada di kernel Linux, jika mau, Anda dapat mengambil pihak ketiga, yang juga ada, atau bahkan menulis sendiri, untungnya semuanya sederhana);
• keandalan dan sumber daya:
  dari lembar data biasa: data disimpan selama 20 tahun, 100000 siklus penghapusan untuk setiap blok;
  dari sumber pihak ketiga: BER sangat rendah, tidak memerlukan kode koreksi kesalahan (beberapa karya menganggap ECC sebagai NOR, tetapi biasanya tetap berarti MLC NOR; hal ini juga terjadi).

Mari kita perkirakan kebutuhan volume dan sumber daya.

Saya ingin data dijamin disimpan selama beberapa hari. Hal ini diperlukan agar jika terjadi masalah komunikasi, riwayat penjualan tidak hilang. Kami akan fokus pada 5 hari, selama periode ini (bahkan dengan memperhitungkan akhir pekan dan hari libur) masalahnya dapat diselesaikan.

Saat ini kami mengumpulkan sekitar 100kb log per hari (3-4 ribu entri), tetapi secara bertahap angka ini bertambah - detailnya meningkat, acara baru ditambahkan. Ditambah lagi, terkadang ada ledakan (misalnya, beberapa sensor mulai mengirim spam dengan positif palsu). Kami akan menghitung 10 ribu catatan masing-masing 100 byte - megabita per hari.

Secara total, 5MB data bersih (terkompresi dengan baik) keluar. Lebih kepada mereka (Taksiran kasar) 1MB data layanan.

Artinya, kita membutuhkan chip sebesar 8MB jika tidak menggunakan kompresi, atau 4MB jika digunakan. Angka yang cukup realistis untuk jenis memori ini.

Adapun sumber dayanya: jika kita merencanakan bahwa seluruh memori akan ditulis ulang tidak lebih dari sekali setiap 5 hari, maka selama 10 tahun pelayanan kita mendapatkan kurang dari seribu siklus penulisan ulang.
Izinkan saya mengingatkan Anda bahwa pabrikan menjanjikan seratus ribu.

Sedikit tentang NOR vs NAND

Saat ini, tentu saja, memori NAND jauh lebih populer, tetapi saya tidak akan menggunakannya untuk proyek ini: NAND, tidak seperti NOR, memerlukan penggunaan kode koreksi kesalahan, tabel blok buruk, dll., dan juga kaki-kaki dari Chip NAND biasanya lebih banyak.

Kerugian dari NOR meliputi:

• volume kecil (dan, karenanya, harga per megabyte yang tinggi);
• kecepatan komunikasi yang rendah (sebagian besar disebabkan oleh penggunaan antarmuka serial, biasanya SPI atau I2C);
• penghapusan lambat (tergantung pada ukuran blok, dibutuhkan sepersekian detik hingga beberapa detik).

Sepertinya tidak ada yang penting bagi kami, jadi kami lanjutkan.

Jika detailnya menarik, sirkuit mikro telah dipilih di25df321a (namun, ini tidak penting, ada banyak analog di pasaran yang kompatibel dalam pinout dan sistem perintah; bahkan jika kita ingin memasang sirkuit mikro dari pabrikan lain dan/atau ukuran berbeda, semuanya akan berfungsi tanpa mengubah kode).

Saya menggunakan driver yang terpasang di kernel Linux; di Raspberry, berkat dukungan overlay pohon perangkat, semuanya sangat sederhana - Anda perlu meletakkan overlay yang dikompilasi di /boot/overlays dan sedikit memodifikasi /boot/config.txt.

Contoh file dts

Sejujurnya, saya tidak yakin ini ditulis tanpa kesalahan, tapi berhasil.

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

Dan baris lain di config.txt

dtoverlay=at25:spimaxfrequency=50000000

Saya akan menghilangkan deskripsi menghubungkan chip ke Raspberry Pi. Di satu sisi, saya bukan ahli elektronik, di sisi lain, semuanya di sini dangkal bahkan bagi saya: sirkuit mikro hanya memiliki 8 kaki, yang mana kita membutuhkan ground, power, SPI (CS, SI, SO, SCK ); levelnya sama dengan Raspberry Pi, tidak diperlukan kabel tambahan - cukup sambungkan 6 pin yang ditunjukkan.

Pernyataan masalah

Seperti biasa, pernyataan masalah mengalami beberapa kali pengulangan, dan menurut saya sudah waktunya untuk pengulangan berikutnya. Jadi mari kita berhenti, kumpulkan apa yang telah ditulis, dan perjelas detail yang masih tersembunyi.

Jadi, kami telah memutuskan bahwa log akan disimpan di SPI NOR Flash.

Apa itu NOR Flash bagi yang belum tahu?

Ini adalah memori non-volatil yang dapat digunakan untuk melakukan tiga operasi:

1. Membaca:
   Pembacaan yang paling umum: kami mengirimkan alamat dan membaca byte sebanyak yang kami butuhkan;
2. Rekam:
   Menulis ke flash NOR terlihat seperti biasa, tetapi memiliki satu kekhasan: Anda hanya dapat mengubah 1 menjadi 0, tetapi tidak sebaliknya. Misalnya, jika kita memiliki 0x55 di sel memori, maka setelah menulis 0x0f ke dalamnya, 0x05 sudah disimpan di sana (lihat tabel tepat di bawah);
3. Menghapus:
   Tentu saja, kita harus bisa melakukan operasi sebaliknya - mengubah 0 menjadi 1, inilah gunanya operasi penghapusan. Berbeda dengan dua yang pertama, ini tidak beroperasi dengan byte, tetapi dengan blok (blok penghapusan minimum dalam chip yang dipilih adalah 4kb). Penghapusan menghancurkan seluruh blok dan merupakan satu-satunya cara untuk mengubah 0 menjadi 1. Oleh karena itu, ketika bekerja dengan memori flash, Anda sering kali harus menyelaraskan struktur data ke batas blok penghapusan.
   Merekam dalam NOR Flash:

Data biner

Apakah
01010101

Tercatat
00001111

Telah menjadi
00000101

Log itu sendiri mewakili urutan catatan dengan panjang variabel. Panjang khas sebuah record adalah sekitar 30 byte (walaupun kadang-kadang ada catatan yang panjangnya beberapa kilobyte). Dalam hal ini, kami bekerja dengan mereka hanya sebagai satu set byte, tetapi, jika Anda tertarik, CBOR digunakan di dalam catatan

Selain log, kita perlu menyimpan beberapa informasi “pengaturan”, baik yang diperbarui maupun tidak: ID perangkat tertentu, kalibrasi sensor, tanda “perangkat dinonaktifkan sementara”, dll.
Informasi ini adalah kumpulan catatan nilai kunci, juga disimpan di CBOR. Kami tidak memiliki banyak informasi ini (paling banyak hanya beberapa kilobyte), dan jarang diperbarui.
Berikut ini kita akan menyebutnya konteks.

Jika kita ingat di mana artikel ini dimulai, sangatlah penting untuk memastikan penyimpanan data yang andal dan, jika mungkin, pengoperasian yang berkelanjutan bahkan jika terjadi kegagalan perangkat keras/kerusakan data.

Sumber masalah apa yang dapat dipertimbangkan?

• Matikan selama operasi tulis/hapus. Ini termasuk dalam kategori “tidak ada trik melawan linggis”.
  Informasi dari diskusi di stackexchange: ketika daya dimatikan saat bekerja dengan flash, penghapusan (setel ke 1) dan tulis (setel ke 0) menyebabkan perilaku tidak terdefinisi: data dapat ditulis, ditulis sebagian (misalnya, kami mentransfer 10 byte/80 bit , tetapi belum hanya 45 bit yang dapat ditulis), mungkin juga beberapa bit berada dalam keadaan “menengah” (pembacaan dapat menghasilkan 0 dan 1);
• Kesalahan pada memori flash itu sendiri.
  BER, meskipun sangat rendah, tidak bisa sama dengan nol;
• kesalahan bus
  Data yang dikirimkan melalui SPI tidak dilindungi dengan cara apa pun; kesalahan bit tunggal dan kesalahan sinkronisasi dapat terjadi - kehilangan atau penyisipan bit (yang menyebabkan distorsi data besar-besaran);
• Kesalahan/gangguan lainnya
  Kesalahan dalam kode, gangguan Raspberry, gangguan alien...

Saya telah merumuskan persyaratan, yang menurut pendapat saya, pemenuhannya diperlukan untuk memastikan keandalan:

• catatan harus segera masuk ke memori flash, penulisan yang tertunda tidak dipertimbangkan; - jika terjadi kesalahan, kesalahan tersebut harus dideteksi dan diproses sedini mungkin; - sistem harus, jika memungkinkan, pulih dari kesalahan.
  (contoh dari kehidupan "bagaimana seharusnya tidak terjadi", yang menurut saya pernah ditemui semua orang: setelah reboot darurat, sistem file "rusak" dan sistem operasi tidak bisa boot)

Ide, pendekatan, refleksi

Ketika saya mulai memikirkan masalah ini, banyak ide terlintas di kepala saya, misalnya:

• gunakan kompresi data;
• menggunakan struktur data yang cerdas, misalnya, menyimpan header rekaman secara terpisah dari rekaman itu sendiri, sehingga jika ada kesalahan dalam rekaman mana pun, Anda dapat membaca sisanya tanpa masalah;
• gunakan bidang bit untuk mengontrol penyelesaian perekaman saat daya dimatikan;
• menyimpan checksum untuk semuanya;
• menggunakan beberapa jenis pengkodean tahan kebisingan.

Beberapa dari ide-ide ini digunakan, sementara yang lain diputuskan untuk ditinggalkan. Ayo berangkat secara berurutan.

Kompresi data

Peristiwa itu sendiri yang kami catat di jurnal cukup mirip dan dapat diulang (“melempar koin 5 rubel”, “menekan tombol untuk memberi uang kembalian”, ...). Oleh karena itu, kompresi seharusnya cukup efektif.

Overhead kompresi tidak signifikan (prosesor kami cukup kuat, bahkan Pi pertama memiliki satu inti dengan frekuensi 700 MHz, model saat ini memiliki beberapa inti dengan frekuensi lebih dari satu gigahertz), nilai tukar dengan penyimpanan rendah (beberapa megabyte per detik), ukuran rekamannya kecil. Secara umum, jika kompresi berdampak pada performa, maka dampaknya hanya positif. (sama sekali tidak kritis, hanya menyatakan). Selain itu, kami tidak memiliki Linux yang benar-benar tertanam, tetapi Linux biasa - jadi implementasinya tidak memerlukan banyak usaha (cukup dengan menautkan perpustakaan dan menggunakan beberapa fungsi darinya).

Sepotong log diambil dari perangkat yang berfungsi (1.7 MB, 70 ribu entri) dan pertama kali diperiksa kompresibilitasnya menggunakan gzip, lz4, lzop, bzip2, xz, zstd yang tersedia di komputer.

• gzip, xz, zstd menunjukkan hasil yang serupa (40Kb).
  Saya terkejut bahwa xz yang modis muncul di sini pada level gzip atau zstd;
• lzip dengan pengaturan default memberikan hasil yang sedikit lebih buruk;
• lz4 dan lzop menunjukkan hasil yang tidak terlalu bagus (150Kb);
• bzip2 menunjukkan hasil yang sangat bagus (18Kb).

Jadi, datanya dikompresi dengan sangat baik.
Jadi (jika kita tidak menemukan kekurangan yang fatal) akan terjadi kompresi! Hanya karena lebih banyak data yang dapat ditampung dalam flash drive yang sama.

Mari kita pikirkan kerugiannya.

Masalah pertama: kita sudah sepakat bahwa setiap record harus segera di-flash. Biasanya, pengarsip mengumpulkan data dari aliran masukan hingga diputuskan bahwa sudah waktunya untuk menulis pada akhir pekan. Kita perlu segera menerima blok data terkompresi dan menyimpannya dalam memori non-volatile.

Saya melihat tiga cara:

1. Kompres setiap catatan menggunakan kompresi kamus, bukan algoritma yang dibahas di atas.
   Ini adalah opsi yang sepenuhnya berfungsi, tapi saya tidak menyukainya. Untuk memastikan tingkat kompresi yang lebih atau kurang layak, kamus harus “disesuaikan” dengan data tertentu; perubahan apa pun akan menyebabkan tingkat kompresi turun drastis. Ya, masalahnya dapat diselesaikan dengan membuat kamus versi baru, tetapi ini memusingkan - kita perlu menyimpan semua versi kamus; di setiap entri kita perlu menunjukkan versi kamus mana yang dikompresi...
2. Kompres setiap rekaman menggunakan algoritme “klasik”, namun independen satu sama lain.
   Algoritma kompresi yang dipertimbangkan tidak dirancang untuk bekerja dengan catatan sebesar ini (puluhan byte), rasio kompresi jelas akan kurang dari 1 (yaitu, meningkatkan volume data alih-alih mengompresi);
3. Lakukan FLUSH setelah setiap rekaman.
   Banyak perpustakaan kompresi memiliki dukungan untuk FLUSH. Ini adalah perintah (atau parameter untuk prosedur kompresi), setelah diterima, pengarsip membentuk aliran terkompresi sehingga dapat digunakan untuk memulihkan semua data terkompresi yang telah diterima. Analog yang seperti itu sync dalam sistem file atau commit di sql.
   Yang penting adalah operasi kompresi selanjutnya akan dapat menggunakan kamus yang terakumulasi dan rasio kompresi tidak akan terlalu terpengaruh seperti pada versi sebelumnya.

Saya rasa sudah jelas saya memilih opsi ketiga, mari kita lihat lebih detail.

Ditemukan artikel bagus tentang FLUSH di zlib.

Saya melakukan tes lutut berdasarkan artikel, mengambil 70 ribu entri log dari perangkat nyata, dengan ukuran halaman 60Kb (kita akan kembali ke ukuran halaman nanti) diterima:

Data mentah
Kompresi gzip -9 (tanpa FLUSH)
zlib dengan Z_PARTIAL_FLUSH
zlib dengan Z_SYNC_FLUSH

Volume, KB
1692
40
352
604

Pada pandangan pertama, harga yang disumbangkan oleh FLUSH sangat tinggi, namun kenyataannya kita tidak punya banyak pilihan - baik tidak mengompres sama sekali, atau mengompres (dan sangat efektif) dengan FLUSH. Kita tidak boleh lupa bahwa kita memiliki 70 ribu record, redundansi yang diperkenalkan oleh Z_PARTIAL_FLUSH hanya 4-5 byte per record. Dan rasio kompresinya ternyata hampir 5:1, yang lebih dari sekadar hasil luar biasa.

Ini mungkin mengejutkan, tapi Z_SYNC_FLUSH sebenarnya adalah cara yang lebih efisien untuk melakukan FLUSH

Saat menggunakan Z_SYNC_FLUSH, 4 byte terakhir setiap entri akan selalu 0x00, 0x00, 0xff, 0xff. Dan jika kita mengetahuinya, maka kita tidak perlu menyimpannya, jadi ukuran akhirnya hanya 324Kb saja.

Artikel yang saya tautkan memiliki penjelasan:

Blok tipe 0 baru dengan konten kosong ditambahkan.

Blok tipe 0 dengan konten kosong terdiri dari:

• header blok tiga-bit;
• 0 hingga 7 bit sama dengan nol, untuk mencapai penyelarasan byte;
• urutan empat byte 00 00 FF FF.

Seperti yang dapat Anda lihat dengan mudah, di blok terakhir sebelum 4 byte ini terdapat 3 hingga 10 bit nol. Namun, praktik telah menunjukkan bahwa sebenarnya ada setidaknya 10 bit nol.

Ternyata blok data pendek seperti itu biasanya (selalu?) dikodekan menggunakan blok tipe 1 (blok tetap), yang diakhiri dengan 7 bit nol, sehingga menghasilkan total 10-17 bit nol yang dijamin (dan sisanya akan menjadi nol dengan probabilitas sekitar 50%).

Jadi, pada data pengujian, dalam 100% kasus terdapat satu byte nol sebelum 0x00, 0x00, 0xff, 0xff, dan di lebih dari sepertiga kasus terdapat dua byte nol (mungkin faktanya saya menggunakan CBOR biner, dan ketika menggunakan teks JSON, blok tipe 2 - blok dinamis akan lebih umum, masing-masing, blok tanpa tambahan nol byte sebelum 0x00, 0x00, 0xff, 0xff akan ditemui).

Secara total, dengan menggunakan data pengujian yang tersedia, dimungkinkan untuk memuat kurang dari 250Kb data terkompresi.

Anda dapat menghemat lebih banyak dengan melakukan bit juggling: untuk saat ini kita abaikan keberadaan beberapa bit nol di akhir blok, beberapa bit di awal blok juga tidak berubah...
Namun kemudian saya mengambil keputusan dengan tekad kuat untuk berhenti, jika tidak, jika terus begini, saya mungkin akan mengembangkan pengarsip saya sendiri.

Secara total, dari data pengujian saya menerima 3-4 byte per penulisan, rasio kompresinya ternyata lebih dari 6:1. Jujur saja: Saya tidak mengharapkan hasil seperti itu; menurut pendapat saya, apa pun yang lebih baik dari 2:1 sudah merupakan hasil yang membenarkan penggunaan kompresi.

Semuanya baik-baik saja, tetapi zlib (deflate) masih merupakan algoritma kompresi yang kuno, memang layak, dan agak kuno. Fakta bahwa 32Kb terakhir dari aliran data yang tidak terkompresi digunakan sebagai kamus terlihat aneh saat ini (yaitu, jika beberapa blok data sangat mirip dengan apa yang ada di aliran masukan 40Kb yang lalu, maka blok tersebut akan mulai diarsipkan lagi, dan tidak akan mengacu pada kejadian sebelumnya). Dalam pengarsip modern yang modis, ukuran kamus sering kali diukur dalam megabyte, bukan kilobyte.

Jadi kami melanjutkan studi singkat kami tentang pengarsipan.

Selanjutnya kami menguji bzip2 (ingat, tanpa FLUSH, ini menunjukkan rasio kompresi yang fantastis hampir 100:1). Sayangnya, kinerjanya sangat buruk dengan FLUSH; ukuran data yang dikompresi ternyata lebih besar daripada data yang tidak dikompresi.

Asumsi saya tentang alasan kegagalan

Libbz2 hanya menawarkan satu opsi flush, yang sepertinya menghapus kamus (analog dengan Z_FULL_FLUSH di zlib); tidak ada pembicaraan tentang kompresi efektif apa pun setelah ini.

Dan yang terakhir diuji adalah zstd. Tergantung pada parameternya, kompresinya berada pada tingkat gzip, tetapi jauh lebih cepat, atau lebih baik daripada gzip.

Sayangnya, dengan FLUSH kinerjanya tidak terlalu baik: ukuran data yang dikompresi sekitar 700Kb.

Я mengajukan pertanyaan di halaman github proyek, saya menerima jawaban bahwa Anda harus mengandalkan hingga 10 byte data layanan untuk setiap blok data terkompresi, yang mendekati hasil yang diperoleh; tidak ada cara untuk mengejar deflasi.

Saya memutuskan untuk berhenti pada titik ini dalam eksperimen saya dengan pengarsip (izinkan saya mengingatkan Anda bahwa xz, lzip, lzo, lz4 tidak menunjukkan diri mereka sendiri bahkan pada tahap pengujian tanpa FLUSH, dan saya tidak mempertimbangkan algoritma kompresi yang lebih eksotis).

Mari kembali ke masalah pengarsipan.

Masalah kedua (seperti yang mereka katakan dalam urutan, bukan dalam nilai) adalah bahwa data yang dikompresi adalah aliran tunggal, di mana selalu ada referensi ke bagian sebelumnya. Jadi, jika suatu bagian dari data terkompresi rusak, kita tidak hanya kehilangan blok terkait dari data yang tidak terkompresi, tetapi juga semua blok berikutnya.

Ada pendekatan untuk mengatasi masalah ini:

1. Cegah terjadinya masalah - tambahkan redundansi ke data terkompresi, yang memungkinkan Anda mengidentifikasi dan memperbaiki kesalahan; kita akan membicarakannya nanti;
2. Minimalkan konsekuensi jika terjadi masalah
   Kami telah mengatakan sebelumnya bahwa Anda dapat mengompresi setiap blok data secara mandiri, dan masalahnya akan hilang dengan sendirinya (kerusakan pada data satu blok akan menyebabkan hilangnya data hanya untuk blok ini). Namun, ini adalah kasus ekstrim dimana kompresi data menjadi tidak efektif. Ekstrem sebaliknya: gunakan semua 4MB chip kami sebagai satu arsip, yang akan memberi kami kompresi yang sangat baik, tetapi konsekuensi yang sangat buruk jika terjadi kerusakan data.
   Ya, diperlukan kompromi dalam hal keandalan. Namun kita harus ingat bahwa kita sedang mengembangkan format penyimpanan data untuk memori non-volatile dengan BER yang sangat rendah dan jangka waktu penyimpanan data yang dinyatakan selama 20 tahun.

Selama percobaan, saya menemukan bahwa kerugian yang kurang lebih nyata pada tingkat kompresi dimulai pada blok data terkompresi yang berukuran kurang dari 10 KB.
Telah disebutkan sebelumnya bahwa memori yang digunakan adalah halaman; Saya tidak melihat alasan mengapa korespondensi “satu halaman - satu blok data terkompresi” tidak boleh digunakan.

Artinya, ukuran halaman minimum yang wajar adalah 16Kb (dengan cadangan untuk informasi layanan). Namun, ukuran halaman sekecil itu memberikan batasan yang signifikan pada ukuran catatan maksimum.

Meskipun saya belum mengharapkan rekaman yang lebih besar dari beberapa kilobyte dalam bentuk terkompresi, saya memutuskan untuk menggunakan halaman 32Kb (dengan total 128 halaman per chip).

Ringkasan:

• Kami menyimpan data yang dikompresi menggunakan zlib (deflate);
• Untuk setiap entri kami menetapkan Z_SYNC_FLUSH;
• Untuk setiap rekaman terkompresi, kami memangkas byte tambahan (misalnya 0x00, 0x00, 0xff, 0xff); di header kami menunjukkan berapa banyak byte yang kami potong;
• Kami menyimpan data dalam halaman 32Kb; ada satu aliran data terkompresi di dalam halaman; Di setiap halaman kami memulai kompresi lagi.

Dan, sebelum menyelesaikan kompresi, saya ingin menarik perhatian Anda pada fakta bahwa kami hanya memiliki beberapa byte data terkompresi per catatan, jadi sangat penting untuk tidak membesar-besarkan informasi layanan, setiap byte penting di sini.

Menyimpan Header Data

Karena kita memiliki catatan dengan panjang variabel, kita perlu menentukan penempatan/batas catatan.

Saya tahu tiga pendekatan:

1. Semua record disimpan dalam aliran berkelanjutan, pertama ada header record yang berisi panjangnya, dan kemudian record itu sendiri.
   Dalam perwujudan ini, header dan data dapat memiliki panjang yang bervariasi.
   Pada dasarnya, kita mendapatkan daftar tertaut tunggal yang digunakan sepanjang waktu;
2. Header dan catatannya sendiri disimpan dalam aliran terpisah.
   Dengan menggunakan header dengan panjang konstan, kami memastikan bahwa kerusakan pada satu header tidak mempengaruhi header lainnya.
   Pendekatan serupa digunakan, misalnya, di banyak sistem file;
3. Catatan disimpan dalam aliran berkelanjutan, batas catatan ditentukan oleh penanda tertentu (karakter/urutan karakter yang dilarang dalam blok data). Jika ada penanda di dalam record, maka kita ganti dengan beberapa sequence (escap it).
   Pendekatan serupa digunakan, misalnya, dalam protokol PPP.

saya akan ilustrasikan.

Option 1:

Semuanya sangat sederhana di sini: mengetahui panjang record, kita dapat menghitung alamat header berikutnya. Jadi kita menelusuri judulnya sampai kita menemukan area yang diisi dengan 0xff (area bebas) atau akhir halaman.

Option 2:

Karena panjang catatan yang bervariasi, kami tidak dapat mengatakan sebelumnya berapa banyak catatan (dan juga header) yang kami perlukan per halaman. Anda dapat menyebarkan header dan datanya ke berbagai halaman berbeda, namun saya lebih memilih pendekatan yang berbeda: kita menempatkan header dan data pada satu halaman, namun header (dengan ukuran konstan) berasal dari awal halaman, dan data (dengan panjang variabel) berasal dari akhir. Segera setelah mereka “bertemu” (tidak ada cukup ruang kosong untuk entri baru), kami menganggap halaman ini selesai.

Option 3:

Tidak perlu menyimpan panjang atau informasi lain tentang lokasi data di header; penanda yang menunjukkan batas-batas catatan sudah cukup. Namun data tersebut harus diolah pada saat menulis/membaca.
Saya akan menggunakan 0xff sebagai penanda (yang mengisi halaman setelah dihapus), sehingga area bebas pasti tidak akan diperlakukan sebagai data.

Tabel perbandingan:

Opsi 1
Opsi 2
Opsi 3

Toleransi kesalahan
-
+
+

Kekompakan
+
-
+

Kompleksitas implementasi
*
**
**

Opsi 1 memiliki kesalahan fatal: jika salah satu header rusak, seluruh rantai berikutnya akan hancur. Opsi lainnya memungkinkan Anda memulihkan beberapa data bahkan jika terjadi kerusakan besar.
Namun di sini penting untuk diingat bahwa kami memutuskan untuk menyimpan data dalam bentuk terkompresi, sehingga kami kehilangan semua data di halaman setelah catatan "rusak", jadi meskipun ada minus di tabel, kami tidak melakukannya memperhitungkannya.

Kekompakan:

• pada opsi pertama, kita hanya perlu menyimpan panjangnya di header, jika kita menggunakan bilangan bulat dengan panjang variabel, maka dalam banyak kasus kita dapat bertahan dengan satu byte;
• pada opsi kedua kita perlu menyimpan alamat awal dan panjangnya; catatan harus berukuran konstan, saya memperkirakan 4 byte per catatan (dua byte untuk offset, dan dua byte untuk panjangnya);
• opsi ketiga hanya membutuhkan satu karakter untuk menunjukkan dimulainya perekaman, ditambah rekaman itu sendiri akan meningkat 1-2% karena pelindung. Secara umum kira-kira setara dengan opsi pertama.

Awalnya, saya menganggap opsi kedua sebagai yang utama (dan bahkan menulis implementasinya). Saya mengabaikannya hanya ketika saya akhirnya memutuskan untuk menggunakan kompresi.

Mungkin suatu hari nanti saya masih akan menggunakan opsi serupa. Misalnya, jika saya harus berurusan dengan penyimpanan data untuk kapal yang melakukan perjalanan antara Bumi dan Mars, akan ada persyaratan yang sangat berbeda untuk keandalan, radiasi kosmik, ...

Adapun opsi ketiga: Saya memberinya dua bintang karena kesulitan implementasinya hanya karena saya tidak suka mengutak-atik pelindung, mengubah durasi proses, dll. Ya, mungkin saya bias, tetapi saya harus menulis kodenya - mengapa memaksakan diri melakukan sesuatu yang tidak Anda sukai.

Ringkasan: Kami memilih opsi penyimpanan dalam bentuk rantai “header dengan panjang - data dengan panjang variabel” karena efisiensi dan kemudahan implementasi.

Menggunakan Bit Fields untuk Memantau Keberhasilan Operasi Tulis

Saya tidak ingat sekarang dari mana saya mendapatkan ide tersebut, tetapi tampilannya seperti ini:
Untuk setiap entri, kami mengalokasikan beberapa bit untuk menyimpan flag.
Seperti yang kami katakan sebelumnya, setelah dihapus semua bit diisi dengan 1, dan kita dapat mengubah 1 menjadi 0, tetapi tidak sebaliknya. Jadi untuk “benderanya tidak disetel” kita menggunakan 1, untuk “benderanya disetel” kita menggunakan 0.

Berikut tampilan memasukkan rekaman dengan panjang variabel ke dalam flash:

1. Setel tanda “perekaman panjang telah dimulai”;
2. Catat panjangnya;
3. Setel tanda “perekaman data telah dimulai”;
4. Kami mencatat data;
5. Setel tanda “perekaman berakhir”.

Selain itu, kita akan memiliki tanda “terjadi kesalahan”, dengan total tanda 4 bit.

Dalam hal ini, kami memiliki dua status stabil "1111" - perekaman belum dimulai dan "1000" - perekaman berhasil; jika terjadi gangguan tak terduga pada proses perekaman, kami akan menerima status peralihan, yang kemudian dapat kami deteksi dan proses.

Pendekatan ini menarik, tetapi hanya melindungi terhadap pemadaman listrik mendadak dan kegagalan serupa, yang tentu saja penting, tetapi ini bukan satu-satunya (atau bahkan alasan utama) penyebab kemungkinan kegagalan.

Ringkasan: Mari kita lanjutkan mencari solusi yang baik.

Checksum

Checksum juga memungkinkan untuk memastikan (dengan probabilitas yang masuk akal) bahwa kita membaca dengan tepat apa yang seharusnya ditulis. Dan, tidak seperti bidang bit yang dibahas di atas, bidang bit tersebut selalu berfungsi.

Jika kita memperhatikan daftar potensi sumber masalah yang kita bahas di atas, maka checksum mampu mengenali kesalahan apapun asalnya. (kecuali, mungkin, untuk alien jahat - mereka juga dapat memalsukan checksum).

Jadi, jika tujuan kita adalah memverifikasi bahwa datanya utuh, checksum adalah ide yang bagus.

Pilihan algoritma untuk menghitung checksum tidak menimbulkan pertanyaan apapun - CRC. Di satu sisi, sifat matematika memungkinkan untuk menangkap jenis kesalahan tertentu 100%; di sisi lain, pada data acak, algoritma ini biasanya menunjukkan kemungkinan tabrakan tidak lebih besar dari batas teoritis. . Ini mungkin bukan algoritma tercepat, juga tidak selalu minimum dalam hal jumlah tabrakan, tetapi ia memiliki kualitas yang sangat penting: dalam pengujian yang saya temui, tidak ada pola yang jelas-jelas gagal. Stabilitas adalah kualitas utama dalam hal ini.

Contoh studi volumetrik: Bagian 1, Bagian 2 (tautan ke narod.ru, maaf).

Namun, tugas memilih checksum belum selesai; CRC adalah keseluruhan keluarga checksum. Anda perlu menentukan panjangnya, lalu memilih polinomial.

Memilih panjang checksum bukanlah pertanyaan yang sederhana seperti yang terlihat pada pandangan pertama.

Izinkan saya mengilustrasikannya:
Mari kita lihat kemungkinan kesalahan di setiap byte dan checksum yang ideal, mari kita hitung jumlah rata-rata kesalahan per juta catatan:

Data, byte
Ceksum, byte
Kesalahan yang tidak terdeteksi
Deteksi kesalahan palsu
Total positif palsu

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

Tampaknya semuanya sederhana - tergantung pada panjang data yang dilindungi, pilih panjang checksum dengan minimal positif yang salah - dan triknya ada di kantong.

Namun, masalah muncul dengan checksum pendek: meskipun mereka pandai mendeteksi kesalahan bit tunggal, mereka dapat dengan probabilitas yang cukup tinggi menerima data yang benar-benar acak sebagai data yang benar. Sudah ada artikel tentang Habré yang menjelaskan masalah dalam kehidupan nyata.

Oleh karena itu, untuk membuat pencocokan checksum acak hampir tidak mungkin dilakukan, Anda perlu menggunakan checksum yang panjangnya 32 bit atau lebih. (untuk panjang lebih dari 64 bit, fungsi hash kriptografi biasanya digunakan).

Terlepas dari kenyataan bahwa saya menulis sebelumnya bahwa kita perlu menghemat ruang dengan segala cara, kita masih akan menggunakan checksum 32-bit (16 bit tidak cukup, kemungkinan tabrakan lebih dari 0.01%; dan 24 bit, karena mereka katakanlah, tidak ada di sini atau di sana).

Keberatan mungkin muncul di sini: apakah kita menyimpan setiap byte saat memilih kompresi agar sekarang memberikan 4 byte sekaligus? Bukankah lebih baik tidak mengompres atau menambahkan checksum? Tentu saja tidak, tanpa kompresi Tidak berarti, bahwa kita tidak memerlukan pemeriksaan integritas.

Saat memilih polinomial, kami tidak akan menemukan kembali rodanya, tetapi mengambil CRC-32C yang sekarang populer.
Kode ini mendeteksi kesalahan 6 bit pada paket hingga 22 byte (mungkin kasus paling umum bagi kami), kesalahan 4 bit pada paket hingga 655 byte (juga merupakan kasus umum bagi kami), kesalahan 2 bit atau jumlah ganjil pada paket dengan panjang yang masuk akal.

Jika ada yang tertarik dengan detailnya

artikel Wikipedia tentang CRC.

Parameter kode crc-32c pada Situs Koopman — mungkin spesialis CRC terkemuka di dunia.

В artikelnya ada kode menarik lainnya, yang memberikan parameter yang sedikit lebih baik untuk panjang paket yang relevan bagi kami, tetapi saya tidak menganggap perbedaannya signifikan, dan saya cukup kompeten untuk memilih kode khusus daripada kode standar dan telah diteliti dengan baik.

Selain itu, karena data kita dikompresi, muncul pertanyaan: haruskah kita menghitung checksum data yang dikompresi atau tidak?

Argumen yang mendukung penghitungan checksum data yang tidak terkompresi:

• Kami pada akhirnya perlu memeriksa keamanan penyimpanan data - jadi kami memeriksanya secara langsung (pada saat yang sama, kemungkinan kesalahan dalam implementasi kompresi/dekompresi, kerusakan yang disebabkan oleh rusaknya memori, dll. akan diperiksa);
• Algoritma deflate di zlib memiliki implementasi yang cukup matang dan seharusnya tidak jatuh dengan data masukan yang "bengkok"; terlebih lagi, sering kali mampu mendeteksi kesalahan dalam aliran masukan secara independen, sehingga mengurangi kemungkinan keseluruhan untuk tidak mendeteksi kesalahan (melakukan pengujian dengan membalik satu bit dalam catatan pendek, zlib mendeteksi kesalahan pada sekitar sepertiga kasus).

Argumen yang menentang penghitungan checksum data yang tidak terkompresi:

• CRC "disesuaikan" secara khusus untuk beberapa kesalahan bit yang merupakan karakteristik memori flash (kesalahan bit dalam aliran terkompresi dapat menyebabkan perubahan besar dalam aliran keluaran, yang secara teori murni, kita dapat "menangkap" tabrakan);
• Saya tidak terlalu menyukai gagasan meneruskan data yang berpotensi rusak ke dekompresor, Siapa tahubagaimana dia akan bereaksi.

Dalam proyek ini, saya memutuskan untuk menyimpang dari praktik umum dalam menyimpan checksum data yang tidak terkompresi.

Ringkasan: Kami menggunakan CRC-32C, kami menghitung checksum dari data dalam bentuk yang ditulis ke flash (setelah kompresi).

Redundansi

Tentu saja, penggunaan pengkodean yang berlebihan tidak menghilangkan kehilangan data, namun hal ini dapat secara signifikan (sering kali lipat) mengurangi kemungkinan kehilangan data yang tidak dapat dipulihkan.

Kita dapat menggunakan berbagai jenis redundansi untuk memperbaiki kesalahan.
Kode Hamming dapat memperbaiki kesalahan bit tunggal, kode karakter Reed-Solomon, banyak salinan data yang dikombinasikan dengan checksum, atau pengkodean seperti RAID-6 dapat membantu memulihkan data bahkan jika terjadi kerusakan besar-besaran.
Awalnya, saya berkomitmen untuk meluasnya penggunaan pengkodean yang tahan terhadap kesalahan, tetapi kemudian saya menyadari bahwa pertama-tama kita perlu memiliki gagasan tentang kesalahan apa yang ingin kita lindungi, dan kemudian memilih pengkodean.

Kami telah mengatakan sebelumnya bahwa kesalahan harus ditangkap secepat mungkin. Pada titik manakah kita dapat menemukan kesalahan?

1. Rekaman yang belum selesai (entah kenapa pada saat perekaman listrik dimatikan, Raspberry membeku, ...)
   Sayangnya, jika terjadi kesalahan seperti itu, yang tersisa hanyalah mengabaikan catatan yang tidak valid dan menganggap data tersebut hilang;
2. Kesalahan penulisan (entah kenapa, apa yang ditulis ke memori flash tidak sesuai dengan yang tertulis)
   Kita dapat segera mendeteksi kesalahan tersebut jika kita melakukan tes pembacaan segera setelah perekaman;
3. Distorsi data dalam memori selama penyimpanan;
4. Kesalahan membaca
   Untuk memperbaikinya jika checksum tidak sesuai cukup dengan mengulang pembacaan beberapa kali.

Artinya, hanya kesalahan tipe ketiga (kerusakan data secara spontan selama penyimpanan) yang tidak dapat diperbaiki tanpa pengkodean yang tahan kesalahan. Tampaknya kesalahan seperti itu masih sangat kecil kemungkinannya.

Ringkasan: diputuskan untuk meninggalkan pengkodean yang berlebihan, tetapi jika operasi menunjukkan kesalahan dari keputusan ini, maka kembali ke pertimbangan masalah (dengan statistik kegagalan yang sudah terakumulasi, yang akan memungkinkan pemilihan jenis pengkodean yang optimal).

Lain

Tentu saja, format artikel tidak memungkinkan kami untuk membenarkan setiap bit dalam formatnya (dan kekuatanku sudah habis), jadi saya akan membahas secara singkat beberapa poin yang belum disinggung sebelumnya.

• Diputuskan untuk membuat semua halaman “sama”
  Artinya, tidak akan ada halaman khusus dengan metadata, thread terpisah, dll., melainkan satu thread yang menulis ulang semua halaman secara bergantian.
  Hal ini memastikan keausan halaman yang rata, tidak ada satu titik pun yang gagal, dan saya menyukainya;
• Sangat penting untuk menyediakan versi format.
  Format tanpa nomor versi di header itu jahat!
  Cukup menambahkan kolom dengan Angka Ajaib (tanda tangan) tertentu ke header halaman, yang akan menunjukkan versi format yang digunakan (Saya tidak berpikir bahwa dalam praktiknya akan ada selusin dari mereka);
• Gunakan header dengan panjang variabel untuk catatan (yang jumlahnya banyak), cobalah membuatnya sepanjang 1 byte dalam banyak kasus;
• Untuk mengkodekan panjang header dan panjang bagian rekaman terkompresi yang dipangkas, gunakan kode biner dengan panjang variabel.

Banyak membantu generator daring Kode Huffman. Hanya dalam beberapa menit kami dapat memilih kode panjang variabel yang diperlukan.

Deskripsi format penyimpanan data

Urutan byte

Bidang yang lebih besar dari satu byte disimpan dalam format big-endian (urutan byte jaringan), yaitu 0x1234 ditulis sebagai 0x12, 0x34.

Paginasi

Semua memori flash dibagi menjadi beberapa halaman dengan ukuran yang sama.

Ukuran halaman default adalah 32Kb, tetapi tidak lebih dari 1/4 dari total ukuran chip memori (untuk chip 4MB, diperoleh 128 halaman).

Setiap halaman menyimpan data secara terpisah (yaitu, data pada satu halaman tidak merujuk pada data pada halaman lain).

Semua halaman diberi nomor secara alami (dalam urutan alamat menaik), dimulai dengan angka 0 (halaman nol dimulai pada alamat 0, halaman pertama dimulai pada 32Kb, halaman kedua dimulai pada 64Kb, dll.)

Chip memori digunakan sebagai buffer siklik (ring buffer), yaitu penulisan pertama ke halaman nomor 0, lalu nomor 1, ..., ketika kita mengisi halaman terakhir, siklus baru dimulai dan perekaman dilanjutkan dari halaman nol .

Di dalam halaman

Di awal halaman disimpan header halaman 4 byte, kemudian header checksum (CRC-32C), kemudian record disimpan dalam format “header, data, checksum”.

Judul halaman (hijau kotor pada diagram) terdiri dari:

• bidang Nomor Ajaib dua byte (juga merupakan tanda versi format)
  untuk versi format saat ini dihitung sebagai 0xed00 ⊕ номер страницы;
• penghitung dua byte "Versi halaman" (nomor siklus penulisan ulang memori).

Entri pada halaman disimpan dalam bentuk terkompresi (algoritma deflate digunakan). Semua catatan pada satu halaman dikompresi dalam satu utas (kamus umum digunakan), dan pada setiap halaman baru, kompresi dimulai dari awal. Artinya, untuk mendekompresi catatan apa pun, semua catatan sebelumnya dari halaman ini (dan hanya yang ini) diperlukan.

Setiap record akan dikompresi dengan flag Z_SYNC_FLUSH, dan di akhir aliran terkompresi akan ada 4 byte 0x00, 0x00, 0xff, 0xff, mungkin didahului oleh satu atau dua byte nol lagi.
Kami membuang urutan ini (panjang 4, 5 atau 6 byte) saat menulis ke memori flash.

Header rekaman menyimpan 1, 2, atau 3 byte:

• satu bit (T) menunjukkan jenis catatan: 0 - konteks, 1 - log;
• bidang panjang variabel (S) dari 1 hingga 7 bit, yang menentukan panjang header dan "ekor" yang harus ditambahkan ke catatan untuk dekompresi;
• panjang rekaman (L).

Tabel nilai S:

S
Panjang header, byte
Dibuang saat menulis, byte

0
1
5 (00 00 00 ff ff)

10
1
6 (00 00 00 00 ff ff)

110
2
4 (00 00 ff ff)

1110
2
5 (00 00 00 ff ff)

11110
2
6 (00 00 00 00 ff ff)

1111100
3
4 (00 00 ff ff)

1111101
3
5 (00 00 00 ff ff)

1111110
3
6 (00 00 00 00 ff ff)

Saya coba ilustrasikan, entah seberapa jelasnya ternyata:

Kuning di sini menandakan field T, putih menandakan field S, hijau L (panjang data terkompresi dalam byte), biru berarti data terkompresi, merah merupakan byte terakhir dari data terkompresi yang tidak ditulis ke memori flash.

Dengan demikian, kita dapat menulis header rekaman dengan panjang paling umum (hingga 63+5 byte dalam bentuk terkompresi) dalam satu byte.

Setelah setiap catatan, checksum CRC-32C disimpan, di mana nilai terbalik dari checksum sebelumnya digunakan sebagai nilai awal (init).

CRC memiliki properti "durasi", rumus berikut berfungsi (plus atau minus inversi bit dalam proses): .
Faktanya, kami menghitung CRC dari semua byte header dan data sebelumnya di halaman ini.

Tepat setelah checksum adalah header dari record berikutnya.

Header dirancang sedemikian rupa sehingga byte pertamanya selalu berbeda dari 0x00 dan 0xff (jika alih-alih byte pertama header kita menemukan 0xff, ini berarti ini adalah area yang tidak digunakan; 0x00 menandakan kesalahan).

Contoh Algoritma

Membaca dari Memori Flash

Setiap pembacaan disertai dengan pemeriksaan checksum.
Jika checksum tidak sesuai maka pembacaan diulangi beberapa kali dengan harapan terbaca data yang benar.

(ini masuk akal, Linux tidak melakukan cache membaca dari NOR Flash, diuji)

Menulis ke memori flash

Kami mencatat datanya.
Mari kita membacanya.

Jika data yang dibaca tidak sesuai dengan data tertulis, kami mengisi area tersebut dengan nol dan memberi sinyal kesalahan.

Mempersiapkan sirkuit mikro baru untuk pengoperasian

Untuk inisialisasi, header dengan versi 1 ditulis ke halaman pertama (atau lebih tepatnya nol).
Setelah itu, konteks awal ditulis ke halaman ini (berisi UUID mesin dan pengaturan default).

Itu saja, memori flash siap digunakan.

Memuat mesin

Saat memuat, 8 byte pertama setiap halaman (header + CRC) dibaca, halaman dengan Nomor Ajaib yang tidak diketahui atau CRC yang salah akan diabaikan.
Dari halaman yang “benar”, halaman dengan versi maksimum dipilih, dan halaman dengan nomor tertinggi diambil darinya.
Catatan pertama dibaca, kebenaran CRC dan keberadaan tanda “konteks” diperiksa. Jika semuanya baik-baik saja, halaman ini dianggap terkini. Jika tidak, kami kembali ke halaman sebelumnya hingga kami menemukan halaman "aktif".
dan di halaman yang ditemukan kami membaca semua catatan, yang kami gunakan dengan tanda “konteks”.
Simpan kamus zlib (diperlukan untuk menambahkan ke halaman ini).

Itu saja, pengunduhan selesai, konteksnya dipulihkan, Anda dapat bekerja.

Menambahkan Entri Jurnal

Kami mengompres rekaman dengan kamus yang benar, menentukan Z_SYNC_FLUSH. Kami melihat apakah rekaman terkompresi cocok dengan halaman saat ini.
Jika tidak cocok (atau ada kesalahan CRC pada halaman), mulailah halaman baru (lihat di bawah).
Kami menuliskan catatan dan CRC. Jika terjadi kesalahan, mulailah halaman baru.

Halaman baru

Kami memilih halaman gratis dengan jumlah minimum (kami menganggap halaman gratis sebagai halaman dengan checksum yang salah di header atau dengan versi yang lebih kecil dari yang sekarang). Jika tidak ada halaman seperti itu, pilih halaman dengan nomor minimum dari halaman yang versinya sama dengan versi saat ini.
Kami menghapus halaman yang dipilih. Kami memeriksa isinya dengan 0xff. Jika ada yang salah, ambil halaman gratis berikutnya, dll.
Kami menulis header pada halaman yang terhapus, entri pertama adalah keadaan konteks saat ini, berikutnya adalah entri log tidak tertulis (jika ada).

Penerapan format

Menurut pendapat saya, ini ternyata merupakan format yang bagus untuk menyimpan aliran informasi yang kurang lebih dapat dikompresi (teks biasa, JSON, MessagePack, CBOR, mungkin protobuf) di NOR Flash.

Tentu saja, formatnya “disesuaikan” untuk SLC NOR Flash.

Sebaiknya tidak digunakan dengan media BER tinggi seperti NAND atau MLC NOR (apakah memori seperti itu tersedia untuk dijual? Saya hanya melihatnya disebutkan dalam karya kode koreksi).

Selain itu, tidak boleh digunakan dengan perangkat yang memiliki FTL sendiri: USB flash, SD, MicroSD, dll (untuk memori seperti itu saya membuat format dengan ukuran halaman 512 byte, tanda tangan di awal setiap halaman dan nomor catatan unik - terkadang dimungkinkan untuk memulihkan semua data dari flash drive yang "bermasalah" dengan membaca berurutan sederhana).

Tergantung pada tugasnya, format dapat digunakan tanpa perubahan pada flash drive dari 128Kbit (16Kb) hingga 1Gbit (128MB). Jika diinginkan, Anda dapat menggunakannya pada chip yang lebih besar, namun Anda mungkin perlu menyesuaikan ukuran halaman (Tetapi di sini pertanyaan tentang kelayakan ekonomi sudah muncul; harga NOR Flash dalam volume besar tidak menggembirakan).

Jika seseorang menganggap formatnya menarik dan ingin menggunakannya dalam proyek terbuka, tulislah, saya akan mencoba mencari waktu, memoles kodenya dan mempostingnya di github.

Kesimpulan

Seperti yang Anda lihat, pada akhirnya formatnya menjadi sederhana dan bahkan membosankan.

Sulit untuk mencerminkan evolusi sudut pandang saya dalam sebuah artikel, tapi percayalah: awalnya saya ingin menciptakan sesuatu yang canggih, tidak bisa dihancurkan, mampu bertahan bahkan dari ledakan nuklir dalam jarak dekat. Namun, nalar (saya harap) tetap menang dan secara bertahap prioritas bergeser ke arah kesederhanaan dan kekompakan.

Mungkinkah aku salah? Ya tentu. Misalnya, mungkin saja kita membeli sejumlah sirkuit mikro berkualitas rendah. Atau karena alasan lain, peralatan tersebut tidak memenuhi harapan keandalan.

Apakah saya punya rencana untuk ini? Saya rasa setelah membaca artikel tersebut Anda yakin bahwa ada rencana. Dan bahkan tidak sendirian.

Pada catatan yang sedikit lebih serius, format ini dikembangkan baik sebagai opsi kerja maupun sebagai “balon percobaan”.

Saat ini semua yang ada di meja berfungsi dengan baik, beberapa hari yang lalu solusinya akan diterapkan (sekitar) di ratusan perangkat, mari kita lihat apa yang terjadi dalam operasi "pertempuran" (untungnya, saya harap format ini memungkinkan Anda mendeteksi kegagalan dengan andal; sehingga Anda dapat mengumpulkan statistik lengkap). Dalam beberapa bulan akan mungkin untuk menarik kesimpulan (dan jika Anda kurang beruntung, bahkan lebih awal).

Jika berdasarkan hasil penggunaan ditemukan masalah serius dan diperlukan perbaikan, maka saya pasti akan menulisnya.

Literatur

Saya tidak ingin membuat daftar panjang karya bekas yang membosankan; lagipula, semua orang punya Google.

Di sini saya memutuskan untuk meninggalkan daftar temuan yang menurut saya sangat menarik, tetapi lambat laun temuan tersebut berpindah langsung ke teks artikel, dan satu item tetap ada di daftar:

1. а infgen dari penulis zlib. Dapat dengan jelas menampilkan isi arsip deflate/zlib/gzip. Jika Anda harus berurusan dengan struktur internal format deflate (atau gzip), saya sangat merekomendasikannya.

Sumber: www.habr.com