پس منظر

ہمارے اپنے ڈیزائن کی وینڈنگ مشینیں ہیں۔ Raspberry Pi کے اندر اور ایک علیحدہ بورڈ پر کچھ وائرنگ۔ ایک سکے قبول کرنے والا، ایک بل قبول کرنے والا، ایک بینک ٹرمینل جڑے ہوئے ہیں... ہر چیز کو خود تحریر کردہ پروگرام کے ذریعے کنٹرول کیا جاتا ہے۔ کام کی پوری تاریخ فلیش ڈرائیو (مائیکرو ایس ڈی) پر لاگ پر لکھی جاتی ہے، جو پھر انٹرنیٹ کے ذریعے (یو ایس بی موڈیم کا استعمال کرتے ہوئے) سرور پر منتقل ہوتی ہے، جہاں اسے ڈیٹا بیس میں محفوظ کیا جاتا ہے۔ سیلز کی معلومات 1c میں بھری ہوئی ہے، نگرانی کے لیے ایک سادہ ویب انٹرفیس بھی ہے، وغیرہ۔

یعنی، جریدہ بہت ضروری ہے - اکاؤنٹنگ (ریونیو، سیلز، وغیرہ)، نگرانی (ہر قسم کی ناکامی اور دیگر زبردستی حالات) کے لیے؛ یہ، کوئی کہہ سکتا ہے، اس مشین کے بارے میں ہمارے پاس موجود تمام معلومات ہیں۔

مسئلہ

فلیش ڈرائیوز اپنے آپ کو بہت ناقابل اعتماد آلات ظاہر کرتی ہیں۔ وہ قابل رشک باقاعدگی کے ساتھ ناکام رہتے ہیں۔ اس سے مشین کا وقت ختم ہوجاتا ہے اور (اگر کسی وجہ سے لاگ کو آن لائن منتقل نہیں کیا جا سکتا ہے) ڈیٹا کے نقصان کی طرف جاتا ہے۔

فلیش ڈرائیوز کے استعمال کا یہ پہلا تجربہ نہیں ہے، اس سے قبل ایک اور پراجیکٹ تھا جس میں سو سے زائد ڈیوائسز موجود تھیں، جہاں میگزین کو USB فلیش ڈرائیوز پر محفوظ کیا جاتا تھا، وہیں وشوسنییتا کے مسائل بھی سامنے آتے تھے، بعض اوقات ناکام ہونے والوں کی تعداد بہت زیادہ تھی۔ ایک مہینہ درجنوں میں تھا۔ ہم نے مختلف فلیش ڈرائیوز آزمائیں، بشمول SLC میموری کے ساتھ برانڈڈ، اور کچھ ماڈلز دوسروں کے مقابلے زیادہ قابل اعتماد ہیں، لیکن فلیش ڈرائیوز کو تبدیل کرنے سے مسئلہ بنیادی طور پر حل نہیں ہوا۔

ہوشیار! لانگ ریڈ! اگر آپ "کیوں" میں دلچسپی نہیں رکھتے، لیکن صرف "کیسے" میں، آپ سیدھے جا سکتے ہیں۔ آخر میں مضامین

حل

پہلی چیز جو ذہن میں آتی ہے وہ ہے: مائیکرو ایس ڈی کو چھوڑ دیں، مثال کے طور پر ایس ایس ڈی انسٹال کریں، اور اس سے بوٹ کریں۔ نظریاتی طور پر ممکن، شاید، لیکن نسبتاً مہنگا، اور اتنا قابل اعتماد نہیں (ایک USB-SATA اڈاپٹر شامل کیا گیا ہے؛ بجٹ SSDs کے ناکامی کے اعداد و شمار بھی حوصلہ افزا نہیں ہیں)۔

USB HDD بھی خاص طور پر پرکشش حل کی طرح نہیں لگتا ہے۔

لہذا، ہم اس آپشن پر آئے ہیں: مائیکرو ایس ڈی سے بوٹنگ چھوڑ دیں، لیکن انہیں صرف پڑھنے کے موڈ میں استعمال کریں، اور آپریشن لاگ (اور ہارڈ ویئر کے کسی خاص ٹکڑے کے لیے منفرد دیگر معلومات - سیریل نمبر، سینسر کیلیبریشن وغیرہ) کو کہیں اور اسٹور کریں۔ .

راسبیریوں کے لیے صرف پڑھنے کے لیے FS کا موضوع پہلے ہی اندر اور باہر پڑھا جا چکا ہے، میں اس مضمون میں نفاذ کی تفصیلات پر غور نہیں کروں گا۔ (لیکن اگر دلچسپی ہے تو شاید میں اس موضوع پر ایک چھوٹا سا مضمون لکھوں گا). صرف ایک نکتہ جو میں نوٹ کرنا چاہتا ہوں وہ یہ ہے کہ ذاتی تجربے اور ان لوگوں کے جائزوں سے جنہوں نے اسے پہلے ہی لاگو کیا ہے، اعتماد میں اضافہ ہوتا ہے۔ جی ہاں، خرابیوں سے مکمل طور پر چھٹکارا حاصل کرنا ناممکن ہے، لیکن ان کی تعدد کو نمایاں طور پر کم کرنا کافی ممکن ہے۔ اور کارڈز متحد ہو رہے ہیں، جس کی وجہ سے سروس اہلکاروں کے لیے تبدیلی بہت آسان ہو جاتی ہے۔

ہارڈ ویئر حصہ

میموری کی قسم کے انتخاب کے بارے میں کوئی خاص شک نہیں تھا - اور نہ ہی فلیش۔
دلائل:

• سادہ کنکشن (اکثر ایس پی آئی بس، جسے استعمال کرنے کا آپ کو پہلے سے تجربہ ہے، اس لیے ہارڈ ویئر کی کوئی پریشانی پیش نہیں آتی)؛
• مضحکہ خیز قیمت؛
• معیاری آپریٹنگ پروٹوکول (عمل درآمد پہلے سے ہی لینکس کے کرنل میں ہے، اگر آپ چاہیں تو، آپ تھرڈ پارٹی لے سکتے ہیں، جو موجود ہے، یا خود بھی لکھ سکتے ہیں، خوش قسمتی سے سب کچھ آسان ہے)؛
• وشوسنییتا اور وسائل:
  ایک عام ڈیٹا شیٹ سے: ڈیٹا 20 سال کے لیے محفوظ کیا جاتا ہے، ہر بلاک کے لیے 100000 مٹانے کے چکر۔
  فریق ثالث کے ذرائع سے: انتہائی کم بی ای آر، غلطی کی اصلاح کے کوڈز کی ضرورت نہیں بتاتا ہے۔ (کچھ کام NOR کے لیے ECC پر غور کرتے ہیں، لیکن عام طور پر ان کا مطلب اب بھی MLC NOR ہوتا ہے؛ ایسا بھی ہوتا ہے).

آئیے حجم اور وسائل کی ضروریات کا اندازہ لگائیں۔

میں چاہتا ہوں کہ ڈیٹا کو کئی دنوں تک محفوظ کرنے کی ضمانت دی جائے۔ یہ ضروری ہے تاکہ مواصلات کے ساتھ کسی بھی پریشانی کی صورت میں، فروخت کی تاریخ ضائع نہ ہو۔ ہم اس مدت کے دوران 5 دنوں پر توجہ مرکوز کریں گے۔ (یہاں تک کہ اختتام ہفتہ اور تعطیلات کو مدنظر رکھتے ہوئے) مسئلہ حل کیا جا سکتا ہے.

ہم فی الحال تقریباً 100kb لاگز فی دن جمع کرتے ہیں (3-4 ہزار اندراجات)، لیکن آہستہ آہستہ یہ تعداد بڑھ رہی ہے - تفصیل بڑھ رہی ہے، نئے واقعات شامل کیے جا رہے ہیں۔ اس کے علاوہ، بعض اوقات پھٹ جاتے ہیں (مثال کے طور پر، کچھ سینسر غلط مثبتات کے ساتھ سپیمنگ شروع کر دیتے ہیں)۔ ہم 10 ہزار ریکارڈ کے لیے حساب کریں گے 100 بائٹس ہر ایک - میگا بائٹس فی دن۔

مجموعی طور پر، 5MB صاف (اچھی طرح سے کمپریسڈ) ڈیٹا نکلتا ہے۔ ان کو مزید (سرسری اندازہ) 1MB سروس ڈیٹا۔

یعنی، اگر ہم کمپریشن استعمال نہیں کرتے ہیں تو ہمیں 8MB چپ کی ضرورت ہے، یا اگر ہم اسے استعمال کرتے ہیں تو 4MB۔ اس قسم کی میموری کے لیے کافی حقیقت پسندانہ نمبر۔

جہاں تک وسائل کا تعلق ہے: اگر ہم منصوبہ بناتے ہیں کہ پوری میموری کو ہر 5 دن میں ایک بار سے زیادہ نہیں لکھا جائے گا، تو 10 سال سے زیادہ کی سروس ہمیں ایک ہزار سے کم دوبارہ لکھنے کے چکر ملتے ہیں۔
میں آپ کو یاد دلاتا ہوں کہ کارخانہ دار ایک لاکھ کا وعدہ کرتا ہے۔

