ماقبل تاریخ

ماشین‌های فروش خودکار با طراحی خودمان وجود دارد. داخل رزبری پای و مقداری سیم کشی روی یک برد جداگانه. یک پذیرنده سکه، یک پذیرنده قبض، یک پایانه بانک وصل است... همه چیز توسط یک برنامه خودنویس کنترل می شود. کل تاریخچه کاری در یک گزارش روی یک درایو فلش (MicroSD) نوشته می شود، که سپس از طریق اینترنت (با استفاده از مودم USB) به سرور منتقل می شود و در یک پایگاه داده ذخیره می شود. اطلاعات فروش در 1c بارگذاری می شود، همچنین یک رابط وب ساده برای نظارت و غیره وجود دارد.

این است که مجله حیاتی است - برای حسابداری (درآمد، فروش و غیره)، نظارت (انواع خرابی ها و سایر شرایط فورس ماژور). شاید بتوان گفت این تمام اطلاعاتی است که ما در مورد این دستگاه داریم.

مشکل

درایوهای فلش خود را دستگاه های بسیار غیر قابل اعتماد نشان می دهند. آنها با نظم رشک برانگیز شکست می خورند. این امر منجر به از کار افتادن دستگاه و (اگر به دلایلی نمی توان گزارش را به صورت آنلاین منتقل کرد) منجر به از دست رفتن داده ها می شود.

این اولین تجربه استفاده از درایوهای فلش نیست، قبل از این پروژه دیگری با بیش از صد دستگاه وجود داشت که در آن مجله در درایوهای فلش USB ذخیره می شد، همچنین مشکلاتی در قابلیت اطمینان وجود داشت، در مواقعی تعداد مواردی که در آن شکست خورده بودند. یک ماه در ده ها بود. ما درایوهای فلش مختلف، از جمله فلش های مارک دار با حافظه SLC را امتحان کردیم، و برخی از مدل ها از بقیه قابل اعتمادتر هستند، اما تعویض درایوهای فلش به طور اساسی مشکل را حل نکرد.

اخطار! طولانی مدت! اگر به «چرا» علاقه ای ندارید، بلکه فقط به «چگونه» علاقه دارید، می توانید مستقیماً پیش بروید در پایان مقالات

تصمیم

اولین چیزی که به ذهن می رسد این است: MicroSD را رها کنید، برای مثال یک SSD را نصب کنید و از آن بوت کنید. از نظر تئوری ممکن است، احتمالا، اما نسبتاً گران، و نه چندان قابل اعتماد (یک آداپتور USB-SATA اضافه شده است؛ آمار خرابی SSD های ارزان قیمت نیز دلگرم کننده نیست).

USB HDD نیز راه حل جذابی به نظر نمی رسد.

بنابراین، به این گزینه رسیدیم: بوت شدن از MicroSD را ترک کنید، اما از آنها در حالت فقط خواندنی استفاده کنید، و گزارش عملیات (و سایر اطلاعات منحصر به فرد برای یک قطعه خاص از سخت افزار - شماره سریال، کالیبراسیون سنسور، و غیره) را در جای دیگری ذخیره کنید. .

موضوع FS فقط خواندنی برای تمشک قبلاً در داخل و خارج مورد مطالعه قرار گرفته است ، من در این مقاله به جزئیات پیاده سازی نمی پردازم. (اما اگر علاقه ای وجود داشته باشد، شاید یک مینی مقاله در مورد این موضوع بنویسم). تنها نکته ای که می خواهم به آن توجه کنم این است که هم از تجربه شخصی و هم از بررسی کسانی که قبلاً آن را اجرا کرده اند، قابلیت اطمینان حاصل می شود. بله، خلاص شدن از شر خرابی ها غیرممکن است، اما کاهش قابل توجه فرکانس آنها کاملاً ممکن است. و کارت ها در حال یکپارچه شدن هستند، که جایگزینی را برای پرسنل خدمات بسیار آسان تر می کند.

سخت افزار

هیچ شک خاصی در مورد انتخاب نوع حافظه وجود نداشت - NOR Flash.
استدلال:

• اتصال ساده (اغلب اتوبوس SPI، که قبلاً تجربه استفاده از آن را دارید، بنابراین هیچ مشکل سخت افزاری پیش بینی نمی شود).
• قیمت مضحک؛
• پروتکل عملیاتی استاندارد (پیاده سازی در حال حاضر در هسته لینوکس است، در صورت تمایل، می توانید یک شخص ثالث را که آن هم وجود دارد، بگیرید، یا حتی خودتان بنویسید، خوشبختانه همه چیز ساده است).
• قابلیت اطمینان و منبع:
  از یک دیتاشیت معمولی: داده ها به مدت 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)؛
• پاک کردن آهسته (بسته به اندازه بلوک، از کسری از ثانیه تا چند ثانیه طول می کشد).

به نظر می رسد چیز مهمی برای ما وجود ندارد، بنابراین ادامه می دهیم.

اگر جزئیات جالب باشد، میکرو مدار انتخاب شده است در 25df321a (با این حال، این مهم نیست، آنالوگ های زیادی در بازار وجود دارد که در سیستم پین اوت و فرمان سازگار هستند؛ حتی اگر بخواهیم یک ریزمدار از یک سازنده دیگر و/یا اندازه متفاوت نصب کنیم، همه چیز بدون تغییر کار خواهد کرد. کد).

من از درایور تعبیه شده در هسته لینوکس استفاده می کنم؛ در 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

من شرح اتصال تراشه به رزبری پای را حذف می کنم. از یک طرف ، من متخصص الکترونیک نیستم ، از طرف دیگر ، همه چیز اینجا حتی برای من پیش پا افتاده است: ریز مدار فقط 8 پایه دارد که ما به زمین ، قدرت ، SPI (CS, SI, SO, SCK) نیاز داریم. ) سطوح مانند Raspberry Pi هستند، هیچ سیم کشی اضافی مورد نیاز نیست - فقط 6 پین نشان داده شده را وصل کنید.

