قبل التاريخ

توجد آلات بيع من تصميمنا الخاص. داخل Raspberry Pi وبعض الأسلاك على لوحة منفصلة. يتم توصيل جهاز قبول العملات المعدنية، وجهاز قبول الفاتورة، ومحطة البنك... يتم التحكم في كل شيء من خلال برنامج مكتوب ذاتيًا. تتم كتابة سجل العمل بالكامل في سجل على محرك أقراص فلاش (MicroSD)، والذي يتم بعد ذلك نقله عبر الإنترنت (باستخدام مودم USB) إلى الخادم، حيث يتم تخزينه في قاعدة بيانات. يتم تحميل معلومات المبيعات في 1C، وهناك أيضًا واجهة ويب بسيطة للمراقبة، وما إلى ذلك.

أي أن المجلة أمر حيوي - للمحاسبة (الإيرادات والمبيعات وما إلى ذلك)، والمراقبة (جميع أنواع الإخفاقات وغيرها من ظروف القوة القاهرة)؛ ويمكن القول أن هذه هي كل المعلومات التي لدينا عن هذا الجهاز.

مشكلة

تظهر محركات الأقراص المحمولة أنها أجهزة غير موثوقة للغاية. إنهم يفشلون بانتظام يحسدون عليه. يؤدي هذا إلى توقف الجهاز عن العمل و(إذا تعذر نقل السجل عبر الإنترنت لسبب ما) إلى فقدان البيانات.

هذه ليست التجربة الأولى لاستخدام محركات الأقراص المحمولة، فقبل ذلك كان هناك مشروع آخر يضم أكثر من مائة جهاز، حيث تم تخزين المجلة على محركات أقراص فلاش USB، وكانت هناك أيضًا مشكلات تتعلق بالموثوقية، وفي بعض الأحيان كان عدد تلك التي فشلت في كان الشهر بالعشرات. لقد جربنا محركات أقراص فلاش مختلفة، بما في ذلك ذات العلامات التجارية مع ذاكرة SLC، وبعض النماذج أكثر موثوقية من غيرها، لكن استبدال محركات الأقراص المحمولة لم يحل المشكلة بشكل جذري.

تحذير! قراءة طويلة! إذا لم تكن مهتمًا بـ "لماذا"، ولكن فقط بـ "كيف"، فيمكنك المضي قدمًا مباشرة في النهاية المادة.

حل

أول ما يتبادر إلى الذهن هو: التخلي عن MicroSD، وتثبيت SSD، على سبيل المثال، والتمهيد منه. ربما يكون ذلك ممكنًا من الناحية النظرية، ولكنه مكلف نسبيًا وغير موثوق به (تمت إضافة محول USB-SATA؛ كما أن إحصائيات الفشل لمحركات أقراص SSD ذات الميزانية ليست مشجعة أيضًا).

لا يبدو محرك الأقراص الثابتة USB أيضًا حلاً جذابًا بشكل خاص.

لذلك، توصلنا إلى هذا الخيار: ترك التشغيل من بطاقة MicroSD، ولكن استخدمها في وضع القراءة فقط، وقم بتخزين سجل التشغيل (ومعلومات أخرى فريدة خاصة بجزء معين من الأجهزة - الرقم التسلسلي، ومعايرات المستشعر، وما إلى ذلك) في مكان آخر .

لقد تمت بالفعل دراسة موضوع FS للقراءة فقط للتوت من الداخل والخارج، ولن أتطرق إلى تفاصيل التنفيذ في هذه المقالة (ولكن إذا كان هناك اهتمام، ربما سأكتب مقالة صغيرة حول هذا الموضوع). النقطة الوحيدة التي أود أن أشير إليها هي أنه من خلال التجربة الشخصية ومن خلال مراجعات أولئك الذين قاموا بتنفيذها بالفعل، هناك مكاسب في الموثوقية. نعم، من المستحيل التخلص تماما من الأعطال، ولكن من الممكن تماما تقليل تواترها بشكل كبير. وأصبحت البطاقات موحدة، مما يجعل استبدالها أسهل بكثير لموظفي الخدمة.

الجزء الأجهزة

لم يكن هناك شك خاص في اختيار نوع الذاكرة - NOR Flash.
الحجج:

• اتصال بسيط (غالبًا ما يكون ناقل SPI، الذي لديك بالفعل خبرة في استخدامه، لذلك لا يُتوقع حدوث مشكلات في الأجهزة)؛
• سعر مثير للسخرية؛
• بروتوكول التشغيل القياسي (التنفيذ موجود بالفعل في Linux kernel، إذا كنت ترغب في ذلك، يمكنك أن تأخذ طرفًا ثالثًا، وهو موجود أيضًا، أو حتى تكتبه بنفسك، ولحسن الحظ، كل شيء بسيط)؛
• الموثوقية والموارد:
  من ورقة بيانات نموذجية: يتم تخزين البيانات لمدة 20 عامًا، و100000 دورة مسح لكل كتلة؛
  من مصادر خارجية: نسبة خطأ في البتات (BER) منخفضة للغاية، مما يفترض عدم الحاجة إلى رموز تصحيح الأخطاء (بعض الأعمال تعتبر ECC لـ NOR، لكنها عادةً ما تزال تعني MLC NOR؛ ويحدث هذا أيضًا).

دعونا نقدر متطلبات الحجم والموارد.

أرغب في ضمان حفظ البيانات لعدة أيام. يعد ذلك ضروريًا حتى لا يتم فقدان سجل المبيعات في حالة حدوث أي مشكلات في الاتصال. وسنركز على 5 أيام خلال هذه الفترة (حتى مع الأخذ في الاعتبار عطلات نهاية الأسبوع والأعياد) يمكن حل المشكلة.

نقوم حاليًا بجمع حوالي 100 كيلو بايت من السجلات يوميًا (3-4 آلاف إدخال)، ولكن هذا الرقم ينمو تدريجيًا - التفاصيل تتزايد، وتتم إضافة أحداث جديدة. بالإضافة إلى ذلك، في بعض الأحيان تكون هناك رشقات نارية (يبدأ بعض أجهزة الاستشعار في إرسال رسائل غير مرغوب فيها بإيجابيات كاذبة، على سبيل المثال). سنقوم بحساب 10 آلاف سجل لكل منها 100 بايت - ميغا بايت في اليوم.

في المجموع، يخرج 5 ميغابايت من البيانات النظيفة (المضغوطة جيدًا). المزيد لهم (تقدير تقريبي) 1 ميغابايت من بيانات الخدمة.

أي أننا نحتاج إلى شريحة بحجم 8 ميجابايت إذا لم نستخدم الضغط، أو 4 ميجابايت إذا استخدمناها. أرقام واقعية تمامًا لهذا النوع من الذاكرة.

أما بالنسبة للمورد: إذا كنا نخطط لإعادة كتابة الذاكرة بأكملها بما لا يزيد عن مرة واحدة كل 5 أيام، فعندئذ خلال 10 سنوات من الخدمة، نحصل على أقل من ألف دورة إعادة كتابة.
اسمحوا لي أن أذكرك أن الشركة المصنعة تعد بمائة ألف.

قليلا عن NOR مقابل NAND

اليوم، بالطبع، أصبحت ذاكرة NAND أكثر شيوعًا، لكنني لن أستخدمها في هذا المشروع: NAND، على عكس NOR، تتطلب بالضرورة استخدام رموز تصحيح الأخطاء، وجدول الكتل السيئة، وما إلى ذلك، وكذلك أرجل رقائق NAND عادة ما تكون أكثر من ذلك بكثير.

تشمل عيوب NOR ما يلي:

• حجم صغير (وبالتالي سعر مرتفع لكل ميغا بايت) ؛
• سرعة اتصال منخفضة (يرجع ذلك إلى حد كبير إلى حقيقة استخدام واجهة تسلسلية، عادةً ما تكون SPI أو I2C)؛
• المسح البطيء (اعتمادًا على حجم الكتلة، يستغرق من جزء من الثانية إلى عدة ثوانٍ).

يبدو أنه لا يوجد شيء حاسم بالنسبة لنا، لذلك نستمر.