NOR بمقابلہ نند کے بارے میں تھوڑا سا

آج، یقیناً، NAND میموری بہت زیادہ مقبول ہے، لیکن میں اسے اس پروجیکٹ کے لیے استعمال نہیں کروں گا: NAND، NOR کے برعکس، ضروری طور پر غلطی کو درست کرنے والے کوڈز، خراب بلاکس کی ایک میز، وغیرہ، اور ٹانگوں کی بھی ضرورت ہوتی ہے۔ NAND چپس عام طور پر بہت زیادہ۔

NOR کے نقصانات میں شامل ہیں:

• چھوٹے حجم (اور، اس کے مطابق، فی میگا بائٹ اعلی قیمت)؛
• کم مواصلات کی رفتار (بڑی حد تک اس حقیقت کی وجہ سے کہ ایک سیریل انٹرفیس استعمال کیا جاتا ہے، عام طور پر SPI یا I2C)؛
• آہستہ سے مٹانا (بلاک کے سائز پر منحصر ہے، اس میں ایک سیکنڈ سے لے کر کئی سیکنڈ تک کا وقت لگتا ہے)۔

ایسا لگتا ہے کہ ہمارے لیے کوئی اہم چیز نہیں ہے، اس لیے ہم جاری رکھتے ہیں۔

اگر تفصیلات دلچسپ ہیں تو، مائیکرو سرکٹ کا انتخاب کیا گیا ہے۔ at25df321a (تاہم، یہ غیر اہم ہے، مارکیٹ میں بہت سارے اینالاگ موجود ہیں جو پن آؤٹ اور کمانڈ سسٹم میں مطابقت رکھتے ہیں؛ یہاں تک کہ اگر ہم کسی مختلف مینوفیکچرر اور/یا مختلف سائز سے مائیکرو سرکٹ انسٹال کرنا چاہتے ہیں، تب بھی سب کچھ تبدیل کیے بغیر کام کرے گا۔ کوڈ).

میں لینکس کرنل میں بنایا ہوا ڈرائیور استعمال کرتا ہوں؛ Raspberry پر، ڈیوائس ٹری اوورلے سپورٹ کی بدولت، سب کچھ بہت آسان ہے - آپ کو مرتب شدہ اوورلے کو /boot/overlays میں ڈالنا ہوگا اور /boot/config.txt میں تھوڑا سا ترمیم کرنا ہوگی۔

ڈی ٹی ایس فائل کی مثال

سچ پوچھیں تو، مجھے یقین نہیں ہے کہ یہ غلطیوں کے بغیر لکھا گیا ہے، لیکن یہ کام کرتا ہے۔

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

/dts-v1/;
/plugin/;

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

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

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

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

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

اور config.txt میں ایک اور لائن

dtoverlay=at25:spimaxfrequency=50000000

میں چپ کو Raspberry Pi سے منسلک کرنے کی تفصیل کو چھوڑ دوں گا۔ ایک طرف، میں الیکٹرانکس کا ماہر نہیں ہوں، دوسری طرف، یہاں پر ہر چیز میرے لیے عام ہے: مائیکرو سرکٹ کی صرف 8 ٹانگیں ہیں، جن میں سے ہمیں زمین، طاقت، SPI (CS، SI، SO، SCK) کی ضرورت ہے۔ ); سطحیں Raspberry Pi کے برابر ہیں، کسی اضافی وائرنگ کی ضرورت نہیں ہے - صرف اشارہ کردہ 6 پنوں کو جوڑیں۔

مسئلہ کی تشکیل

ہمیشہ کی طرح، مسئلہ کا بیان کئی تکرارات سے گزرتا ہے، اور مجھے لگتا ہے کہ اگلے کا وقت آگیا ہے۔ تو آئیے رکیں، جو کچھ پہلے سے لکھا جا چکا ہے اس کو جمع کریں، اور ان تفصیلات کو واضح کریں جو سائے میں رہ گئی ہیں۔

لہذا، ہم نے فیصلہ کیا ہے کہ لاگ کو SPI اور نہ ہی فلیش میں محفوظ کیا جائے گا۔

جو نہیں جانتے ان کے لیے NOR فلیش کیا ہے؟

یہ غیر مستحکم میموری ہے جس کے ساتھ آپ تین آپریشن کر سکتے ہیں:

1. پڑھنا:
   سب سے عام پڑھنا: ہم ایڈریس منتقل کرتے ہیں اور جتنے بائٹس کی ضرورت ہوتی ہے اسے پڑھتے ہیں۔
2. ریکارڈ:
   NOR فلیش پر لکھنا معمول کی طرح لگتا ہے، لیکن اس کی ایک خاصیت ہے: آپ صرف 1 سے 0 کو تبدیل کر سکتے ہیں، لیکن اس کے برعکس نہیں۔ مثال کے طور پر، اگر ہمارے پاس میموری سیل میں 0x55 ہے، تو اس پر 0x0f لکھنے کے بعد، 0x05 پہلے ہی وہاں محفوظ ہو جائے گا۔ (صرف نیچے کی میز دیکھیں);
3. مٹانا:
   بلاشبہ، ہمیں مخالف آپریشن کرنے کے قابل ہونے کی ضرورت ہے - 0 سے 1 کو تبدیل کریں، یہ بالکل وہی ہے جس کے لیے مٹانے کا عمل ہے۔ پہلے دو کے برعکس، یہ بائٹس کے ساتھ نہیں بلکہ بلاکس کے ساتھ کام کرتا ہے (منتخب چپ میں کم از کم ایریز بلاک 4kb ہے)۔ ایریز پورے بلاک کو تباہ کر دیتا ہے اور یہ 0 سے 1 کو تبدیل کرنے کا واحد طریقہ ہے۔ اس لیے، فلیش میموری کے ساتھ کام کرتے وقت، آپ کو اکثر ڈیٹا سٹرکچر کو ایریز بلاک باؤنڈری کے ساتھ سیدھا کرنا پڑتا ہے۔
   NOR فلیش میں ریکارڈنگ:

بائنری ڈیٹا

تھا
01010101

محفوظ شدہ
00001111

بن گیا ہے
00000101

لاگ بذات خود متغیر لمبائی کے ریکارڈز کی ایک ترتیب کی نمائندگی کرتا ہے۔ ایک ریکارڈ کی عام لمبائی تقریباً 30 بائٹس ہوتی ہے (حالانکہ ایسے ریکارڈز جن کی لمبائی کئی کلو بائٹس ہوتی ہے کبھی کبھار ہوتی ہے)۔ اس معاملے میں، ہم ان کے ساتھ صرف بائٹس کے سیٹ کے طور پر کام کرتے ہیں، لیکن، اگر آپ دلچسپی رکھتے ہیں، تو CBOR ریکارڈ کے اندر استعمال ہوتا ہے۔

لاگ کے علاوہ، ہمیں کچھ "سیٹنگ" معلومات کو ذخیرہ کرنے کی ضرورت ہے، دونوں اپ ڈیٹ شدہ اور نہیں: ایک مخصوص ڈیوائس ID، سینسر کیلیبریشنز، "آلہ عارضی طور پر غیر فعال ہے" جھنڈا، وغیرہ۔
یہ معلومات کلیدی قدر کے ریکارڈز کا ایک مجموعہ ہے، جو CBOR میں بھی محفوظ ہے۔ ہمارے پاس اس میں زیادہ معلومات نہیں ہیں (زیادہ سے زیادہ چند کلو بائٹس)، اور اسے کبھی کبھار اپ ڈیٹ کیا جاتا ہے۔
اس کے بعد ہم اسے سیاق و سباق کہیں گے۔

اگر ہمیں یاد ہے کہ یہ مضمون کہاں سے شروع ہوا ہے، تو قابل اعتماد ڈیٹا اسٹوریج کو یقینی بنانا بہت ضروری ہے اور، اگر ممکن ہو تو، ہارڈ ویئر کی ناکامی/ڈیٹا کرپٹ ہونے کی صورت میں بھی مسلسل آپریشن۔

مسائل کے کن ذرائع پر غور کیا جا سکتا ہے؟

• لکھنے/مٹانے کی کارروائیوں کے دوران پاور آف کریں۔ یہ "کروبار کے خلاف کوئی چال نہیں ہے" کے زمرے سے ہے۔
  سے معلومات بات چیت اسٹیک ایکسچینج پر: جب فلیش کے ساتھ کام کرتے وقت پاور آف ہو جاتی ہے، دونوں مٹاتے ہیں (1 پر سیٹ کریں) اور لکھیں (0 پر سیٹ کریں) غیر متعینہ رویے کا باعث بنتے ہیں: ڈیٹا لکھا جا سکتا ہے، جزوی طور پر لکھا جا سکتا ہے (کہیں، ہم نے 10 بائٹس/80 بٹس منتقل کیے ہیں) ، لیکن ابھی تک صرف 45 بٹس نہیں لکھے جاسکتے ہیں)، یہ بھی ممکن ہے کہ کچھ بٹس "انٹرمیڈیٹ" حالت میں ہوں گے (پڑھنے سے 0 اور 1 دونوں پیدا ہوسکتے ہیں)؛