بیانیه مشکل

طبق معمول، بیانیه مشکل چندین بار تکرار می شود و به نظر من زمان مورد بعدی فرا رسیده است. پس بیایید بایستیم، آنچه قبلاً نوشته شده را جمع آوری کنیم و جزئیاتی را که در سایه باقی مانده اند روشن کنیم.

بنابراین، ما تصمیم گرفتیم که لاگ در SPI NOR Flash ذخیره شود.

NOR Flash برای کسانی که نمی دانند چیست؟

این حافظه غیر فرار است که با آن می توانید سه عملیات را انجام دهید:

1. خواندن:
   رایج ترین خواندن: ما آدرس را ارسال می کنیم و به تعداد بایت هایی که نیاز داریم می خوانیم.
2. رکورد:
   نوشتن بر روی فلش NOR مانند یک فلش معمولی به نظر می رسد، اما یک ویژگی دارد: شما فقط می توانید 1 را به 0 تغییر دهید، اما نه برعکس. به عنوان مثال، اگر در یک سلول حافظه 0x55 داشتیم، پس از نوشتن 0x0f در آن، 0x05 قبلاً در آنجا ذخیره می شود. (جدول زیر را ببینید);
3. پاک کردن:
   البته، باید بتوانیم عملیات مخالف را انجام دهیم - 0 را به 1 تغییر دهید، این دقیقاً همان چیزی است که عملیات پاک کردن برای آن است. برخلاف دو مورد اول، نه با بایت، بلکه با بلوک ها کار می کند (حداقل بلوک پاک کردن در تراشه انتخاب شده 4 کیلوبایت است). Erase کل بلوک را از بین می برد و تنها راه برای تغییر 0 به 1 است. بنابراین، هنگام کار با فلش مموری، اغلب باید ساختارهای داده را با مرز بلوک پاک کنید.
   ضبط در NOR Flash:

داده های باینری

بود
01010101

ثبت شده
00001111

تبدیل شده است
00000101

log خود نشان دهنده دنباله ای از رکوردها با طول متغیر است. طول معمول یک رکورد حدود 30 بایت است (البته گاهی اوقات رکوردهایی با طول چندین کیلوبایت اتفاق می افتد). در این مورد، ما با آنها به سادگی به عنوان مجموعه ای از بایت ها کار می کنیم، اما، اگر شما علاقه مند هستید، CBOR در داخل رکوردها استفاده می شود.

علاوه بر گزارش، ما باید برخی از اطلاعات "تنظیم" را ذخیره کنیم، چه به روز شده و چه نه: شناسه دستگاه خاص، کالیبراسیون حسگر، پرچم "دستگاه به طور موقت غیرفعال شده است" و غیره.
این اطلاعات مجموعه‌ای از رکوردهای کلید-مقدار است که در CBOR نیز ذخیره می‌شود. ما تعداد زیادی از این اطلاعات (حداکثر چند کیلوبایت) را نداریم و به ندرت به‌روزرسانی می‌شود.
در ادامه آن را زمینه می نامیم.

اگر به یاد بیاوریم که این مقاله از کجا شروع شد، بسیار مهم است که از ذخیره سازی قابل اعتماد داده ها و در صورت امکان عملکرد مداوم حتی در صورت خرابی سخت افزار/ خرابی داده ها اطمینان حاصل کنیم.

چه منابعی از مشکلات را می توان در نظر گرفت؟

• در حین عملیات نوشتن/پاک کردن خاموش شود. این از دسته "هیچ ترفندی در برابر لنگ نیست" است.
  اطلاعات از بحث ها در stackexchange: هنگامی که هنگام کار با فلش برق خاموش می شود، هم پاک کردن (تنظیم روی 1) و هم نوشتن (تنظیم روی 0) منجر به رفتار نامشخص می شود: داده ها را می توان نوشت، تا حدی نوشت (مثلاً 10 بایت/80 بیت انتقال دادیم. ، اما هنوز فقط 45 بیت را نمی توان نوشت)، همچنین ممکن است برخی از بیت ها در حالت "متوسط" باشند (خواندن می تواند هم 0 و هم 1 را تولید کند).
• خطا در خود فلش مموری.
  BER، اگرچه بسیار کم است، اما نمی تواند برابر با صفر باشد.
• خطاهای اتوبوس
  داده های منتقل شده از طریق SPI به هیچ وجه محافظت نمی شوند؛ هم خطاهای تک بیتی و هم خطاهای همگام سازی ممکن است رخ دهد - از دست دادن یا درج بیت ها (که منجر به اعوجاج گسترده داده ها می شود).
• سایر خطاها / اشکالات
  خطا در کد، اشکالات رزبری، تداخل بیگانگان...

من الزاماتی را تنظیم کرده ام که به نظر من تحقق آنها برای اطمینان از قابلیت اطمینان ضروری است:

• رکوردها باید فوراً به حافظه فلش بروند، نوشتن با تأخیر در نظر گرفته نمی شود؛ - اگر خطایی رخ دهد، باید در اسرع وقت شناسایی و پردازش شود؛ - سیستم باید در صورت امکان، خطاها را بازیابی کند.
  (نمونه ای از زندگی "چگونه نباید باشد"، که فکر می کنم همه با آن مواجه شده اند: پس از راه اندازی مجدد اضطراری، سیستم فایل "شکسته" است و سیستم عامل بوت نمی شود)

ایده ها، رویکردها، تفکرات

وقتی شروع به فکر کردن به این مشکل کردم، ایده های زیادی در سرم جرقه زد، به عنوان مثال:

• استفاده از فشرده سازی داده ها؛
• از ساختارهای داده هوشمندانه استفاده کنید، به عنوان مثال، هدر رکوردها را جدا از خود رکوردها ذخیره کنید تا اگر در هر رکوردی خطایی وجود داشت، بتوانید بقیه را بدون مشکل بخوانید.
• از فیلدهای بیت برای کنترل کامل شدن ضبط در هنگام خاموش شدن برق استفاده کنید.
• چک جمع ها را برای همه چیز ذخیره کنید.
• از نوعی کدگذاری مقاوم در برابر نویز استفاده کنید.

برخی از این ایده‌ها مورد استفاده قرار گرفت، در حالی که برخی دیگر تصمیم به کنار گذاشته شدن شدند. به ترتیب بریم

متراکم سازی داده ها

خود رویدادهایی که در مجله ثبت می کنیم کاملاً مشابه و قابل تکرار هستند ("یک سکه 5 روبلی انداخت" ، "دکمه برای دادن پول را فشار داد" ...). بنابراین، فشرده سازی باید کاملا موثر باشد.

سربار فشرده سازی ناچیز است (پردازنده ما بسیار قدرتمند است، حتی اولین Pi یک هسته با فرکانس 700 مگاهرتز داشت، مدل های فعلی چندین هسته با فرکانس بیش از یک گیگاهرتز دارند)، نرخ تبادل با ذخیره سازی پایین است (چندین مگابایت در ثانیه)، اندازه رکوردها کوچک است. به طور کلی، اگر فشرده سازی بر عملکرد تأثیر بگذارد، فقط مثبت خواهد بود. (کاملاً غیرانتقادی، فقط بیان کردم). به علاوه، ما لینوکس واقعی جاسازی شده، اما معمولی نداریم - بنابراین پیاده سازی نباید به تلاش زیادی نیاز داشته باشد (کافی است فقط کتابخانه را پیوند داده و از چندین عملکرد از آن استفاده کنید).

یک قطعه از گزارش از یک دستگاه کار گرفته شد (1.7 مگابایت، 70 هزار ورودی) و ابتدا با استفاده از gzip، lz4، lzop، bzip2، xz، zstd موجود در رایانه، از نظر فشرده‌سازی بررسی شد.

• gzip، xz، zstd نتایج مشابهی (40Kb) نشان دادند.
  من تعجب کردم که xz مد روز خود را در اینجا در سطح gzip یا zstd نشان داد.
• lzip با تنظیمات پیش فرض نتایج کمی بدتر ارائه کرد.
• lz4 و lzop نتایج نه چندان خوبی را نشان دادند (150Kb).
• bzip2 یک نتیجه شگفت آور خوب (18 کیلوبایت) را نشان داد.

بنابراین، داده ها به خوبی فشرده می شوند.
بنابراین (اگر نقص های کشنده ای پیدا نکنیم) فشرده سازی وجود خواهد داشت! صرفاً به این دلیل که داده های بیشتری می توانند روی یک فلش مموری قرار بگیرند.

بیایید به معایب آن فکر کنیم.

مشکل اول: ما قبلاً توافق کرده ایم که هر رکورد باید فوراً فلش شود. به طور معمول، بایگانی داده ها را از جریان ورودی جمع آوری می کند تا زمانی که تصمیم بگیرد که زمان نوشتن در آخر هفته است. ما باید فوراً یک بلوک فشرده از داده را دریافت کرده و آن را در حافظه غیر فرار ذخیره کنیم.

من سه راه می بینم:

1. هر رکورد را با استفاده از فشرده سازی فرهنگ لغت به جای الگوریتم های مورد بحث در بالا فشرده کنید.
   این یک گزینه کاملا کاربردی است، اما من آن را دوست ندارم. برای اطمینان از یک سطح کم و بیش مناسب از فشرده سازی، فرهنگ لغت باید برای داده های خاص «تطبیق» شود؛ هر تغییری منجر به کاهش فاجعه آمیز سطح فشرده سازی می شود. بله، مشکل را می توان با ایجاد یک نسخه جدید از فرهنگ لغت حل کرد، اما این یک سردرد است - ما باید تمام نسخه های فرهنگ لغت را ذخیره کنیم. در هر ورودی باید مشخص کنیم که با کدام نسخه از فرهنگ لغت فشرده شده است...
2. هر رکورد را با استفاده از الگوریتم‌های «کلاسیک»، اما مستقل از بقیه، فشرده کنید.
   الگوریتم های فشرده سازی مورد بررسی برای کار با رکوردهایی با این اندازه (ده ها بایت) طراحی نشده اند، نسبت فشرده سازی به وضوح کمتر از 1 خواهد بود (یعنی افزایش حجم داده ها به جای فشرده سازی).
3. بعد از هر ضبط FLUSH را انجام دهید.
   بسیاری از کتابخانه های فشرده از FLUSH پشتیبانی می کنند. این یک فرمان (یا پارامتری برای روش فشرده سازی) است که پس از دریافت آن، بایگانی کننده یک جریان فشرده را تشکیل می دهد تا بتوان از آن برای بازیابی استفاده کرد. همه داده های فشرده نشده ای که قبلاً دریافت شده است. چنین آنالوگ sync در سیستم های فایل یا commit در sql
   آنچه مهم است این است که عملیات فشرده سازی بعدی قادر به استفاده از دیکشنری انباشته خواهد بود و نسبت فشرده سازی به اندازه نسخه قبلی آسیب نخواهد دید.

من فکر می کنم واضح است که من گزینه سوم را انتخاب کردم، بیایید با جزئیات بیشتر به آن نگاه کنیم.

پیدا شد مقاله عالی درباره FLUSH در zlib.

من یک تست زانو بر اساس مقاله انجام دادم، 70 هزار ورودی از یک دستگاه واقعی، با اندازه صفحه 60 کیلوبایت گرفتم. (بعداً به اندازه صفحه باز می گردیم) اخذ شده:

داده های خام
فشرده سازی gzip -9 (بدون FLUSH)
zlib با Z_PARTIAL_FLUSH
zlib با Z_SYNC_FLUSH