إذا كانت التفاصيل مثيرة للاهتمام، فقد تم اختيار الدائرة الدقيقة at25df321a (ومع ذلك، هذا غير مهم، فهناك الكثير من نظائرها في السوق المتوافقة مع نظام pinout ونظام الأوامر؛ حتى لو أردنا تثبيت دائرة كهربائية صغيرة من مصنع مختلف و/أو بحجم مختلف، فسيعمل كل شيء دون تغيير شفرة).

أستخدم برنامج التشغيل المدمج في Linux kernel؛ في Raspberry، بفضل دعم تراكب شجرة الجهاز، كل شيء بسيط للغاية - تحتاج إلى وضع التراكب المترجم في /boot/overlays وتعديل /boot/config.txt قليلاً.

مثال لملف dts

لأكون صادقًا، لست متأكدًا من أنه مكتوب بدون أخطاء، لكنه يعمل.

/*
 * Device tree overlay for at25 at spi0.1
 */

/dts-v1/;
/plugin/;

/ {
    compatible = "brcm,bcm2835", "brcm,bcm2836", "brcm,bcm2708", "brcm,bcm2709"; 

    /* disable spi-dev for spi0.1 */
    fragment@0 {
        target = <&spi0>;
        __overlay__ {
            status = "okay";
            spidev@1{
                status = "disabled";
            };
        };
    };

    /* the spi config of the at25 */
    fragment@1 {
        target = <&spi0>;
        __overlay__ {
            #address-cells = <1>;
            #size-cells = <0>;
            flash: m25p80@1 {
                    compatible = "atmel,at25df321a";
                    reg = <1>;
                    spi-max-frequency = <50000000>;

                    /* default to false:
                    m25p,fast-read ;
                    */
            };
        };
    };

    __overrides__ {
        spimaxfrequency = <&flash>,"spi-max-frequency:0";
        fastread = <&flash>,"m25p,fast-read?";
    };
};

وسطر آخر في ملف config.txt

dtoverlay=at25:spimaxfrequency=50000000

سأحذف وصف توصيل الشريحة بـ Raspberry Pi. من ناحية، أنا لست خبيرا في الإلكترونيات، من ناحية أخرى، كل شيء هنا عادي حتى بالنسبة لي: تحتوي الدائرة الدقيقة على 8 أرجل فقط، والتي نحتاج منها إلى الأرض والطاقة وSPI (CS، SI، SO، SCK) ); المستويات هي نفس مستويات Raspberry Pi، ولا يلزم وجود أسلاك إضافية - فقط قم بتوصيل الدبابيس الستة المشار إليها.

صياغة المشكلة

كالعادة، يمر بيان المشكلة بعدة تكرارات، ويبدو لي أن الوقت قد حان للتكرار التالي. لذلك دعونا نتوقف ونجمع ما تم كتابته بالفعل ونوضح التفاصيل التي ظلت في الظل.

لذلك، قررنا أن يتم تخزين السجل في SPI NOR Flash.

ما هو NOR Flash لمن لا يعرفه؟

هذه ذاكرة غير متطايرة يمكنك من خلالها القيام بثلاث عمليات:

1. القراءة:
   القراءة الأكثر شيوعًا: ننقل العنوان ونقرأ أكبر عدد ممكن من البايتات؛
2. سجل:
   تبدو الكتابة إلى NOR flash وكأنها طريقة عادية، ولكنها تتميز بخصوصية واحدة: يمكنك فقط تغيير 1 إلى 0، ولكن ليس العكس. على سبيل المثال، إذا كان لدينا 0x55 في خلية ذاكرة، فبعد كتابة 0x0f إليها، سيتم تخزين 0x05 هناك بالفعل (انظر الجدول أدناه);
3. مسح:
   بالطبع، نحن بحاجة إلى أن نكون قادرين على القيام بالعملية المعاكسة - تغيير 0 إلى 1، وهذا هو بالضبط ما تهدف إليه عملية المسح. على عكس الأولين، فإنه لا يعمل بالبايت، ولكن بالكتل (الحد الأدنى لكتلة المسح في الشريحة المحددة هو 4 كيلو بايت). يؤدي المسح إلى تدمير الكتلة بأكملها وهي الطريقة الوحيدة لتغيير 0 إلى 1. لذلك، عند العمل باستخدام ذاكرة فلاش، يتعين عليك غالبًا محاذاة هياكل البيانات مع حدود كتلة المسح.
   التسجيل في NOR Flash:

البيانات الثنائية

كان
01010101

مسجل
00001111

أصبح
00000101

يمثل السجل نفسه سلسلة من السجلات ذات الطول المتغير. يبلغ الطول النموذجي للسجل حوالي 30 بايت (على الرغم من وجود سجلات يبلغ طولها عدة كيلو بايت في بعض الأحيان). في هذه الحالة، نحن نعمل معهم ببساطة كمجموعة من البايتات، ولكن إذا كنت مهتمًا، فسيتم استخدام CBOR داخل السجلات

بالإضافة إلى السجل، نحتاج إلى تخزين بعض معلومات "الإعدادات"، سواء المحدثة أو غير المحدثة: معرف جهاز معين، ومعايرة أجهزة الاستشعار، وعلامة "تم تعطيل الجهاز مؤقتًا"، وما إلى ذلك.
هذه المعلومات عبارة عن مجموعة من سجلات القيمة الأساسية، ويتم تخزينها أيضًا في CBOR، وليس لدينا الكثير من هذه المعلومات (بضعة كيلو بايت على الأكثر)، ويتم تحديثها بشكل غير منتظم.
في ما يلي سوف نسميها السياق.

إذا تذكرنا أين بدأت هذه المقالة، فمن المهم جدًا ضمان تخزين البيانات بشكل موثوق، والتشغيل المستمر، إن أمكن، حتى في حالة فشل الأجهزة/تلف البيانات.

ما هي مصادر المشاكل التي يمكن النظر فيها؟

• قم بإيقاف التشغيل أثناء عمليات الكتابة/المسح. وهذا من باب «لا حيلة على المخل».
  معلومات من مناقشات عند تبادل المكدس: عند إيقاف تشغيل الطاقة أثناء العمل باستخدام الفلاش، يؤدي كل من المسح (الضبط على 1) والكتابة (الضبط على 0) إلى سلوك غير محدد: يمكن كتابة البيانات، وكتابتها جزئيًا (على سبيل المثال، قمنا بنقل 10 بايت/80 بت ، ولكن لم يتم حتى الآن كتابة 45 بت فقط)، فمن الممكن أيضًا أن تكون بعض البتات في حالة "متوسطة" (يمكن أن تنتج القراءة كلا من 0 و1)؛
• أخطاء في ذاكرة الفلاش نفسها.
  على الرغم من أن نسبة الخطأ في البتات (BER) منخفضة جدًا، إلا أنها لا يمكن أن تساوي الصفر؛
• أخطاء الحافلة
  البيانات المرسلة عبر SPI غير محمية بأي شكل من الأشكال؛ قد تحدث أخطاء بتات مفردة وأخطاء في المزامنة - فقدان أو إدخال البتات (مما يؤدي إلى تشويه كبير للبيانات)؛
• أخطاء / مواطن الخلل الأخرى
  أخطاء في التعليمات البرمجية، ومواطن الخلل في التوت، والتدخل الأجنبي...

لقد قمت بصياغة المتطلبات التي، في رأيي، ضرورية لضمان الموثوقية:

• يجب أن تنتقل السجلات إلى ذاكرة الفلاش على الفور، ولا يؤخذ في الاعتبار عمليات الكتابة المتأخرة؛ - في حالة حدوث خطأ، يجب اكتشافه ومعالجته في أقرب وقت ممكن؛ - يجب على النظام، إن أمكن، التعافي من الأخطاء.
  (مثال من الحياة "كيف لا ينبغي أن يكون الأمر"، والذي أعتقد أن الجميع قد واجهوه: بعد إعادة التشغيل الطارئة، يكون نظام الملفات "معطلاً" ولا يتم تشغيل نظام التشغيل)

أفكار، مناهج، تأملات