• فلیش میموری میں ہی خرابیاں۔
  BER، اگرچہ بہت کم ہے، صفر کے برابر نہیں ہو سکتا۔
• بس کی غلطیاں
  SPI کے ذریعے منتقل ہونے والا ڈیٹا کسی بھی طرح سے محفوظ نہیں ہے؛ سنگل بٹ کی غلطیاں اور مطابقت پذیری کی خرابیاں اچھی طرح سے ہو سکتی ہیں - بٹس کا نقصان یا اندراج (جو بڑے پیمانے پر ڈیٹا کی خرابی کا باعث بنتا ہے)؛
• دیگر غلطیاں/خرابیاں
  کوڈ میں غلطیاں، راسبیری کی خرابیاں، اجنبی مداخلت...

میں نے تقاضے وضع کیے ہیں، جن کی تکمیل، میری رائے میں، وشوسنییتا کو یقینی بنانے کے لیے ضروری ہے:

• ریکارڈز کو فوری طور پر فلیش میموری میں جانا چاہیے، تاخیر سے لکھے جانے پر غور نہیں کیا جاتا؛ - اگر کوئی غلطی ہوتی ہے، تو اسے جلد از جلد پتہ لگانا اور اس پر کارروائی کرنی چاہیے؛ - سسٹم کو، اگر ممکن ہو، غلطیوں سے باز آنا چاہیے۔
  (زندگی کی ایک مثال "یہ کیسے نہیں ہونا چاہئے"، جس کا میرے خیال میں ہر کسی کو سامنا ہوا ہے: ایمرجنسی ریبوٹ کے بعد، فائل سسٹم "ٹوٹا ہوا" ہے اور آپریٹنگ سسٹم بوٹ نہیں ہوتا ہے)

خیالات، نقطہ نظر، عکاسی

جب میں نے اس مسئلے کے بارے میں سوچنا شروع کیا تو میرے ذہن میں بہت سے خیالات اُبھرے، مثال کے طور پر:

• ڈیٹا کمپریشن کا استعمال کریں؛
• ہوشیار ڈیٹا سٹرکچرز کا استعمال کریں، مثال کے طور پر، ریکارڈ ہیڈرز کو ریکارڈز سے الگ ذخیرہ کرنا، تاکہ اگر کسی ریکارڈ میں کوئی خرابی ہو، تو آپ بقیہ کو بغیر کسی پریشانی کے پڑھ سکیں؛
• بجلی بند ہونے پر ریکارڈنگ کی تکمیل کو کنٹرول کرنے کے لیے بٹ فیلڈز کا استعمال کریں۔
• ہر چیز کے لیے چیکسم اسٹور کریں؛
• کچھ قسم کی شور مزاحم کوڈنگ استعمال کریں۔

ان خیالات میں سے کچھ استعمال کیے گئے تھے، جبکہ دیگر کو ترک کرنے کا فیصلہ کیا گیا تھا۔ آئیے ترتیب سے چلتے ہیں۔

ڈیٹا سکیڑنا۔

خود جو واقعات ہم جریدے میں ریکارڈ کرتے ہیں وہ کافی ملتے جلتے اور دہرائے جا سکتے ہیں ("5 روبل کا سکہ پھینکا"، "تبدیلی دینے کے لیے بٹن دبایا"، ...)۔ لہذا، کمپریشن کافی مؤثر ہونا چاہئے.

کمپریشن اوور ہیڈ غیر اہم ہے (ہمارا پروسیسر کافی طاقتور ہے، یہاں تک کہ پہلے پائی میں 700 میگا ہرٹز کی فریکوئنسی کے ساتھ ایک کور تھا، موجودہ ماڈلز میں ایک گیگا ہرٹز سے زیادہ فریکوئنسی کے ساتھ کئی کور ہیں)، اسٹوریج کے ساتھ شرح تبادلہ کم ہے (کئی میگا بائٹس فی سیکنڈ)، ریکارڈز کا سائز چھوٹا ہے۔ عام طور پر، اگر کمپریشن کا کارکردگی پر اثر پڑتا ہے، تو یہ صرف مثبت ہوگا۔ (بالکل غیر تنقیدی، صرف بیان کرتے ہوئے). اس کے علاوہ، ہمارے پاس اصلی ایمبیڈڈ نہیں ہے، لیکن باقاعدہ لینکس - لہذا عمل درآمد کے لیے زیادہ محنت کی ضرورت نہیں ہونی چاہیے (صرف لائبریری کو لنک کرنا اور اس سے کئی فنکشنز استعمال کرنا کافی ہے)۔

لاگ کا ایک ٹکڑا ایک ورکنگ ڈیوائس سے لیا گیا تھا (1.7 MB، 70 ہزار اندراجات) اور پہلے کمپیوٹر پر دستیاب gzip, lz4, lzop, bzip2, xz, zstd کا استعمال کرتے ہوئے کمپریسبلٹی کے لیے چیک کیا گیا۔

• gzip, xz, zstd نے اسی طرح کے نتائج دکھائے (40Kb)۔
  میں حیران تھا کہ فیشن ایبل ایکس زیڈ نے خود کو یہاں gzip یا zstd کی سطح پر ظاہر کیا۔
• پہلے سے طے شدہ ترتیبات کے ساتھ lzip نے قدرے خراب نتائج دیے۔
• lz4 اور lzop نے بہت اچھے نتائج نہیں دکھائے (150Kb)؛
• bzip2 نے حیرت انگیز طور پر اچھا نتیجہ دکھایا (18Kb)۔

لہذا، ڈیٹا کو بہت اچھی طرح سے کمپریس کیا جاتا ہے.
تو (اگر ہم مہلک خامیاں نہیں ڈھونڈتے ہیں) تو کمپریشن ہو جائے گا! صرف اس لیے کہ ایک ہی فلیش ڈرائیو پر زیادہ ڈیٹا فٹ ہو سکتا ہے۔

آئیے نقصانات کے بارے میں سوچتے ہیں۔

پہلا مسئلہ: ہم پہلے ہی اس بات پر متفق ہو چکے ہیں کہ ہر ریکارڈ کو فوری طور پر فلیش پر جانا چاہیے۔ عام طور پر، آرکائیور ان پٹ اسٹریم سے ڈیٹا اکٹھا کرتا ہے جب تک کہ یہ فیصلہ نہ کر لے کہ ویک اینڈ پر لکھنے کا وقت آگیا ہے۔ ہمیں فوری طور پر ڈیٹا کا ایک کمپریسڈ بلاک حاصل کرنے اور اسے غیر مستحکم میموری میں ذخیرہ کرنے کی ضرورت ہے۔

میں تین طریقے دیکھتا ہوں:

1. اوپر زیر بحث الگورتھم کی بجائے ڈکشنری کمپریشن کا استعمال کرتے ہوئے ہر ریکارڈ کو کمپریس کریں۔
   یہ مکمل طور پر کام کرنے والا آپشن ہے، لیکن مجھے یہ پسند نہیں ہے۔ کمپریشن کی کم و بیش مہذب سطح کو یقینی بنانے کے لیے، لغت کو مخصوص ڈیٹا کے مطابق "مطابق" ہونا چاہیے؛ کوئی بھی تبدیلی کمپریشن کی سطح کو تباہ کن طور پر گرنے کا باعث بنے گی۔ جی ہاں، لغت کا نیا ورژن بنا کر مسئلہ حل کیا جا سکتا ہے، لیکن یہ سر درد ہے - ہمیں لغت کے تمام ورژنز کو ذخیرہ کرنے کی ضرورت ہوگی۔ ہر اندراج میں ہمیں یہ بتانا ہوگا کہ لغت کے کس ورژن کے ساتھ اسے کمپریس کیا گیا تھا...
2. "کلاسیکی" الگورتھم کا استعمال کرتے ہوئے ہر ریکارڈ کو سکیڑیں، لیکن دوسروں سے آزاد۔
   زیر غور کمپریشن الگورتھم اس سائز (دسیوں بائٹس) کے ریکارڈز کے ساتھ کام کرنے کے لیے ڈیزائن نہیں کیے گئے ہیں، کمپریشن کا تناسب واضح طور پر 1 سے کم ہوگا (یعنی، کمپریس کرنے کے بجائے ڈیٹا والیوم میں اضافہ)؛
