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

این مقاله در حال حاضر دومین مقاله در موضوع فشرده سازی داده با سرعت بالا است. مقاله اول یک کمپرسور را توضیح داد که با سرعت 10 گیگابایت بر ثانیه کار می کند. در هر هسته پردازنده (حداقل فشرده سازی، RTT-Min).

این کمپرسور قبلاً در تجهیزات کپی‌کننده‌های پزشکی قانونی برای فشرده‌سازی سریع رسانه‌های ذخیره‌سازی و افزایش قدرت رمزنگاری پیاده‌سازی شده است؛ همچنین می‌توان از آن برای فشرده‌سازی تصاویر ماشین‌های مجازی و فایل‌های تعویض رم در هنگام ذخیره آن‌ها در سرعت بالا استفاده کرد. درایوهای SSD

مقاله اول همچنین توسعه یک الگوریتم فشرده‌سازی را برای فشرده‌سازی نسخه‌های پشتیبان از درایوهای دیسک HDD و SSD (فشرده‌سازی متوسط، RTT-Mid) با پارامترهای فشرده‌سازی داده‌ها به‌طور قابل توجهی اعلام کرد. در حال حاضر، این کمپرسور کاملا آماده است و این مقاله در مورد آن است.

کمپرسوری که الگوریتم RTT-Mid را پیاده سازی می کند، نسبت فشرده سازی قابل مقایسه با آرشیوهای استاندارد مانند WinRar، 7-Zip را ارائه می دهد که در حالت پرسرعت کار می کنند. در عین حال، سرعت عملکرد آن حداقل یک مرتبه بزرگتر است.

سرعت بسته‌بندی/بازکردن داده‌ها یک پارامتر حیاتی است که دامنه کاربرد فناوری‌های فشرده‌سازی را تعیین می‌کند. بعید است که کسی به فکر فشرده سازی یک ترابایت داده با سرعت 10-15 مگابایت در ثانیه باشد (این دقیقاً سرعت بایگانی کننده ها در حالت فشرده سازی استاندارد است) زیرا با بارگذاری کامل پردازنده تقریباً بیست ساعت طول می کشد. .

از سوی دیگر، همین ترابایت را می توان با سرعتی در حدود 2 تا 3 گیگابایت در ثانیه در حدود ده دقیقه کپی کرد.

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

کمپرسورهای مدرن می توانند چنین سرعت هایی را فقط در حالت "سریع" تولید کنند. در این حالت فعلی است که ما الگوریتم RTT-Mid را با کمپرسورهای سنتی مقایسه خواهیم کرد.

آزمایش مقایسه ای یک الگوریتم فشرده سازی جدید

کمپرسور RTT-Mid به عنوان بخشی از برنامه آزمایشی کار می کرد. در یک برنامه واقعی "کار" بسیار سریعتر کار می کند، از multithreading هوشمندانه استفاده می کند و از یک کامپایلر "عادی" استفاده می کند، نه C#.

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

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

اینم فایل dump:

فایل dump با استفاده از کمپرسورهای PTT-Mid، 7-zip و WinRar فشرده شد. کمپرسور WinRar و 7-zip روی حداکثر سرعت تنظیم شد.

کمپرسور کار می کند 7-zip:

این پردازنده را 100٪ بارگیری می کند، در حالی که سرعت متوسط ​​خواندن Dump اصلی حدود 60 مگابایت در ثانیه است.

کمپرسور کار می کند وینار:

وضعیت مشابه است، بار پردازنده تقریباً 100٪ است، متوسط ​​سرعت خواندن Dump حدود 125 مگابایت در ثانیه است.

همانطور که در مورد قبلی، سرعت بایگانی توسط قابلیت های پردازنده محدود شده است.

برنامه تست کمپرسور اکنون در حال اجرا است RTT-Mid:

اسکرین شات نشان می دهد که پردازنده در 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 مگابایتی، می توانید پنج رشته فشرده سازی را اجرا کنید.

همچنین تأخیر رم به پارامتر مهمی تبدیل می شود که سرعت کمپرسور را تعیین می کند. این الگوریتم از دسترسی تصادفی به OP استفاده می کند، که برخی از آنها به حافظه نهان (حدود 10٪) وارد نمی شوند و باید در حالت غیرفعال قرار بگیرند و منتظر داده های OP هستند که سرعت عملیات را کاهش می دهد.