حجم، کیلوبایت
1692
40
352
604

در نگاه اول، قیمت ارائه شده توسط FLUSH بیش از حد بالا است، اما در واقع ما انتخاب کمی داریم - یا اصلا فشرده سازی نکنیم، یا فشرده سازی کنیم (و بسیار موثر) با FLUSH. ما نباید فراموش کنیم که ما 70 هزار رکورد داریم، افزونگی معرفی شده توسط Z_PARTIAL_FLUSH تنها 4-5 بایت در هر رکورد است. و نسبت تراکم تقریباً 5: 1 بود که بیش از یک نتیجه عالی است.

ممکن است تعجب آور باشد، اما Z_SYNC_FLUSH در واقع روش کارآمدتری برای انجام FLUSH است.

هنگام استفاده از Z_SYNC_FLUSH، 4 بایت آخر هر ورودی همیشه 0x00، 0x00، 0xff، 0xff خواهد بود. و اگر آنها را بشناسیم، دیگر لازم نیست آنها را ذخیره کنیم، بنابراین اندازه نهایی فقط 324 کیلوبایت است.

مقاله ای که به آن لینک دادم توضیحی دارد:

یک بلوک نوع 0 جدید با محتوای خالی اضافه شده است.

یک بلوک نوع 0 با محتوای خالی شامل موارد زیر است:

• هدر بلوک سه بیتی؛
• 0 تا 7 بیت برابر با صفر، برای دستیابی به تراز بایت.
• دنباله چهار بایتی 00 00 FF FF.

همانطور که به راحتی می بینید، در آخرین بلوک قبل از این 4 بایت از 3 تا 10 بیت صفر وجود دارد. با این حال، تمرین نشان داده است که در واقع حداقل 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 (deflate) هنوز یک الگوریتم فشرده سازی قدیمی، شایسته و کمی قدیمی است. صرف این واقعیت که آخرین 32 کیلوبایت جریان داده فشرده نشده به عنوان یک فرهنگ لغت استفاده می شود، امروزه عجیب به نظر می رسد (یعنی اگر برخی از بلوک های داده بسیار شبیه به آنچه در جریان ورودی 40 کیلوبایت قبل بود، دوباره بایگانی می شود، و به اتفاق قبلی اشاره نخواهد کرد). در آرشیوهای مدرن مد روز، اندازه فرهنگ لغت اغلب با مگابایت به جای کیلوبایت اندازه گیری می شود.

بنابراین ما به مطالعه کوچک خود در مورد بایگانی ها ادامه می دهیم.

سپس bzip2 را آزمایش کردیم (به یاد داشته باشید، بدون FLUSH نسبت فشرده سازی فوق العاده تقریباً 100:1 را نشان داد). متأسفانه، با FLUSH بسیار ضعیف عمل کرد؛ اندازه داده های فشرده بزرگتر از داده های فشرده نشده بود.

فرضیات من در مورد دلایل شکست

Libbz2 تنها یک گزینه flush ارائه می دهد که به نظر می رسد فرهنگ لغت را پاک می کند (مشابه با Z_FULL_FLUSH در zlib)؛ پس از این هیچ صحبتی در مورد فشرده سازی موثر وجود ندارد.

و آخرین موردی که تست شد zstd بود. بسته به پارامترها، یا در سطح gzip فشرده می شود، اما بسیار سریعتر یا بهتر از gzip.

افسوس، با FLUSH عملکرد چندان خوبی نداشت: اندازه داده های فشرده حدود 700 کیلوبایت بود.

Я سوالی پرسید در صفحه github پروژه، پاسخی دریافت کردم که باید برای هر بلوک داده فشرده روی 10 بایت داده سرویس حساب کنید که نزدیک به نتایج به دست آمده است؛ راهی برای رسیدن به deflate وجود ندارد.

من تصمیم گرفتم در آزمایش های خود با بایگانی ها در این مرحله متوقف شوم (اجازه دهید یادآوری کنم که xz، lzip، lzo، lz4 حتی در مرحله آزمایش بدون FLUSH خود را نشان ندادند، و من الگوریتم های فشرده سازی عجیب و غریب بیشتری را در نظر نگرفتم).

به مشکلات آرشیو برگردیم.

مشکل دوم (آنطور که می گویند به ترتیب، نه از نظر ارزش) این است که داده های فشرده یک جریان واحد است که در آن به طور مداوم به بخش های قبلی ارجاع داده می شود. بنابراین، اگر بخشی از داده های فشرده آسیب ببیند، ما نه تنها بلوک مربوط به داده های فشرده نشده، بلکه تمام داده های بعدی را نیز از دست می دهیم.

روشی برای حل این مشکل وجود دارد:

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 بایت در هر رکورد را تخمین می زنم (دو بایت برای افست و دو بایت برای طول).
• گزینه سوم فقط به یک کاراکتر نیاز دارد تا شروع ضبط را نشان دهد، به علاوه خود ضبط به دلیل محافظت 1-2٪ افزایش می یابد. به طور کلی، تقریبا برابری با گزینه اول است.

در ابتدا گزینه دوم را به عنوان اصلی در نظر گرفتم (و حتی اجرا را نوشتم). من آن را تنها زمانی رها کردم که در نهایت تصمیم گرفتم از فشرده سازی استفاده کنم.

شاید روزی من همچنان از یک گزینه مشابه استفاده کنم. به عنوان مثال، اگر من مجبور باشم با ذخیره سازی داده های یک کشتی که بین زمین و مریخ در حال حرکت است سر و کار داشته باشم، الزامات کاملاً متفاوتی برای قابلیت اطمینان، تشعشعات کیهانی و ... وجود خواهد داشت.

در مورد گزینه سوم: من به دلیل سختی اجرا دو ستاره به آن دادم زیرا دوست ندارم با محافظ کردن، تغییر طول فرآیند و غیره کار کنم. بله، شاید من مغرضانه هستم، اما باید کد را بنویسم - چرا خودتان را مجبور به انجام کاری کنید که دوست ندارید.