3. ہر ریکارڈنگ کے بعد فلش کریں۔
   بہت سی کمپریشن لائبریریوں کو فلش کے لیے سپورٹ حاصل ہے۔ یہ ایک کمانڈ ہے (یا کمپریشن کے طریقہ کار کا ایک پیرامیٹر)، جسے موصول ہونے پر آرکائیور ایک کمپریسڈ اسٹریم بناتا ہے تاکہ اسے بحال کرنے کے لیے استعمال کیا جا سکے۔ تمام غیر کمپریسڈ ڈیٹا جو پہلے ہی موصول ہو چکا ہے۔ ایسا ینالاگ sync فائل سسٹم میں یا commit ایس کیو ایل میں
   اہم بات یہ ہے کہ بعد میں ہونے والے کمپریشن آپریشنز جمع شدہ لغت کو استعمال کرنے کے قابل ہوں گے اور کمپریشن کا تناسب پچھلے ورژن کی طرح متاثر نہیں ہوگا۔

میرے خیال میں یہ واضح ہے کہ میں نے تیسرا آپشن منتخب کیا ہے، آئیے اسے مزید تفصیل سے دیکھتے ہیں۔

ملا بہت اچھا مضمون zlib میں فلش کے بارے میں۔

میں نے مضمون کی بنیاد پر گھٹنے کا ٹیسٹ کیا، اصلی ڈیوائس سے 70 ہزار لاگ انٹری لی، جس کا صفحہ سائز 60Kb ہے۔ (ہم بعد میں صفحہ کے سائز پر واپس آئیں گے) موصول:

ماخذ کا ڈیٹا
کمپریشن gzip -9 (کوئی فلش نہیں)
Z_PARTIAL_FLUSH کے ساتھ zlib
Z_SYNC_FLUSH کے ساتھ zlib

حجم، KB
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 ہوں گے۔ اور اگر ہم انہیں جانتے ہیں، تو ہمیں انہیں ذخیرہ کرنے کی ضرورت نہیں ہے، لہذا حتمی سائز صرف 324Kb ہے۔

جس مضمون سے میں نے لنک کیا ہے اس کی وضاحت ہے:

خالی مواد کے ساتھ ایک نئی قسم کا 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 سے پہلے اضافی صفر بائٹس کے بغیر بلاکس کا سامنا کرنا پڑے گا).

مجموعی طور پر، دستیاب ٹیسٹ ڈیٹا کا استعمال کرتے ہوئے، 250Kb سے کم کمپریسڈ ڈیٹا میں فٹ ہونا ممکن ہے۔

آپ تھوڑا سا جگلنگ کر کے کچھ اور بچا سکتے ہیں: فی الحال ہم بلاک کے آخر میں چند زیرو بٹس کی موجودگی کو نظر انداز کر دیتے ہیں، بلاک کے شروع میں کچھ بٹس بھی تبدیل نہیں ہوتے...
لیکن پھر میں نے رکنے کا پختہ ارادہ فیصلہ کیا، ورنہ اس شرح سے میں اپنا آرکائیور تیار کر سکتا ہوں۔

مجموعی طور پر، میرے ٹیسٹ ڈیٹا سے مجھے فی تحریر 3-4 بائٹس موصول ہوئے، کمپریشن کا تناسب 6:1 سے زیادہ نکلا۔ میں ایماندار رہوں گا: مجھے اس طرح کے نتیجے کی توقع نہیں تھی؛ میری رائے میں، 2:1 سے بہتر کچھ بھی پہلے سے ہی ایک نتیجہ ہے جو کمپریشن کے استعمال کا جواز پیش کرتا ہے۔

سب کچھ ٹھیک ہے، لیکن zlib (deflate) اب بھی ایک قدیم، اچھی طرح سے مستحق اور قدرے پرانے زمانے کا کمپریشن الگورتھم ہے۔ محض حقیقت یہ ہے کہ غیر کمپریسڈ ڈیٹا سٹریم کا آخری 32Kb لغت کے طور پر استعمال ہوتا ہے آج عجیب لگتا ہے (یعنی اگر کچھ ڈیٹا بلاک 40Kb پہلے ان پٹ سٹریم میں موجود تھا، تو اسے دوبارہ آرکائیو کرنا شروع ہو جائے گا، اور پچھلے واقعہ کا حوالہ نہیں دے گا)۔ فیشن ایبل جدید آرکائیورز میں، لغت کا سائز اکثر کلو بائٹس کے بجائے میگا بائٹس میں ماپا جاتا ہے۔

لہذا ہم آرکائیورز کا اپنا چھوٹا مطالعہ جاری رکھیں گے۔

اس کے بعد ہم نے bzip2 کا تجربہ کیا (یاد رکھیں، فلش کے بغیر اس نے تقریباً 100:1 کا شاندار کمپریشن تناسب دکھایا)۔ بدقسمتی سے، اس نے FLUSH کے ساتھ بہت خراب کارکردگی کا مظاہرہ کیا؛ کمپریسڈ ڈیٹا کا سائز غیر کمپریسڈ ڈیٹا سے بڑا نکلا۔

ناکامی کی وجوہات کے بارے میں میرے مفروضے۔

Libbz2 صرف ایک فلش آپشن پیش کرتا ہے، جو لگتا ہے کہ لغت کو صاف کرتا ہے (zlib میں Z_FULL_FLUSH کے مترادف ہے)؛ اس کے بعد کسی موثر کمپریشن کی کوئی بات نہیں ہے۔

اور آخری ٹیسٹ zstd تھا۔ پیرامیٹرز پر منحصر ہے، یہ یا تو gzip کی سطح پر، لیکن بہت تیز، یا gzip سے بہتر ہے۔

افسوس، فلش کے ساتھ اس نے بہت اچھی کارکردگی نہیں دکھائی: کمپریسڈ ڈیٹا کا سائز تقریباً 700Kb تھا۔

Я ایک سوال پوچھا پروجیکٹ کے گیتھب صفحہ پر، مجھے جواب ملا کہ آپ کو کمپریسڈ ڈیٹا کے ہر بلاک کے لیے 10 بائٹس تک سروس ڈیٹا پر اعتماد کرنا چاہیے، جو کہ حاصل کردہ نتائج کے قریب ہے؛ ڈیفلیٹ کو پکڑنے کا کوئی طریقہ نہیں ہے۔

میں نے آرکائیورز کے ساتھ اپنے تجربات میں اس مقام پر رکنے کا فیصلہ کیا (میں آپ کو یاد دلاتا ہوں کہ xz, lzip, lzo, lz4 فلش کے بغیر ٹیسٹنگ کے مرحلے پر بھی خود کو ظاہر نہیں کرتا تھا، اور میں نے زیادہ غیر ملکی کمپریشن الگورتھم پر غور نہیں کیا)۔

آئیے آرکائیونگ کے مسائل پر واپس آتے ہیں۔

دوسرا (جیسا کہ وہ ترتیب میں کہتے ہیں، قدر میں نہیں) مسئلہ یہ ہے کہ کمپریسڈ ڈیٹا ایک واحد سلسلہ ہے، جس میں پچھلے حصوں کے حوالے مسلسل موجود ہیں۔ اس طرح، اگر کمپریسڈ ڈیٹا کے کسی حصے کو نقصان پہنچتا ہے، تو ہم نہ صرف غیر کمپریسڈ ڈیٹا کے متعلقہ بلاک کو کھو دیتے ہیں، بلکہ اس کے بعد کے تمام کو بھی کھو دیتے ہیں۔

اس مسئلے کو حل کرنے کا ایک طریقہ ہے:

1. مسئلہ کو ہونے سے روکیں - کمپریسڈ ڈیٹا میں فالتو پن شامل کریں، جو آپ کو غلطیوں کی شناخت اور درست کرنے کی اجازت دے گا۔ ہم اس کے بارے میں بعد میں بات کریں گے؛
2. اگر کوئی مسئلہ ہوتا ہے تو نتائج کو کم سے کم کریں۔
   ہم پہلے ہی کہہ چکے ہیں کہ آپ ہر ڈیٹا بلاک کو آزادانہ طور پر کمپریس کر سکتے ہیں، اور مسئلہ خود بخود ختم ہو جائے گا (ایک بلاک کے ڈیٹا کو نقصان پہنچنے سے صرف اس بلاک کا ڈیٹا ضائع ہو جائے گا)۔ تاہم، یہ ایک انتہائی صورت ہے جس میں ڈیٹا کمپریشن غیر مؤثر ہو جائے گا. مخالف انتہا: ہماری تمام 4MB چپ کو ایک ہی آرکائیو کے طور پر استعمال کریں، جو ہمیں بہترین کمپریشن دے گا، لیکن ڈیٹا کرپٹ ہونے کی صورت میں تباہ کن نتائج۔
   ہاں، اعتبار کے معاملے میں سمجھوتہ کی ضرورت ہے۔ لیکن ہمیں یاد رکھنا چاہیے کہ ہم انتہائی کم بی ای آر کے ساتھ نان ولیٹائل میموری کے لیے ڈیٹا سٹوریج فارمیٹ تیار کر رہے ہیں اور 20 سال کی اعلان کردہ ڈیٹا اسٹوریج کی مدت ہے۔

