บทความนี้เป็นบทความที่สองในหัวข้อการบีบอัดข้อมูลความเร็วสูงแล้ว บทความแรกอธิบายการทำงานของคอมเพรสเซอร์ที่ความเร็ว 10 GB/วินาที ต่อคอร์โปรเซสเซอร์ (การบีบอัดขั้นต่ำ, 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-Zip:
โดยจะโหลดโปรเซสเซอร์ 100% ในขณะที่ความเร็วเฉลี่ยในการอ่านดัมพ์ดั้งเดิมอยู่ที่ประมาณ 60 เมกะไบต์/วินาที
คอมเพรสเซอร์ทำงาน WinRAR:
สถานการณ์คล้ายกัน โหลดโปรเซสเซอร์เกือบ 100% ความเร็วในการอ่านดัมพ์เฉลี่ยอยู่ที่ประมาณ 125 เมกะไบต์/วินาที
เช่นเดียวกับในกรณีก่อนหน้านี้ ความเร็วของ Archiver จะถูกจำกัดโดยความสามารถของโปรเซสเซอร์
ขณะนี้โปรแกรมทดสอบคอมเพรสเซอร์กำลังทำงานอยู่ RTT-กลาง:
ภาพหน้าจอแสดงว่าโปรเซสเซอร์ถูกโหลดที่ 50% และไม่ได้ใช้งานในช่วงเวลาที่เหลือ เนื่องจากไม่มีที่ใดให้อัปโหลดข้อมูลที่บีบอัด ดิสก์อัพโหลดข้อมูล (ดิสก์ 0) โหลดเกือบเต็มแล้ว ความเร็วในการอ่านข้อมูล (ดิสก์ 1) แตกต่างกันมาก แต่โดยเฉลี่ยแล้วมากกว่า 200 เมกะไบต์/วินาที
ในกรณีนี้ ความเร็วของคอมเพรสเซอร์ถูกจำกัดโดยความสามารถในการเขียนข้อมูลที่บีบอัดลงในดิสก์ 0
ตอนนี้อัตราส่วนการบีบอัดของไฟล์เก็บถาวรผลลัพธ์:
จะเห็นได้ว่าคอมเพรสเซอร์ RTT-Mid ทำหน้าที่บีบอัดได้ดีที่สุด โดยไฟล์เก็บถาวรที่สร้างนั้นมีขนาดเล็กกว่าไฟล์เก็บถาวร WinRar 1,3 กิกะไบต์ และเล็กกว่าไฟล์เก็บถาวร 2,1z 7 กิกะไบต์
เวลาที่ใช้ในการสร้างไฟล์เก็บถาวร:
- 7-zip – 26 นาที 10 วินาที;
- WinRar – 17 นาที 40 วินาที;
- RTT-กลาง – 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 จากบล็อก I/O ร้องขอข้อมูลจาก CPU ซึ่งจะลดความเร็วการบีบอัดด้วย ปัญหานี้มีความสำคัญสำหรับแล็ปท็อปและเดสก์ท็อป สำหรับเซิร์ฟเวอร์ ปัญหานี้มีความสำคัญน้อยกว่าเนื่องจากมีหน่วยควบคุมการเข้าถึงบัสระบบขั้นสูงและ RAM แบบหลายช่องสัญญาณ
ตลอดทั้งข้อความในบทความเราพูดถึงการบีบอัด การบีบอัดยังคงอยู่นอกขอบเขตของบทความนี้เนื่องจาก "ทุกอย่างถูกปกคลุมไปด้วยช็อกโกแลต" การบีบอัดข้อมูลทำได้เร็วกว่ามากและถูกจำกัดด้วยความเร็ว I/O ฟิสิคัลคอร์หนึ่งคอร์ในหนึ่งเธรดให้ความเร็วในการคลายแพ็ก 3-4 GB/วินาทีได้อย่างง่ายดาย
นี่เป็นเพราะไม่มีการดำเนินการค้นหาที่ตรงกันในระหว่างกระบวนการคลายการบีบอัดซึ่ง "กิน" ทรัพยากรหลักของโปรเซสเซอร์และหน่วยความจำแคชในระหว่างการบีบอัด
ความน่าเชื่อถือของการจัดเก็บข้อมูลที่ถูกบีบอัด
ดังที่ชื่อของซอฟต์แวร์ทั้งคลาสที่ใช้การบีบอัดข้อมูล (ผู้จัดเก็บ) แนะนำ ซอฟต์แวร์เหล่านี้ได้รับการออกแบบมาเพื่อจัดเก็บข้อมูลในระยะยาว ไม่ใช่เป็นเวลาหลายปี แต่เป็นเวลาหลายศตวรรษและนับพันปี...
ในระหว่างการจัดเก็บ สื่อจัดเก็บข้อมูลจะสูญเสียข้อมูลบางส่วน ต่อไปนี้เป็นตัวอย่าง:
ผู้ให้บริการข้อมูล "แอนะล็อก" นี้มีอายุนับพันปี ชิ้นส่วนบางส่วนสูญหายไป แต่โดยทั่วไปแล้วข้อมูลนั้น "สามารถอ่านได้"...
ไม่มีผู้ผลิตที่รับผิดชอบระบบจัดเก็บข้อมูลดิจิทัลสมัยใหม่และสื่อดิจิทัลรายใดที่ให้การรับประกันความปลอดภัยของข้อมูลโดยสมบูรณ์มานานกว่า 75 ปี
และนี่คือปัญหา แต่ปัญหาเลื่อนออกไป ทายาทของเราก็จะแก้ไขได้...
ระบบจัดเก็บข้อมูลดิจิทัลสามารถสูญเสียข้อมูลได้ไม่เพียงแต่หลังจากผ่านไป 75 ปีเท่านั้น ข้อผิดพลาดในข้อมูลอาจปรากฏขึ้นได้ตลอดเวลา แม้ในระหว่างการบันทึก พวกเขาพยายามลดการบิดเบือนเหล่านี้ให้เหลือน้อยที่สุดโดยใช้ความซ้ำซ้อนและแก้ไขด้วยระบบแก้ไขข้อผิดพลาด ระบบสำรองและแก้ไขไม่สามารถกู้คืนข้อมูลที่สูญหายได้เสมอไป และหากเป็นเช่นนั้น ก็ไม่รับประกันว่าการดำเนินการกู้คืนจะเสร็จสมบูรณ์อย่างถูกต้อง
และนี่ก็เป็นปัญหาใหญ่เช่นกัน แต่ไม่ใช่ปัญหาที่ถูกเลื่อนออกไป แต่เป็นปัญหาในปัจจุบัน
คอมเพรสเซอร์สมัยใหม่ที่ใช้สำหรับการเก็บข้อมูลดิจิทัลนั้นถูกสร้างขึ้นจากการปรับเปลี่ยนวิธีการพจนานุกรมต่างๆ และสำหรับการเก็บข้อมูลดังกล่าวการสูญเสียข้อมูลบางส่วนจะเป็นเหตุการณ์ร้ายแรง มีแม้กระทั่งคำที่กำหนดไว้สำหรับสถานการณ์เช่นนี้ - ไฟล์เก็บถาวร "เสียหาย" ...
ความน่าเชื่อถือต่ำของการจัดเก็บข้อมูลในไฟล์เก็บถาวรที่มีการบีบอัดพจนานุกรมนั้นสัมพันธ์กับโครงสร้างของข้อมูลที่บีบอัด ข้อมูลในไฟล์เก็บถาวรดังกล่าวไม่มีข้อความต้นฉบับ จำนวนรายการในพจนานุกรมจะถูกเก็บไว้ที่นั่น และตัวพจนานุกรมเองได้รับการแก้ไขแบบไดนามิกโดยข้อความที่บีบอัดในปัจจุบัน หากส่วนย่อยของไฟล์เก็บถาวรสูญหายหรือเสียหาย รายการไฟล์เก็บถาวรที่ตามมาทั้งหมดจะไม่สามารถระบุได้จากเนื้อหาหรือตามความยาวของรายการในพจนานุกรม เนื่องจากไม่ชัดเจนว่าหมายเลขรายการในพจนานุกรมสอดคล้องกับอะไร
ไม่สามารถกู้คืนข้อมูลจากไฟล์เก็บถาวรที่ "เสียหาย" ได้
อัลกอริธึม RTT ใช้วิธีการจัดเก็บข้อมูลที่ถูกบีบอัดที่เชื่อถือได้มากขึ้น โดยจะใช้วิธีดัชนีของการบัญชีสำหรับการทำซ้ำแฟรกเมนต์ วิธีการบีบอัดนี้ช่วยให้คุณลดผลกระทบของการบิดเบือนข้อมูลบนสื่อบันทึกข้อมูลได้น้อยที่สุด และในหลายกรณีจะแก้ไขการบิดเบือนที่เกิดขึ้นระหว่างการจัดเก็บข้อมูลโดยอัตโนมัติ
เนื่องจากไฟล์เก็บถาวรในกรณีของการบีบอัดดัชนีมีสองฟิลด์:
- ช่องข้อความต้นฉบับที่มีส่วนที่ซ้ำถูกลบออก
- ฟิลด์ดัชนี
ช่องดัชนีซึ่งมีความสำคัญอย่างยิ่งต่อการกู้คืนข้อมูล มีขนาดไม่ใหญ่นักและสามารถทำซ้ำได้เพื่อการจัดเก็บข้อมูลที่เชื่อถือได้ ดังนั้น แม้ว่าส่วนของข้อความต้นฉบับหรืออาร์เรย์ดัชนีจะหายไป ข้อมูลอื่นๆ ทั้งหมดจะถูกกู้คืนโดยไม่มีปัญหา ดังเช่นในภาพที่มีสื่อบันทึกแบบ "อะนาล็อก"
ข้อเสียของอัลกอริทึม
ไม่มีข้อดีไม่มีข้อเสีย วิธีการบีบอัดดัชนีไม่บีบอัดลำดับการทำซ้ำสั้นๆ นี่เป็นเพราะข้อจำกัดของวิธีดัชนี ดัชนีมีขนาดอย่างน้อย 3 ไบต์และสามารถมีขนาดได้สูงสุด 12 ไบต์ หากพบการซ้ำซ้อนในขนาดที่เล็กกว่าดัชนีที่อธิบายไว้ ก็จะไม่นำมาพิจารณา ไม่ว่าจะตรวจพบการซ้ำซ้อนดังกล่าวในไฟล์บีบอัดบ่อยแค่ไหนก็ตาม
วิธีการบีบอัดพจนานุกรมแบบดั้งเดิมจะบีบอัดการทำซ้ำของความยาวสั้นได้อย่างมีประสิทธิภาพ ดังนั้นจึงได้อัตราส่วนการบีบอัดที่สูงกว่าการบีบอัดดัชนี จริงอยู่ สิ่งนี้เกิดขึ้นได้เนื่องจากมีภาระงานสูงบนโปรเซสเซอร์กลาง เพื่อให้วิธีพจนานุกรมเริ่มบีบอัดข้อมูลได้อย่างมีประสิทธิภาพมากกว่าวิธีดัชนี จะต้องลดความเร็วในการประมวลผลข้อมูลลงเหลือ 10-20 เมกะไบต์ต่อวินาทีแบบเรียลไทม์ การติดตั้งคอมพิวเตอร์ที่มีโหลด CPU เต็ม
ความเร็วต่ำดังกล่าวเป็นสิ่งที่ยอมรับไม่ได้สำหรับระบบจัดเก็บข้อมูลสมัยใหม่ และเป็นที่สนใจด้าน "วิชาการ" มากกว่าในทางปฏิบัติ
ระดับการบีบอัดข้อมูลจะเพิ่มขึ้นอย่างมีนัยสำคัญในการปรับเปลี่ยนอัลกอริทึม RTT (RTT-Max) ครั้งต่อไปซึ่งอยู่ในการพัฒนาแล้ว
จึงขอติดตามกันต่อไปเช่นเคย...
ที่มา: will.com