عندما بدأت بالتفكير في هذه المشكلة، خطرت في ذهني أفكار كثيرة، منها على سبيل المثال:

• استخدام ضغط البيانات؛
• استخدام هياكل البيانات الذكية، على سبيل المثال، تخزين رؤوس السجلات بشكل منفصل عن السجلات نفسها، بحيث إذا كان هناك خطأ في أي سجل، يمكنك قراءة الباقي دون أي مشاكل؛
• استخدام حقول البت للتحكم في اكتمال التسجيل عند إيقاف تشغيل الطاقة؛
• تخزين المجاميع الاختبارية لكل شيء؛
• استخدام نوع من الترميز المقاوم للضوضاء.

تم استخدام بعض هذه الأفكار، بينما تقرر التخلي عن البعض الآخر. دعنا نذهب بالترتيب.

ضغط البيانات

الأحداث نفسها التي نسجلها في المجلة متشابهة تمامًا وقابلة للتكرار ("ألقيت عملة بقيمة 5 روبل"، "ضغطت على الزر لإعطاء الفكة"، ...). لذلك، يجب أن يكون الضغط فعالاً للغاية.

الحمل الزائد للضغط ضئيل (معالجنا قوي جدًا، حتى أن Pi الأول كان يحتوي على نواة واحدة بتردد 700 ميجاهرتز، والنماذج الحالية بها عدة نوى بتردد يزيد عن جيجاهيرتز)، وسعر الصرف مع التخزين منخفض (عدة نوى) ميغا بايت في الثانية)، حجم السجلات صغير. بشكل عام، إذا كان للضغط تأثير على الأداء، فسيكون إيجابيًا فقط. (غير نقدي على الإطلاق، فقط ذكر). بالإضافة إلى ذلك، ليس لدينا نظام Linux مضمن حقيقي، ولكن نظام Linux عادي - لذا يجب ألا يتطلب التنفيذ الكثير من الجهد (يكفي فقط ربط المكتبة واستخدام عدة وظائف منها).

تم أخذ جزء من السجل من جهاز يعمل (1.7 ميجابايت، 70 ألف إدخال) وتم التحقق أولاً من قابلية الضغط باستخدام gzip، وlz4، وlzop، وbzip2، وxz، وzstd المتوفرة على الكمبيوتر.

• أظهر gzip وxz وzstd نتائج مماثلة (40 كيلو بايت).
  لقد فوجئت بأن XZ العصري أظهر نفسه هنا على مستوى gzip أو zstd؛
• أعطى lzip مع الإعدادات الافتراضية نتائج أسوأ قليلاً؛
• لم يُظهر lz4 وlzop نتائج جيدة جدًا (150 كيلو بايت)؛
• أظهر bzip2 نتيجة جيدة بشكل مدهش (18 كيلو بايت).

لذلك، يتم ضغط البيانات بشكل جيد للغاية.
لذا (إذا لم نجد عيوبًا قاتلة) فسيكون هناك ضغط! ببساطة لأنه يمكن احتواء المزيد من البيانات على نفس محرك الأقراص المحمول.

دعونا نفكر في العيوب.

المشكلة الأولى: لقد اتفقنا بالفعل على أن كل سجل يجب أن يتحول إلى الفلاش على الفور. عادةً ما يقوم المؤرشف بجمع البيانات من تدفق الإدخال حتى يقرر أن الوقت قد حان للكتابة في عطلة نهاية الأسبوع. نحن بحاجة إلى تلقي كتلة مضغوطة من البيانات على الفور وتخزينها في ذاكرة غير متطايرة.

أرى ثلاث طرق:

1. قم بضغط كل سجل باستخدام ضغط القاموس بدلاً من الخوارزميات التي تمت مناقشتها أعلاه.
   إنه خيار عملي تمامًا، لكني لا أحبه. ولضمان مستوى ضغط لائق إلى حد ما، يجب أن يكون القاموس "مصممًا" ليناسب بيانات محددة؛ وأي تغيير سيؤدي إلى انخفاض مستوى الضغط بشكل كارثي. نعم، يمكن حل المشكلة عن طريق إنشاء نسخة جديدة من القاموس، ولكن هذا يسبب صداعًا - سنحتاج إلى تخزين جميع إصدارات القاموس؛ سنحتاج في كل إدخال إلى الإشارة إلى إصدار القاموس الذي تم ضغطه به...
2. ضغط كل سجل باستخدام الخوارزميات "الكلاسيكية"، ولكن بشكل مستقل عن السجلات الأخرى.
   خوارزميات الضغط قيد النظر ليست مصممة للعمل مع سجلات بهذا الحجم (عشرات البايتات)، ومن الواضح أن نسبة الضغط ستكون أقل من 1 (أي زيادة حجم البيانات بدلاً من الضغط)؛
3. قم بإجراء FLUSH بعد كل تسجيل.
   العديد من مكتبات الضغط تدعم FLUSH. هذا أمر (أو معلمة لإجراء الضغط)، عند استلامه يقوم المؤرشف بتكوين دفق مضغوط بحيث يمكن استخدامه لاستعادة جميع البيانات غير المضغوطة التي تم تلقيها بالفعل. مثل هذا التناظرية sync في أنظمة الملفات أو commit في SQL.
   المهم هو أن عمليات الضغط اللاحقة ستكون قادرة على استخدام القاموس المتراكم ولن تتأثر نسبة الضغط بقدر ما كانت في الإصدار السابق.

أعتقد أنه من الواضح أنني اخترت الخيار الثالث، دعونا ننظر إليه بمزيد من التفصيل.

وجد مقال رائع حول فلوش في زليب.

لقد قمت بإجراء اختبار الركبة بناءً على المقالة، وحصلت على 70 ألف إدخال سجل من جهاز حقيقي، بحجم صفحة 60 كيلو بايت (سنعود إلى حجم الصفحة لاحقًا) تلقى:

البيانات الأولية
ضغط gzip -9 (بدون تدفق)
زليب مع Z_PARTIAL_FLUSH
زليب مع Z_SYNC_FLUSH

الحجم، كيلو بايت
1692
40
352
604

للوهلة الأولى، يكون السعر الذي تساهم به FLUSH مرتفعًا للغاية، ولكن في الواقع ليس لدينا خيار كبير - إما عدم الضغط على الإطلاق، أو الضغط (وبشكل فعال جدًا) باستخدام FLUSH. يجب ألا ننسى أن لدينا 70 ألف سجل، والتكرار الذي قدمته Z_PARTIAL_FLUSH هو 4-5 بايت فقط لكل سجل. وتبين أن نسبة الضغط كانت 5:1 تقريبًا، وهي أكثر من نتيجة ممتازة.

قد يكون الأمر مفاجئًا، لكن Z_SYNC_FLUSH هي في الواقع طريقة أكثر فعالية لإجراء FLUSH

عند استخدام Z_SYNC_FLUSH، ستكون آخر 4 بايتات من كل إدخال دائمًا 0x00، 0x00، 0xff، 0xff. وإذا كنا نعرفها، فلا يتعين علينا تخزينها، وبالتالي فإن الحجم النهائي هو 324 كيلو بايت فقط.

المقالة التي قمت بربطها بها شرح:

يتم إلحاق كتلة جديدة من النوع 0 بمحتويات فارغة.

تتكون الكتلة من النوع 0 ذات المحتويات الفارغة من:

• رأس الكتلة ذات الثلاث بتات؛
• 0 إلى 7 بتات تساوي الصفر، لتحقيق محاذاة البايت؛
• تسلسل أربعة بايت 00 00 FF FF.

كما ترون بسهولة، في الكتلة الأخيرة قبل هذه البايتات الأربع هناك من 4 إلى 3 بتات. ومع ذلك، فقد أظهرت الممارسة أن هناك في الواقع ما لا يقل عن 10 بتات صفرية.

اتضح أن مثل هذه الكتل القصيرة من البيانات يتم تشفيرها عادةً (دائمًا؟) باستخدام كتلة من النوع 1 (كتلة ثابتة)، والتي تنتهي بالضرورة بـ 7 بتات صفرية، مما يعطي إجمالي 10-17 بتة صفرية مضمونة (والباقي سوف يكون يكون صفرًا مع احتمال حوالي 50٪).