تجربات کے دوران، میں نے دریافت کیا کہ کمپریشن لیول میں کم و بیش نمایاں نقصانات 10 KB سائز سے کم کمپریسڈ ڈیٹا کے بلاکس سے شروع ہوتے ہیں۔
یہ پہلے ذکر کیا گیا تھا کہ استعمال شدہ میموری کا صفحہ کیا جاتا ہے؛ مجھے کوئی وجہ نظر نہیں آتی کہ "ایک صفحہ - کمپریسڈ ڈیٹا کا ایک بلاک" خط و کتابت کا استعمال نہ کیا جائے۔

یعنی، کم از کم مناسب صفحہ کا سائز 16Kb ہے (سروس کی معلومات کے لیے ریزرو کے ساتھ)۔ تاہم، صفحہ کا اتنا چھوٹا سائز زیادہ سے زیادہ ریکارڈ سائز پر اہم پابندیاں عائد کرتا ہے۔

اگرچہ مجھے ابھی تک کمپریسڈ شکل میں چند کلو بائٹس سے بڑے ریکارڈز کی توقع نہیں ہے، میں نے 32Kb صفحات (کل 128 صفحات فی چپ کے لیے) استعمال کرنے کا فیصلہ کیا۔

خلاصہ:

• ہم zlib (deflate) کا استعمال کرتے ہوئے کمپریسڈ ڈیٹا کو اسٹور کرتے ہیں۔
• ہر اندراج کے لیے ہم سیٹ کرتے ہیں Z_SYNC_FLUSH؛
• ہر کمپریسڈ ریکارڈ کے لیے، ہم ٹریلنگ بائٹس کو تراشتے ہیں۔ (جیسے 0x00, 0x00, 0xff, 0xff); ہیڈر میں ہم اس بات کی نشاندہی کرتے ہیں کہ ہم نے کتنے بائٹس کو کاٹ دیا۔
• ہم 32Kb صفحات میں ڈیٹا ذخیرہ کرتے ہیں۔ صفحہ کے اندر کمپریسڈ ڈیٹا کا ایک سلسلہ ہے؛ ہر صفحے پر ہم دوبارہ کمپریشن شروع کرتے ہیں۔

اور، کمپریشن کو ختم کرنے سے پہلے، میں آپ کی توجہ اس حقیقت کی طرف مبذول کرانا چاہوں گا کہ ہمارے پاس فی ریکارڈ کمپریسڈ ڈیٹا کے صرف چند بائٹس ہیں، اس لیے یہ انتہائی اہم ہے کہ سروس کی معلومات میں اضافہ نہ کیا جائے، یہاں ہر بائٹ کا شمار ہوتا ہے۔

ڈیٹا ہیڈرز کو ذخیرہ کرنا

چونکہ ہمارے پاس متغیر طوالت کے ریکارڈ موجود ہیں، ہمیں کسی نہ کسی طرح ریکارڈز کی جگہ/حدود کا تعین کرنے کی ضرورت ہے۔

میں تین طریقوں کو جانتا ہوں:

1. تمام ریکارڈز ایک مسلسل سلسلے میں محفوظ کیے جاتے ہیں، پہلے ایک ریکارڈ ہیڈر ہوتا ہے جس میں لمبائی ہوتی ہے، اور پھر خود ہی ریکارڈ ہوتا ہے۔
   اس مجسم میں، دونوں ہیڈر اور ڈیٹا متغیر لمبائی کے ہو سکتے ہیں۔
   بنیادی طور پر، ہمیں ایک اکیلے منسلک فہرست ملتی ہے جو ہر وقت استعمال ہوتی ہے۔
2. ہیڈرز اور ریکارڈ خود الگ الگ سلسلے میں محفوظ کیے جاتے ہیں۔
   مستقل طوالت کے ہیڈر استعمال کرکے، ہم اس بات کو یقینی بناتے ہیں کہ ایک ہیڈر کو پہنچنے والا نقصان دوسرے کو متاثر نہیں کرتا ہے۔
   اسی طرح کا طریقہ استعمال کیا جاتا ہے، مثال کے طور پر، بہت سے فائل سسٹم میں؛
3. ریکارڈز کو ایک مسلسل سلسلے میں ذخیرہ کیا جاتا ہے، ریکارڈ کی حد کا تعین ایک مخصوص مارکر کے ذریعے کیا جاتا ہے (حروف کی ترتیب/حروف کی ترتیب جو ڈیٹا بلاکس کے اندر ممنوع ہے)۔ اگر ریکارڈ کے اندر کوئی مارکر ہے، تو ہم اسے کچھ ترتیب سے بدل دیتے ہیں (اسے فرار)۔
   اسی طرح کا طریقہ استعمال کیا جاتا ہے، مثال کے طور پر، پی پی پی پروٹوکول میں۔

میں مثال دوں گا۔

آپشن 1:

یہاں سب کچھ بہت آسان ہے: ریکارڈ کی لمبائی کو جانتے ہوئے، ہم اگلے ہیڈر کے ایڈریس کا حساب لگا سکتے ہیں۔ لہٰذا ہم سرخیوں کے ذریعے اس وقت تک آگے بڑھتے ہیں جب تک کہ ہمیں 0xff (مفت علاقہ) یا صفحہ کے آخر میں بھرے ہوئے علاقے کا سامنا نہ ہو۔

آپشن 2:

متغیر ریکارڈ کی لمبائی کی وجہ سے، ہم پہلے سے نہیں کہہ سکتے کہ ہمیں فی صفحہ کتنے ریکارڈز (اور اس وجہ سے ہیڈرز) کی ضرورت ہوگی۔ آپ خود ہی ہیڈر اور ڈیٹا کو مختلف صفحات پر پھیلا سکتے ہیں، لیکن میں ایک مختلف نقطہ نظر کو ترجیح دیتا ہوں: ہم ہیڈر اور ڈیٹا دونوں کو ایک صفحے پر رکھتے ہیں، لیکن ہیڈر (مستقل سائز کے) صفحہ کے شروع سے آتے ہیں، اور ڈیٹا (متغیر لمبائی کا) آخر سے آتا ہے۔ جیسے ہی وہ "ملتے ہیں" (نئی اندراج کے لیے کافی خالی جگہ نہیں ہے)، ہم اس صفحہ کو مکمل سمجھتے ہیں۔

آپشن 3:

ہیڈر میں اعداد و شمار کے مقام کے بارے میں لمبائی یا دیگر معلومات کو ذخیرہ کرنے کی ضرورت نہیں ہے؛ ریکارڈ کی حدود کی نشاندہی کرنے والے مارکر کافی ہیں۔ تاہم، لکھتے/پڑھتے وقت ڈیٹا پر کارروائی کرنی پڑتی ہے۔
میں 0xff بطور مارکر استعمال کروں گا (جو صفحہ کو مٹانے کے بعد بھرتا ہے)، لہذا مفت علاقے کو یقینی طور پر ڈیٹا کے طور پر نہیں سمجھا جائے گا۔

موازنہ کی میز:

اختیار 1
اختیار 2
اختیار 3

غلطی کی رواداری
-
+
+

کومپیکٹینس۔
+
-
+

نفاذ کی پیچیدگی
*
**
**

آپشن 1 میں ایک مہلک خامی ہے: اگر ہیڈروں میں سے کسی کو نقصان پہنچا ہے، تو اس کے بعد کی پوری چین تباہ ہو جاتی ہے۔ باقی آپشنز آپ کو بڑے پیمانے پر نقصان کی صورت میں بھی کچھ ڈیٹا بازیافت کرنے کی اجازت دیتے ہیں۔
لیکن یہاں یہ یاد رکھنا مناسب ہے کہ ہم نے ڈیٹا کو کمپریسڈ شکل میں ذخیرہ کرنے کا فیصلہ کیا ہے، اور اس لیے ہم صفحہ پر موجود تمام ڈیٹا کو "ٹوٹے" ریکارڈ کے بعد کھو دیتے ہیں، اس لیے ٹیبل میں مائنس ہونے کے باوجود ہم ایسا نہیں کرتے۔ اسے مدنظر رکھیں.

کومپیکٹنس:

• پہلے آپشن میں، ہمیں ہیڈر میں صرف لمبائی کو ذخیرہ کرنے کی ضرورت ہے؛ اگر ہم متغیر لمبائی والے عدد استعمال کریں، تو زیادہ تر صورتوں میں ہم ایک بائٹ کے ساتھ حاصل کر سکتے ہیں۔
• دوسرے آپشن میں ہمیں ابتدائی پتہ اور لمبائی ذخیرہ کرنے کی ضرورت ہے۔ ریکارڈ کا سائز مستقل ہونا چاہیے، میں فی ریکارڈ 4 بائٹس کا تخمینہ لگاتا ہوں (آفسیٹ کے لیے دو بائٹس، اور لمبائی کے لیے دو بائٹس)؛
• تیسرے آپشن کو ریکارڈنگ کے آغاز کی نشاندہی کرنے کے لیے صرف ایک کردار کی ضرورت ہے، نیز شیلڈنگ کی وجہ سے ریکارڈنگ میں 1-2% اضافہ ہوگا۔ عام طور پر، پہلے اختیار کے ساتھ تقریبا برابری.

