tarih öncesi

Kendi tasarımımız olan otomatlar bulunmaktadır. Raspberry Pi'nin içinde ve ayrı bir kartta bazı kablolar. Bir madeni para kabul eden, bir fatura kabul eden, bir banka terminali birbirine bağlıdır... Her şey kendi yazdığı bir program tarafından kontrol edilir. Çalışma geçmişinin tamamı bir flash sürücüdeki (MicroSD) bir günlüğe yazılır ve bu daha sonra İnternet üzerinden (bir USB modem kullanılarak) bir veritabanında saklandığı sunucuya iletilir. Satış bilgileri 1c'ye yüklenir, ayrıca izleme için basit bir web arayüzü vb. vardır.

Yani dergi hayati öneme sahiptir - muhasebe (gelir, satış vb.), izleme (her türlü arıza ve diğer mücbir sebep durumları); Bu makine hakkında sahip olduğumuz tüm bilgilerin bu olduğu söylenebilir.

Sorun

Flash sürücüler kendilerini çok güvenilmez cihazlar olarak gösterir. Kıskanılacak bir düzenlilikle başarısız oluyorlar. Bu hem makinenin aksamasına hem de (eğer herhangi bir nedenle kayıt çevrimiçi olarak aktarılamazsa) veri kaybına neden olur.

Bu, flash sürücüleri kullanmanın ilk deneyimi değil, bundan önce, derginin USB flash sürücülerde saklandığı yüzden fazla cihaza sahip başka bir proje vardı, zaman zaman başarısız olanların sayısında da güvenilirlik sorunları vardı. bir ay düzinelerceydi. SLC belleğe sahip markalı olanlar da dahil olmak üzere farklı flash sürücüleri denedik ve bazı modeller diğerlerinden daha güvenilir, ancak flash sürücüleri değiştirmek sorunu kökten çözmedi.

Uyarı! Uzun okuma! Eğer “neden” ile değil, sadece “nasıl” ile ilgileniyorsanız, doğrudan ilerleyebilirsiniz. iş parçacığında makale.

karar

Akla gelen ilk şey şudur: MicroSD'den vazgeçin, örneğin bir SSD takın ve ondan önyükleme yapın. Muhtemelen teorik olarak mümkün, ancak nispeten pahalı ve o kadar da güvenilir değil (bir USB-SATA adaptörü eklendi; bütçe SSD'leri için arıza istatistikleri de cesaret verici değil).

USB HDD de pek çekici bir çözüm gibi görünmüyor.

Bu nedenle, bu seçeneğe geldik: MicroSD'den önyüklemeyi bırakın, ancak bunları salt okunur modda kullanın ve işlem günlüğünü (ve belirli bir donanım parçasına özgü diğer bilgileri - seri numarası, sensör kalibrasyonları vb.) başka bir yerde saklayın. .

Ahududular için salt okunur FS konusu zaten baştan sona incelenmiştir, bu makalede uygulama ayrıntıları üzerinde durmayacağım (ama ilgi olursa belki bu konuyla ilgili bir mini makale yazarım). Belirtmek istediğim tek nokta, hem kişisel deneyimlerden hem de bunu zaten uygulamış olanların incelemelerinden güvenilirlikte bir kazanç olduğudur. Evet, arızalardan tamamen kurtulmak imkansızdır, ancak bunların sıklığını önemli ölçüde azaltmak oldukça mümkündür. Ve kartlar birleşiyor, bu da servis personeli için değiştirmeyi çok daha kolay hale getiriyor.

donanım parçası

Bellek türünün seçimi konusunda özel bir şüphe yoktu - NOR Flash.
argümanlar:

• basit bağlantı (çoğunlukla zaten kullanma deneyimine sahip olduğunuz SPI veri yolu, dolayısıyla herhangi bir donanım sorunu öngörülmez);
• saçma fiyat;
• standart işletim protokolü (uygulama zaten Linux çekirdeğindedir, dilerseniz, aynı zamanda mevcut olan üçüncü taraf bir protokol de alabilir, hatta kendinizinkini yazabilirsiniz, neyse ki her şey basit);
• güvenilirlik ve kaynak:
  Tipik bir veri sayfasından: veriler 20 yıl boyunca, her blok için 100000 silme döngüsünde saklanır;
  üçüncü taraf kaynaklardan: son derece düşük BER, hata düzeltme kodlarına gerek olmadığını varsayar (bazı çalışmalar NOR için ECC'yi dikkate alır, ancak genellikle yine de MLC NOR anlamına gelir; bu da olur).

Hacim ve kaynak gereksinimlerini tahmin edelim.

Verilerin birkaç gün boyunca kaydedileceğinin garanti edilmesini istiyorum. Bu, herhangi bir iletişim sorunu olması durumunda satış geçmişinin kaybolmaması için gereklidir. Bu dönemde 5 güne odaklanacağız (hafta sonları ve tatil günleri de dikkate alınarak) sorun çözülebilir.

Şu anda günde yaklaşık 100kb günlük topluyoruz (3-4 bin giriş), ancak bu rakam giderek artıyor - ayrıntılar artıyor, yeni etkinlikler ekleniyor. Ayrıca bazen patlamalar olabiliyor (örneğin bazı sensörler yanlış pozitiflerle spam göndermeye başlıyor). 10 bin kayıt için her biri 100 bayt (günde megabayt) hesaplayacağız.

Toplamda 5 MB temiz (iyi sıkıştırılmış) veri çıkıyor. Onlara daha fazlası (kabaca tahmin) 1MB servis verisi.

Yani sıkıştırma kullanmıyorsak 8 MB, kullanıyorsak 4 MB'lık bir çipe ihtiyacımız var. Bu tip bir hafıza için oldukça gerçekçi rakamlar.

Kaynağa gelince: Belleğin tamamının her 5 günde bir defadan fazla yeniden yazılmamasını planlıyorsak, 10 yıllık hizmet boyunca binden az yeniden yazma döngüsü elde ederiz.
Üreticinin yüz bin vaat ettiğini hatırlatayım.

NOR ve NAND hakkında biraz

Bugün, elbette, NAND belleği çok daha popüler, ancak ben onu bu proje için kullanmayacağım: NAND, NOR'dan farklı olarak mutlaka hata düzeltme kodlarının, bozuk bloklardan oluşan bir tablonun vb. ve ayrıca bacakların kullanılmasını gerektirir. NAND çipleri genellikle çok daha fazladır.

NOR'un dezavantajları şunları içerir:

• küçük hacimli (ve buna göre megabayt başına yüksek fiyat);
• düşük iletişim hızı (büyük ölçüde seri bir arayüzün kullanılması nedeniyle, genellikle SPI veya I2C);
• yavaş silme (blok boyutuna bağlı olarak, bir saniyeden birkaç saniyeye kadar sürer).

Görünüşe göre bizim için kritik bir şey yok, o yüzden devam ediyoruz.

Detaylar ilginçse, mikro devre seçilmiştir at25df321a (ancak bu önemli değil, piyasada pin çıkışı ve komut sistemi açısından uyumlu birçok analog var; farklı bir üreticiden ve/veya farklı boyutta bir mikro devre kurmak istesek bile, her şey değişmeden çalışacaktır. kod).

Linux çekirdeğinde yerleşik sürücüyü kullanıyorum; Raspberry'de, aygıt ağacı yer paylaşımı desteği sayesinde her şey çok basit - derlenmiş katmanı /boot/overlays içine yerleştirmeniz ve /boot/config.txt dosyasını biraz değiştirmeniz gerekiyor.

Örnek dts dosyası

Dürüst olmak gerekirse hatasız yazıldığından emin değilim ama işe yarıyor.

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

Ve config.txt dosyasında başka bir satır

dtoverlay=at25:spimaxfrequency=50000000

Çipin Raspberry Pi'ye bağlanmasına ilişkin açıklamayı atlayacağım. Bir yandan elektronik konusunda uzman değilim, diğer yandan buradaki her şey benim için bile banal: mikro devrenin sadece 8 bacağı var, bunlardan toprağa, güce, SPI'ye (CS, SI, SO, SCK) ihtiyacımız var ); seviyeler Raspberry Pi'ninkilerle aynıdır, ek kablolamaya gerek yoktur - yalnızca belirtilen 6 pimi bağlayın.