خلاصه: ما به دلیل کارایی و سهولت اجرا، گزینه ذخیره سازی را به صورت زنجیره ای "هدر با طول - داده با طول متغیر" انتخاب می کنیم.

استفاده از فیلدهای بیت برای نظارت بر موفقیت عملیات نوشتن

الان یادم نیست این ایده را از کجا آوردم، اما چیزی شبیه به این است:
برای هر ورودی، چند بیت را برای ذخیره پرچم ها اختصاص می دهیم.
همانطور که قبلاً گفتیم، پس از پاک کردن، همه بیت ها با 1 پر می شوند و ما می توانیم 1 را به 0 تغییر دهیم، اما برعکس نه. بنابراین برای "پرچم تنظیم نشده است" از 1 و برای "پرچم تنظیم شده است" از 0 استفاده می کنیم.

در اینجا قرار دادن یک رکورد با طول متغیر در فلش ممکن است به نظر برسد:

1. پرچم "ضبط طول شروع شده است" را تنظیم کنید.
2. طول را ثبت کنید؛
3. پرچم "ضبط داده ها شروع شده است" را تنظیم کنید.
4. ما داده ها را ثبت می کنیم.
5. پرچم "ضبط پایان یافت" را تنظیم کنید.

علاوه بر این، ما یک پرچم "خطا رخ داده" خواهیم داشت که در مجموع پرچم 4 بیتی دارد.

در این مورد، ما دو حالت پایدار "1111" داریم - ضبط شروع نشده است و "1000" - ضبط موفقیت آمیز بود. در صورت وقفه غیرمنتظره در فرآیند ضبط، ما حالت های میانی را دریافت می کنیم که سپس می توانیم آنها را شناسایی و پردازش کنیم.

رویکرد جالب است، اما فقط در برابر قطع ناگهانی برق و خرابی های مشابه محافظت می کند، که البته مهم است، اما این تنها دلیل (یا حتی اصلی) خرابی های احتمالی نیست.

خلاصه: بیایید در جستجوی یک راه حل خوب حرکت کنیم.

جمع های چک

چک‌جمع‌ها همچنین این امکان را فراهم می‌کنند که (با احتمال معقول) مطمئن شویم که دقیقاً آنچه باید نوشته می‌شد می‌خوانیم. و برخلاف فیلدهای بیتی که در بالا بحث شد، آنها همیشه کار می کنند.

اگر فهرستی از منابع بالقوه مشکلات را که در بالا مورد بحث قرار دادیم در نظر بگیریم، آنگاه چک‌سوم قادر است یک خطا را بدون توجه به منشأ آن تشخیص دهد. (به جز، شاید، برای بیگانگان مخرب - آنها نیز می توانند چک سام را جعل کنند).

بنابراین اگر هدف ما این است که بررسی کنیم که داده ها دست نخورده هستند، جمع های چک ایده خوبی هستند.

انتخاب الگوریتم برای محاسبه جمع کنترلی هیچ سوالی ایجاد نکرد - CRC. از یک طرف، ویژگی های ریاضی امکان گرفتن انواع خاصی از خطاها را 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

پارامترهای کد crc-32c بر وب سایت کوپمن - شاید متخصص برجسته CRC در این سیاره.

В مقاله او وجود دارد یک کد جالب دیگر، که کمی پارامترهای بهتری را برای طول بسته ها ارائه می دهد که به ما مربوط می شود، اما من تفاوت را قابل توجه ندانستم و به اندازه کافی صلاحیت داشتم که به جای کد استاندارد و کاملاً تحقیق شده کد سفارشی را انتخاب کنم.

همچنین از آنجایی که داده‌های ما فشرده است، این سوال پیش می‌آید که آیا جمع چک داده‌های فشرده یا غیر فشرده را باید محاسبه کنیم؟

استدلال به نفع محاسبه جمع چک داده های فشرده نشده:

• ما در نهایت باید ایمنی ذخیره سازی داده ها را بررسی کنیم - بنابراین مستقیماً آن را بررسی می کنیم (در عین حال، خطاهای احتمالی در اجرای فشرده سازی/فشرده سازی، آسیب های ناشی از حافظه شکسته و غیره بررسی می شود).
• الگوریتم deflate در zlib پیاده سازی نسبتاً بالغی دارد و نباید با داده های ورودی "کم" سقوط می کند؛ علاوه بر این، اغلب می تواند به طور مستقل خطاها را در جریان ورودی تشخیص دهد و احتمال کلی تشخیص خطا را کاهش دهد (آزمایشی با معکوس کردن یک بیت در یک رکورد کوتاه انجام شد، zlib یک خطا را تشخیص داد. در حدود یک سوم موارد).

استدلال علیه محاسبه جمع کنترلی داده های فشرده نشده:

• CRC به طور خاص برای چند خطای بیتی که مشخصه فلش مموری است "طراحی شده است" (یک خطای بیتی در یک جریان فشرده می تواند باعث تغییر عظیم در جریان خروجی شود، که در آن، صرفاً از نظر تئوری، می توانیم یک برخورد را "گرفتن" کنیم).
• من واقعاً از ایده انتقال داده های بالقوه شکسته به کمپرسور خوشم نمی آید، چه کسی می دانداو چگونه واکنش نشان خواهد داد

در این پروژه، من تصمیم گرفتم از رویه پذیرفته شده ذخیره سازی یک جمع کنترلی از داده های فشرده نشده منحرف شوم.

خلاصه: ما از CRC-32C استفاده می کنیم، ما چک جمع را از روی داده ها به شکلی که در آن نوشته شده اند تا فلش (پس از فشرده سازی) محاسبه می کنیم.

افزونگی