شروع میں، میں نے دوسرے آپشن کو اہم سمجھا (اور عمل درآمد بھی لکھا)۔ میں نے اسے تب ہی چھوڑ دیا جب میں نے آخر کار کمپریشن استعمال کرنے کا فیصلہ کیا۔

شاید کسی دن میں اب بھی اسی طرح کا آپشن استعمال کروں گا۔ مثال کے طور پر، اگر مجھے زمین اور مریخ کے درمیان سفر کرنے والے جہاز کے لیے ڈیٹا سٹوریج سے نمٹنا ہے، تو وشوسنییتا، کائناتی تابکاری، ... کے لیے بالکل مختلف تقاضے ہوں گے۔

جہاں تک تیسرے آپشن کا تعلق ہے: میں نے اس پر عمل درآمد کی دشواری کے لیے اسے دو ستارے صرف اس لیے دیے کہ مجھے شیلڈنگ، عمل کی لمبائی کو تبدیل کرنا وغیرہ پسند نہیں۔ ہاں، شاید میں متعصب ہوں، لیکن مجھے کوڈ لکھنا پڑے گا - کیوں اپنے آپ کو ایسا کرنے پر مجبور کریں جو آپ کو پسند نہیں ہے۔

خلاصہ: ہم زنجیروں کی شکل میں اسٹوریج آپشن کا انتخاب کرتے ہیں "لمبائی کے ساتھ ہیڈر - متغیر لمبائی کا ڈیٹا" کارکردگی اور عمل میں آسانی کی وجہ سے۔

تحریری کارروائیوں کی کامیابی کی نگرانی کے لیے بٹ فیلڈز کا استعمال

مجھے اب یاد نہیں ہے کہ مجھے یہ خیال کہاں سے آیا، لیکن یہ کچھ اس طرح لگتا ہے:
ہر اندراج کے لیے، ہم جھنڈوں کو ذخیرہ کرنے کے لیے کئی بٹس مختص کرتے ہیں۔
جیسا کہ ہم نے پہلے کہا، مٹانے کے بعد تمام بٹس 1s سے بھر جاتے ہیں، اور ہم 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

ایسا لگتا ہے کہ سب کچھ آسان ہے - محفوظ کیے جانے والے ڈیٹا کی لمبائی پر منحصر ہے، کم از کم غلط مثبتات کے ساتھ چیکسم کی لمبائی کا انتخاب کریں - اور چال بیگ میں ہے۔

تاہم، مختصر چیکسم کے ساتھ ایک مسئلہ پیدا ہوتا ہے: اگرچہ وہ سنگل بٹ کی غلطیوں کا پتہ لگانے میں اچھے ہیں، لیکن وہ کافی زیادہ امکان کے ساتھ مکمل طور پر بے ترتیب ڈیٹا کو درست تسلیم کر سکتے ہیں۔ Habré پر ایک مضمون پہلے ہی بیان کر چکا تھا۔ حقیقی زندگی میں مسئلہ.

لہذا، بے ترتیب چیکسم میچ کو تقریباً ناممکن بنانے کے لیے، آپ کو ایسے چیکسم استعمال کرنے کی ضرورت ہے جن کی لمبائی 32 بٹس یا اس سے زیادہ ہو۔ (64 بٹس سے زیادہ لمبائی کے لیے، عام طور پر کرپٹوگرافک ہیش فنکشنز استعمال کیے جاتے ہیں).

اس حقیقت کے باوجود کہ میں نے پہلے لکھا تھا کہ ہمیں ہر طرح سے جگہ بچانے کی ضرورت ہے، ہم پھر بھی 32 بٹ چیکسم استعمال کریں گے (16 بٹس کافی نہیں ہیں، تصادم کا امکان 0.01٪ سے زیادہ ہے؛ اور 24 بٹس، جیسا کہ وہ کہو، نہ یہاں ہیں نہ وہاں)۔

یہاں ایک اعتراض پیدا ہوسکتا ہے: کیا ہم نے کمپریشن کا انتخاب کرتے وقت ہر بائٹ کو محفوظ کیا تھا تاکہ اب ایک ساتھ 4 بائٹس دیں؟ کیا یہ بہتر نہیں ہوگا کہ چیکسم کو کمپریس یا شامل نہ کیا جائے؟ بالکل نہیں، کوئی کمپریشن نہیں۔ مطلب نہیں، کہ ہمیں سالمیت کی جانچ کی ضرورت نہیں ہے۔

کثیر نام کا انتخاب کرتے وقت، ہم پہیے کو دوبارہ نہیں بنائیں گے، لیکن اب مقبول CRC-32C لیں گے۔
یہ کوڈ 6 بائٹس تک کے پیکٹوں پر 22 بٹ کی خرابیوں کا پتہ لگاتا ہے (شاید ہمارے لیے یہ سب سے عام معاملہ ہے)، 4 بائٹس تک کے پیکٹوں پر 655 بٹ کی خرابیاں (ہمارے لیے ایک عام معاملہ بھی ہے)، 2 یا پیکٹوں پر کسی بھی عجیب تعداد میں بٹ کی خرابی کسی بھی معقول لمبائی کے۔

اگر کسی کو تفصیلات میں دلچسپی ہے۔

ویکیپیڈیا مضمون CRC کے بارے میں

کوڈ پیرامیٹرز crc-32c پر کوپ مین ویب سائٹ - شاید سیارے پر معروف CRC ماہر۔

В اس کا مضمون وہاں ہے ایک اور دلچسپ کوڈ، جو پیکٹ کی لمبائی کے لیے قدرے بہتر پیرامیٹرز فراہم کرتا ہے جو ہمارے لیے متعلقہ ہیں، لیکن میں نے اس فرق کو اہم نہیں سمجھا، اور میں معیاری اور اچھی طرح سے تحقیق شدہ کی بجائے حسب ضرورت کوڈ کا انتخاب کرنے کے لیے کافی حد تک اہل تھا۔

نیز، چونکہ ہمارا ڈیٹا کمپریسڈ ہے، اس لیے سوال پیدا ہوتا ہے: کیا ہمیں کمپریسڈ یا غیر کمپریسڈ ڈیٹا کے چیک سم کا حساب لگانا چاہیے؟

غیر کمپریسڈ ڈیٹا کے چیک سم کا حساب لگانے کے حق میں دلائل:

• ہمیں بالآخر ڈیٹا اسٹوریج کی حفاظت کو چیک کرنے کی ضرورت ہے - لہذا ہم اسے براہ راست چیک کرتے ہیں (ایک ہی وقت میں، کمپریشن/ڈیکمپریشن کے نفاذ میں ممکنہ خرابیاں، ٹوٹی ہوئی میموری کی وجہ سے ہونے والے نقصان وغیرہ کی جانچ کی جائے گی)؛
• zlib میں deflate الگورتھم کا نفاذ کافی حد تک پختہ ہے اور نہیں کرنا چاہئے۔ "ٹیڑھی" ان پٹ ڈیٹا کے ساتھ گرنا؛ مزید یہ کہ، یہ اکثر ان پٹ اسٹریم میں غلطیوں کا پتہ لگانے کے قابل ہوتا ہے، جس سے غلطی کا پتہ نہ لگنے کے مجموعی امکان کو کم کیا جاتا ہے (ایک مختصر ریکارڈ میں ایک بٹ کو الٹ کر ٹیسٹ کیا گیا، zlib نے غلطی کا پتہ لگایا تقریباً ایک تہائی معاملات میں)۔

غیر کمپریسڈ ڈیٹا کے چیکسم کا حساب لگانے کے خلاف دلائل:

• سی آر سی خاص طور پر ان چند چھوٹی غلطیوں کے لیے "مطابق" بنایا گیا ہے جو فلیش میموری کی خصوصیت ہیں (کمپریسڈ سٹریم میں تھوڑی سی خرابی آؤٹ پٹ سٹریم میں بڑے پیمانے پر تبدیلی کا باعث بن سکتی ہے، جس پر خالصتاً نظریاتی طور پر، ہم تصادم کو "پکڑ" سکتے ہیں)؛
• مجھے ممکنہ طور پر ٹوٹے ہوئے ڈیٹا کو ڈیکمپریسر کو منتقل کرنے کا خیال پسند نہیں ہے، کسے پتاوہ کس طرح ردعمل کرے گا.

اس پروجیکٹ میں، میں نے غیر کمپریسڈ ڈیٹا کے چیک سم کو اسٹور کرنے کے عام طور پر قبول شدہ عمل سے انحراف کرنے کا فیصلہ کیا۔

خلاصہ: ہم CRC-32C استعمال کرتے ہیں، ہم اس فارم میں ڈیٹا سے چیکسم کا حساب لگاتے ہیں جس میں وہ فلیش کے لیے لکھے جاتے ہیں (کمپریشن کے بعد)۔

