ضغط عالي السرعة وآمن من الفشل (تابع)

هذه المقالة هي بالفعل الثانية في موضوع ضغط البيانات عالي السرعة. وصفت المقالة الأولى الضاغط الذي يعمل بسرعة 10 جيجابايت/ثانية. لكل نواة المعالج (الحد الأدنى من الضغط، RTT-Min).

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

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

يوفر الضاغط الذي يطبق خوارزمية RTT-Mid نسبة ضغط قابلة للمقارنة بأجهزة الأرشيف القياسية مثل WinRar و7-Zip، التي تعمل في الوضع عالي السرعة. وفي الوقت نفسه، تكون سرعة تشغيلها أعلى على الأقل من حيث الحجم.

تعد سرعة تعبئة/تفريغ البيانات معلمة مهمة تحدد نطاق تطبيق تقنيات الضغط. من غير المحتمل أن يفكر أي شخص في ضغط تيرابايت من البيانات بسرعة 10-15 ميجابايت في الثانية (هذه هي بالضبط سرعة الأرشيف في وضع الضغط القياسي)، لأنه سيستغرق الأمر ما يقرب من عشرين ساعة مع التحميل الكامل للمعالج. .

ومن ناحية أخرى، يمكن نسخ نفس التيرابايت بسرعات تصل إلى 2-3 جيجا بايت في الثانية خلال حوالي عشر دقائق.

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

لا يمكن للضواغط الحديثة إنتاج مثل هذه السرعات إلا في الوضع "السريع". في هذا الوضع الحالي سنقوم بمقارنة خوارزمية RTT-Mid مع الضواغط التقليدية.

اختبار مقارن لخوارزمية الضغط الجديدة

يعمل الضاغط RTT-Mid كجزء من برنامج الاختبار. في التطبيق "العامل" الحقيقي، يعمل بشكل أسرع بكثير، ويستخدم تعدد مؤشرات الترابط بحكمة ويستخدم مترجمًا "عاديًا"، وليس C#.

بما أن الضواغط المستخدمة في الاختبار المقارن مبنية على مبادئ مختلفة وأنواع مختلفة من البيانات تضغط بشكل مختلف، ومن أجل موضوعية الاختبار، تم استخدام طريقة قياس “متوسط ​​درجة الحرارة في المستشفى”...

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

هنا ملف التفريغ:

تم ضغط ملف التفريغ باستخدام ضواغط PTT-Mid و7-zip وWinRar. تم ضبط ضاغط WinRar و7-zip على السرعة القصوى.

تشغيل الضاغط 7 زيب:

يقوم بتحميل المعالج بنسبة 100%، بينما يبلغ متوسط ​​سرعة قراءة التفريغ الأصلي حوالي 60 ميجابايت/ثانية.

تشغيل الضاغط برنامج WinRAR:

الوضع مشابه، يبلغ حمل المعالج 100٪ تقريبًا، ويبلغ متوسط ​​سرعة قراءة التفريغ حوالي 125 ميجابايت / ثانية.

كما في الحالة السابقة، فإن سرعة الأرشفة محدودة بقدرات المعالج.

برنامج اختبار الضاغط قيد التشغيل الآن RTT-منتصف:

توضح لقطة الشاشة أن المعالج محمل بنسبة 50% ويكون خاملاً بقية الوقت، لأنه لا يوجد مكان لتحميل البيانات المضغوطة. تم تحميل قرص تحميل البيانات (القرص 0) بالكامل تقريبًا. تختلف سرعة قراءة البيانات (القرص 1) بشكل كبير، ولكنها في المتوسط ​​تزيد عن 200 ميجابايت/ثانية.

تقتصر سرعة الضاغط في هذه الحالة على القدرة على كتابة البيانات المضغوطة على القرص 0.

الآن نسبة الضغط للأرشيفات الناتجة:

يمكن ملاحظة أن ضاغط RTT-Mid قام بأفضل وظيفة في الضغط؛ كان الأرشيف الذي أنشأه أصغر بمقدار 1,3 جيجا بايت من أرشيف WinRar و2,1 جيجا بايت أصغر من أرشيف 7z.

الوقت المستغرق في إنشاء الأرشيف:

• 7-زيب - 26 دقيقة و10 ثوانٍ؛
• برنامج WinRar - 17 دقيقة و40 ثانية؛
• RTT-Mid – 7 دقائق و30 ثانية.

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

أولئك الذين لا يصدقون لقطات الشاشة يمكنهم التحقق من صحتها بأنفسهم. برنامج الاختبار متاح في صلة، قم بالتنزيل والتحقق.

لكن فقط على المعالجات التي تدعم AVX-2، بدون دعم هذه التعليمات لا يعمل الضاغط، ولا تختبر الخوارزمية على معالجات AMD الأقدم، فهي بطيئة من حيث تنفيذ تعليمات AVX...

طريقة الضغط المستخدمة

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

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

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

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

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

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

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

كل هذا جعل من الممكن الحصول في ضاغط PTT-Mid على نسبة ضغط مماثلة للضواغط المصنوعة باستخدام طريقة القاموس، ولكنها تعمل بشكل أسرع بكثير.

سرعة خوارزمية الضغط الجديدة

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

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

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

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

نتحدث في جميع أنحاء النص في المقالة عن الضغط، ويبقى فك الضغط خارج نطاق هذه المقالة حيث أن “كل شيء مغطى بالشوكولاتة”. يعد إلغاء الضغط أسرع بكثير ويقتصر على سرعة الإدخال/الإخراج. يوفر نواة مادية واحدة في مؤشر ترابط واحد سرعات تفريغ تبلغ 3-4 جيجابايت/ثانية بسهولة.

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

موثوقية تخزين البيانات المضغوطة

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

أثناء التخزين، تفقد وسائط التخزين بعض البيانات، إليك مثال على ذلك:

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

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

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

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

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

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

من المستحيل استعادة المعلومات من هذا الأرشيف "المكسور".

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

• حقل نص مصدر مع إزالة المقاطع المتكررة منه؛
• حقل الفهرس.

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

عيوب الخوارزمية

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

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

مثل هذه السرعات المنخفضة غير مقبولة لأنظمة تخزين البيانات الحديثة وهي ذات أهمية "أكاديمية" أكثر من كونها عملية.

سيتم زيادة درجة ضغط المعلومات بشكل كبير في التعديل التالي لخوارزمية RTT (RTT-Max)، والتي هي قيد التطوير بالفعل.

لذلك، كما هو الحال دائما، لنواصل...

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