لذا، في بيانات الاختبار، في 100% من الحالات يوجد صفر بايت قبل 0x00، 0x00، 0xff، 0xff، وفي أكثر من ثلث الحالات يوجد صفر بايت (ربما الحقيقة هي أنني أستخدم CBOR الثنائي، وعند استخدام النص JSON، ستكون الكتل من النوع 2 - الكتلة الديناميكية أكثر شيوعًا، على التوالي، الكتل التي لا تحتوي على صفر بايت إضافية قبل مواجهة 0x00، 0x00، 0xff، 0xff).

في المجمل، باستخدام بيانات الاختبار المتاحة، من الممكن استيعاب أقل من 250 كيلو بايت من البيانات المضغوطة.

يمكنك توفير المزيد عن طريق تبديل البتات: في الوقت الحالي نتجاهل وجود عدد قليل من البتات الصفرية في نهاية الكتلة، كما أن بعض البتات في بداية الكتلة لا تتغير أيضًا...
ولكن بعد ذلك اتخذت قرارًا قويًا بالتوقف، وإلا فقد ينتهي بي الأمر بهذا المعدل إلى تطوير أرشيفي الخاص.

في المجمل، من بيانات الاختبار الخاصة بي، تلقيت 3-4 بايت لكل كتابة، وتبين أن نسبة الضغط أكثر من 6:1. سأكون صادقًا: لم أتوقع مثل هذه النتيجة؛ في رأيي، أي شيء أفضل من 2:1 هو بالفعل نتيجة تبرر استخدام الضغط.

كل شيء على ما يرام، لكن zlib (الانكماش) ​​لا يزال خوارزمية ضغط قديمة ومستحقة وقديمة الطراز بعض الشيء. إن حقيقة استخدام آخر 32 كيلو بايت من دفق البيانات غير المضغوطة كقاموس تبدو غريبة اليوم (أي، إذا كانت بعض كتل البيانات مشابهة جدًا لما كان موجودًا في دفق الإدخال قبل 40 كيلو بايت، فستبدأ أرشفتها مرة أخرى، ولن يشير إلى حدث سابق). في أرشيفات الأرشيف الحديثة العصرية، غالبًا ما يتم قياس حجم القاموس بالميجابايت بدلاً من الكيلوبايت.

لذلك نواصل دراستنا المصغرة للمحفوظات.

بعد ذلك قمنا باختبار bzip2 (تذكر أنه بدون FLUSH أظهر نسبة ضغط رائعة تصل إلى 100:1 تقريبًا). ولسوء الحظ، كان أداؤه سيئًا للغاية مع FLUSH، حيث تبين أن حجم البيانات المضغوطة أكبر من البيانات غير المضغوطة.

افتراضاتي حول أسباب الفشل

يوفر Libbz2 خيار تدفق واحد فقط، والذي يبدو أنه يمسح القاموس (مشابه لـ Z_FULL_FLUSH في zlib)؛ ولا يوجد حديث عن أي ضغط فعال بعد ذلك.

وآخر ما تم اختباره هو zstd. اعتمادًا على المعلمات، يتم ضغطه إما على مستوى gzip، ولكن بشكل أسرع بكثير، أو أفضل من gzip.

للأسف، مع FLUSH لم يكن أداءه جيدًا: كان حجم البيانات المضغوطة حوالي 700 كيلو بايت.

Я طرح سؤالا في صفحة جيثب الخاصة بالمشروع، تلقيت إجابة مفادها أنه يجب الاعتماد على ما يصل إلى 10 بايت من بيانات الخدمة لكل كتلة من البيانات المضغوطة، وهي قريبة من النتائج التي تم الحصول عليها، ولا توجد طريقة للحاق بالانكماش.

قررت أن أتوقف عند هذه النقطة في تجاربي مع المحفوظات (دعني أذكرك أن xz، lzip، lzo، lz4 لم تظهر نفسها حتى في مرحلة الاختبار بدون FLUSH، ولم أفكر في خوارزميات ضغط أكثر غرابة).

دعنا نعود إلى مشاكل الأرشفة.

المشكلة الثانية (كما يقولون بالترتيب وليس بالقيمة) هي أن البيانات المضغوطة عبارة عن دفق واحد، حيث توجد باستمرار إشارات إلى الأقسام السابقة. وبالتالي، في حالة تلف جزء من البيانات المضغوطة، فإننا لا نفقد الكتلة المرتبطة من البيانات غير المضغوطة فحسب، بل نفقد أيضًا جميع البيانات اللاحقة.

هناك طريقة لحل هذه المشكلة:

1. منع حدوث المشكلة - أضف تكرارًا إلى البيانات المضغوطة، مما سيسمح لك بتحديد الأخطاء وتصحيحها؛ سنتحدث عن هذا لاحقا؛
2. تقليل العواقب في حالة حدوث مشكلة
   لقد قلنا سابقًا أنه يمكنك ضغط كل كتلة بيانات بشكل مستقل، وسوف تختفي المشكلة من تلقاء نفسها (سيؤدي تلف بيانات كتلة واحدة إلى فقدان البيانات الخاصة بهذه الكتلة فقط). ومع ذلك، فهذه حالة متطرفة حيث لن يكون ضغط البيانات فعالاً. والعكس المعاكس: استخدم كل 4 ميجابايت من شريحتنا كأرشيف واحد، مما سيعطينا ضغطًا ممتازًا، ولكن عواقب كارثية في حالة تلف البيانات.
   نعم، هناك حاجة إلى حل وسط من حيث الموثوقية. ولكن يجب أن نتذكر أننا نعمل على تطوير تنسيق تخزين البيانات للذاكرة غير المتطايرة مع معدل خطأ في البت (BER) منخفض للغاية وفترة تخزين بيانات معلنة مدتها 20 عامًا.

خلال التجارب، اكتشفت أن الخسائر الملحوظة إلى حد ما في مستوى الضغط تبدأ عند كتل البيانات المضغوطة التي يقل حجمها عن 10 كيلو بايت.
لقد ذكرنا سابقًا أن الذاكرة المستخدمة مقسمة إلى صفحات، ولا أرى أي سبب يمنع استخدام مراسلات "صفحة واحدة - كتلة واحدة من البيانات المضغوطة".

أي أن الحد الأدنى لحجم الصفحة المعقول هو 16 كيلو بايت (مع حجز معلومات الخدمة). ومع ذلك، فإن حجم الصفحة الصغير هذا يفرض قيودًا كبيرة على الحد الأقصى لحجم السجل.

على الرغم من أنني لا أتوقع حتى الآن تسجيلات أكبر من بضعة كيلو بايت في شكل مضغوط، فقد قررت استخدام صفحات بحجم 32 كيلو بايت (بإجمالي 128 صفحة لكل شريحة).

ملخص:

• نقوم بتخزين البيانات المضغوطة باستخدام zlib (deflate)؛
• لكل إدخال قمنا بتعيين Z_SYNC_FLUSH؛
• لكل سجل مضغوط، نقوم بقص البايتات الزائدة (على سبيل المثال 0x00، 0x00، 0xff، 0xff); نشير في الرأس إلى عدد البايتات التي قطعناها؛
• نقوم بتخزين البيانات في صفحات بحجم 32 كيلو بايت؛ يوجد دفق واحد من البيانات المضغوطة داخل الصفحة؛ في كل صفحة نبدأ الضغط مرة أخرى.

وقبل الانتهاء من عملية الضغط، أود أن ألفت انتباهك إلى حقيقة أنه لدينا فقط عدد قليل من البايتات من البيانات المضغوطة لكل سجل، لذلك من المهم للغاية عدم تضخيم معلومات الخدمة، فكل بايت له أهميته هنا.

تخزين رؤوس البيانات

نظرًا لأن لدينا سجلات ذات أطوال متغيرة، فنحن بحاجة إلى تحديد موضع/حدود السجلات بطريقة أو بأخرى.

أعرف ثلاث طرق:

1. يتم تخزين كافة السجلات في دفق مستمر، أولاً يوجد رأس سجل يحتوي على الطول، ثم السجل نفسه.
   في هذا النموذج، يمكن أن تكون كل من الرؤوس والبيانات ذات طول متغير.
   في الأساس، نحصل على قائمة مرتبطة منفردة يتم استخدامها طوال الوقت؛
2. يتم تخزين الرؤوس والسجلات نفسها في تدفقات منفصلة.
   باستخدام رؤوس ذات طول ثابت، نضمن أن الضرر الذي يلحق بإحدى الرؤوس لا يؤثر على الرؤوس الأخرى.
   يتم استخدام نهج مماثل، على سبيل المثال، في العديد من أنظمة الملفات؛
3. يتم تخزين السجلات في دفق مستمر، ويتم تحديد حدود السجل بواسطة علامة معينة (حرف/تسلسل أحرف محظور داخل كتل البيانات). إذا كان هناك علامة داخل السجل، فإننا نستبدلها ببعض التسلسل (الخروج منها).
   يتم استخدام نهج مماثل، على سبيل المثال، في بروتوكول PPP.

سوف أوضح.

الخيار 1:

كل شيء بسيط للغاية هنا: معرفة طول السجل، يمكننا حساب عنوان الرأس التالي. لذلك ننتقل عبر العناوين حتى نواجه منطقة مليئة بـ 0xff (منطقة خالية) أو نهاية الصفحة.

الخيار 2:

نظرًا لطول السجل المتغير، لا يمكننا أن نقول مسبقًا عدد السجلات (وبالتالي الرؤوس) التي سنحتاجها لكل صفحة. يمكنك نشر الرؤوس والبيانات نفسها عبر صفحات مختلفة، لكنني أفضّل أسلوبًا مختلفًا: فنحن نضع كلاً من الرؤوس والبيانات في صفحة واحدة، لكن الرؤوس (ذات الحجم الثابت) تأتي من بداية الصفحة، والصفحة البيانات (ذات الطول المتغير) تأتي من النهاية. بمجرد أن "يجتمعوا" (لا توجد مساحة خالية كافية لإدخال جديد)، فإننا نعتبر هذه الصفحة مكتملة.

الخيار 3:

ليست هناك حاجة لتخزين الطول أو معلومات أخرى حول موقع البيانات في الرأس، فالعلامات التي تشير إلى حدود السجلات كافية. ومع ذلك، يجب معالجة البيانات عند الكتابة/القراءة.
سأستخدم 0xff كعلامة (تملأ الصفحة بعد المسح)، لذلك لن يتم التعامل مع المنطقة الحرة كبيانات بالتأكيد.

جدول المقارنة:

الخيار 1
الخيار 2
الخيار 3

التسامح مع الخطأ
-
+
+

كثافة
+
-
+

تعقيد التنفيذ
*
**
**

الخيار 1 به عيب فادح: في حالة تلف أي من الرؤوس، يتم تدمير السلسلة اللاحقة بأكملها. تتيح لك الخيارات المتبقية استعادة بعض البيانات حتى في حالة حدوث أضرار جسيمة.
ولكن هنا من المناسب أن نتذكر أننا قررنا تخزين البيانات في شكل مضغوط، وهكذا نفقد جميع البيانات الموجودة في الصفحة بعد سجل "مكسور"، لذلك على الرغم من وجود ناقص في الجدول، إلا أننا لا أخذه بعين الاعتبار.

الاكتناز:

• في الخيار الأول، نحتاج إلى تخزين الطول في الرأس فقط، وإذا استخدمنا أعدادًا صحيحة متغيرة الطول، فيمكننا في معظم الحالات التعامل مع بايت واحد؛
• في الخيار الثاني نحتاج إلى تخزين عنوان البداية والطول؛ يجب أن يكون حجم السجل ثابتًا، وأقدر 4 بايت لكل سجل (بايتان للإزاحة، وXNUMX بايت للطول)؛
• الخيار الثالث يحتاج إلى حرف واحد فقط للإشارة إلى بداية التسجيل، بالإضافة إلى أن التسجيل نفسه سيزيد بنسبة 1-2% بسبب التدريع. بشكل عام، ما يقرب من التكافؤ مع الخيار الأول.

في البداية، اعتبرت الخيار الثاني هو الخيار الرئيسي (وحتى كتبت التنفيذ). لقد تخليت عنه فقط عندما قررت أخيرًا استخدام الضغط.

ربما يومًا ما سأستمر في استخدام خيار مماثل. على سبيل المثال، إذا كان علي التعامل مع تخزين البيانات لسفينة تسافر بين الأرض والمريخ، فستكون هناك متطلبات مختلفة تمامًا من حيث الموثوقية والإشعاع الكوني ...

أما الخيار الثالث: فقد أعطيته نجمتين لصعوبة التنفيذ لمجرد أنني لا أحب العبث بالتدريع وتغيير الطول أثناء العملية وما إلى ذلك. نعم، ربما أكون متحيزًا، لكن سيتعين علي كتابة الكود - لماذا تجبر نفسك على فعل شيء لا يعجبك.

ملخص: نختار خيار التخزين على شكل سلاسل “رأسية بطول – بيانات متغيرة الطول” بسبب الكفاءة وسهولة التنفيذ.

استخدام حقول البت لمراقبة نجاح عمليات الكتابة

لا أتذكر الآن من أين جاءتني الفكرة، لكنها تبدو كما يلي:
لكل إدخال، نخصص عدة بتات لتخزين الأعلام.
كما قلنا سابقًا، بعد المسح، تمتلئ جميع البتات بالرقم 1، ويمكننا تغيير 1 إلى 0، ولكن ليس العكس. لذلك بالنسبة إلى "لم يتم تعيين العلم" نستخدم 1، وبالنسبة إلى "تم تعيين العلم" نستخدم 0.

إليك ما قد يبدو عليه وضع سجل متغير الطول في الفلاش:

1. اضبط العلامة "بدأ تسجيل المدة"؛
2. سجل الطول
3. اضبط علامة "بدء تسجيل البيانات"؛
4. نحن نسجل البيانات.
5. اضبط علامة "انتهى التسجيل".

بالإضافة إلى ذلك، سيكون لدينا إشارة "حدث خطأ"، بإجمالي 4 إشارات بت.

في هذه الحالة، لدينا حالتان مستقرتان "1111" - لم يبدأ التسجيل و"1000" - كان التسجيل ناجحًا؛ في حالة حدوث انقطاع غير متوقع لعملية التسجيل، سنتلقى حالات وسيطة، والتي يمكننا بعد ذلك اكتشافها ومعالجتها.

هذا النهج مثير للاهتمام، لكنه يحمي فقط من انقطاع التيار الكهربائي المفاجئ والإخفاقات المماثلة، وهو أمر مهم بالطبع، ولكن هذا ليس السبب الوحيد (أو حتى الرئيسي) للفشل المحتمل.

ملخص: دعنا ننتقل للبحث عن حل جيد.

المجاميع الاختبارية

تتيح المجاميع الاختبارية أيضًا التأكد (باحتمال معقول) من أننا نقرأ بالضبط ما كان ينبغي كتابته. وعلى عكس حقول البت التي تمت مناقشتها أعلاه، فإنها تعمل دائمًا.

إذا أخذنا بعين الاعتبار قائمة المصادر المحتملة للمشاكل التي ناقشناها أعلاه، فسيكون المجموع الاختباري قادرًا على التعرف على الخطأ بغض النظر عن مصدره (ربما باستثناء الكائنات الفضائية الخبيثة - حيث يمكنهم تزوير المجموع الاختباري أيضًا).

لذا، إذا كان هدفنا هو التحقق من سلامة البيانات، فإن المجاميع الاختبارية تعد فكرة رائعة.

لم يثير اختيار الخوارزمية لحساب المجموع الاختباري أي أسئلة - اتفاقية حقوق الطفل. من ناحية، تتيح الخصائص الرياضية اكتشاف أنواع معينة من الأخطاء بنسبة 100%؛ ومن ناحية أخرى، في البيانات العشوائية، تُظهر هذه الخوارزمية عادةً احتمالية الاصطدامات التي لا تزيد كثيرًا عن الحد النظري . قد لا تكون أسرع خوارزمية، كما أنها ليست دائمًا الحد الأدنى من حيث عدد التصادمات، ولكنها تتمتع بميزة مهمة جدًا: في الاختبارات التي واجهتها، لم تكن هناك أنماط فشلت فيها بشكل واضح. الاستقرار هو الجودة الرئيسية في هذه الحالة.