فالتو پن

بے کار کوڈنگ کا استعمال، یقیناً، ڈیٹا کے نقصان کو ختم نہیں کرتا، تاہم، یہ نمایاں طور پر (اکثر وسعت کے بہت سے آرڈرز کے ذریعے) ناقابل واپسی ڈیٹا کے نقصان کے امکان کو کم کر سکتا ہے۔

ہم غلطیوں کو درست کرنے کے لیے مختلف قسم کے فالتو پن کا استعمال کر سکتے ہیں۔
ہیمنگ کوڈز سنگل بٹ کی غلطیوں کو درست کر سکتے ہیں، Reed-Solomon کریکٹر کوڈز، چیکسم کے ساتھ مل کر ڈیٹا کی متعدد کاپیاں، یا RAID-6 جیسی انکوڈنگز بڑے پیمانے پر بدعنوانی کی صورت میں بھی ڈیٹا کو بازیافت کرنے میں مدد کر سکتی ہیں۔
شروع میں، میں ایرر ریزسٹنٹ کوڈنگ کے وسیع پیمانے پر استعمال کے لیے پرعزم تھا، لیکن پھر میں نے محسوس کیا کہ ہمیں پہلے اس بات کا اندازہ ہونا چاہیے کہ ہم کن غلطیوں سے خود کو بچانا چاہتے ہیں، اور پھر کوڈنگ کا انتخاب کریں۔

ہم نے پہلے کہا تھا کہ غلطیوں کو جلد از جلد پکڑنے کی ضرورت ہے۔ کن نکات پر ہم غلطیوں کا سامنا کر سکتے ہیں؟

1. نامکمل ریکارڈنگ (ریکارڈنگ کے وقت کسی وجہ سے پاور آف کر دی گئی، راسبیری جم گئی، ...)
   افسوس، ایسی خرابی کی صورت میں، صرف غلط ریکارڈوں کو نظر انداز کرنا اور ڈیٹا کے ضائع ہونے پر غور کرنا باقی رہ جاتا ہے۔
2. غلطیاں لکھیں (کسی وجہ سے، فلیش میموری میں جو لکھا گیا تھا وہ نہیں تھا)
   اگر ہم ریکارڈنگ کے فوراً بعد ٹیسٹ پڑھتے ہیں تو ہم ایسی غلطیوں کا فوری پتہ لگا سکتے ہیں۔
3. اسٹوریج کے دوران میموری میں ڈیٹا کی تحریف؛
4. پڑھنے کی غلطیاں
   اسے درست کرنے کے لیے، چیکسم کی عدم مماثلت کی صورت میں پڑھنے کو کئی بار دہرانا کافی ہے۔

یعنی صرف تیسری قسم کی غلطیاں (ذخیرہ کرنے کے دوران ڈیٹا کی بے ساختہ بدعنوانی) کو ایرر ریزسٹنٹ کوڈنگ کے بغیر درست نہیں کیا جا سکتا۔ ایسا لگتا ہے کہ ایسی غلطیاں اب بھی بہت کم ہیں۔

خلاصہ: بے کار کوڈنگ کو ترک کرنے کا فیصلہ کیا گیا تھا، لیکن اگر آپریشن اس فیصلے کی غلطی کو ظاہر کرتا ہے، تو اس مسئلے پر غور کرنے پر واپس جائیں (ناکامیوں پر پہلے سے جمع شدہ اعدادوشمار کے ساتھ، جو کوڈنگ کی بہترین قسم کا انتخاب کرنے کی اجازت دے گا)۔

دیگر

بلاشبہ، مضمون کی شکل ہمیں اس بات کی اجازت نہیں دیتی کہ ہم ہر ایک کو فارمیٹ میں درست ثابت کریں۔ (اور میری طاقت ختم ہو چکی ہے)، لہذا میں مختصر طور پر کچھ نکات پر جاؤں گا جن کو پہلے چھوا نہیں گیا تھا۔

• تمام صفحات کو "برابر" کرنے کا فیصلہ کیا گیا۔
  یعنی میٹا ڈیٹا، علیحدہ تھریڈز وغیرہ کے ساتھ کوئی خاص صفحہ نہیں ہوگا، بلکہ اس کے بجائے ایک ہی تھریڈ ہوگا جو تمام صفحات کو باری باری لکھتا ہے۔
  یہ یقینی بناتا ہے کہ صفحات پر بھی پہننا، ناکامی کا کوئی ایک نقطہ، اور مجھے یہ پسند ہے۔
• فارمیٹ کا ورژن فراہم کرنا ضروری ہے۔
  ہیڈر میں ورژن نمبر کے بغیر فارمیٹ برا ہے!
  صفحہ کے ہیڈر میں ایک مخصوص میجک نمبر (دستخط) کے ساتھ فیلڈ شامل کرنا کافی ہے، جو استعمال شدہ فارمیٹ کے ورژن کی نشاندہی کرے گا۔ (مجھے نہیں لگتا کہ عملی طور پر ان میں سے ایک درجن بھی ہوں گے);
• ریکارڈز کے لیے متغیر کی لمبائی والا ہیڈر استعمال کریں (جن میں سے بہت کچھ ہے)، زیادہ تر معاملات میں اسے 1 بائٹ لمبا کرنے کی کوشش کریں؛
• ہیڈر کی لمبائی اور کمپریسڈ ریکارڈ کے تراشے ہوئے حصے کی لمبائی کو انکوڈ کرنے کے لیے، متغیر لمبائی والے بائنری کوڈز استعمال کریں۔

بہت مدد کی۔ آن لائن جنریٹر ہف مین کوڈز۔ صرف چند منٹوں میں ہم مطلوبہ متغیر لمبائی کے کوڈز کو منتخب کرنے میں کامیاب ہو گئے۔

ڈیٹا اسٹوریج فارمیٹ کی تفصیل

بائٹ آرڈر

ایک بائٹ سے بڑی فیلڈز کو بگ اینڈین فارمیٹ (نیٹ ورک بائٹ آرڈر) میں محفوظ کیا جاتا ہے، یعنی 0x1234 کو 0x12، 0x34 لکھا جاتا ہے۔

صفحہ بندی

تمام فلیش میموری کو برابر سائز کے صفحات میں تقسیم کیا گیا ہے۔

پہلے سے طے شدہ صفحہ کا سائز 32Kb ہے، لیکن میموری چپ کے کل سائز کے 1/4 سے زیادہ نہیں (4MB چپ کے لیے، 128 صفحات حاصل کیے جاتے ہیں)۔

ہر صفحہ ڈیٹا کو دوسروں سے آزادانہ طور پر اسٹور کرتا ہے (یعنی ایک صفحہ پر موجود ڈیٹا دوسرے صفحے پر ڈیٹا کا حوالہ نہیں دیتا)۔

تمام صفحات کو فطری ترتیب میں نمبر دیا گیا ہے (پتوں کی صعودی ترتیب میں)، نمبر 0 سے شروع ہوتا ہے (صفحہ صفر ایڈریس 0 سے شروع ہوتا ہے، پہلا صفحہ 32Kb سے شروع ہوتا ہے، دوسرا صفحہ 64Kb سے شروع ہوتا ہے، وغیرہ)

میموری چپ کو سائکلک بفر (رنگ بفر) کے طور پر استعمال کیا جاتا ہے، یعنی پہلے تحریر صفحہ نمبر 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
ہیڈر کی لمبائی، بائٹس
لکھنے، بائٹ پر رد کر دیا گیا۔

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 فلیش سے پڑھے ہوئے کو کیش نہیں کرتا، ٹیسٹ کیا گیا)

فلیش میموری پر لکھیں۔

ہم ڈیٹا ریکارڈ کرتے ہیں۔
آئیے انہیں پڑھیں۔

اگر پڑھا ہوا ڈیٹا تحریری ڈیٹا سے میل نہیں کھاتا ہے، تو ہم اس علاقے کو صفر سے بھرتے ہیں اور غلطی کا اشارہ دیتے ہیں۔

آپریشن کے لیے ایک نئے مائیکرو سرکٹ کی تیاری

ابتداء کے لیے، ورژن 1 والا ہیڈر پہلے (یا بلکہ صفر) صفحہ پر لکھا جاتا ہے۔
اس کے بعد، ابتدائی سیاق و سباق اس صفحہ پر لکھا جاتا ہے (مشین کا UUID اور پہلے سے طے شدہ ترتیبات پر مشتمل ہوتا ہے)۔

بس، فلیش میموری استعمال کے لیے تیار ہے۔

مشین لوڈ ہو رہی ہے۔