به طور قابل توجهی بر سرعت کمپرسور و عملکرد سیستم ورودی/خروجی داده تأثیر می گذارد. درخواست‌هایی به OP از I/O بلوک درخواست داده از CPU، که سرعت فشرده‌سازی را نیز کاهش می‌دهد. این مشکل برای لپ‌تاپ‌ها و دسکتاپ‌ها قابل توجه است؛ برای سرورها به دلیل واحد کنترل دسترسی اتوبوس سیستم پیشرفته‌تر و رم چند کاناله، اهمیت کمتری دارد.

در سراسر متن مقاله در مورد فشرده سازی صحبت می کنیم؛ رفع فشار خارج از محدوده این مقاله باقی می ماند زیرا "همه چیز با شکلات پوشیده شده است". فشرده سازی بسیار سریعتر است و با سرعت I/O محدود می شود. یک هسته فیزیکی در یک رشته به راحتی سرعت باز کردن بسته بندی 3-4 گیگابایت در ثانیه را فراهم می کند.

این به دلیل عدم وجود عملیات جستجوی بازی در طول فرآیند فشرده سازی است که منابع اصلی پردازنده و حافظه کش را در حین فشرده سازی "می خورد".

قابلیت اطمینان ذخیره سازی داده های فشرده

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

در طول ذخیره سازی، رسانه های ذخیره سازی برخی از داده ها را از دست می دهند، مثالی در اینجا آمده است:

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

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

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

و این نیز یک مشکل بزرگ است، اما نه یک مشکل معوق، بلکه یک مشکل فعلی.

کمپرسورهای مدرنی که برای بایگانی داده های دیجیتال استفاده می شوند بر اساس اصلاحات مختلف روش فرهنگ لغت ساخته شده اند و برای چنین آرشیوهایی از دست دادن یک قطعه اطلاعات یک رویداد مرگبار خواهد بود؛ حتی یک اصطلاح ثابت برای چنین وضعیتی وجود دارد - آرشیو "شکسته" ...

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

بازیابی اطلاعات از چنین آرشیو "شکسته" غیرممکن است.

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

• یک فیلد متن منبع با بخش های تکراری حذف شده از آن؛
• فیلد فهرست

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

معایب الگوریتم

هیچ مزیتی بدون معایب وجود ندارد. روش فشرده سازی شاخص، توالی های کوتاه تکرار شونده را فشرده نمی کند. این به دلیل محدودیت های روش شاخص است. اندازه ایندکس ها حداقل 3 بایت است و می تواند حداکثر 12 بایت باشد. اگر تکراری با اندازه کوچکتر از نمایه توصیف شده مواجه شود، مهم نیست که هر چند وقت یکبار چنین تکرارهایی در فایل فشرده تشخیص داده شود، به آن توجه نمی شود.

روش فشرده سازی فرهنگ لغت سنتی به طور موثر تکرارهای متعدد با طول کوتاه را فشرده می کند و بنابراین به نسبت فشرده سازی بالاتری نسبت به فشرده سازی شاخص دست می یابد. درست است، این به دلیل بار زیاد روی پردازنده مرکزی به دست می‌آید؛ برای اینکه روش دیکشنری شروع به فشرده‌سازی داده‌ها با کارایی بیشتری نسبت به روش شاخص کند، باید سرعت پردازش داده‌ها را به 10-20 مگابایت در ثانیه در حالت واقعی کاهش دهد. تاسیسات محاسباتی با بار کامل CPU.

چنین سرعت‌های پایینی برای سیستم‌های ذخیره‌سازی داده‌های مدرن غیرقابل قبول هستند و بیشتر از آن‌که عملی باشند، از علاقه «آکادمیک» هستند.

درجه فشرده سازی اطلاعات در اصلاح بعدی الگوریتم RTT (RTT-Max) که در حال توسعه است، به طور قابل توجهی افزایش می یابد.

پس مثل همیشه ادامه دارد...

منبع: www.habr.com