นี่คือลักษณะของความซ้ำซ้อน
รหัสสำรอง* ใช้กันอย่างแพร่หลายในระบบคอมพิวเตอร์เพื่อเพิ่มความน่าเชื่อถือของการจัดเก็บข้อมูล ในยานเดกซ์มีการใช้ในหลายโครงการ ตัวอย่างเช่น การใช้รหัสซ้ำซ้อนแทนการจำลองในพื้นที่เก็บข้อมูลออบเจ็กต์ภายในของเราจะช่วยประหยัดเงินได้นับล้านโดยไม่กระทบต่อความน่าเชื่อถือ แต่ถึงแม้จะมีการใช้งานอย่างแพร่หลาย แต่คำอธิบายที่ชัดเจนเกี่ยวกับวิธีการทำงานของโค้ดสำรองนั้นหาได้ยากมาก ผู้ที่ต้องการทำความเข้าใจต้องเผชิญกับสิ่งต่อไปนี้โดยประมาณ (จาก ):
ฉันชื่อ Vadim ที่ Yandex ฉันกำลังพัฒนา MDS ที่เก็บข้อมูลอ็อบเจ็กต์ภายใน ในบทความนี้ ผมจะอธิบายด้วยคำง่ายๆ ถึงรากฐานทางทฤษฎีของรหัสความซ้ำซ้อน (รหัส Reed-Solomon และ LRC) ฉันจะบอกคุณว่ามันทำงานอย่างไร โดยไม่มีคณิตศาสตร์ที่ซับซ้อนและคำศัพท์ที่หายาก ในตอนท้ายฉันจะยกตัวอย่างการใช้รหัสซ้ำซ้อนใน Yandex
ฉันจะไม่พิจารณารายละเอียดทางคณิตศาสตร์จำนวนหนึ่งโดยละเอียด แต่ฉันจะให้ลิงก์สำหรับผู้ที่ต้องการเจาะลึกยิ่งขึ้น ฉันจะทราบด้วยว่าคำจำกัดความทางคณิตศาสตร์บางอย่างอาจไม่เข้มงวด เนื่องจากบทความนี้ไม่ได้มีไว้สำหรับนักคณิตศาสตร์ แต่สำหรับวิศวกรที่ต้องการเข้าใจสาระสำคัญของปัญหา
* ในวรรณคดีภาษาอังกฤษ รหัสซ้ำซ้อนมักเรียกว่ารหัสลบ
1. สาระสำคัญของรหัสซ้ำซ้อน
สาระสำคัญของรหัสสำรองทั้งหมดนั้นง่ายมาก: จัดเก็บ (หรือส่ง) ข้อมูลเพื่อไม่ให้สูญหายเมื่อเกิดข้อผิดพลาด (ความล้มเหลวของดิสก์ ข้อผิดพลาดในการถ่ายโอนข้อมูล ฯลฯ )
ในรหัสความซ้ำซ้อนส่วนใหญ่* ข้อมูลจะถูกแบ่งออกเป็นบล็อกข้อมูล n บล็อก โดยจะนับบล็อกของรหัสซ้ำซ้อนจำนวน m บล็อก ส่งผลให้มีบล็อกทั้งหมด n + m รหัสความซ้ำซ้อนถูกสร้างขึ้นในลักษณะที่สามารถกู้คืนบล็อกข้อมูลได้ n บล็อกโดยใช้เพียงส่วนหนึ่งของบล็อก n + m ต่อไปเราจะพิจารณาเฉพาะรหัสบล็อกซ้ำซ้อนซึ่งก็คือรหัสที่ข้อมูลถูกแบ่งออกเป็นบล็อก
ในการกู้คืนข้อมูลทั้งหมด n บล็อก คุณจะต้องมีบล็อกอย่างน้อย n จาก n + m เนื่องจากคุณไม่สามารถรับ n บล็อกจากการมีบล็อกเพียง n-1 เท่านั้น (ในกรณีนี้ คุณจะต้องนำ 1 บล็อก “ออกจากแบบบาง” อากาศ"). บล็อกสุ่มจำนวน n + m บล็อกเพียงพอที่จะกู้คืนข้อมูลทั้งหมดหรือไม่ ขึ้นอยู่กับประเภทของรหัสความซ้ำซ้อน เช่น รหัส Reed-Solomon ช่วยให้คุณสามารถกู้คืนข้อมูลทั้งหมดโดยใช้บล็อก n ที่กำหนดเองได้ แต่รหัสความซ้ำซ้อนของ LRC อาจไม่เสมอไป
การจัดเก็บข้อมูล
ตามกฎแล้วในระบบจัดเก็บข้อมูล แต่ละบล็อกข้อมูลและบล็อกรหัสซ้ำซ้อนจะถูกเขียนลงในดิสก์แยกต่างหาก จากนั้น หากดิสก์ที่กำหนดเองล้มเหลว ข้อมูลต้นฉบับก็ยังสามารถกู้คืนและอ่านได้ ข้อมูลสามารถกู้คืนได้แม้ว่าดิสก์หลายตัวจะล้มเหลวในเวลาเดียวกัน
การถ่ายโอนข้อมูล
รหัสสำรองสามารถใช้เพื่อส่งข้อมูลผ่านเครือข่ายที่ไม่น่าเชื่อถือได้อย่างน่าเชื่อถือ ข้อมูลที่ส่งจะถูกแบ่งออกเป็นบล็อก และรหัสความซ้ำซ้อนจะถูกคำนวณสำหรับบล็อกเหล่านั้น ทั้งบล็อกข้อมูลและบล็อกโค้ดสำรองจะถูกส่งผ่านเครือข่าย หากเกิดข้อผิดพลาดในการบล็อกโดยพลการ (ไม่เกินจำนวนบล็อกที่กำหนด) ข้อมูลยังคงสามารถส่งข้อมูลผ่านเครือข่ายได้โดยไม่มีข้อผิดพลาด ตัวอย่างเช่น รหัสรีด-โซโลมอนใช้ในการส่งข้อมูลผ่านสายสื่อสารด้วยแสงและในการสื่อสารผ่านดาวเทียม
* นอกจากนี้ยังมีรหัสสำรองซึ่งข้อมูลไม่ได้แบ่งออกเป็นบล็อก เช่น รหัส Hamming และรหัส CRC ซึ่งใช้กันอย่างแพร่หลายสำหรับการส่งข้อมูลในเครือข่ายอีเทอร์เน็ต รหัสเหล่านี้เป็นรหัสสำหรับการเข้ารหัสแก้ไขข้อผิดพลาด ได้รับการออกแบบมาเพื่อตรวจจับข้อผิดพลาดและไม่แก้ไข (รหัส Hamming ยังอนุญาตให้แก้ไขข้อผิดพลาดบางส่วนได้)
2. รหัสรีด-โซโลมอน
รหัส Reed-Solomon เป็นหนึ่งในรหัสสำรองที่ใช้กันอย่างแพร่หลายที่สุด คิดค้นขึ้นในทศวรรษ 1960 และใช้กันอย่างแพร่หลายครั้งแรกในทศวรรษ 1980 สำหรับการผลิตคอมแพคดิสก์จำนวนมาก
มีคำถามสำคัญสองข้อในการทำความเข้าใจรหัส Reed-Solomon: 1) วิธีสร้างบล็อกของรหัสซ้ำซ้อน; 2) วิธีการกู้คืนข้อมูลโดยใช้บล็อคโค้ดซ้ำซ้อน เรามาค้นหาคำตอบให้กับพวกเขากันดีกว่า
เพื่อความง่าย เราจะสมมติเพิ่มเติมว่า n=6 และ m=4 รูปแบบอื่น ๆ พิจารณาโดยการเปรียบเทียบ
วิธีสร้างบล็อคโค้ดซ้ำซ้อน
แต่ละบล็อกของรหัสซ้ำซ้อนจะถูกนับแยกจากบล็อกอื่นๆ บล็อกข้อมูลทั้งหมด n รายการใช้เพื่อนับแต่ละบล็อก ในแผนภาพด้านล่าง X1-X6 คือบล็อกข้อมูล P1-P4 คือบล็อกโค้ดสำรอง
บล็อกข้อมูลทั้งหมดจะต้องมีขนาดเท่ากัน และสามารถใช้ศูนย์บิตในการจัดตำแหน่งได้ บล็อกรหัสความซ้ำซ้อนที่ได้จะมีขนาดเท่ากับบล็อกข้อมูล บล็อกข้อมูลทั้งหมดแบ่งออกเป็นคำ (เช่น 16 บิต) สมมติว่าเราแบ่งบล็อคข้อมูลออกเป็น k คำ จากนั้นบล็อกทั้งหมดของรหัสซ้ำซ้อนจะถูกแบ่งออกเป็นคำ k
หากต้องการนับคำที่ i ของแต่ละบล็อกความซ้ำซ้อน ระบบจะใช้คำที่ i-th ของบล็อกข้อมูลทั้งหมด จะถูกคำนวณตามสูตรต่อไปนี้:
ที่นี่ค่า x คือคำของบล็อกข้อมูล p คือคำของบล็อกโค้ดซ้ำซ้อน อัลฟา เบต้า แกมมา และเดลต้าทั้งหมดเป็นตัวเลขที่เลือกมาเป็นพิเศษซึ่งเหมือนกันสำหรับ i ทั้งหมด ต้องบอกทันทีว่าค่าเหล่านี้ทั้งหมดไม่ใช่ตัวเลขธรรมดา แต่เป็นองค์ประกอบของฟิลด์ Galois การดำเนินการ +, -, *, / ไม่ใช่การดำเนินการที่เราทุกคนคุ้นเคย แต่เป็นการดำเนินการพิเศษที่นำมาใช้กับองค์ประกอบของ Galois สนาม.
เหตุใดจึงต้องมีทุ่ง Galois?
ดูเหมือนว่าทุกอย่างจะง่าย: เราแบ่งข้อมูลออกเป็นบล็อก บล็อกเป็นคำ โดยใช้คำของบล็อกข้อมูลที่เรานับคำของบล็อกรหัสซ้ำซ้อน - เราได้รับบล็อกรหัสซ้ำซ้อน โดยทั่วไปนี่คือวิธีการทำงาน แต่ปีศาจอยู่ในรายละเอียด:
- ตามที่ระบุไว้ข้างต้น ขนาดคำได้รับการแก้ไขแล้ว ในตัวอย่างของเราคือ 16 บิต สูตรด้านบนสำหรับรหัสรีด-โซโลมอนคือเมื่อใช้จำนวนเต็มธรรมดา ผลลัพธ์ของการคำนวณ p อาจไม่สามารถแทนค่าได้โดยใช้คำที่มีขนาดถูกต้อง
- ในการกู้คืนข้อมูลสูตรข้างต้นจะถือเป็นระบบสมการที่ต้องแก้เพื่อกู้คืนข้อมูล ในระหว่างกระบวนการแก้ปัญหา อาจจำเป็นต้องหารจำนวนเต็มซึ่งกันและกัน ส่งผลให้จำนวนจริงไม่สามารถแสดงได้อย่างแม่นยำในหน่วยความจำคอมพิวเตอร์
ปัญหาเหล่านี้ทำให้ไม่สามารถใช้จำนวนเต็มสำหรับรหัสรีด-โซโลมอน วิธีแก้ปัญหาเป็นของเดิมซึ่งสามารถอธิบายได้ดังนี้: ลองคิดตัวเลขพิเศษที่สามารถแสดงโดยใช้คำที่มีความยาวที่ต้องการ (เช่น 16 บิต) และผลลัพธ์ของการดำเนินการทั้งหมดซึ่ง (นอกจากนี้ , ลบ, คูณ, หาร) จะถูกนำเสนอในหน่วยความจำคอมพิวเตอร์โดยใช้คำที่มีความยาวที่ต้องการ
คณิตศาสตร์ได้รับการศึกษาตัวเลข "พิเศษ" ดังกล่าวมาเป็นเวลานานแล้วเรียกว่าฟิลด์ ฟิลด์คือชุดขององค์ประกอบที่มีการบวก ลบ คูณหาร ตามที่กำหนดไว้
ฟิลด์ Galois* คือฟิลด์ที่มีผลลัพธ์เฉพาะจากการดำเนินการแต่ละครั้ง (+, -, *, /) สำหรับสององค์ประกอบใดๆ ของฟิลด์ สนามกาลัวส์สามารถสร้างขึ้นสำหรับตัวเลขที่เป็นกำลังของ 2: 2, 4, 8, 16 เป็นต้น (จริงๆ แล้วเป็นกำลังของจำนวนเฉพาะ p แต่ในทางปฏิบัติแล้ว เราสนใจเฉพาะกำลังของ 2 เท่านั้น) ตัวอย่างเช่น สำหรับคำแบบ 16 บิต นี่คือฟิลด์ที่มีองค์ประกอบ 65 รายการ สำหรับแต่ละคู่คุณสามารถค้นหาผลลัพธ์ของการดำเนินการใดๆ (+, -, *, /) ค่าของ x, p, alpha, beta, gamma, delta จากสมการข้างต้นจะถือเป็นองค์ประกอบของสนาม Galois ในการคำนวณ
ดังนั้นเราจึงมีระบบสมการที่เราสามารถสร้างบล็อกของรหัสซ้ำซ้อนโดยการเขียนโปรแกรมคอมพิวเตอร์ที่เหมาะสม เมื่อใช้ระบบสมการเดียวกัน คุณสามารถดำเนินการกู้คืนข้อมูลได้
* นี่ไม่ใช่คำจำกัดความที่เข้มงวด แต่เป็นคำอธิบาย
วิธีการกู้คืนข้อมูล
จำเป็นต้องมีการคืนค่าเมื่อบล็อก n + m บางส่วนหายไป สิ่งเหล่านี้สามารถเป็นได้ทั้งบล็อกข้อมูลและบล็อกโค้ดซ้ำซ้อน การไม่มีบล็อกข้อมูลและ/หรือบล็อกโค้ดซ้ำซ้อนจะหมายความว่าไม่ทราบตัวแปร x และ/หรือ p ที่สอดคล้องกันในสมการข้างต้น
สมการสำหรับรหัสรีด-โซโลมอนสามารถดูได้เป็นระบบสมการซึ่งค่าอัลฟ่า, เบต้า, แกมมา, เดลต้าทั้งหมดเป็นค่าคงที่, x และ p ทั้งหมดที่สอดคล้องกับบล็อกที่มีอยู่นั้นเป็นตัวแปรที่รู้จัก และตัวแปร x และ p ที่เหลือ ไม่เป็นที่รู้จัก
ตัวอย่างเช่น ปล่อยให้บล็อกข้อมูล 1, 2, 3 และบล็อกรหัสซ้ำซ้อน 2 ไม่พร้อมใช้งาน จากนั้นสำหรับกลุ่มคำที่ i จะมีระบบสมการต่อไปนี้ (ไม่ทราบจะถูกทำเครื่องหมายด้วยสีแดง):
เรามีระบบ 4 สมการที่มี 4 ไม่ทราบ ซึ่งหมายความว่าเราสามารถแก้มันและกู้คืนข้อมูลได้!
จากระบบสมการนี้ มีข้อสรุปหลายประการเกี่ยวกับการกู้คืนข้อมูลสำหรับรหัส Reed-Solomon (n data block, m redundancy code block):
- ข้อมูลสามารถกู้คืนได้หากมีการสูญหายของบล็อก m หรือน้อยกว่า หากบล็อก m+1 หรือมากกว่านั้นหายไป ข้อมูลจะไม่สามารถกู้คืนได้: เป็นไปไม่ได้ที่จะแก้ระบบสมการ m ที่ไม่ทราบค่า m + 1
- หากต้องการกู้คืนบล็อกข้อมูลแม้แต่บล็อกเดียว คุณต้องใช้บล็อกที่เหลือจำนวน n บล็อก และคุณสามารถใช้รหัสซ้ำซ้อนใดก็ได้
อะไรที่คุณต้องรู้
ในคำอธิบายข้างต้น ฉันหลีกเลี่ยงประเด็นสำคัญหลายประการที่ต้องอาศัยความรู้เชิงลึกในวิชาคณิตศาสตร์มาพิจารณา โดยเฉพาะอย่างยิ่ง ฉันไม่ได้พูดอะไรเกี่ยวกับสิ่งต่อไปนี้:
- ระบบสมการสำหรับรหัสรีด-โซโลมอนจะต้องมีคำตอบ (เฉพาะ) สำหรับค่าที่ไม่ทราบค่าผสมกัน (ไม่เกินค่าที่ไม่ทราบ m) ตามข้อกำหนดนี้จะมีการเลือกค่าอัลฟา, เบต้า, แกมมาและเดลต้า
- ระบบสมการต้องสามารถสร้างได้โดยอัตโนมัติ (ขึ้นอยู่กับว่าบล็อกใดไม่พร้อมใช้งาน) และแก้ไขได้
- เราจำเป็นต้องสร้างฟิลด์ Galois: สำหรับขนาดคำที่กำหนด สามารถค้นหาผลลัพธ์ของการดำเนินการใดๆ (+, -, *, /) สำหรับสององค์ประกอบใดก็ได้
ในตอนท้ายของบทความมีการอ้างอิงถึงวรรณกรรมเกี่ยวกับประเด็นสำคัญเหล่านี้
ทางเลือกของ n และ m
จะเลือก n และ m ในทางปฏิบัติได้อย่างไร? ในทางปฏิบัติ ในระบบจัดเก็บข้อมูล รหัสความซ้ำซ้อนจะถูกใช้เพื่อประหยัดพื้นที่ ดังนั้น m จึงถูกเลือกให้น้อยกว่า n เสมอ ค่าเฉพาะของพวกเขาขึ้นอยู่กับปัจจัยหลายประการ ได้แก่ :
- ความน่าเชื่อถือของการจัดเก็บข้อมูล ยิ่ง m มากเท่าใด จำนวนความล้มเหลวของดิสก์ที่สามารถอยู่รอดได้ก็จะยิ่งมากขึ้นเท่านั้น กล่าวคือ ความน่าเชื่อถือก็จะยิ่งสูงขึ้นเท่านั้น
- พื้นที่เก็บข้อมูลซ้ำซ้อน ยิ่งอัตราส่วน m/n สูง ความซ้ำซ้อนในการจัดเก็บข้อมูลก็จะยิ่งสูงขึ้น และระบบก็จะมีราคาแพงมากขึ้นด้วย
- ขอเวลาดำเนินการ ยิ่งผลรวม n + m มากเท่าใด เวลาตอบสนองต่อคำขอก็จะยิ่งนานขึ้นเท่านั้น เนื่องจากการอ่านข้อมูล (ระหว่างการกู้คืน) จำเป็นต้องอ่าน n บล็อกที่จัดเก็บไว้ในดิสก์ n ตัวที่แตกต่างกัน เวลาในการอ่านจะถูกกำหนดโดยดิสก์ที่ช้าที่สุด
นอกจากนี้ การจัดเก็บข้อมูลใน DC หลายแห่งยังกำหนดข้อจำกัดเพิ่มเติมในการเลือก n และ m: หากปิด 1 DC ข้อมูลดังกล่าวจะต้องพร้อมสำหรับการอ่าน ตัวอย่างเช่น เมื่อจัดเก็บข้อมูลใน 3 DC ต้องเป็นไปตามเงื่อนไขต่อไปนี้: m >= n/2 มิฉะนั้นอาจมีสถานการณ์ที่ข้อมูลไม่สามารถอ่านได้เมื่อปิด 1 DC
3. LRC - รหัสการฟื้นฟูท้องถิ่น
ในการกู้คืนข้อมูลโดยใช้รหัส Reed-Solomon คุณต้องใช้ n บล็อกข้อมูลที่กำหนดเอง นี่เป็นข้อเสียที่สำคัญมากสำหรับระบบจัดเก็บข้อมูลแบบกระจายเนื่องจากในการกู้คืนข้อมูลบนดิสก์ที่เสียหายคุณจะต้องอ่านข้อมูลจากดิสก์อื่น ๆ ส่วนใหญ่สร้างภาระเพิ่มเติมจำนวนมากบนดิสก์และเครือข่าย
ข้อผิดพลาดที่พบบ่อยที่สุดคือการเข้าไม่ถึงบล็อกข้อมูลหนึ่งบล็อกเนื่องจากความล้มเหลวหรือการโอเวอร์โหลดของดิสก์หนึ่งตัว เป็นไปได้ไหมที่จะลดภาระส่วนเกินสำหรับการกู้คืนข้อมูลในกรณี (ที่พบบ่อยที่สุด) นี้? ปรากฎว่าคุณทำได้: มีรหัสซ้ำซ้อน LRC เพื่อจุดประสงค์นี้โดยเฉพาะ
LRC (รหัสการสร้างใหม่ในท้องถิ่น) เป็นรหัสซ้ำซ้อนที่ Microsoft คิดค้นขึ้นเพื่อใช้ใน Windows Azure Storage แนวคิดของ LRC นั้นง่ายที่สุดเท่าที่จะเป็นไปได้: แบ่งบล็อคข้อมูลทั้งหมดออกเป็นสองกลุ่ม (หรือมากกว่า) และอ่านส่วนหนึ่งของบล็อคโค้ดซ้ำซ้อนสำหรับแต่ละกลุ่มแยกกัน จากนั้นบล็อกรหัสซ้ำซ้อนบางส่วนจะถูกนับโดยใช้บล็อกข้อมูลทั้งหมด (ใน LRC เรียกว่ารหัสซ้ำซ้อนส่วนกลาง) และบางส่วน - ใช้หนึ่งในสองกลุ่มของบล็อกข้อมูล (เรียกว่ารหัสซ้ำซ้อนในเครื่อง)
LRC แสดงด้วยตัวเลขสามตัว: nrl โดยที่ n คือจำนวนบล็อกข้อมูล r คือจำนวนบล็อกโค้ดสำรองส่วนกลาง l คือจำนวนบล็อกโค้ดสำรองเฉพาะที่ หากต้องการอ่านข้อมูลเมื่อบล็อกข้อมูลหนึ่งไม่พร้อมใช้งาน คุณต้องอ่านเฉพาะบล็อก n/l ซึ่งน้อยกว่ารหัสรีด-โซโลมอน l เท่า
ตัวอย่างเช่น พิจารณาโครงการ LRC 6-2-2 X1–X6 — 6 บล็อกข้อมูล, P1, P2 — 2 บล็อกความซ้ำซ้อนส่วนกลาง, P3, P4 — 2 บล็อกความซ้ำซ้อนในเครื่อง
บล็อกโค้ดสำรอง P1, P2 จะถูกนับโดยใช้บล็อกข้อมูลทั้งหมด บล็อกรหัสซ้ำซ้อน P3 - ใช้บล็อกข้อมูล X1-X3 บล็อกรหัสซ้ำซ้อน P4 - ใช้บล็อกข้อมูล X4-X6
ส่วนที่เหลือทำใน LRC โดยการเปรียบเทียบกับรหัส Reed-Solomon สมการในการนับคำของบล็อกโค้ดซ้ำซ้อนจะเป็น:
ในการเลือกตัวเลขอัลฟ่า, เบต้า, แกมม่า, เดลต้า จะต้องปฏิบัติตามเงื่อนไขหลายประการเพื่อรับประกันความเป็นไปได้ของการกู้คืนข้อมูล (นั่นคือการแก้ระบบสมการ) คุณสามารถอ่านเพิ่มเติมเกี่ยวกับพวกเขาได้ใน .
นอกจากนี้ในทางปฏิบัติ การดำเนินการ XOR ยังใช้ในการคำนวณรหัสความซ้ำซ้อนในเครื่อง P3, P4
ข้อสรุปจำนวนหนึ่งตามมาจากระบบสมการของ LRC:
- หากต้องการกู้คืน 1 บล็อกข้อมูล ก็เพียงพอที่จะอ่านบล็อก n/l (n/2 ในตัวอย่างของเรา)
- หากบล็อก r + l ไม่พร้อมใช้งาน และบล็อกทั้งหมดรวมอยู่ในกลุ่มเดียว ข้อมูลจะไม่สามารถกู้คืนได้ นี่เป็นเรื่องง่ายที่จะอธิบายด้วยตัวอย่าง ปล่อยให้บล็อก X1–X3 และ P3 ไม่พร้อมใช้งาน: สิ่งเหล่านี้คือบล็อก r + l จากกลุ่มเดียวกัน 4 ในกรณีของเรา จากนั้นเราก็มีระบบ 3 สมการที่มี 4 ไม่ทราบที่ไม่สามารถแก้ไขได้
- ในกรณีอื่นๆ ทั้งหมดที่ไม่มีบล็อก r + l (เมื่อมีอย่างน้อยหนึ่งบล็อกจากแต่ละกลุ่ม) ข้อมูลใน LRC ก็สามารถกู้คืนได้
ดังนั้น LRC จึงมีประสิทธิภาพเหนือกว่าโค้ด Reed-Solomon ในการกู้คืนข้อมูลหลังจากเกิดข้อผิดพลาดเพียงครั้งเดียว ในรหัส Reed-Solomon หากต้องการกู้คืนข้อมูลแม้แต่บล็อกเดียว คุณต้องใช้ n บล็อก และใน LRC เพื่อกู้คืนข้อมูลหนึ่งบล็อก ก็เพียงพอที่จะใช้บล็อก n/l (n/2 ในตัวอย่างของเรา) ในทางกลับกัน LRC นั้นด้อยกว่ารหัส Reed-Solomon ในแง่ของจำนวนข้อผิดพลาดสูงสุดที่อนุญาต ในตัวอย่างข้างต้น รหัส Reed-Solomon สามารถกู้คืนข้อมูลสำหรับข้อผิดพลาด 4 ข้อใดก็ได้ และสำหรับ LRC จะมีข้อผิดพลาด 2 ข้อรวมกัน 4 รายการเมื่อไม่สามารถกู้คืนข้อมูลได้
สิ่งที่สำคัญกว่านั้นขึ้นอยู่กับสถานการณ์เฉพาะ แต่บ่อยครั้งการประหยัดภาระส่วนเกินที่ LRC มอบให้มีมากกว่าพื้นที่จัดเก็บที่เชื่อถือได้น้อยกว่าเล็กน้อย
4. รหัสสำรองอื่นๆ
นอกจากรหัส Reed-Solomon และ LRC แล้ว ยังมีรหัสสำรองอื่นๆ อีกมากมาย รหัสซ้ำซ้อนที่ต่างกันใช้คณิตศาสตร์ต่างกัน นี่คือรหัสสำรองอื่นๆ:
- รหัสซ้ำซ้อนโดยใช้ตัวดำเนินการ XOR การดำเนินการ XOR ดำเนินการกับบล็อกข้อมูล n บล็อก และได้รับรหัสความซ้ำซ้อน 1 บล็อก นั่นคือโครงร่าง n+1 (บล็อกข้อมูล n รหัสความซ้ำซ้อน 1 รายการ) ใช้ใน โดยที่บล็อกข้อมูลและรหัสซ้ำซ้อนจะถูกเขียนแบบวนรอบไปยังดิสก์ทั้งหมดของอาร์เรย์
- อัลกอริธึมเลขคู่ตามการดำเนินการ XOR ช่วยให้คุณสร้างโค้ดสำรองได้ 2 บล็อก ซึ่งก็คือโครงร่าง n+2
- อัลกอริธึม STAR ตามการดำเนินการ XOR ช่วยให้คุณสร้างโค้ดสำรองได้ 3 บล็อก ซึ่งก็คือโครงร่าง n+3
- รหัส Pyramide เป็นรหัสซ้ำซ้อนจาก Microsoft
5. ใช้ใน Yandex
โครงการโครงสร้างพื้นฐาน Yandex จำนวนหนึ่งใช้รหัสซ้ำซ้อนเพื่อการจัดเก็บข้อมูลที่เชื่อถือได้ นี่คือตัวอย่างบางส่วน:
- ที่เก็บข้อมูลอ็อบเจ็กต์ภายใน MDS ซึ่งฉันเขียนถึงตอนต้นบทความ
- — ระบบ MapReduce ของ Yandex.
- (Yandex DataBase) - ฐานข้อมูลกระจาย newSQL
MDS ใช้รหัสซ้ำซ้อน LRC โครงการ 8-2-2 ข้อมูลที่มีรหัสความซ้ำซ้อนจะถูกเขียนลงในดิสก์ 12 ดิสก์ที่แตกต่างกันในเซิร์ฟเวอร์ที่แตกต่างกันใน 3 DC ที่แตกต่างกัน: 4 เซิร์ฟเวอร์ในแต่ละ DC อ่านเพิ่มเติมเกี่ยวกับเรื่องนี้ใน .
YT ใช้ทั้งรหัส Reed-Solomon (Scheme 6-3) ซึ่งเป็นรหัสแรกที่ใช้ และรหัสสำรอง LRC (Scheme 12-2-2) โดย LRC เป็นวิธีการจัดเก็บที่ต้องการ
YDB ใช้รหัสซ้ำซ้อนแบบเลขคู่ (รูปที่ 4-2) เกี่ยวกับรหัสซ้ำซ้อนใน YDB แล้ว .
การใช้โครงร่างรหัสสำรองที่แตกต่างกันมีสาเหตุมาจากข้อกำหนดที่แตกต่างกันสำหรับระบบ ตัวอย่างเช่น ใน MDS ข้อมูลที่จัดเก็บโดยใช้ LRC จะถูกวางไว้ใน DC 3 เครื่องพร้อมกัน เป็นสิ่งสำคัญสำหรับเราที่ข้อมูลจะยังคงพร้อมสำหรับการอ่านหาก 1 DC ใด ๆ ล้มเหลว ดังนั้นบล็อกจะต้องถูกกระจายไปยัง DCs เพื่อว่าหาก DC ใด ๆ ไม่พร้อมใช้งาน จำนวนบล็อกที่ไม่สามารถเข้าถึงได้นั้นไม่เกินที่อนุญาต ในรูปแบบ 8-2-2 คุณสามารถวาง 4 บล็อกในแต่ละ DC จากนั้นเมื่อปิด DC ใด ๆ จะไม่สามารถใช้งาน 4 บล็อกได้และสามารถอ่านข้อมูลได้ ไม่ว่ารูปแบบใดที่เราเลือกเมื่อวางไว้ใน 3 DC ไม่ว่าในกรณีใดควรมี (r + l) / n >= 0,5 นั่นคือความซ้ำซ้อนในการจัดเก็บจะมีอย่างน้อย 50%
ใน YT สถานการณ์จะแตกต่างออกไป: แต่ละคลัสเตอร์ YT ตั้งอยู่ใน 1 DC (คลัสเตอร์ที่แตกต่างกันใน DC ที่แตกต่างกัน) ดังนั้นจึงไม่มีข้อจำกัดดังกล่าว แบบแผน 12-2-2 ให้ความซ้ำซ้อน 33% กล่าวคือ การจัดเก็บข้อมูลมีราคาถูกกว่า และยังสามารถอยู่รอดได้เมื่อดิสก์ขัดข้องพร้อมกันสูงสุด 4 ครั้ง เช่นเดียวกับแบบแผน MDS
มีคุณสมบัติอื่น ๆ อีกมากมายของการใช้รหัสซ้ำซ้อนในระบบจัดเก็บข้อมูลและประมวลผล: ความแตกต่างของการกู้คืนข้อมูล, ผลกระทบของการกู้คืนต่อเวลาในการดำเนินการแบบสอบถาม, คุณสมบัติของการบันทึกข้อมูล ฯลฯ ฉันจะพูดแยกกันเกี่ยวกับคุณสมบัติเหล่านี้และคุณสมบัติอื่น ๆ ของการใช้รหัสซ้ำซ้อนในทางปฏิบัติหากหัวข้อนั้นน่าสนใจ
6. ลิงค์
- ชุดบทความเกี่ยวกับรหัส Reed-Solomon และฟิลด์ Galois:
พวกเขาเจาะลึกคณิตศาสตร์ในภาษาที่เข้าถึงได้ - บทความจาก Microsoft เกี่ยวกับ LRC:
ส่วนที่ 2 อธิบายทฤษฎีโดยย่อ จากนั้นอภิปรายการประสบการณ์กับ LRC ในทางปฏิบัติ - โครงการเลขคู่:
- โครงการ STAR:
- รหัสพีระมิด:
- รหัสความซ้ำซ้อนใน MDS:
- รหัสซ้ำซ้อนใน YT:
- รหัสซ้ำซ้อนใน YDB:
ที่มา: will.com