لوڈ کرتے وقت، ہر صفحہ کے پہلے 8 بائٹس (ہیڈر + CRC) پڑھے جاتے ہیں، نامعلوم میجک نمبر والے صفحات یا غلط CRC کو نظر انداز کر دیا جاتا ہے۔
"درست" صفحات سے، زیادہ سے زیادہ ورژن والے صفحات کو منتخب کیا جاتا ہے، اور سب سے زیادہ نمبر والا صفحہ ان سے لیا جاتا ہے۔
پہلا ریکارڈ پڑھا جاتا ہے، CRC کی درستگی اور "سیاق و سباق" پرچم کی موجودگی کی جانچ کی جاتی ہے۔ اگر سب کچھ ٹھیک ہے، تو اس صفحہ کو موجودہ سمجھا جاتا ہے۔ اگر نہیں، تو ہم پچھلے والے پر واپس چلے جاتے ہیں جب تک کہ ہمیں "لائیو" صفحہ نہیں مل جاتا۔
اور پائے گئے صفحہ پر ہم تمام ریکارڈز پڑھتے ہیں، جو ہم "سیاق و سباق" کے جھنڈے کے ساتھ استعمال کرتے ہیں۔
zlib ڈکشنری کو محفوظ کریں (اس صفحہ میں شامل کرنے کے لیے اس کی ضرورت ہوگی)۔

بس، ڈاؤن لوڈ مکمل ہو گیا، سیاق و سباق بحال ہو گیا، آپ کام کر سکتے ہیں۔

جرنل اندراج شامل کرنا

ہم Z_SYNC_FLUSH کی وضاحت کرتے ہوئے درست لغت کے ساتھ ریکارڈ کو کمپریس کرتے ہیں۔ ہم دیکھتے ہیں کہ کیا کمپریسڈ ریکارڈ موجودہ صفحہ پر فٹ بیٹھتا ہے۔
اگر یہ فٹ نہیں ہے (یا صفحہ پر CRC کی غلطیاں تھیں)، ایک نیا صفحہ شروع کریں (نیچے دیکھیں)۔
ہم ریکارڈ اور CRC لکھتے ہیں۔ اگر کوئی غلطی ہو جائے تو نیا صفحہ شروع کریں۔

نیا صفحہ

ہم کم از کم تعداد کے ساتھ ایک مفت صفحہ منتخب کرتے ہیں (ہم ایک مفت صفحہ کو ہیڈر میں غلط چیکسم کے ساتھ یا موجودہ سے کم ورژن والا صفحہ سمجھتے ہیں)۔ اگر ایسے صفحات نہیں ہیں، تو ان میں سے کم از کم نمبر والا صفحہ منتخب کریں جن کا موجودہ ورژن کے برابر ورژن ہو۔
ہم منتخب صفحہ کو مٹا دیتے ہیں۔ ہم مواد کو 0xff کے ساتھ چیک کرتے ہیں۔ اگر کچھ غلط ہے، تو اگلا مفت صفحہ لے لو، وغیرہ۔
ہم مٹائے گئے صفحہ پر ایک ہیڈر لکھتے ہیں، پہلی اندراج سیاق و سباق کی موجودہ حالت ہے، اگلی غیر تحریری لاگ انٹری ہے (اگر کوئی ہے)۔

فارمیٹ قابل اطلاق

میری رائے میں، یہ NOR فلیش میں کسی بھی زیادہ یا کم دبانے والی معلومات کے سلسلے (سادہ متن، JSON، MessagePack، CBOR، ممکنہ طور پر protobuf) کو ذخیرہ کرنے کے لیے ایک اچھا فارمیٹ ثابت ہوا۔

بلاشبہ، فارمیٹ SLC اور نہ ہی فلیش کے لیے "مطابق" ہے۔

اسے اعلی BER میڈیا جیسے NAND یا MLC NOR کے ساتھ استعمال نہیں کیا جانا چاہئے۔ (کیا ایسی میموری فروخت کے لیے بھی دستیاب ہے؟ میں نے صرف اصلاحی کوڈز کے کاموں میں اس کا ذکر دیکھا ہے).

مزید یہ کہ، اسے ان آلات کے ساتھ استعمال نہیں کیا جانا چاہیے جن کا اپنا FTL ہے: USB فلیش، SD، MicroSD، وغیرہ (اس طرح کی میموری کے لیے میں نے 512 بائٹس کے صفحے کے سائز کے ساتھ ایک فارمیٹ بنایا، ہر صفحے کے شروع میں ایک دستخط اور منفرد ریکارڈ نمبرز - بعض اوقات سادہ ترتیب وار پڑھنے کے ذریعے "گلیچڈ" فلیش ڈرائیو سے تمام ڈیٹا کو بازیافت کرنا ممکن ہوتا تھا).

کاموں پر منحصر ہے، فارمیٹ کو فلیش ڈرائیوز پر 128Kbit (16Kb) سے 1Gbit (128MB) تک تبدیلیوں کے بغیر استعمال کیا جا سکتا ہے۔ اگر آپ چاہیں تو، آپ اسے بڑے چپس پر استعمال کر سکتے ہیں، لیکن آپ کو شاید صفحہ کا سائز ایڈجسٹ کرنے کی ضرورت ہے۔ (لیکن یہاں معاشی فزیبلٹی کا سوال پہلے ہی پیدا ہوتا ہے؛ بڑے حجم اور نہ ہی فلیش کی قیمت حوصلہ افزا نہیں ہے).

اگر کسی کو فارمیٹ دلچسپ لگتا ہے اور وہ اسے کسی اوپن پروجیکٹ میں استعمال کرنا چاہتا ہے تو لکھیں، میں کوشش کروں گا کہ وقت تلاش کروں، کوڈ کو پالش کروں اور گیتھب پر پوسٹ کروں۔

حاصل يہ ہوا

جیسا کہ آپ دیکھ سکتے ہیں، آخر میں فارمیٹ سادہ نکلا۔ اور یہاں تک کہ بورنگ.

ایک مضمون میں اپنے نقطہ نظر کے ارتقاء کی عکاسی کرنا مشکل ہے، لیکن مجھ پر یقین کریں: شروع میں میں کوئی ایسی نفیس، ناقابلِ تباہی پیدا کرنا چاہتا تھا، جو قریب میں ہونے والے جوہری دھماکے سے بھی بچنے کے قابل ہو۔ تاہم، وجہ (مجھے امید ہے) پھر بھی جیت گئی اور دھیرے دھیرے ترجیحات سادگی اور کمپیکٹ پن کی طرف منتقل ہو گئیں۔

کیا یہ ہو سکتا ہے کہ میں غلط تھا؟ ہاں بالکل. یہ اچھی طرح سے نکل سکتا ہے، مثال کے طور پر، کہ ہم نے کم معیار کے مائیکرو سرکٹس کا ایک بیچ خریدا ہے۔ یا کسی اور وجہ سے سامان وشوسنییتا کی توقعات کو پورا نہیں کرے گا۔

کیا میرے پاس اس کے لیے کوئی منصوبہ ہے؟ میرا خیال ہے کہ مضمون پڑھنے کے بعد آپ کو کوئی شک نہیں ہوگا کہ کوئی منصوبہ ہے۔ اور اکیلا بھی نہیں۔

قدرے زیادہ سنجیدہ نوٹ پر، فارمیٹ کو ایک ورکنگ آپشن اور "ٹرائل بیلون" دونوں کے طور پر تیار کیا گیا تھا۔

اس وقت میز پر سب کچھ ٹھیک کام کر رہا ہے، لفظی طور پر دوسرے دن حل تعینات کیا جائے گا (تقریباً) سینکڑوں آلات پر، آئیے دیکھتے ہیں کہ "جنگی" آپریشن میں کیا ہوتا ہے (خوش قسمتی سے، مجھے امید ہے کہ فارمیٹ آپ کو ناکامیوں کا قابل اعتماد طریقے سے پتہ لگانے کی اجازت دیتا ہے؛ تاکہ آپ مکمل اعدادوشمار جمع کر سکیں)۔ چند ماہ میں نتیجہ اخذ کرنا ممکن ہو جائے گا۔ (اور اگر آپ بدقسمت ہیں تو پہلے بھی).

اگر، استعمال کے نتائج کی بنیاد پر، سنگین مسائل دریافت ہوتے ہیں اور بہتری کی ضرورت ہوتی ہے، تو میں اس کے بارے میں ضرور لکھوں گا.

ادب

میں استعمال شدہ کاموں کی ایک لمبی تھکا دینے والی فہرست نہیں بنانا چاہتا تھا؛ سب کے بعد، ہر کسی کے پاس گوگل ہے۔

یہاں میں نے ان نتائج کی ایک فہرست چھوڑنے کا فیصلہ کیا جو میرے لیے خاصے دلچسپ لگ رہے تھے، لیکن آہستہ آہستہ وہ براہ راست مضمون کے متن میں منتقل ہو گئے، اور ایک چیز فہرست میں رہ گئی:

1. افادیت۔ infgen مصنف zlib سے. deflate/zlib/gzip آرکائیوز کے مواد کو واضح طور پر ظاہر کر سکتا ہے۔ اگر آپ کو deflate (یا gzip) فارمیٹ کے اندرونی ڈھانچے سے نمٹنا ہے تو میں اس کی انتہائی سفارش کرتا ہوں۔

ماخذ: www.habr.com