مثال على الدراسة الحجمية: جزء 1, جزء 2 (روابط إلى narod.ru، آسف).

ومع ذلك، فإن مهمة اختيار المجموع الاختباري لم تكتمل؛ إذ إن CRC عبارة عن عائلة كاملة من المجاميع الاختبارية. عليك أن تقرر الطول، ثم تختار متعدد الحدود.

إن اختيار طول المجموع الاختباري ليس سؤالاً بسيطًا كما يبدو للوهلة الأولى.

اسمحوا لي أن أوضح:
دعونا نحصل على احتمال وجود خطأ في كل بايت والمجموع الاختباري المثالي، لنحسب متوسط ​​عدد الأخطاء لكل مليون سجل:

البيانات، بايت
المجموع الاختباري، بايت
أخطاء غير مكتشفة
اكتشافات الأخطاء الكاذبة
إجمالي الإيجابيات الكاذبة

1
0
1000
0
1000

1
1
4
999
1003

1
2
≈0
1997
1997

1
4
≈0
3990
3990

10
0
9955
0
9955

10
1
39
990
1029

10
2
≈0
1979
1979

10
4
≈0
3954
3954

1000
0
632305
0
632305

1000
1
2470
368
2838

1000
2
10
735
745

1000
4
≈0
1469
1469

يبدو أن كل شيء بسيط - اعتمادًا على طول البيانات المحمية، اختر طول المجموع الاختباري مع الحد الأدنى من الإيجابيات غير الصحيحة - والخدعة في الحقيبة.

ومع ذلك، تنشأ مشكلة مع المجاميع الاختبارية القصيرة: على الرغم من أنها جيدة في اكتشاف أخطاء البتات الفردية، إلا أنها يمكنها، باحتمال كبير إلى حد ما، قبول البيانات العشوائية تمامًا على أنها صحيحة. كان هناك بالفعل مقال عن حبري يصف مشكلة في الحياة الحقيقية.

لذلك، لجعل مطابقة المجموع الاختباري العشوائي مستحيلة تقريبًا، تحتاج إلى استخدام المجموع الاختباري الذي يبلغ طوله 32 بت أو أطول. (للأطوال الأكبر من 64 بت، تُستخدم عادةً وظائف التجزئة المشفرة).

على الرغم من أنني كتبت سابقًا أننا بحاجة إلى توفير المساحة بكل الوسائل، إلا أننا سنستمر في استخدام المجموع الاختباري 32 بت (16 بت ليست كافية، واحتمال الاصطدام أكثر من 0.01٪؛ و24 بت، كما هي) قل لا هنا ولا هناك).

قد ينشأ هنا اعتراض: هل قمنا بحفظ كل بايت عند اختيار الضغط لنعطي الآن 4 بايت مرة واحدة؟ ألن يكون من الأفضل عدم ضغط أو إضافة المجموع الاختباري؟ بالطبع لا، لا يوجد ضغط لا يعني، أننا لا نحتاج إلى التحقق من النزاهة.

عند اختيار كثيرة الحدود، لن نقوم بإعادة اختراع العجلة، لكننا سنأخذ CRC-32C المشهور الآن.
يكتشف هذا الرمز أخطاء 6 بت في الحزم التي يصل حجمها إلى 22 بايت (ربما الحالة الأكثر شيوعًا بالنسبة لنا)، أو أخطاء 4 بت في الحزم التي يصل حجمها إلى 655 بايت (أيضًا حالة شائعة بالنسبة لنا)، أو 2 أو أي عدد فردي من أخطاء البت في الحزم بأي طول معقول.

إذا كان أي شخص مهتم بالتفاصيل

مقالة ويكيبيديا حول اتفاقية حقوق الطفل.

معلمات الكود CRC-32C في موقع كوبمان - ربما يكون المتخصص الرائد في اتفاقية حقوق الطفل على هذا الكوكب.

В مقالته غير رمز آخر مثير للاهتمام، والذي يوفر معلمات أفضل قليلاً لأطوال الحزمة ذات الصلة بنا، لكنني لم أعتبر الفرق مهمًا، وكنت مؤهلاً بما يكفي لاختيار رمز مخصص بدلاً من الرمز القياسي والمدروس جيدًا.

أيضًا، بما أن بياناتنا مضغوطة، فإن السؤال الذي يطرح نفسه هو: هل يجب علينا حساب المجموع الاختباري للبيانات المضغوطة أو غير المضغوطة؟

الحجج المؤيدة لحساب المجموع الاختباري للبيانات غير المضغوطة:

• نحتاج في النهاية إلى التحقق من سلامة تخزين البيانات - لذلك نتحقق منها مباشرة (في نفس الوقت، سيتم التحقق من الأخطاء المحتملة في تنفيذ الضغط/إلغاء الضغط، والأضرار الناجمة عن الذاكرة المكسورة، وما إلى ذلك)؛
• تتمتع خوارزمية الانكماش في zlib بتطبيق ناضج إلى حد ما و لا ينبغي تقع مع بيانات الإدخال "الملتوية"؛ علاوة على ذلك، غالبًا ما تكون قادرة على اكتشاف الأخطاء بشكل مستقل في تدفق الإدخال، مما يقلل من الاحتمال الإجمالي لعدم اكتشاف الخطأ (أجري اختبار بعكس بت واحد في سجل قصير، اكتشف zlib خطأ في حوالي ثلث الحالات).

الحجج ضد حساب المجموع الاختباري للبيانات غير المضغوطة:

• تم تصميم CRC خصيصًا لأخطاء البت القليلة التي تتميز بها ذاكرة الفلاش (يمكن أن يتسبب خطأ بسيط في تيار مضغوط في حدوث تغيير هائل في تدفق الإخراج، حيث يمكننا، من الناحية النظرية البحتة، "التصادم")؛
• لا أحب حقًا فكرة تمرير البيانات التي يحتمل أن تكون معطلة إلى برنامج إلغاء الضغط، من تعرفكيف سيكون رد فعله.

في هذا المشروع، قررت الابتعاد عن الممارسة المقبولة عمومًا المتمثلة في تخزين المجموع الاختباري للبيانات غير المضغوطة.

ملخص: نستخدم CRC-32C، ونحسب المجموع الاختباري من البيانات بالشكل الذي تمت كتابته به للفلاش (بعد الضغط).

وفرة

إن استخدام الترميز الزائد لا يؤدي بالطبع إلى القضاء على فقدان البيانات، ومع ذلك، فإنه يمكن أن يقلل بشكل كبير (في كثير من الأحيان بعدة مراتب من حيث الحجم) من احتمالية فقدان البيانات غير القابلة للاسترداد.

يمكننا استخدام أنواع مختلفة من التكرار لتصحيح الأخطاء.
يمكن أن تصحح رموز Hamming أخطاء البتات الفردية، أو رموز أحرف Reed-Solomon، أو النسخ المتعددة من البيانات المدمجة مع المجاميع الاختبارية، أو الترميزات مثل RAID-6 التي يمكن أن تساعد في استرداد البيانات حتى في حالة حدوث تلف كبير.
في البداية، كنت ملتزمًا بالاستخدام الواسع النطاق للتشفير المقاوم للأخطاء، ولكن بعد ذلك أدركت أننا بحاجة أولاً إلى أن تكون لدينا فكرة عن الأخطاء التي نريد حماية أنفسنا منها، ثم نختار البرمجة.

قلنا سابقًا أنه يجب اكتشاف الأخطاء في أسرع وقت ممكن. في أي نقطة يمكن أن نواجه الأخطاء؟

1. التسجيل غير مكتمل (لسبب ما، تم إيقاف تشغيل الطاقة أثناء التسجيل، وتجمد جهاز Raspberry، ...)
   للأسف، في حالة حدوث مثل هذا الخطأ، يبقى فقط تجاهل السجلات غير الصالحة واعتبار البيانات مفقودة؛