البته استفاده از کدگذاری زائد از بین رفتن داده ها را از بین نمی برد، با این حال، می تواند به طور قابل توجهی (اغلب با درجه های مختلف) احتمال از دست دادن داده های غیرقابل جبران را کاهش دهد.

ما می توانیم از انواع مختلف افزونگی برای تصحیح خطاها استفاده کنیم.
کدهای همینگ می‌توانند خطاهای تک بیتی را تصحیح کنند، کدهای کاراکتر Reed-Solomon، کپی‌های متعدد داده‌ها همراه با چک‌سام‌ها یا رمزگذاری‌هایی مانند RAID-6 می‌توانند به بازیابی اطلاعات حتی در صورت خرابی گسترده کمک کنند.
در ابتدا، من متعهد به استفاده گسترده از کدنویسی مقاوم در برابر خطا بودم، اما بعد متوجه شدم که ابتدا باید ایده ای داشته باشیم که می خواهیم از چه خطاهایی محافظت کنیم و سپس کدنویسی را انتخاب کنیم.

قبلاً گفتیم که خطاها باید در اسرع وقت شناسایی شوند. در چه نقاطی می توانیم با خطا مواجه شویم؟

1. ضبط ناتمام (به دلایلی در زمان ضبط برق خاموش شد، Raspberry یخ زد، ...)
   افسوس، در صورت بروز چنین خطایی، تنها چیزی که باقی می ماند نادیده گرفتن سوابق نامعتبر و در نظر گرفتن داده ها از دست رفته است.
2. خطاهای نوشتن (به دلایلی چیزی که روی فلش مموری نوشته شده همان چیزی نبود که نوشته شده بود)
   اگر بلافاصله پس از ضبط، آزمایش خواندن را انجام دهیم، می توانیم فوراً چنین خطاهایی را تشخیص دهیم.
3. تحریف داده ها در حافظه در حین ذخیره سازی؛
4. خطاهای خواندن
   برای تصحیح آن، در صورت عدم تطابق چک سام، کافی است چند بار خواندن را تکرار کنید.

یعنی فقط خطاهای نوع سوم (فساد خود به خودی داده ها در حین ذخیره سازی) بدون کدگذاری مقاوم در برابر خطا قابل اصلاح نیستند. به نظر می رسد که چنین خطاهایی هنوز بسیار بعید است.

خلاصه: تصمیم گرفته شد که کدگذاری اضافی را کنار بگذاریم، اما اگر عملیات خطای این تصمیم را نشان دهد، سپس به بررسی موضوع برگردیم (با آمار انباشته شده در مورد خرابی ها، که امکان انتخاب نوع بهینه کدگذاری را فراهم می کند).

دیگر

البته فرمت مقاله به ما اجازه نمی دهد که هر ذره در قالب را توجیه کنیم (و قدرت من در حال حاضر تمام شده است)، بنابراین به طور خلاصه به برخی از نکاتی که قبلاً به آنها اشاره نشده است می پردازم.

• تصمیم گرفته شد که همه صفحات "برابر" شوند
  یعنی هیچ صفحه خاصی با ابرداده، رشته های مجزا و غیره وجود نخواهد داشت، بلکه در عوض یک رشته وجود نخواهد داشت که همه صفحات را به نوبه خود بازنویسی می کند.
  این تضمین می کند که حتی روی صفحات پوشیده شود، هیچ نقطه شکستی وجود ندارد، و من فقط آن را دوست دارم.
• ارائه نسخه‌سازی فرمت ضروری است.
  فرمت بدون شماره نسخه در هدر شر است!
  کافی است یک فیلد با یک عدد جادویی خاص (امضا) به هدر صفحه اضافه کنید که نشان دهنده نسخه فرمت استفاده شده است. (من فکر نمی کنم که در عمل حتی یک دوجین از آنها وجود داشته باشد);
• از یک هدر با طول متغیر برای رکوردها استفاده کنید (که تعداد زیادی از آنها وجود دارد)، سعی کنید در بیشتر موارد آن را 1 بایت طولانی کنید.
• برای رمزگذاری طول هدر و طول قسمت بریده شده رکورد فشرده، از کدهای باینری با طول متغیر استفاده کنید.

کمک زیادی کرد ژنراتور آنلاین کدهای هافمن تنها در چند دقیقه توانستیم کدهای طول متغیر مورد نیاز را انتخاب کنیم.

شرح فرمت ذخیره سازی داده ها

ترتیب بایت

فیلدهای بزرگتر از یک بایت در قالب big-endian (ترتیب بایت شبکه) ذخیره می شوند، یعنی 0x1234 به صورت 0x12، 0x34 نوشته می شود.

صفحه بندی

تمام فلش مموری ها به صفحات با اندازه مساوی تقسیم می شوند.

اندازه پیش فرض صفحه 32 کیلوبایت است، اما بیش از 1/4 اندازه کل تراشه حافظه نیست (برای یک تراشه 4 مگابایتی، 128 صفحه به دست می آید).

هر صفحه داده ها را مستقل از سایرین ذخیره می کند (یعنی داده های یک صفحه به داده های صفحه دیگر ارجاع نمی دهد).

همه صفحات به ترتیب طبیعی (به ترتیب صعودی آدرس ها) شماره گذاری می شوند که با شماره 0 شروع می شود (صفحه صفر از آدرس 0 شروع می شود، صفحه اول با 32 کیلوبایت شروع می شود، صفحه دوم با 64 کیلوبایت شروع می شود و غیره)

تراشه حافظه به عنوان بافر چرخه ای (حلقه بافر) استفاده می شود، یعنی ابتدا نوشتن به صفحه شماره 0 می رود، سپس شماره 1، ...، وقتی صفحه آخر را پر می کنیم، چرخه جدیدی شروع می شود و ضبط از صفحه صفر ادامه می یابد. .

داخل صفحه

در ابتدای صفحه، یک هدر صفحه 4 بایتی ذخیره می شود، سپس یک جمع کنترل سرصفحه (CRC-32C)، سپس رکوردها در قالب «هدر، داده، جمع کنترل» ذخیره می شوند.