Sorunun formüle edilmesi

Her zamanki gibi, sorun bildirimi birkaç yinelemeden geçiyor ve bana öyle geliyor ki bir sonrakinin zamanı geldi. O halde duralım, yazılanları bir araya getirelim ve gölgede kalan detayları netleştirelim.

Bu nedenle günlüğün SPI NOR Flash'ta saklanmasına karar verdik.

Bilmeyenler için NOR Flash nedir?

Bu, üç işlemi gerçekleştirebileceğiniz kalıcı bellektir:

1. Okuma:
   En yaygın okuma: adresi iletiyoruz ve ihtiyacımız olduğu kadar bayt okuyoruz;
2. kayıt:
   NOR flash'a yazmak normal bir işlem gibi görünür ancak bir özelliği vardır: yalnızca 1'i 0'a değiştirebilirsiniz, ancak tersini yapamazsınız. Örneğin, bir bellek hücresinde 0x55 varsa, ona 0x0f yazdıktan sonra 0x05 zaten orada depolanacaktır. (hemen aşağıdaki tabloya bakınız);
3. sil:
   Elbette ters işlemi yapabilmemiz gerekiyor - 0'ı 1'e değiştirelim, silme işlemi tam olarak bunun içindir. İlk ikisinden farklı olarak baytlarla değil bloklarla çalışır (seçilen çipteki minimum silme bloğu 4kb'dir). Silme tüm bloğu yok eder ve 0'ı 1'e değiştirmenin tek yoludur. Bu nedenle, flash bellekle çalışırken genellikle veri yapılarını silme bloğu sınırına hizalamanız gerekir.
   NOR Flash'ta kayıt:

Ikili veri

Bu oldu
01010101

Kaydedildi
00001111

Oldu
00000101

Günlüğün kendisi değişken uzunluktaki kayıtların bir dizisini temsil eder. Bir kaydın tipik uzunluğu yaklaşık 30 bayttır (bazen birkaç kilobayt uzunluğunda kayıtlar olmasına rağmen). Bu durumda, onlarla yalnızca bir bayt kümesi olarak çalışırız, ancak eğer ilgileniyorsanız, kayıtların içinde CBOR kullanılır.

Günlüğe ek olarak, hem güncellenmiş hem de güncellenmemiş bazı "ayar" bilgilerini saklamamız gerekir: belirli bir cihaz kimliği, sensör kalibrasyonları, "cihaz geçici olarak devre dışı bırakıldı" bayrağı vb.
Bu bilgi, yine CBOR'da saklanan bir dizi anahtar-değer kaydıdır.Bu bilgilerin çoğuna sahip değiliz (en fazla birkaç kilobayt) ve nadiren güncelleniyor.
Bundan sonra buna bağlam adını vereceğiz.

Bu yazının nerede başladığını hatırlarsak, güvenilir veri depolamanın sağlanması ve mümkünse donanım arızaları/veri bozulması durumunda bile sürekli çalışmanın sağlanması çok önemlidir.

Sorunların hangi kaynakları dikkate alınabilir?

• Yazma/silme işlemleri sırasında gücü kapatın. Bu, “levyeye karşı hile yoktur” kategorisindendir.
  Den bilgi tartışma yığın değişiminde: flaşla çalışırken güç kapatıldığında, hem silme (1'e ayarlı) hem de yazma (0'a ayarlı) tanımsız davranışa yol açar: veriler yazılabilir, kısmen yazılabilir (örneğin, 10 bayt/80 bit aktardık) , ancak henüz yalnızca 45 bit yazılamıyor), bazı bitlerin "ara" durumda olması da mümkündür (okuma hem 0 hem de 1 üretebilir);
• Flash belleğin kendisindeki hatalar.
  BER çok düşük olmasına rağmen sıfıra eşit olamaz;
• Veri yolu hataları
  SPI aracılığıyla iletilen veriler hiçbir şekilde korunmaz; hem tek bit hataları hem de senkronizasyon hataları meydana gelebilir - bitlerin kaybı veya eklenmesi (bu da büyük veri bozulmasına yol açar);
• Diğer hatalar/aksaklıklar
  Koddaki hatalar, Raspberry hataları, uzaylı müdahalesi...

Güvenilirliği sağlamak için yerine getirilmesinin gerekli olduğunu düşündüğüm gereksinimleri formüle ettim:

• kayıtlar hemen flash belleğe gitmeli, gecikmeli yazmalar dikkate alınmamalıdır; - bir hata meydana gelirse, mümkün olan en kısa sürede tespit edilip işlenmelidir; - mümkünse sistem hatalardan kurtarılmalıdır.
  (Herkesin karşılaştığını düşündüğüm "nasıl olmaması gerektiği" hayattan bir örnek: acil bir yeniden başlatmanın ardından dosya sistemi "bozuk" ve işletim sistemi önyükleme yapmıyor)

Fikirler, yaklaşımlar, düşünceler

Bu sorun hakkında düşünmeye başladığımda aklımda birçok fikir canlandı, örneğin:

• veri sıkıştırmayı kullanın;
• akıllı veri yapılarını kullanın, örneğin kayıt başlıklarını kayıtlardan ayrı olarak saklayın, böylece herhangi bir kayıtta hata varsa geri kalanını sorunsuzca okuyabilirsiniz;
• güç kapatıldığında kaydın tamamlanmasını kontrol etmek için bit alanlarını kullanın;
• her şey için sağlama toplamlarını saklayın;
• bir tür gürültüye dayanıklı kodlama kullanın.

Bu fikirlerin bir kısmı kullanıldı, bir kısmının ise terk edilmesine karar verildi. Sırayla gidelim.

Veri sıkıştırma

Günlüğe kaydettiğimiz olaylar oldukça benzer ve tekrarlanabilir (“5 ruble para attı”, “para üstü vermek için düğmeye bastı”, ...). Bu nedenle sıkıştırmanın oldukça etkili olması gerekir.