2. أخطاء الكتابة (لسبب ما، ما تم كتابته على ذاكرة الفلاش لم يكن هو ما تم كتابته)
   يمكننا اكتشاف مثل هذه الأخطاء على الفور إذا أجرينا اختبار القراءة مباشرة بعد التسجيل؛
3. تشويه البيانات في الذاكرة أثناء التخزين؛
4. أخطاء القراءة
   لتصحيح ذلك، إذا كان المجموع الاختباري غير متطابق، يكفي تكرار القراءة عدة مرات.

أي أن الأخطاء من النوع الثالث فقط (التلف التلقائي للبيانات أثناء التخزين) لا يمكن تصحيحها بدون تشفير مقاوم للأخطاء. يبدو أن مثل هذه الأخطاء لا تزال مستبعدة للغاية.

ملخص: تقرر التخلي عن الترميز الزائد، ولكن إذا أظهرت العملية خطأ في هذا القرار، فارجع إلى النظر في المشكلة (مع الإحصائيات المتراكمة بالفعل حول حالات الفشل، والتي ستسمح باختيار النوع الأمثل من الترميز).

آخر

وبطبيعة الحال، شكل المقال لا يسمح لنا بتبرير كل جزء في الشكل (وقد نفدت قوتي بالفعل)لذا سأتناول بإيجاز بعض النقاط التي لم أتطرق إليها سابقًا.

• تقرر جعل جميع الصفحات "متساوية"
  أي أنه لن يكون هناك صفحات خاصة تحتوي على بيانات وصفية أو سلاسل رسائل منفصلة وما إلى ذلك، بل سيكون هناك بدلاً من ذلك مؤشر ترابط واحد يعيد كتابة جميع الصفحات تباعًا.
  وهذا يضمن تآكلًا متساويًا للصفحات، دون أي نقطة فشل، وأنا أحب ذلك تمامًا؛
• من الضروري توفير إصدار التنسيق.
  التنسيق الذي لا يحتوي على رقم إصدار في الرأس هو أمر شرير!
  يكفي إضافة حقل برقم سحري معين (توقيع) إلى رأس الصفحة، والذي سيشير إلى إصدار التنسيق المستخدم (لا أعتقد أنه في الممارسة العملية سيكون هناك حتى عشرات منهم);
• استخدم رأسًا متغير الطول للسجلات (التي يوجد منها الكثير)، محاولًا جعل طوله بايتًا واحدًا في معظم الحالات؛
• لترميز طول الرأس وطول الجزء المقصوص من السجل المضغوط، استخدم رموز ثنائية متغيرة الطول.

ساعد كثيرا مولد على الانترنت رموز هوفمان. في بضع دقائق فقط تمكنا من تحديد رموز الطول المتغيرة المطلوبة.

وصف تنسيق تخزين البيانات

ترتيب البايت

يتم تخزين الحقول الأكبر من بايت واحد بتنسيق big-endian (ترتيب بايت الشبكة)، أي أنه يتم كتابة 0x1234 كـ 0x12، 0x34.

ترقيم الصفحات

يتم تقسيم كل ذاكرة الفلاش إلى صفحات متساوية الحجم.

حجم الصفحة الافتراضي هو 32 كيلو بايت، ولكن ليس أكثر من 1/4 من الحجم الإجمالي لشريحة الذاكرة (لشريحة 4 ميجابايت، يتم الحصول على 128 صفحة).

تقوم كل صفحة بتخزين البيانات بشكل مستقل عن الصفحات الأخرى (أي أن البيانات الموجودة في إحدى الصفحات لا تشير إلى البيانات الموجودة في صفحة أخرى).

يتم ترقيم جميع الصفحات بالترتيب الطبيعي (بترتيب تصاعدي للعناوين)، بدءًا من الرقم 0 (تبدأ الصفحة صفر من العنوان 0، وتبدأ الصفحة الأولى عند 32 كيلو بايت، وتبدأ الصفحة الثانية عند 64 كيلو بايت، وما إلى ذلك)

تُستخدم شريحة الذاكرة كمخزن مؤقت دوري (مخزن مؤقت حلقي)، أي أن الكتابة أولاً تنتقل إلى الصفحة رقم 0، ثم الرقم 1، ...، وعندما نملأ الصفحة الأخيرة تبدأ دورة جديدة ويستمر التسجيل من الصفحة صفر .

داخل الصفحة

في بداية الصفحة، يتم تخزين رأس صفحة بحجم 4 بايت، ثم المجموع الاختباري للرأس (CRC-32C)، ثم يتم تخزين السجلات بتنسيق "الرأس، البيانات، المجموع الاختباري".

يتكون عنوان الصفحة (الأخضر القذر في الرسم التخطيطي) من:

• حقل الرقم السحري ثنائي البايت (أيضًا علامة على إصدار التنسيق)
  بالنسبة للإصدار الحالي من التنسيق، يتم حسابه كـ 0xed00 ⊕ номер страницы;
• عداد ثنائي البايت "إصدار الصفحة" (رقم دورة إعادة كتابة الذاكرة).

يتم تخزين الإدخالات الموجودة على الصفحة في شكل مضغوط (يتم استخدام خوارزمية الانكماش). يتم ضغط كافة السجلات الموجودة على صفحة واحدة في موضوع واحد (يتم استخدام قاموس مشترك)، وفي كل صفحة جديدة يبدأ الضغط من جديد. أي أنه لفك ضغط أي سجل، يلزم وجود جميع السجلات السابقة من هذه الصفحة (وهذه الصفحة فقط).

سيتم ضغط كل سجل باستخدام علامة Z_SYNC_FLUSH، وفي نهاية الدفق المضغوط سيكون هناك 4 بايت 0x00، 0x00، 0xff، 0xff، ربما يسبقها بايت واحد أو اثنين من البايتات الصفرية.
نتجاهل هذا التسلسل (بطول 4 أو 5 أو 6 بايت) عند الكتابة على ذاكرة فلاش.

رأس السجل هو 1 أو 2 أو 3 بايت لتخزين:

• بت واحد (T) يشير إلى نوع السجل: 0 - السياق، 1 - السجل؛
• حقل متغير الطول (S) من 1 إلى 7 بتات، يحدد طول الرأس و"الذيل" الذي يجب إضافته إلى السجل لإزالة الضغط؛
• طول السجل (L).

جدول القيمة S:

S
طول الرأس، بايت
تم التخلص منها عند الكتابة، بايت

0
1
5 (00 00 00 ff ff)

10
1
6 (00 00 00 00 ff ff)

110
2
4 (00 00 ff ff)

1110
2
5 (00 00 00 ff ff)

11110
2
6 (00 00 00 00 ff ff)

1111100
3
4 (00 00 ff ff)

1111101
3
5 (00 00 00 ff ff)

1111110
3
6 (00 00 00 00 ff ff)

حاولت أن أوضح، لا أعرف مدى وضوح الأمر:

يشير اللون الأصفر هنا إلى الحقل T، والأبيض إلى الحقل S، والأخضر L (طول البيانات المضغوطة بالبايت)، والأزرق البيانات المضغوطة، والأحمر البايتات النهائية للبيانات المضغوطة التي لم تتم كتابتها على ذاكرة فلاش.

وبالتالي، يمكننا كتابة رؤوس التسجيل ذات الطول الأكثر شيوعًا (حتى 63+5 بايت في شكل مضغوط) في بايت واحد.

بعد كل سجل، يتم تخزين المجموع الاختباري CRC-32C، حيث يتم استخدام القيمة المعكوسة للمجموع الاختباري السابق كقيمة أولية (init).

تتمتع CRC بخاصية "المدة"، وتعمل الصيغة التالية (معكوس البت الزائد أو الناقص في العملية): .
وهذا يعني أننا في الواقع نحسب CRC لجميع البايتات السابقة من الرؤوس والبيانات الموجودة في هذه الصفحة.

مباشرة بعد المجموع الاختباري هو رأس السجل التالي.

تم تصميم الرأس بحيث يختلف البايت الأول دائمًا عن 0x00 و0xff (إذا واجهنا 0xff بدلاً من البايت الأول من الرأس، فهذا يعني أن هذه منطقة غير مستخدمة؛ ويشير 0x00 إلى وجود خطأ).