عنوان صفحه (سبز کثیف در نمودار) شامل موارد زیر است:

• فیلد شماره جادویی دو بایتی (همچنین نشانه ای از نسخه قالب)
  برای نسخه فعلی فرمت به صورت محاسبه می شود 0xed00 ⊕ номер страницы;
• شمارنده دو بایتی "نسخه صفحه" (شماره چرخه بازنویسی حافظه).

ورودی های صفحه به صورت فشرده ذخیره می شوند (الگوریتم deflate استفاده می شود). تمام رکوردهای یک صفحه در یک رشته فشرده می شوند (یک فرهنگ لغت رایج استفاده می شود)، و در هر صفحه جدید فشرده سازی دوباره شروع می شود. یعنی برای از حالت فشرده خارج کردن هر رکورد، تمام رکوردهای قبلی از این صفحه (و فقط این صفحه) مورد نیاز است.

هر رکورد با پرچم Z_SYNC_FLUSH فشرده می شود و در انتهای جریان فشرده 4 بایت 0x00, 0x00, 0xff, 0xff وجود خواهد داشت که احتمالاً قبل از آن یک یا دو بایت صفر دیگر وجود دارد.
هنگام نوشتن در حافظه فلش، این دنباله (طول 4، 5 یا 6 بایت) را کنار می گذاریم.

هدر رکورد 1، 2 یا 3 بایت ذخیره می شود:

• یک بیت (T) که نوع رکورد را نشان می دهد: 0 - زمینه، 1 - ورود.
• یک فیلد با طول متغیر (S) از 1 تا 7 بیت، که طول هدر و "دم" را که باید برای رفع فشرده سازی به رکورد اضافه شود، تعریف می کند.
• طول رکورد (L).

جدول مقدار S:

S
طول هدر، بایت
هنگام نوشتن، بایت حذف شد

0
1
5 (00 00 00 ff ff)

10
1
6 (00 00 00 00 ff ff)

110
2
4 (00 00 ff ff)

1110
2
5 (00 00 00 ff ff)

11110
2
6 (00 00 00 00 ff ff)

1111100
3
4 (00 00 ff ff)

1111101
3
5 (00 00 00 ff ff)

1111110
3
6 (00 00 00 00 ff ff)

سعی کردم نشان دهم، نمی دانم چقدر واضح بود:

رنگ زرد در اینجا نشان دهنده فیلد T، سفید فیلد S، L سبز (طول داده های فشرده شده بر حسب بایت)، آبی رنگ داده های فشرده، قرمز بایت های نهایی داده های فشرده که در حافظه فلش نوشته نشده اند را نشان می دهد.

بنابراین، می‌توانیم سرصفحه‌های رکوردی با متداول‌ترین طول (تا 63+5 بایت به صورت فشرده) را در یک بایت بنویسیم.

پس از هر رکورد، یک چک‌سوم CRC-32C ذخیره می‌شود که در آن مقدار وارونه چک‌سوم قبلی به عنوان مقدار اولیه (init) استفاده می‌شود.

CRC دارای ویژگی "مدت" است، فرمول زیر کار می کند (به علاوه یا منهای معکوس بیت در فرآیند): .
یعنی در واقع ما CRC تمام بایت های قبلی هدرها و داده های این صفحه را محاسبه می کنیم.

به‌طور مستقیم به دنبال چک‌سوم، سرصفحه رکورد بعدی است.

هدر به گونه ای طراحی شده است که بایت اول آن همیشه با 0x00 و 0xff متفاوت است (اگر به جای بایت اول هدر با 0xff روبرو شویم، این بدان معنی است که این یک منطقه استفاده نشده است؛ 0x00 یک خطا را نشان می دهد).

الگوریتم های مثال

خواندن از فلش مموری

هر قرائتی همراه با چک جمع است.
اگر جمع چک مطابقت نداشته باشد، خواندن چندین بار به امید خواندن داده های صحیح تکرار می شود.

(این منطقی است، لینوکس خواندن را از NOR Flash در حافظه پنهان نمی کند، آزمایش شده است)

روی فلش مموری بنویسید

داده ها را ثبت می کنیم.
آنها را بخوانیم.

اگر داده های خوانده شده با داده های نوشته شده مطابقت نداشته باشد، منطقه را با صفر پر می کنیم و علامت خطا می دهیم.

آماده سازی یک ریز مدار جدید برای عملیات

برای مقداردهی اولیه، یک هدر با نسخه 1 در صفحه اول (یا بهتر است بگوییم صفر) نوشته می شود.
پس از آن، زمینه اولیه در این صفحه نوشته می شود (شامل UUID ماشین و تنظیمات پیش فرض).

تمام، فلش مموری آماده استفاده است.

در حال بارگیری دستگاه

هنگام بارگذاری، 8 بایت اول هر صفحه (هدر + CRC) خوانده می شود، صفحاتی با شماره جادویی ناشناخته یا CRC نادرست نادیده گرفته می شوند.
از صفحات "صحیح" صفحاتی با حداکثر نسخه انتخاب می شوند و صفحه ای که بیشترین تعداد را دارد از آنها گرفته می شود.
اولین رکورد خوانده می شود، صحت CRC و وجود پرچم "زمینه" بررسی می شود. اگر همه چیز خوب باشد، این صفحه فعلی در نظر گرفته می شود. اگر نه، به صفحه قبلی برمی گردیم تا زمانی که یک صفحه "زنده" پیدا کنیم.
و در صفحه یافت شده، همه رکوردها را می خوانیم، آنهایی که با پرچم "زمینه" استفاده می کنیم.
فرهنگ لغت zlib را ذخیره کنید (برای افزودن به این صفحه لازم است).

تمام شد، دانلود کامل شد، زمینه بازیابی شد، می توانید کار کنید.

افزودن یک مدخل مجله