Sıkıştırma ek yükü önemsizdir (işlemcimiz oldukça güçlüdür, ilk Pi'nin bile 700 MHz frekanslı bir çekirdeği vardı, mevcut modellerde bir gigahertz'in üzerinde frekansa sahip birkaç çekirdeğe sahiptir), depolama ile değişim oranı düşüktür (birkaç megabayt/saniye), kayıtların boyutu küçüktür. Genel olarak, sıkıştırmanın performans üzerinde bir etkisi varsa, bu yalnızca olumlu olacaktır. (kesinlikle eleştirmiyorum, sadece belirtiyorum). Ayrıca, gerçek yerleşik Linux'umuz yok, normal Linux'umuz var - bu nedenle uygulama fazla çaba gerektirmemelidir (sadece kütüphaneyi bağlamak ve ondan birkaç işlevi kullanmak yeterlidir).

Çalışan bir cihazdan (1.7 MB, 70 bin giriş) günlüğün bir parçası alındı ​​ve önce bilgisayarda bulunan gzip, lz4, lzop, bzip2, xz, zstd kullanılarak sıkıştırılabilirlik açısından kontrol edildi.

• gzip, xz, zstd benzer sonuçlar gösterdi (40Kb).
  Modaya uygun xz'nin burada gzip veya zstd düzeyinde kendini göstermesine şaşırdım;
• Varsayılan ayarlarla lzip biraz daha kötü sonuçlar verdi;
• lz4 ve lzop pek iyi sonuçlar vermedi (150Kb);
• bzip2 şaşırtıcı derecede iyi bir sonuç gösterdi (18Kb).

Böylece veriler çok iyi sıkıştırılır.
Yani (ölümcül kusurlar bulamazsak) sıkıştırma olacaktır! Çünkü aynı flash sürücüye daha fazla veri sığabilir.

Dezavantajlarını düşünelim.

İlk sorun: Her kaydın derhal flaşa aktarılması konusunda zaten anlaşmıştık. Genellikle arşivleyici, hafta sonu yazma zamanının geldiğine karar verene kadar giriş akışından veri toplar. Derhal sıkıştırılmış bir veri bloğu almamız ve onu kalıcı bellekte saklamamız gerekiyor.

Üç yol görüyorum:

1. Yukarıda tartışılan algoritmalar yerine sözlük sıkıştırmasını kullanarak her kaydı sıkıştırın.
   Tamamen uygulanabilir bir seçenek ama hoşuma gitmedi. Az ya da çok iyi bir sıkıştırma seviyesi sağlamak için sözlüğün belirli verilere göre "uyarlanması" gerekir; herhangi bir değişiklik sıkıştırma seviyesinin felaketle düşmesine yol açacaktır. Evet, sözlüğün yeni bir sürümünü oluşturarak sorun çözülebilir, ancak bu baş ağrısıdır - sözlüğün tüm sürümlerini saklamamız gerekecek; her girişte sözlüğün hangi sürümüyle sıkıştırıldığını belirtmemiz gerekecek...
2. Her kaydı "klasik" algoritmalar kullanarak, ancak diğerlerinden bağımsız olarak sıkıştırın.
   Söz konusu sıkıştırma algoritmaları, bu boyuttaki (onlarca bayt) kayıtlarla çalışacak şekilde tasarlanmamıştır; sıkıştırma oranı açıkça 1'den az olacaktır (yani, sıkıştırmak yerine veri hacmini arttırmak);
3. Her kayıttan sonra FLUSH yapın.
   Çoğu sıkıştırma kütüphanesinin FLUSH desteği vardır. Bu, arşivleyicinin geri yüklemek için kullanılabilecek şekilde sıkıştırılmış bir akış oluşturduğu bir komuttur (veya sıkıştırma prosedürünün bir parametresidir). tüm Daha önce alınmış olan sıkıştırılmamış veriler. Böyle bir analog sync dosya sistemlerinde veya commit sql'de.
   Önemli olan sonraki sıkıştırma işlemlerinin biriken sözlüğü kullanabilmesi ve sıkıştırma oranının önceki sürümdeki kadar zarar görmemesidir.

Sanırım üçüncü seçeneği seçtiğim açık, gelin daha detaylı bakalım.

Kurmak harika makale zlib'de FLUSH hakkında.

Yazıya dayanarak diz testi yaptım, gerçek bir cihazdan 70Kb sayfa boyutunda 60 bin log girişi aldım (sayfa boyutuna daha sonra döneceğiz) kabul edilmiş:

Ham veriler
Sıkıştırma gzip -9 (FLUSH yok)
Z_PARTIAL_FLUSH ile zlib
Z_SYNC_FLUSH ile zlib

Hacim, KB
1692
40
352
604

İlk bakışta, FLUSH'ın getirdiği fiyat aşırı derecede yüksek, ancak gerçekte çok az seçeneğimiz var - ya hiç sıkıştırmamak ya da FLUSH ile sıkıştırmak (ve çok etkili bir şekilde). Unutmamalıyız ki 70 bin kaydımız var, Z_PARTIAL_FLUSH'un getirdiği artıklık kayıt başına sadece 4-5 bayttır. Ve sıkıştırma oranının neredeyse 5:1 olduğu ortaya çıktı; bu mükemmel bir sonuçtan daha fazlasıdır.

Sürpriz gelebilir ama Z_SYNC_FLUSH aslında FLUSH yapmanın daha etkili bir yoludur

Z_SYNC_FLUSH kullanıldığında her girişin son 4 baytı her zaman 0x00, 0x00, 0xff, 0xff olacaktır. Ve eğer bunları biliyorsak, onları saklamamıza gerek kalmaz, dolayısıyla son boyut yalnızca 324Kb olur.

Bağlantısını verdiğim makalede bir açıklama var:

Boş içeriğe sahip yeni bir tip 0 blok eklenir.

Boş içeriğe sahip bir tip 0 blok aşağıdakilerden oluşur:

• üç bitlik blok başlığı;
• Bayt hizalamasını sağlamak için 0 ila 7 bit sıfıra eşittir;
• dört baytlık dizi 00 00 FF FF.

Kolayca görebileceğiniz gibi, bu 4 bayttan önceki son blokta 3 ile 10 arasında sıfır bit bulunmaktadır. Ancak uygulama aslında en az 10 sıfır bitin olduğunu göstermiştir.