خوارزميات المثال

القراءة من ذاكرة الفلاش

أي قراءة تأتي مع فحص المجموع الاختباري.
إذا لم يتطابق المجموع الاختباري، يتم تكرار القراءة عدة مرات على أمل قراءة البيانات الصحيحة.

(هذا منطقي، Linux لا يقوم بتخزين القراءة مؤقتًا من NOR Flash، تم اختباره)

الكتابة على ذاكرة فلاش

نحن نسجل البيانات.
دعونا نقرأهم.

إذا كانت بيانات القراءة لا تتطابق مع البيانات المكتوبة، فإننا نملأ المنطقة بالأصفار ونشير إلى وجود خطأ.

تحضير دائرة كهربائية دقيقة جديدة للتشغيل

للتهيئة، يتم كتابة رأس الإصدار 1 في الصفحة الأولى (أو بالأحرى الصفر).
بعد ذلك، يتم كتابة السياق الأولي لهذه الصفحة (يحتوي على UUID الخاص بالجهاز والإعدادات الافتراضية).

هذا كل شيء، ذاكرة الفلاش جاهزة للاستخدام.

تحميل الآلة

عند التحميل، تتم قراءة أول 8 بايت من كل صفحة (رأس + CRC)، ويتم تجاهل الصفحات التي تحتوي على رقم سحري غير معروف أو CRC غير صحيح.
من الصفحات "الصحيحة"، يتم اختيار الصفحات ذات الإصدار الأقصى، وتؤخذ منها الصفحة ذات العدد الأعلى.
تتم قراءة السجل الأول والتحقق من صحة اتفاقية حقوق الطفل ووجود علامة "السياق". إذا كان كل شيء على ما يرام، تعتبر هذه الصفحة الحالية. إذا لم يكن الأمر كذلك، فإننا نعود إلى الصفحة السابقة حتى نجد صفحة "مباشرة".
وفي الصفحة التي تم العثور عليها، نقرأ جميع السجلات، تلك التي نستخدمها مع علامة "السياق".
احفظ قاموس zlib (سيكون ضروريًا للإضافة إلى هذه الصفحة).

هذا كل شيء، اكتمل التنزيل، وتمت استعادة السياق، ويمكنك العمل.

إضافة إدخال دفتر اليومية

نقوم بضغط السجل بالقاموس الصحيح، مع تحديد Z_SYNC_FLUSH، ونرى ما إذا كان السجل المضغوط مناسبًا للصفحة الحالية.
إذا لم يكن مناسبًا (أو كانت هناك أخطاء CRC في الصفحة)، فابدأ صفحة جديدة (انظر أدناه).
نكتب المحضر واتفاقية حقوق الطفل. في حالة حدوث خطأ، ابدأ صفحة جديدة.

صفحة جديدة

نختار صفحة مجانية بأقل عدد (نعتبر الصفحة المجانية صفحة ذات مجموع اختباري غير صحيح في الرأس أو بإصدار أقل من الإصدار الحالي). إذا لم تكن هناك مثل هذه الصفحات، فحدد الصفحة ذات العدد الأدنى من الصفحات التي لها إصدار مساوٍ للصفحة الحالية.
نقوم بمسح الصفحة المحددة. نتحقق من المحتويات باستخدام 0xff. إذا كان هناك خطأ ما، فانتقل إلى الصفحة المجانية التالية، وما إلى ذلك.
نكتب رأسًا على الصفحة المحذوفة، والإدخال الأول هو الحالة الحالية للسياق، والإدخال التالي هو إدخال السجل غير المكتوب (إذا كان هناك واحد).

قابلية تطبيق الشكل

في رأيي، اتضح أنه تنسيق جيد لتخزين أي تدفقات معلومات قابلة للضغط أكثر أو أقل (نص عادي، JSON، MessengerPack، CBOR، ربما protobuf) في NOR Flash.

وبطبيعة الحال، فإن التنسيق "مصمم" لـ SLC NOR Flash.

لا ينبغي استخدامه مع وسائط BER عالية مثل NAND أو MLC NOR (هل هذه الذاكرة متاحة للبيع؟ لقد رأيتها مذكورة فقط في الأعمال المتعلقة برموز التصحيح).

علاوة على ذلك، لا ينبغي استخدامه مع الأجهزة التي تحتوي على FTL الخاصة بها: فلاش USB، وSD، وMicroSD، وما إلى ذلك (لمثل هذه الذاكرة، قمت بإنشاء تنسيق بحجم صفحة يبلغ 512 بايت، وتوقيع في بداية كل صفحة وأرقام تسجيل فريدة - في بعض الأحيان كان من الممكن استعادة جميع البيانات من محرك أقراص فلاش "معطل" عن طريق قراءة تسلسلية بسيطة).

اعتمادًا على المهام، يمكن استخدام التنسيق دون إجراء تغييرات على محركات الأقراص المحمولة من 128 كيلوبت (16 كيلو بايت) إلى 1 جيجابت (128 ميجابايت). إذا رغبت في ذلك، يمكنك استخدامه على شرائح أكبر، ولكن ربما تحتاج إلى ضبط حجم الصفحة (ولكن هنا تطرح مسألة الجدوى الاقتصادية بالفعل؛ فسعر الكميات الكبيرة من NOR Flash ليس مشجعًا).

إذا وجد شخص ما التنسيق مثيرًا للاهتمام ويريد استخدامه في مشروع مفتوح، فاكتب، سأحاول إيجاد الوقت وصقل الكود ونشره على جيثب.

اختتام

كما ترون، في النهاية تبين أن التنسيق بسيط وحتى مملة.

من الصعب أن أعكس تطور وجهة نظري في مقال، لكن صدقني: في البداية أردت إنشاء شيء متطور وغير قابل للتدمير وقادر على النجاة حتى من انفجار نووي على مسافة قريبة. لكن العقل (آمل) ما زال منتصراً، وتحولت الأولويات تدريجياً نحو البساطة والاكتناز.

هل يمكن أن أكون مخطئا؟ نعم بالتأكيد. قد يتبين، على سبيل المثال، أننا اشترينا مجموعة من الدوائر الدقيقة منخفضة الجودة. أو لسبب آخر، لن تلبي المعدات توقعات الموثوقية.

هل لدي خطة لهذا؟ أعتقد أنه بعد قراءة المقال ليس لديك شك في أن هناك خطة. وليس حتى وحده.

وعلى صعيد أكثر جدية، تم تطوير التنسيق باعتباره خيارًا عمليًا و"بالونًا تجريبيًا".

في الوقت الحالي، كل شيء على الطاولة يعمل بشكل جيد، وفي اليوم التالي سيتم نشر الحل حرفيًا (تقريبًا) على مئات الأجهزة، دعونا نرى ما يحدث في العملية "القتال" (لحسن الحظ، آمل أن يسمح لك التنسيق باكتشاف حالات الفشل بشكل موثوق؛ حتى تتمكن من جمع إحصائيات كاملة). في غضون بضعة أشهر سيكون من الممكن استخلاص النتائج (وإذا كنت سيئ الحظ، حتى قبل ذلك).

إذا تم اكتشاف مشاكل خطيرة بناءً على نتائج الاستخدام وكانت هناك حاجة إلى تحسينات، فسأكتب عنها بالتأكيد.

أدب

لم أكن أرغب في إعداد قائمة طويلة مملة من الأعمال المستخدمة؛ ففي نهاية المطاف، كل شخص لديه جوجل.

قررت هنا أن أترك قائمة بالنتائج التي بدت مثيرة للاهتمام بشكل خاص بالنسبة لي، لكنها انتقلت تدريجيًا مباشرة إلى نص المقالة، وبقي عنصر واحد في القائمة:

1. فائدة infgen من المؤلف زليب. يمكن عرض محتويات أرشيفات deflate/zlib/gzip بوضوح. إذا كان عليك التعامل مع البنية الداخلية للتنسيق المفرغ (أو gzip)، فإنني أوصي به بشدة.

المصدر: www.habr.com