ما رکورد را با دیکشنری صحیح فشرده می کنیم و Z_SYNC_FLUSH را مشخص می کنیم. می بینیم که آیا رکورد فشرده در صفحه فعلی مطابقت دارد یا خیر.
اگر مناسب نیست (یا خطاهای CRC در صفحه وجود دارد)، صفحه جدیدی را شروع کنید (به زیر مراجعه کنید).
ما رکورد و CRC را یادداشت می کنیم. اگر خطایی رخ داد، صفحه جدیدی را شروع کنید.

صفحه جدید

ما یک صفحه رایگان با حداقل تعداد را انتخاب می کنیم (صفحه رایگان را صفحه ای با چک جمع نادرست در هدر یا با نسخه کمتر از نسخه فعلی در نظر می گیریم). اگر چنین صفحاتی وجود ندارد، از بین صفحاتی که نسخه ای برابر با نسخه فعلی دارند، صفحه با حداقل تعداد را انتخاب کنید.
صفحه انتخاب شده را پاک می کنیم. محتویات را با 0xff بررسی می کنیم. اگر مشکلی وجود دارد، صفحه رایگان بعدی و غیره را انتخاب کنید.
ما یک سرصفحه در صفحه پاک شده می نویسیم، اولین ورودی وضعیت فعلی متن است، ورودی بعدی ورودی ثبت نشده است (اگر وجود داشته باشد).

قابلیت کاربرد قالب

به نظر من، فرمت خوبی برای ذخیره هر جریان اطلاعات کم و بیش فشرده (متن ساده، JSON، MessagePack، CBOR، احتمالاً پروتوباف) در NOR Flash بود.

البته، فرمت برای SLC NOR Flash "طراحی شده" است.

نباید با رسانه های BER بالا مانند NAND یا MLC NOR استفاده شود (آیا چنین حافظه ای حتی برای فروش موجود است؟ من فقط در آثار مربوط به کدهای تصحیح ذکر شده است).

علاوه بر این، نباید با دستگاه هایی که FTL خود را دارند استفاده شود: فلش USB، SD، MicroSD و غیره (برای چنین حافظه ای قالبی با اندازه صفحه 512 بایت، امضا در ابتدای هر صفحه و اعداد رکورد منحصر به فرد ایجاد کردم - گاهی اوقات می توان با خواندن متوالی ساده تمام داده ها را از یک درایو فلش "مشکلات" بازیابی کرد).

بسته به وظایف، فرمت را می توان بدون تغییر در درایوهای فلش از 128 کیلوبیت (16 کیلوبایت) تا 1 گیگابیت (128 مگابایت) استفاده کرد. در صورت تمایل، می توانید از آن بر روی تراشه های بزرگتر استفاده کنید، اما احتمالاً باید اندازه صفحه را تنظیم کنید (اما در اینجا سوال امکان سنجی اقتصادی پیش می آید؛ قیمت NOR Flash با حجم زیاد دلگرم کننده نیست).

اگر کسی قالب را جالب می‌داند و می‌خواهد از آن در یک پروژه باز استفاده کند، بنویسد، سعی می‌کنم زمان را پیدا کنم، کد را صیقل دهم و آن را در github پست کنم.

نتیجه

همانطور که می بینید، در نهایت فرمت ساده شد و حتی خسته کننده.

انعکاس تکامل دیدگاه من در یک مقاله دشوار است، اما باور کنید: در ابتدا می خواستم چیزی پیچیده، تخریب ناپذیر ایجاد کنم که حتی از یک انفجار هسته ای در نزدیکی زنده بماند. با این حال، عقل (امیدوارم) همچنان پیروز شد و به تدریج اولویت ها به سمت سادگی و فشردگی تغییر یافت.

ممکنه من اشتباه کردم؟ بله حتما. به عنوان مثال، ممکن است معلوم شود که ما یک سری ریز مدارهای با کیفیت پایین خریداری کرده ایم. یا به دلایل دیگری تجهیزات انتظارات قابلیت اطمینان را برآورده نمی کنند.

آیا من برای این کار برنامه ای دارم؟ من فکر می کنم که پس از خواندن مقاله هیچ شکی ندارید که برنامه ای وجود دارد. و نه حتی تنها.

در یک نکته جدی تر، این قالب هم به عنوان یک گزینه کار و هم به عنوان یک "بالون آزمایشی" توسعه داده شد.

در حال حاضر همه چیز روی میز خوب کار می کند، به معنای واقعی کلمه روز دیگر راه حل مستقر خواهد شد (تقریبا) در صدها دستگاه، بیایید ببینیم در عملیات "مبارزه" چه اتفاقی می‌افتد (خوشبختانه، امیدوارم این فرمت به شما امکان دهد به طور قابل اعتماد خرابی‌ها را شناسایی کنید؛ بنابراین می‌توانید آمار کامل را جمع‌آوری کنید). در عرض چند ماه می توان نتیجه گیری کرد (و اگر بدشانس باشید، حتی زودتر).

اگر بر اساس نتایج استفاده، مشکلات جدی کشف شود و نیاز به بهبود باشد، قطعاً در مورد آن خواهم نوشت.

ادبیات

نمی‌خواستم فهرست طولانی و خسته‌کننده‌ای از کارهای استفاده شده تهیه کنم؛ بالاخره همه گوگل دارند.

در اینجا تصمیم گرفتم فهرستی از یافته‌ها را بگذارم که برای من جالب به نظر می‌رسید، اما به تدریج آنها مستقیماً به متن مقاله مهاجرت کردند و یک مورد در لیست باقی ماند:

1. سودمندی infgen از نویسنده zlib. می تواند محتویات آرشیوهای deflate/zlib/gzip را به وضوح نمایش دهد. اگر باید با ساختار داخلی فرمت deflate (یا gzip) سر و کار داشته باشید، آن را به شدت توصیه می کنم.

منبع: www.habr.com