Bu tür kısa veri bloklarının genellikle (her zaman?) tip 1 blok (sabit blok) kullanılarak kodlandığı, bunun zorunlu olarak 7 sıfır bitle bittiği ve toplamda 10-17 garantili sıfır bit verdiği (ve geri kalanı yaklaşık %50 olasılıkla sıfır olacaktır.

Yani, test verilerinde vakaların %100'ünde 0x00, 0x00, 0xff, 0xff'den önce bir sıfır bayt vardır ve vakaların üçte birinden fazlasında iki sıfır bayt vardır (belki de gerçek şu ki, ikili CBOR kullanıyorum ve metin JSON kullanırken, tip 2 - dinamik blok blokları daha yaygın olacaktır; sırasıyla, 0x00, 0x00, 0xff, 0xff ile karşılaşılmadan önce ek sıfır bayt içermeyen bloklar).

Toplamda, mevcut test verilerini kullanarak 250 Kb'den daha az sıkıştırılmış veriye sığdırmak mümkündür.

Bitlerle hokkabazlık yaparak biraz daha tasarruf edebilirsiniz: şimdilik bloğun sonunda birkaç sıfır bitin varlığını göz ardı ediyoruz, bloğun başındaki birkaç bit de değişmiyor...
Ama sonra güçlü bir iradeyle durmaya karar verdim, aksi takdirde bu gidişle kendi arşivleyicimi geliştirmek zorunda kalabilirdim.

Toplamda, yazma başına 3-4 bayt aldığım test verilerimden sıkıştırma oranının 6:1'den fazla olduğu ortaya çıktı. Dürüst olacağım: Böyle bir sonuç beklemiyordum; bence 2:1'den daha iyi olan her şey zaten sıkıştırma kullanımını haklı çıkaran bir sonuçtur.

Her şey yolunda, ancak zlib (deflate) hala arkaik, hak edilmiş ve biraz eski moda bir sıkıştırma algoritmasıdır. Sıkıştırılmamış veri akışının son 32Kb'sinin sözlük olarak kullanılması gerçeği bugün tuhaf görünüyor (yani, bazı veri blokları 40Kb önceki giriş akışındakine çok benziyorsa, o zaman yeniden arşivlenmeye başlanacaktır, ve daha önceki bir olaya atıfta bulunmayacaktır). Modaya uygun modern arşivleyicilerde sözlük boyutu genellikle kilobayt yerine megabayt cinsinden ölçülür.

Böylece arşivleyicilerle ilgili mini çalışmamıza devam ediyoruz.

Daha sonra bzip2'yi test ettik (unutmayın, FLUSH olmadan neredeyse 100:1 gibi harika bir sıkıştırma oranı gösterdi). Maalesef FLUSH ile çok kötü performans gösterdi; sıkıştırılmış verinin boyutunun sıkıştırılmamış veriden daha büyük olduğu ortaya çıktı.

Başarısızlığın nedenleri hakkındaki varsayımlarım

Libbz2, sözlüğü temizleyen tek bir temizleme seçeneği sunuyor (zlib'deki Z_FULL_FLUSH'a benzer); bundan sonra herhangi bir etkili sıkıştırmadan söz edilmiyor.

Ve test edilecek son şey zstd idi. Parametrelere bağlı olarak ya gzip düzeyinde, ancak çok daha hızlı ya da gzip'ten daha iyi sıkıştırır.

Ne yazık ki FLUSH ile pek iyi performans göstermedi: sıkıştırılmış verinin boyutu yaklaşık 700 Kb idi.

Я bir soru sordu projenin github sayfasında, her sıkıştırılmış veri bloğu için 10 bayta kadar hizmet verisine güvenmeniz gerektiği yönünde bir yanıt aldım, bu da elde edilen sonuçlara yakın; deflate'i yakalamanın bir yolu yok.

Arşivleyicilerle yaptığım denemeleri bu noktada durdurmaya karar verdim (xz, lzip, lzo, lz4'ün FLUSH olmadan test aşamasında bile kendilerini göstermediğini ve daha egzotik sıkıştırma algoritmalarını dikkate almadığımı hatırlatayım).

Arşivleme sorunlarına dönelim.

İkinci (değer olarak değil, sırayla söyledikleri gibi) sorun, sıkıştırılmış verilerin, önceki bölümlere sürekli referansların bulunduğu tek bir akış olmasıdır. Dolayısıyla, sıkıştırılmış verinin bir bölümü hasar görürse, yalnızca ilgili sıkıştırılmamış veri bloğunu değil, aynı zamanda sonraki tüm blokları da kaybederiz.

Bu sorunu çözmek için bir yaklaşım var:

1. Sorunun ortaya çıkmasını önleyin - sıkıştırılmış verilere, hataları tanımlamanıza ve düzeltmenize olanak sağlayacak artıklık ekleyin; bunu daha sonra konuşacağız;
2. Bir sorun oluştuğunda sonuçları en aza indirin
   Her veri bloğunu bağımsız olarak sıkıştırabileceğinizi ve sorunun kendiliğinden ortadan kalkacağını daha önce söylemiştik (bir bloğun verilerine zarar verilmesi, yalnızca bu blok için veri kaybına yol açacaktır). Ancak bu, veri sıkıştırmanın etkisiz olacağı aşırı bir durumdur. Tam tersi: 4 MB'lık çipimizin tamamını tek bir arşiv olarak kullanmak, bu bize mükemmel sıkıştırma sağlayacaktır, ancak veri bozulması durumunda felaketle sonuçlanacaktır.
   Evet, güvenilirlik açısından bir uzlaşmaya ihtiyaç var. Ancak, son derece düşük BER'e ve 20 yıllık beyan edilen veri depolama süresine sahip, kalıcı bellek için bir veri depolama formatı geliştirdiğimizi unutmamalıyız.

Deneyler sırasında, boyutu 10 KB'tan küçük sıkıştırılmış veri bloklarında sıkıştırma düzeyinde az çok gözle görülür kayıpların başladığını keşfettim.
Kullanılan belleğin sayfalanmış olduğundan daha önce bahsedilmişti; “bir sayfa - bir sıkıştırılmış veri bloğu” yazışmasının kullanılmaması için hiçbir neden göremiyorum.

Yani, minimum makul sayfa boyutu 16Kb'dir (hizmet bilgileri için bir rezerv ile). Ancak bu kadar küçük bir sayfa boyutu, maksimum kayıt boyutuna önemli kısıtlamalar getirir.

Henüz sıkıştırılmış biçimde birkaç kilobayttan büyük kayıtlar beklemesem de 32Kb sayfa kullanmaya karar verdim (çip başına toplam 128 sayfa).

Özet:

• Zlib (deflate) kullanılarak sıkıştırılmış verileri saklıyoruz;
• Her giriş için Z_SYNC_FLUSH'u ayarladık;
• Her sıkıştırılmış kayıt için sondaki baytları kırpıyoruz (örneğin 0x00, 0x00, 0xff, 0xff); başlıkta kaç bayt kestiğimizi belirtiyoruz;
• Verileri 32Kb sayfalarda saklıyoruz; sayfanın içinde tek bir sıkıştırılmış veri akışı vardır; Her sayfada sıkıştırmaya yeniden başlıyoruz.

Sıkıştırmayı bitirmeden önce, kayıt başına yalnızca birkaç bayt sıkıştırılmış veriye sahip olduğumuz gerçeğine dikkatinizi çekmek isterim, bu nedenle hizmet bilgilerini abartmamak son derece önemlidir, burada her bayt önemlidir.

Veri Başlıklarının Saklanması

Elimizde değişken uzunlukta kayıtlar olduğu için kayıtların yerleşimini/sınırlarını bir şekilde belirlememiz gerekiyor.

Üç yaklaşımı biliyorum:

1. Tüm kayıtlar sürekli bir akışta saklanır; önce uzunluğu içeren bir kayıt başlığı, ardından kaydın kendisi bulunur.
   Bu düzenlemede hem başlıklar hem de veriler değişken uzunlukta olabilir.
   Temel olarak, her zaman kullanılan tek bağlantılı bir liste elde ederiz;
2. Başlıklar ve kayıtların kendisi ayrı akışlarda saklanır.
   Sabit uzunlukta başlıklar kullanarak, bir başlıktaki hasarın diğerlerini etkilememesini sağlıyoruz.
   Örneğin birçok dosya sisteminde benzer bir yaklaşım kullanılır;
3. Kayıtlar sürekli bir akışta saklanır, kayıt sınırı belirli bir işaretleyici (veri blokları içinde yasaklanmış bir karakter/karakter dizisi) tarafından belirlenir. Kaydın içinde bir işaret varsa, onu bir diziyle değiştiririz (kaçarız).
   Benzer bir yaklaşım örneğin PPP protokolünde kullanılır.

Göstereceğim.

Seçenek 1:

Burada her şey çok basit: Kaydın uzunluğunu bilerek bir sonraki başlığın adresini hesaplayabiliriz. Böylece 0xff (boş alan) ile dolu bir alan veya sayfa sonu ile karşılaşıncaya kadar başlıklar arasında ilerliyoruz.

Seçenek 2:

Değişken kayıt uzunluğundan dolayı, sayfa başına kaç kayda (ve dolayısıyla başlığa) ihtiyacımız olacağını önceden söyleyemeyiz. Başlıkları ve verileri farklı sayfalara dağıtabilirsiniz, ancak ben farklı bir yaklaşımı tercih ediyorum: hem başlıkları hem de verileri tek bir sayfaya yerleştiriyoruz, ancak başlıklar (sabit boyutta) sayfanın başından geliyor ve veriler (değişken uzunlukta) sondan gelir. "Buluştukları" anda (yeni bir giriş için yeterli boş alan yok), bu sayfayı tamamlanmış sayıyoruz.

Seçenek 3:

Başlıkta verinin uzunluğunu veya konumu hakkında başka bir bilgiyi saklamaya gerek yoktur, kayıtların sınırlarını gösteren işaretleyiciler yeterlidir. Ancak veri yazarken/okurken işlenmesi gerekmektedir.
İşaretçi olarak 0xff'yi kullanırdım (silme sonrasında sayfayı doldurur), dolayısıyla boş alan kesinlikle veri olarak değerlendirilmez.

Karşılaştırma Tablosu:

opsiyon 1
opsiyon 2
opsiyon 3

Hata toleransı
-
+
+

yoğunluk
+
-
+

Uygulamanın karmaşıklığı
*
**
**

Seçenek 1'in ölümcül bir kusuru vardır: Başlıklardan herhangi biri hasar görürse, sonraki zincirin tamamı yok edilir. Kalan seçenekler, büyük hasar durumunda bile bazı verileri kurtarmanıza olanak tanır.
Ancak burada, verileri sıkıştırılmış bir biçimde saklamaya karar verdiğimizi ve bu nedenle "bozuk" bir kayıttan sonra sayfadaki tüm verileri kaybettiğimizi, dolayısıyla tabloda bir eksi olsa bile, bunu hatırlamamakta fayda var. Hesaba katmak.

kompaktlık:

• ilk seçenekte, başlıkta yalnızca uzunluğu saklamamız gerekir; değişken uzunluktaki tamsayılar kullanırsak, çoğu durumda bir baytla idare edebiliriz;
• ikinci seçenekte başlangıç ​​adresini ve uzunluğunu saklamamız gerekiyor; kayıt sabit bir boyutta olmalı, kayıt başına 4 bayt olduğunu tahmin ediyorum (ofset için iki bayt ve uzunluk için iki bayt);
• üçüncü seçenekte kaydın başlangıcını belirtmek için yalnızca bir karakter yeterlidir, ayrıca koruma nedeniyle kaydın kendisi de %1-2 oranında artacaktır. Genel olarak, ilk seçeneğe yaklaşık olarak eşittir.

Başlangıçta ikinci seçeneği ana seçenek olarak değerlendirdim (ve hatta uygulamayı yazdım). Ancak sonunda sıkıştırmayı kullanmaya karar verdiğimde bundan vazgeçtim.

Belki bir gün hala benzer bir seçeneği kullanacağım. Örneğin, Dünya ile Mars arasında seyahat eden bir geminin veri depolamasıyla uğraşmam gerekiyorsa, güvenilirlik, kozmik radyasyon vb. açısından tamamen farklı gereksinimler ortaya çıkacaktır.

Üçüncü seçeneğe gelince: Uygulamanın zorluğu nedeniyle iki yıldız verdim çünkü ekranlamayla uğraşmayı, süreçteki uzunluğu değiştirmeyi vb. sevmiyorum. Evet, belki önyargılıyım ama kodu yazmam gerekecek - neden kendinizi hoşlanmadığınız bir şeyi yapmaya zorluyorsunuz?

Özet: Verimlilik ve uygulama kolaylığı nedeniyle "uzunluklu başlık - değişken uzunluktaki veriler" zincirleri şeklindeki depolama seçeneğini seçiyoruz.

Yazma İşlemlerinin Başarısını İzlemek İçin Bit Alanlarını Kullanma

Bu fikri nereden bulduğumu şimdi hatırlamıyorum ama şuna benziyor:
Her giriş için bayrakları depolamak için birkaç bit tahsis ediyoruz.
Daha önce de söylediğimiz gibi, silme işleminden sonra tüm bitler 1'lerle dolar ve 1'i 0'a değiştirebiliriz ancak tersini yapamayız. Yani “bayrak ayarlanmadı” için 1, “bayrak ayarlandı” için 0 kullanıyoruz.

Değişken uzunluktaki bir kaydı flash'a koymak şöyle görünebilir:

1. “Uzunluk kaydı başladı” bayrağını ayarlayın;
2. Uzunluğu kaydedin;
3. “Veri kaydı başladı” bayrağını ayarlayın;
4. Verileri kaydediyoruz;
5. “Kayıt sona erdi” bayrağını ayarlayın.

Ayrıca toplam 4 bitlik bayraklardan oluşan bir “hata oluştu” bayrağımız olacak.

Bu durumda iki kararlı durumumuz vardır: "1111" - kayıt başlamadı ve "1000" - kayıt başarılı oldu; Kayıt sürecinin beklenmedik bir şekilde kesintiye uğraması durumunda, daha sonra tespit edip işleyebileceğimiz ara durumları alacağız.

Yaklaşım ilginç, ancak yalnızca ani elektrik kesintilerine ve benzeri arızalara karşı koruma sağlıyor ki bu elbette önemli, ancak bu olası arızaların tek (ve hatta ana) nedeni olmaktan uzak.

Özet: İyi bir çözüm aramaya devam edelim.

sağlama toplamı

Sağlama toplamları aynı zamanda (makul olasılıkla) tam olarak ne yazılması gerektiğini okuduğumuzdan emin olmamızı da mümkün kılar. Yukarıda tartışılan bit alanlarının aksine, bunlar her zaman çalışır.

Yukarıda tartıştığımız potansiyel sorun kaynaklarının listesini dikkate alırsak, sağlama toplamı, kaynağına bakılmaksızın bir hatayı tanıyabilir. (belki kötü niyetli uzaylılar hariç - onlar da sağlama toplamını düzenleyebilirler).

Dolayısıyla amacımız verilerin sağlam olduğunu doğrulamaksa sağlama toplamları harika bir fikirdir.

Sağlama toplamını hesaplamak için algoritma seçimi herhangi bir soruyu gündeme getirmedi - CRC. Bir yandan matematiksel özellikler belirli hata türlerini %100 yakalamayı mümkün kılarken diğer yandan rastgele verilerde bu algoritma genellikle çarpışma olasılığını teorik sınırdan çok da yüksek olmayan şekilde gösterir. . Çarpışma sayısı açısından en hızlı algoritma olmayabilir ya da her zaman en düşük algoritma olmayabilir, ancak çok önemli bir niteliği var: Karşılaştığım testlerde açıkça başarısız olduğu hiçbir model yoktu. Bu durumda istikrar ana kalitedir.

Hacimsel bir çalışma örneği: Bölüm 1, Bölüm 2 (narod.ru'ya bağlantılar, üzgünüm).

Ancak sağlama toplamı seçme görevi tamamlanmamıştır; CRC tam bir sağlama toplamı ailesidir. Uzunluğa karar vermeniz ve ardından bir polinom seçmeniz gerekir.

Sağlama toplamı uzunluğunun seçilmesi ilk bakışta göründüğü kadar basit bir soru değildir.

Şöyle örneklendireyim:
Her baytta hata olasılığını alalım ve ideal bir sağlama toplamı için milyon kayıt başına ortalama hata sayısını hesaplayalım:

Veri, bayt
Sağlama toplamı, bayt
Algılanmayan hatalar
Yanlış hata tespitleri
Toplam hatalı pozitifler

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

Görünüşe göre her şey basit - korunan verinin uzunluğuna bağlı olarak, minimum hatalı pozitiflerle sağlama toplamının uzunluğunu seçin - ve işin püf noktası çantada.

Bununla birlikte, kısa sağlama toplamlarıyla ilgili bir sorun ortaya çıkar: Tek bitlik hataları tespit etmede iyi olmalarına rağmen, oldukça yüksek bir olasılıkla tamamen rastgele verileri doğru olarak kabul edebilirler. Habré hakkında zaten açıklayan bir makale vardı. gerçek hayatta sorun.

Bu nedenle, rastgele bir sağlama toplamı eşleşmesini neredeyse imkansız hale getirmek için, uzunluğu 32 bit veya daha uzun olan sağlama toplamları kullanmanız gerekir. (64 bitten büyük uzunluklar için genellikle kriptografik karma işlevleri kullanılır).

Her ne kadar yerden tasarruf etmemiz gerektiğini daha önce yazmış olsam da, yine de 32 bitlik bir sağlama toplamı kullanacağız (16 bit yeterli değil, çarpışma olasılığı %0.01'den fazladır; ve 24 bit, çünkü bunlar) diyelim ki, ne burada ne de oradayız).

Burada şöyle bir itiraz ortaya çıkabilir: Sıkıştırmayı seçerken şimdi tek seferde 4 bayt vermek için her baytı mı kaydettik? Sağlama toplamını sıkıştırmamak veya eklememek daha iyi olmaz mıydı? Tabii ki hayır, sıkıştırma yok değil, bütünlük kontrolüne ihtiyacımız olmadığını.

Bir polinom seçerken tekerleği yeniden icat etmeyeceğiz, ancak artık popüler olan CRC-32C'yi alacağız.
Bu kod, 6 bayta kadar olan paketlerdeki 22 bitlik hataları (belki de bizim için en yaygın durum), 4 bayta kadar olan paketlerdeki 655 bitlik hataları (bizim için de yaygın bir durum), paketlerdeki 2 veya herhangi bir tek sayıdaki bit hatalarını tespit eder. makul herhangi bir uzunlukta.

Eğer ayrıntılarla ilgilenen varsa

Vikipedi makalesi CRC hakkında.

Kod parametreleri crc-32c üzerinde Koopman'ın web sitesi — belki de gezegendeki önde gelen CRC uzmanı.

В onun makalesi var ilginç bir kod dahaBu, bizimle ilgili paket uzunlukları için biraz daha iyi parametreler sağlıyor, ancak aradaki farkın önemli olduğunu düşünmedim ve standart ve iyi araştırılmış olanın yerine özel kodu seçecek kadar yetkindim.

Ayrıca verilerimiz sıkıştırıldığı için şu soru ortaya çıkıyor: sıkıştırılmış verilerin mi yoksa sıkıştırılmamış verilerin sağlama toplamını mı hesaplamalıyız?

Sıkıştırılmamış verilerin sağlama toplamının hesaplanması lehine argümanlar:

• Sonuçta veri depolamanın güvenliğini kontrol etmemiz gerekiyor - bu yüzden doğrudan kontrol ediyoruz (aynı zamanda sıkıştırma/açma uygulamasındaki olası hatalar, bozuk hafızanın neden olduğu hasar vb. de kontrol edilecektir);
• Zlib'deki deflate algoritması oldukça olgun bir uygulamaya sahiptir ve olmamalı "çarpık" giriş verileriyle düşme; üstelik, genellikle giriş akışındaki hataları bağımsız olarak tespit edebilir, bu da genel olarak bir hatanın tespit edilmeme olasılığını azaltır (kısa bir kayıtta tek bir bitin ters çevrilmesiyle bir test yapıldı, zlib bir hata tespit etti) vakaların yaklaşık üçte birinde).

Sıkıştırılmamış verilerin sağlama toplamının hesaplanmasına karşı argümanlar:

• CRC, özellikle flash belleğin karakteristiği olan birkaç bit hatası için "uyarlanmıştır" (sıkıştırılmış bir akıştaki bir bit hatası, çıkış akışında büyük bir değişikliğe neden olabilir, bu durumda tamamen teorik olarak bir çarpışmayı "yakalayabiliriz");
• Potansiyel olarak bozulmuş verileri sıkıştırıcıya aktarma fikrinden pek hoşlanmıyorum. Kim bilirnasıl tepki vereceğini.

Bu projede, sıkıştırılmamış verilerin sağlama toplamını depolamaya ilişkin genel kabul görmüş uygulamadan sapmaya karar verdim.

Özet: CRC-32C kullanıyoruz, sağlama toplamını flaşa yazıldıkları formdaki (sıkıştırmadan sonra) verilerden hesaplıyoruz.

Artıklık

Yedekli kodlamanın kullanılması elbette veri kaybını ortadan kaldırmaz, ancak kurtarılamaz veri kaybı olasılığını önemli ölçüde (çoğunlukla birçok büyüklük düzeyinde) azaltabilir.

Hataları düzeltmek için farklı artıklık türlerini kullanabiliriz.
Hamming kodları tek bitlik hataları düzeltebilir, Reed-Solomon karakter kodları, sağlama toplamlarıyla birleştirilmiş birden fazla veri kopyası veya RAID-6 gibi kodlamalar, büyük bir bozulma durumunda bile verilerin kurtarılmasına yardımcı olabilir.
Başlangıçta hataya dayanıklı kodlamanın yaygın olarak kullanılmasına kararlıydım ancak daha sonra fark ettim ki öncelikle kendimizi hangi hatalardan korumak istediğimize dair bir fikre sahip olmamız ve ardından kodlamayı seçmemiz gerekiyor.

Hataların mümkün olduğu kadar çabuk yakalanması gerektiğini daha önce söylemiştik. Hangi noktalarda hatalarla karşılaşabiliriz?

1. Bitmemiş kayıt (kayıt sırasında bazı nedenlerden dolayı güç kapatıldı, Raspberry dondu, ...)
   Ne yazık ki, böyle bir hata durumunda geriye geçersiz kayıtları yok saymak ve kaybolan verileri dikkate almak kalıyor;
2. Yazma hataları (bazı nedenlerden dolayı flash belleğe yazılanlar yazılanlar değildi)
   Kayıttan hemen sonra bir test okuması yaparsak bu tür hataları hemen tespit edebiliriz;
3. Depolama sırasında bellekteki verilerin bozulması;
4. Hataları okuma
   Bunu düzeltmek için, eğer sağlama toplamı eşleşmiyorsa, okumayı birkaç kez tekrarlamak yeterlidir.

Yani, yalnızca üçüncü türdeki hatalar (depolama sırasında verilerin kendiliğinden bozulması), hataya dayanıklı kodlama olmadan düzeltilemez. Görünüşe göre bu tür hatalar hala son derece düşük bir ihtimal.

Özet: gereksiz kodlamadan vazgeçilmesine karar verildi, ancak işlem bu kararın hatasını gösteriyorsa, o zaman sorunun değerlendirilmesine geri dönün (hatalara ilişkin zaten birikmiş istatistiklerle, bu, en uygun kodlama türünün seçilmesine olanak tanıyacak).

Diğer

Tabii ki, makalenin formatı formattaki her şeyi haklı çıkarmamıza izin vermiyor (ve gücüm çoktan tükendi)Bu yüzden daha önce değinmediğim bazı noktaların üzerinden kısaca geçeceğim.

• Tüm sayfaların “eşit” hale getirilmesine karar verildi
  Yani, meta veriler, ayrı başlıklar vb. içeren özel sayfalar olmayacak, bunun yerine tüm sayfaları sırayla yeniden yazan tek bir iş parçacığı olacak.
  Bu, sayfaların eşit şekilde aşınmasını sağlar, tek bir hata noktası oluşmaz ve bu hoşuma gidiyor;
• Formatın versiyonlandırılmasının sağlanması zorunludur.
  Başlığında sürüm numarası olmayan bir format kötüdür!
  Sayfa başlığına, kullanılan formatın sürümünü gösterecek belirli bir Sihirli Numaraya (imza) sahip bir alan eklemek yeterlidir. (Pratikte bunlardan bir düzine bile olacağını sanmıyorum);
• Kayıtlar için değişken uzunluklu bir başlık kullanın (bunlardan çok sayıda vardır), çoğu durumda onu 1 bayt uzunluğunda yapmaya çalışın;
• Başlığın uzunluğunu ve sıkıştırılmış kaydın kırpılmış kısmının uzunluğunu kodlamak için değişken uzunluklu ikili kodlar kullanın.

Çok yardımcı oldu çevrimiçi jeneratör Huffman kodları. Sadece birkaç dakika içinde gerekli değişken uzunluk kodlarını seçebildik.

Veri depolama formatının açıklaması

Bayt sırası

Bir bayttan büyük alanlar big-endian formatında (ağ bayt sırası) saklanır, yani 0x1234 0x12, 0x34 olarak yazılır.

Sayfalandırma

Tüm flash bellek eşit boyutta sayfalara bölünmüştür.

Varsayılan sayfa boyutu 32Kb'dir, ancak bellek yongasının toplam boyutunun 1/4'ünden fazla değildir (4 MB'lık bir yonga için 128 sayfa elde edilir).

Her sayfa, verileri diğerlerinden bağımsız olarak depolar (yani, bir sayfadaki veriler, başka bir sayfadaki verilere referans vermez).

Tüm sayfalar, 0 rakamından başlayarak doğal sırayla (adreslerin artan sırasına göre) numaralandırılır (sıfır sayfa, adres 0'dan başlar, ilk sayfa 32Kb'den başlar, ikinci sayfa 64Kb'den başlar, vb.)

Bellek yongası döngüsel tampon (halka tampon) olarak kullanılır, yani önce 0 numaralı sayfaya, sonra 1 numaralı sayfaya yazı gider, son sayfayı doldurduğumuzda yeni bir döngü başlar ve kayıt sıfırdan devam eder. .

Sayfanın içinde

Sayfanın başında 4 baytlık bir sayfa başlığı saklanır, ardından başlık sağlama toplamı (CRC-32C), ardından kayıtlar “başlık, veri, sağlama toplamı” formatında saklanır.

Sayfa başlığı (diyagramda kirli yeşil) aşağıdakilerden oluşur:

• iki baytlık Sihirli Sayı alanı (aynı zamanda format versiyonunun bir işareti)
  formatın mevcut sürümü için şu şekilde hesaplanır: 0xed00 ⊕ номер страницы;
• iki baytlık sayaç “Sayfa sürümü” (bellek yeniden yazma döngüsü numarası).

Sayfadaki girişler sıkıştırılmış biçimde saklanır (deflate algoritması kullanılır). Bir sayfadaki tüm kayıtlar tek bir başlıkta sıkıştırılır (ortak bir sözlük kullanılır) ve her yeni sayfada sıkıştırma yeniden başlar. Yani, herhangi bir kaydın sıkıştırmasını açmak için bu sayfadaki (ve yalnızca bu sayfadaki) önceki tüm kayıtlara ihtiyaç vardır.

Her kayıt Z_SYNC_FLUSH bayrağıyla sıkıştırılacak ve sıkıştırılmış akışın sonunda 4 bayt 0x00, 0x00, 0xff, 0xff olacak ve ardından muhtemelen bir veya iki sıfır bayt daha gelecektir.
Flaş belleğe yazarken bu sırayı (4, 5 veya 6 bayt uzunluğunda) atıyoruz.

Kayıt başlığı 1, 2 veya 3 baytlık depolama alanıdır:

• kayıt türünü belirten bir bit (T): 0 - bağlam, 1 - günlük;
• dekompresyon için kayda eklenmesi gereken başlığın ve "kuyruk"un uzunluğunu tanımlayan, 1 ila 7 bit arasında değişken uzunluklu bir alan (S);
• kayıt uzunluğu (L).

S değeri tablosu:

S
Başlık uzunluğu, bayt
Yazma sırasında atıldı, bayt

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)

Örneklemeye çalıştım, ne kadar net ortaya çıktığını bilmiyorum:

Burada sarı, T alanını, beyaz S alanını, yeşil L (sıkıştırılmış verinin bayt cinsinden uzunluğu), mavi sıkıştırılmış veriyi, kırmızı ise sıkıştırılmış verinin flash belleğe yazılmayan son baytını belirtir.

Böylece, en yaygın uzunluktaki (sıkıştırılmış biçimde 63+5 bayta kadar) kayıt başlıklarını bir bayta yazabiliriz.

Her kayıttan sonra, önceki sağlama toplamının ters çevrilmiş değerinin başlangıç ​​değeri (init) olarak kullanıldığı bir CRC-32C sağlama toplamı saklanır.

CRC "süre" özelliğine sahiptir, aşağıdaki formül çalışır (işlemde artı veya eksi bitlerin ters çevrilmesi): .
Yani aslında bu sayfadaki önceki tüm başlık ve veri baytlarının CRC'sini hesaplıyoruz.

Sağlama toplamının hemen ardından bir sonraki kaydın başlığı gelir.

Başlık, ilk baytı her zaman 0x00 ve 0xff'den farklı olacak şekilde tasarlanmıştır (başlığın ilk baytı yerine 0xff ile karşılaşırsak, bu, bunun kullanılmayan bir alan olduğu anlamına gelir; 0x00 bir hata sinyali verir).

Örnek Algoritmalar

Flash Bellekten Okuma

Herhangi bir okuma bir sağlama toplamı kontrolüyle birlikte gelir.
Sağlama toplamı eşleşmiyorsa, doğru verinin okunması umuduyla okuma birkaç kez tekrarlanır.

(bu mantıklıdır, Linux NOR Flash'tan gelen okumaları önbelleğe almaz, test edilmiştir)

Flaş belleğe yaz

Verileri kaydediyoruz.
Onları okuyalım.

Okunan veriler yazılan verilerle eşleşmiyorsa alanı sıfırlarla doldurup hata sinyali veririz.

Operasyon için yeni bir mikro devrenin hazırlanması

Başlatma için, ilk (veya daha doğrusu sıfır) sayfaya sürüm 1'e sahip bir başlık yazılır.
Bundan sonra, ilk içerik bu sayfaya yazılır (makinenin UUID'sini ve varsayılan ayarları içerir).

İşte bu, flash bellek kullanıma hazır.

Makineyi yükleme

Yükleme sırasında her sayfanın (başlık + CRC) ilk 8 baytı okunur, bilinmeyen Sihir Numarasına veya yanlış CRC'ye sahip sayfalar dikkate alınmaz.
“Doğru” sayfalardan maksimum sürüme sahip sayfalar seçilir ve bunlardan en yüksek sayıdaki sayfa alınır.
İlk kayıt okunur, CRC'nin doğruluğu ve “bağlam” bayrağının varlığı kontrol edilir. Her şey yolundaysa bu sayfa güncel kabul edilir. Değilse, "canlı" bir sayfa bulana kadar bir öncekine geri döneriz.
ve bulunan sayfada “bağlam” bayrağıyla kullandığımız tüm kayıtları okuyoruz.
Zlib sözlüğünü kaydedin (bu sayfaya eklemek için gerekli olacaktır).

İşte bu, indirme tamamlandı, içerik geri yüklendi, çalışabilirsiniz.

Yevmiye Girişi Ekleme

Kaydı Z_SYNC_FLUSH belirterek doğru sözlükle sıkıştırıyoruz ve sıkıştırılmış kaydın mevcut sayfaya sığıp sığmadığını görüyoruz.
Uymuyorsa (veya sayfada CRC hataları varsa), yeni bir sayfa başlatın (aşağıya bakın).
Kaydı ve CRC'yi yazıyoruz. Bir hata oluşursa yeni bir sayfa başlatın.

Yeni sayfa

Minimum sayıya sahip ücretsiz bir sayfa seçiyoruz (ücretsiz bir sayfayı, başlıkta yanlış sağlama toplamı olan veya mevcut olandan daha düşük bir sürüme sahip bir sayfa olarak kabul ediyoruz). Böyle bir sayfa yoksa, mevcut sayfaya eşit sürüme sahip olanlardan minimum sayıdaki sayfayı seçin.
Seçilen sayfayı siliyoruz. İçeriği 0xff ile kontrol ediyoruz. Bir sorun varsa sonraki boş sayfaya geçin vb.
Silinen sayfaya bir başlık yazıyoruz, ilk giriş bağlamın mevcut durumu, sonraki ise yazılmamış günlük girişi (varsa).

Biçim uygulanabilirliği

Bana göre, NOR Flash'ta az çok sıkıştırılabilir bilgi akışlarını (düz metin, JSON, Mesaj Paketi, CBOR, muhtemelen protobuf) depolamak için iyi bir format olduğu ortaya çıktı.

Elbette format SLC NOR Flash için "özelleştirilmiştir".

NAND veya MLC NOR gibi yüksek BER ortamlarıyla kullanılmamalıdır. (böyle bir hafıza satılıyor mu? Sadece düzeltme kodları üzerinde yapılan çalışmalarda bahsedildiğini gördüm).

Üstelik kendi FTL'si olan cihazlarla kullanılmamalıdır: USB flash, SD, MicroSD vb. (böyle bir bellek için 512 bayt sayfa boyutuna, her sayfanın başında bir imzaya ve benzersiz kayıt numaralarına sahip bir format oluşturdum - bazen "arızalı" bir flash sürücüdeki tüm verileri basit sıralı okumayla kurtarmak mümkündü).

Görevlere bağlı olarak format, flash sürücülerde 128Kbit'ten (16Kb) 1Gbit'e (128MB) kadar değişiklik yapılmadan kullanılabilir. İsterseniz daha büyük çiplerde kullanabilirsiniz ancak muhtemelen sayfa boyutunu ayarlamanız gerekir (Ancak burada ekonomik fizibilite sorunu zaten ortaya çıkıyor; büyük hacimli NOR Flash'ın fiyatı cesaret verici değil).

Birisi formatı ilginç buluyorsa ve açık bir projede kullanmak istiyorsa yazın, ben de zamanı bulmaya çalışacağım, kodu düzeltip github'da yayınlayacağım.

Sonuç

Gördüğünüz gibi, sonunda formatın basit olduğu ortaya çıktı ve hatta sıkıcı.

Bakış açımın gelişimini bir makaleye yansıtmak zor ama inanın bana: Başlangıçta sofistike, yok edilemez, yakın bir nükleer patlamaya bile dayanabilecek bir şey yaratmak istedim. Ancak yine de mantık (umarım) galip geldi ve yavaş yavaş öncelikler basitliğe ve kompaktlığa doğru kaydı.

Yanılmış olabilir miyim? Evet elbette. Örneğin, bir grup düşük kaliteli mikro devre satın aldığımız ortaya çıkabilir. Veya başka bir nedenden dolayı ekipman güvenilirlik beklentilerini karşılamayacaktır.

Bunun için bir planım var mı? Sanırım makaleyi okuduktan sonra bir plan olduğuna dair hiçbir şüpheniz kalmadı. Ve yalnız bile değil.

Biraz daha ciddi bir husus, formatın hem bir çalışma seçeneği hem de bir "deneme balonu" olarak geliştirilmiş olmasıdır.

Şu anda masadaki her şey yolunda çalışıyor, kelimenin tam anlamıyla geçen gün çözüm devreye girecek (yaklaşık olarak) yüzlerce cihazda, "savaş" işleminde neler olacağını görelim (neyse ki format, arızaları güvenilir bir şekilde tespit etmenize izin veriyor; böylece tüm istatistikleri toplayabilirsiniz). Birkaç ay içinde sonuç çıkarmak mümkün olacak (ve eğer şanssızsanız daha da erken).

Kullanım sonuçlarına göre ciddi sorunlar tespit edilirse ve iyileştirmeler gerekiyorsa mutlaka yazacağım.

Edebiyat

Kullanılmış eserlerin uzun ve sıkıcı bir listesini yapmak istemedim; sonuçta herkesin Google'ı var.

Burada bana özellikle ilginç gelen bulguların bir listesini bırakmaya karar verdim, ancak bunlar yavaş yavaş doğrudan makalenin metnine taşındı ve listede bir madde kaldı:

1. Yarar Infgen yazar zlib'den. deflate/zlib/gzip arşivlerinin içeriğini net bir şekilde görüntüleyebilir. Eğer deflate (veya gzip) formatının iç yapısıyla uğraşmak zorundaysanız kesinlikle tavsiye ederim.

Kaynak: habr.com