เทคโนโลยี Erasure Coding สำหรับระบบแบบกระจาย
(transactional.blog)- Erasure Coding คือเทคนิคประนีประนอมระหว่างประสิทธิภาพการจัดเก็บกับความทนทานต่อความขัดข้อง โดยแบ่งข้อมูลเป็นชิ้นข้อมูลและพาริตี ทำให้ทนต่อความเสียหายได้ด้วยพื้นที่จัดเก็บน้อยกว่าการทำสำเนาทั้งหมด
- โมเดลพื้นฐานคือ k+m=n โดย k คือจำนวนชิ้นข้อมูลที่จำเป็นต่อการกู้คืน, m คือจำนวนชิ้นพาริตีและเป็นจำนวนความล้มเหลวที่ยอมรับได้, n คือจำนวนชิ้นทั้งหมด
- ในที่เก็บข้อมูลแบบ object/blob สามารถใช้การตั้งค่าอย่าง 10+5 แทนการทำสำเนาทั้งหมด 3 ชุด เพื่อวางชิ้นข้อมูลเล็ก ๆ บนเซิร์ฟเวอร์จำนวนมากขึ้นและลดปริมาณพื้นที่จัดเก็บได้
- ระบบ Quorum มีข้อจำกัดในการลดพื้นที่จัดเก็บหากใช้แค่เสียงข้างมากธรรมดา และถ้าปรับเป็น 3+2, 2+2, 1+2 ตามจำนวน replica ที่พร้อมใช้งานแบบ HRaft ก็จะเกิดภาระด้านการเข้ารหัสใหม่และการ provision ความจุ
- ในการนำไปใช้จริง ต้องตรวจสอบ ความผันผวนของต้นทุนการถอดรหัส ตามชุดชิ้นข้อมูลที่ตอบกลับ รวมถึงความแตกต่างด้าน metadata และข้อกำหนดการจัดเรียงของ Jerasure, ISA-L และ liberasurecode
การประนีประนอมพื้นฐานระหว่างประสิทธิภาพการจัดเก็บกับการทนต่อความขัดข้อง
- วิธีสุดขั้วในการเก็บไฟล์บนเซิร์ฟเวอร์ N เครื่องมีสองแบบ
- หากวาง สำเนาไฟล์เต็ม ไว้บนทุกเซิร์ฟเวอร์ แม้เซิร์ฟเวอร์ N-1 เครื่องจะหายไปก็ยังไม่เสียไฟล์ แต่ต้นทุนพื้นที่จัดเก็บสูงที่สุด
- หากแบ่งไฟล์เป็นชิ้นขนาดเท่ากัน N ชิ้นแล้วเก็บแต่ละชิ้นไว้บนแต่ละเซิร์ฟเวอร์ ประสิทธิภาพการจัดเก็บจะดีที่สุด แต่ตอนอ่านต้องใช้ชิ้นข้อมูลครบทั้ง N ชิ้น
- Erasure Coding ปรับสมดุลระหว่างสองสุดขั้วนี้ในด้านประสิทธิภาพการจัดเก็บและการทนต่อความขัดข้อง
- สามารถสร้างโค้ดให้ตรงกับเป้าหมายว่า “จะแบ่งไฟล์เป็น N ชิ้น แต่ยังต้องกู้คืนได้แม้มีชิ้นข้อมูล M ชิ้นถูกทำลาย”
- ให้ชิ้นข้อมูลที่มีขนาดเล็กที่สุดเท่าที่จำเป็นเพื่อให้บรรลุเป้าหมายนี้
- สัญชาตญาณที่ง่ายที่สุดคือกรณีที่อ่านเพียง 2 เครื่องใดก็ได้จากเซิร์ฟเวอร์ 3 เครื่อง แล้วได้ไฟล์ทั้งไฟล์
- แบ่งไฟล์เป็นสองชิ้น A, B
- สร้างชิ้นที่สาม C เป็น A ⊕ B
- ถ้าอ่าน A กับ B ก็รวมกันได้ทันที และถ้าอ่าน A กับ C หรือ B กับ C ก็ใช้ XOR เพื่อกู้ชิ้นที่หายไป
- Erasure Code ทุกแบบทำให้แพตเทิร์นนี้เป็นรูปทั่วไป โดยแยกชิ้นข้อมูลกับ ชิ้นพาริตี
โมเดล k+m=n และ overhead ของพื้นที่จัดเก็บ
- การตั้งค่า Erasure Code เขียนเป็น k + m = n
- k: จำนวนชิ้นที่แบ่งข้อมูลออกมา และต้องอ่านอย่างน้อย k ชิ้นเพื่อกู้ค่า
- m: จำนวนชิ้นพาริตีที่จะสร้าง และเป็นจำนวนครั้งของการอ่านที่ล้มเหลวหรือจำนวนความขัดข้องที่ยอมให้เกิดได้
- n: จำนวนชิ้นทั้งหมดที่สร้างขึ้น
- ขนาดของชิ้นผลลัพธ์หนึ่งชิ้นคือ 1/k ของไฟล์ต้นฉบับ
- โดยทั่วไป Erasure Code มักถูกเรียกด้วย tuple แบบ
k+m- ชื่อตัวแปรในเอกสารแต่ละแหล่งไม่สอดคล้องกันเสมอไป
x+yหมายถึงชิ้นข้อมูล x ชิ้นและชิ้นพาริตี y ชิ้น
- เหตุผลที่ผู้ให้บริการจัดเก็บข้อมูลสนใจคือสามารถได้ความทนทานต่อความขัดข้องด้วย overhead ของพื้นที่จัดเก็บที่ต่ำ
- Backblaze B2 ใช้ 17+3 เพื่อทนต่อความล้มเหลว 3 จุดด้วยพื้นที่จัดเก็บ 1.18 เท่า
- OVH Cloud ใช้โค้ด 8+4 เพื่อทนต่อความล้มเหลว 4 จุดด้วยพื้นที่จัดเก็บ 1.5 เท่า
- Scaleway ใช้โค้ด 6+3 เพื่อทนต่อความล้มเหลว 3 จุดด้วยพื้นที่จัดเก็บ 1.5 เท่า
- ต้นทุนหลักคือการแลกเปลี่ยนระหว่างการลดพื้นที่จัดเก็บกับจำนวนคำขออ่านที่เพิ่มขึ้น
- แทนที่จะอ่านจากดิสก์เดียวเป็นขนาดเท่ากับไฟล์ จะส่งคำขอไปยัง ดิสก์ k+m ลูก
- ระบบจัดเก็บสำหรับข้อมูลที่ไม่ถูกเข้าถึงบ่อยเหมาะกับแนวทางนี้ เพราะภาระ IOPS เพิ่มเติมค่อนข้างน้อยและได้ผลลดพื้นที่จัดเก็บมาก
ขอบเขตของอัลกอริทึมและโค้ด MDS
- “Erasure Coding” ไม่ใช่อัลกอริทึมเฉพาะตัวเดียว แต่เป็น ตระกูลอัลกอริทึม
- โดยทั่วไปสามารถใช้ Reed-Solomon code เพื่อทำ Erasure Code สำหรับการตั้งค่า k+m ใด ๆ ได้
- มีความสัมพันธ์เทียบเคียงกับ RAID ด้วย
- RAID-0 คือ Erasure Coding แบบ k+0
- RAID-1 คือ Erasure Coding แบบ 1+m
- RAID-4 และ RAID-5 คือ Erasure Coding แบบ k+1 ที่ต่างกันเล็กน้อย
- RAID-6 คือ Erasure Coding แบบ k+2
- ขอบเขตของบทความนี้คือ Erasure Code แบบ MDS(Minimum Distance Separable)
- โค้ด MDS ให้คุณสมบัติคล้าย quorum ที่ทนต่อการสูญเสียชิ้นข้อมูล m ชิ้นใดก็ได้
- ตระกูล Erasure Code แบบอื่นอาจกู้คืนได้ด้วยชิ้นข้อมูลน้อยกว่า m ในบางชุด แต่ในบางชุดอาจต้องใช้ชิ้นข้อมูลมากกว่า m
- หากรู้รูปแบบความขัดข้องที่คาดว่าจะเกิดขึ้นล่วงหน้า อาจได้เปรียบกว่าหากทำให้ความขัดข้องที่พบบ่อยกู้คืนได้ด้วยชิ้นข้อมูลน้อยลง และให้ความขัดข้องที่เป็นข้อยกเว้นใช้ชิ้นข้อมูลมากขึ้น
- Local Reconstruction Codes และ SD Codes ของ Azure Storage ถูกกล่าวถึงเป็นตัวอย่างในทิศทางนี้
การใช้งานใน object storage และ cache
- จุดใช้งานที่ตรงที่สุดคือกรณีลดต้นทุนพื้นที่จัดเก็บและเพิ่ม durability ในระบบที่มีชุด replica คงที่
- ตัวอย่างคือที่เก็บข้อมูลแบบ blob/object หรือ NFS storage
- บริการ metadata จะ map เส้นทางไฟล์ไปยังเซิร์ฟเวอร์ที่เก็บไฟล์นั้น
- แทนที่ replica 3 ชุดจะเก็บไฟล์เต็มแต่ละชุด replica 15 ชุดสามารถเก็บชิ้นไฟล์ที่ทำ Erasure Code แบบ 10+5 ได้
- ปริมาณข้อมูลจัดเก็บรวมลดลงครึ่งหนึ่ง
- ความทนทานต่อความขัดข้องเพิ่มขึ้นมากกว่าสองเท่า
- แพตเทิร์นทั่วไปกว่าคือ “แทนที่จะเก็บข้อมูลบนเซิร์ฟเวอร์ X เครื่อง ให้เก็บบน replica X+m ชุดด้วย Erasure Code แบบ X+m”
- ตัวอย่างระบบแคชของ Marc Brooker นำแพตเทิร์นนี้ไปใช้กับ cache
- แทนที่จะใช้ consistent hashing เพื่อเลือกหนึ่งในเซิร์ฟเวอร์ cache k เครื่อง ให้ใช้ Erasure Code แบบ k+m บนเซิร์ฟเวอร์ cache k+m เครื่อง
- ไม่จำเป็นต้องรอ response ที่ช้าที่สุด m รายการ
- สามารถปรับปรุงทั้งพื้นที่จัดเก็บและ tail latency ได้พร้อมกัน
- การประหยัดนี้มาพร้อมต้นทุนเป็น IOPS/QPS หรือ CPU ที่เพิ่มขึ้น
- จำเป็นต้องมีสมมติฐานว่าทรัพยากรจำกัดของระบบคือความจุจัดเก็บ และยังมี CPU เหลือ
- สำหรับระบบที่ใกล้ถึงขีดจำกัด CPU อยู่แล้ว อาจไม่ใช่แนวคิดที่ช่วยลดต้นทุน
ข้อจำกัดของระบบ Quorum และ HRaft
- Quorum แบบเสียงข้างมากธรรมดาที่ต้องใช้ขั้นต่ำ 3 ชุดทั้งอ่านและเขียนจาก replica 5 ชุด เข้ากันได้ดีกับ Erasure Code แบบ 3+2 ในมุมการอ่าน
- เพราะสามารถอ่านจบได้จากผลลัพธ์ของ replica 3 ชุดใดก็ได้
- การเขียนสามารถเสร็จได้เมื่อ replica 3 ชุดใดก็ได้รับข้อมูล ดังนั้นถ้าใช้ Erasure Code แบบคงที่ จะใช้ได้เพียงโค้ด 1+2
- 1+2 เท่ากับการทำสำเนาไฟล์เต็ม 3 ชุด
- การใช้งานแบบตรงไปตรงมาจึงไม่ช่วยลดพื้นที่จัดเก็บ
- RS-Paxos มองว่าเมื่อใช้ Erasure Code กับ Paxos จะได้ประโยชน์ก็ต่อเมื่อส่วนทับซ้อนของ quorum สองชุดมีมากกว่า replica 1 ชุด
- เช่น ถ้า replica 7 ชุดต้องใช้ขั้นต่ำ 5 ชุดทั้งอ่านและเขียน จะทนความขัดข้องได้ 2 จุด และสามารถใช้โค้ด 3+2 ได้
- โดยทั่วไป เมื่อมี replica N ชุดและต้องการทนความขัดข้อง f จุด สิ่งที่ดีที่สุดที่ทำได้ด้วย Erasure Coding แบบคงที่คือ (N-2f)+f
- HRaft ปรับการ coding ให้สอดคล้องกับจำนวน replica ที่พร้อมใช้งาน แม้จะเป็น quorum แบบเสียงข้างมากธรรมดา
- ถ้าทั้ง 5 ชุดพร้อมใช้งาน จะเป็น 3+2
- ถ้าพร้อมใช้งาน 4 ชุด จะเป็น 2+2
- ถ้าพร้อมใช้งาน 3 ชุด จะเป็น 1+2
- แนวทาง adaptive มีโอกาสปรับปรุงได้ แต่ก็มีข้อจำกัดด้านปฏิบัติการมาก
- การเขียนแต่ละครั้งประเมินจำนวน replica ที่พร้อมใช้งานในปัจจุบันแบบมองโลกในแง่ดี
- หาก replica หนึ่งชุดไม่ยอมรับการเขียนโดยไม่คาดคิด ต้องเข้ารหัสการเขียนใหม่แล้วส่งไปยัง replica ทุกชุดอีกครั้ง
- แม้หลังความล้มเหลวสองครั้งและทำงานด้วยการตั้งค่า 1+2 ก็ต้อง provision ชุด replica ที่สามารถเก็บค่าทั้งหมดได้ เพื่อไม่ให้ availability พังเพราะพื้นที่ดิสก์หรือ throughput ไม่พอ
- หากความล้มเหลวเกิดไม่บ่อยและฟื้นตัวเร็ว adaptive encoding ของ HRaft จะให้การปรับปรุงได้มาก
ไลบรารีและตัวอย่างการใช้งาน
- สำหรับการคำนวณ Erasure Coding มีไลบรารีมาตรฐานที่สุกงอมแล้วคือ Jerasure
- บนโปรเซสเซอร์ Intel รุ่นใหม่ Intel Intelligent Storage Acceleration Library เป็นไลบรารีที่ optimize ด้วย SIMD และอยู่ในอันดับต้น ๆ ของ benchmark อย่างต่อเนื่อง
- ใน Python สามารถเข้าถึง implementation ของ Erasure Coding ได้ด้วย pyeclib
- ตัวอย่างใช้ไดรเวอร์
liberasurecode_rs_vand - แต่ละชิ้นจะมี metadata สำหรับระบุตำแหน่งนำหน้าอยู่
- ยังมี byte เพิ่มเติมบางส่วนด้วย
- ตัวอย่างใช้ไดรเวอร์
- ผลลัพธ์ตัวอย่างตามจำนวน replica ที่พร้อมใช้งานของ HRaft มีดังนี้
- 3+2, ต้นฉบับ 10000 byte: 5 ชิ้น, ชิ้นละ 3355 byte, รวมจริง 16775 byte, ประสิทธิภาพ 59.61%
- 2+2, ต้นฉบับ 10000 byte: 4 ชิ้น, ชิ้นละ 5021 byte, รวมจริง 20084 byte, ประสิทธิภาพ 49.79%
- 1+2, ต้นฉบับ 10000 byte: 3 ชิ้น, ชิ้นละ 10021 byte, รวมจริง 30063 byte, ประสิทธิภาพ 33.26%
- Erasure Encoding แบบ 1+2 เทียบเท่ากับสำเนาข้อมูลเต็ม 3 ชุด จึงเหมือนกับไม่ได้ใช้ Erasure Encoding
ต้นทุนการถอดรหัสและความแตกต่างของแต่ละ implementation
- ประสิทธิภาพการถอดรหัสขึ้นอยู่กับจำนวนชิ้นข้อมูลที่ต้องกู้คืน
- การถอดรหัสโค้ด 3+2 ด้วยชิ้นข้อมูล 3 ชิ้น แทบจะเป็นงานคำนวณที่เรียบง่าย
- หากถอดรหัสไฟล์เดียวกันด้วยชิ้นข้อมูล 2 ชิ้นและชิ้นพาริตี 1 ชิ้น ต้องแก้ระบบสมการเชิงเส้นด้วย Gaussian elimination
- ยิ่งจำนวนชิ้นพาริตีที่ต้องใช้เพิ่มขึ้น ปริมาณการคำนวณก็เพิ่มขึ้น
- เมื่อใช้ Erasure Code ในระบบ Quorum ต้นทุน CPU อาจต่างกันตามว่า replica ใดตอบกลับมา
- liberasurecode abstract ไลบรารี implementation ของ Erasure Coding ที่พบบ่อย แต่ไม่ได้หมายความว่า implementation เหล่านั้นเทียบเท่ากัน
- การที่โค้ดสองแบบเป็น 3+2 ทั้งคู่ ไม่ได้หมายความว่าสร้างด้วยคณิตศาสตร์เดียวกัน
- liberasurecode เพิ่ม metadata ที่จำเป็นต่อการตั้งค่าและใช้งาน decoder นอกเหนือจากงาน linear algebra
- metadata นี้ไม่สามารถปิดหรือแก้ไขได้
- หากใช้ Jerasure หรือ ISA-L โดยตรง จะจัดการได้เฉพาะข้อมูลที่ทำ Erasure Code แล้ว
- อย่างไรก็ตาม API ต้องให้ข้อมูลด้วยว่าแต่ละชิ้นเป็นชิ้นข้อมูลลำดับที่ N หรือชิ้นพาริตี ดังนั้นต้องคง index ไว้เป็น metadata ด้วยวิธีใดวิธีหนึ่ง
- Jerasure และ ISA-L ต่างกันในข้อกำหนดด้านการจัดเรียงด้วย
- Jerasure ใช้ permutation กับผลลัพธ์ linear algebra ที่คาดหวัง
- Jerasure ไม่สามารถอ่าน subset หรือ superset ของสิ่งที่เข้ารหัสไว้แบบไม่เรียงลำดับได้
- ISA-L ไม่ใช้ permutation จึงถอดรหัส subset หรือ superset ที่ไม่เรียงลำดับได้
- implementation อื่น ๆ ก็เป็นตัวเลือกได้
- tahoe-lafs/zfec
- catid/cm256
- catid/longhair
- catid/leopard
- หากกลายเป็น bottleneck ก็อาจหาไลบรารีที่ optimize สำหรับ use case เฉพาะมากขึ้นได้ แต่โดยทั่วไป ISA-L ดีพอ
การเลือกอัลกอริทึมและโครงสร้างทางคณิตศาสตร์
- ในการใช้งานจริง สามารถมอง Erasure Code เป็นเหมือน ฟังก์ชันวิเศษ ที่เปลี่ยนไฟล์ 1 ไฟล์เป็นชิ้นข้อมูล n ชิ้นแล้วกู้กลับมาได้ โดยไม่มีปัญหา
- การสร้างชิ้นข้อมูล n ชิ้นโดยทั่วไปทำด้วย linear algebra ที่ใช้ Galois Field
- ไม่จำเป็นต้องเข้าใจคณิตศาสตร์นี้เพื่อใช้งาน Erasure Code อย่างมีประสิทธิผล
- โค้ด MDS ส่วนใหญ่คำนวณด้วยการคูณเมทริกซ์
- การบวกถูกแทนด้วย XOR
- การคูณถูกแทนด้วยการคูณบน GF(256) ที่มีต้นทุนสูงกว่า
- กรณีพิเศษที่จำนวนชิ้นพาริตี 1–3 ชิ้น มีอัลกอริทึมเฉพาะ XOR ที่ไม่ใช่ Reed-Solomon
- m=1: ชิ้นพาริตีเดี่ยวที่เป็น XOR ของชิ้นข้อมูลทั้งหมด
- m=2: เทียบเท่า RAID-6 และมีการกล่าวถึง Liberation codes, HDP codes, EVENODD, X-Codes เป็นต้น
- m=3: ทำได้ด้วย STAR coding
- ในกรณีทั่วไปใช้ตระกูล Reed-Solomon
- ใช้การสร้างเมทริกซ์ Vandermonde หรือเมทริกซ์ Cauchy
- เป้าหมายคือให้ส่วนบน k×k เป็น identity matrix เพื่อคงชิ้นข้อมูลแต่ละชิ้นไว้ และยังมี inverse matrix อยู่หลังจากลบแถว m แถว
- การเข้ารหัสคือการคูณด้วยเมทริกซ์นี้ และการถอดรหัสคือการลบแถวที่ตรงกับชิ้นที่ถูกลบ แล้วแก้ระบบสมการเชิงเส้น
- Gaussian elimination ที่ ISA-L ใช้เป็นวิธีถอดรหัสที่ง่ายที่สุดแต่ช้าที่สุด
- สำหรับเมทริกซ์ Cauchy สามารถปรับปรุงได้ และ catid/cm256 ใช้วิธีนี้
- วิธีที่เร็วที่สุดในปัจจุบันดูเหมือนจะเป็น implementation ใน catid/leopard ซึ่งใช้ Fast Fourier Transform สำหรับการเข้ารหัสและถอดรหัส
ขั้นตอนการเพิ่มประสิทธิภาพ implementation
- วิธีทำให้ implementation ของ Erasure Code ที่ทำงานกับการตั้งค่า k+m ใด ๆ เร็วขึ้น แบ่งได้หลายขั้น
- ขั้นแรกคือ implement อัลกอริทึมด้วย C และพึ่งพา auto-vectorization ของ compiler
- ง่ายที่สุดและ portability สูง
- การใช้
restrictและการระบุ flag compile ตามสถาปัตยกรรมอย่าง-march=nativeเป็นเรื่องสำคัญ
- ขั้นที่สองคือ abstract รายละเอียดของ platform ด้วยไลบรารี vectorization หรือ compiler intrinsic
- google/highway
- xtensor-stack/xsimd
std::experimental::simd- GCC vector extension builtins
- แกนหลักของการเข้ารหัสและถอดรหัสคือการคูณและการบวกใน Galois Field
- ไลบรารีที่ optimize แล้วซึ่งถูกกล่าวถึงคือ catid/gf256 และ James Plank’s Fast Galois Field Arithmetic Library
- ขั้นที่สามคือเขียนฟังก์ชันเข้ารหัส/ถอดรหัสแกนหลักโดย vectorize เอง
- fast-gf-multiplication และ xor_depends work ของโครงการ PARPAR กล่าวถึงการคำนวณ GF(256) ที่รวดเร็ว
- สรุปว่ามีฉันทามติว่า GF multiplication แบบใช้ XOR ล้วนเร็วกว่า multiplication แบบใช้ตาราง
- ถัดไปยังสามารถ specialize โค้ดให้เหมาะกับการตั้งค่า k+m เฉพาะได้
- หา coding matrix และ XOR schedule ที่เหมาะที่สุดกับ GF polynomial และ encoding matrix เฉพาะ
- ใช้การ optimize ด้าน operation, memory และ cache
- ใช้โปรแกรมค้นหา instruction schedule ที่เหมาะที่สุดสำหรับสถาปัตยกรรมเฉพาะ
- implementation และเอกสารที่เกี่ยวข้องที่ถูกนำเสนอ ได้แก่ yuezato/xorslp_ec, Thesys-lab/tvm-ec, "Fast Erasure Coding for Data Storage: A Comprehensive Study of the Acceleration Techniques"
แหล่งข้อมูลสำหรับอ่านลึกขึ้น
- ลิงก์ต่อไปนี้มีประโยชน์สำหรับการเริ่มต้นเรียน linear algebra ของ Erasure Coding
- บทนำพื้นฐาน ของ Backblaze
- "A Gentle Introduction to Erasure Codes" ของ Fred Akalin
- "Reed-Solomon Error Correcting Codes from the Bottom Up"
- Tutorial on Reed-Solomon Error Correction Coding ของ NASA
- หากต้องการเจาะลึกอย่างกว้างขวาง มีข้อเสนอให้เริ่มจาก ผลงานตีพิมพ์ของ James S. Plank
1 ความคิดเห็น
ความคิดเห็นจาก Hacker News
แปลกใจที่ไม่มีการพูดถึง rateless fountain code ถ้าชอบหัวข้อนี้ Luby Transform Code ก็น่าสนใจ: https://en.wikipedia.org/wiki/Luby_transform_code
งานวิจัยชิ้นนี้ก็ให้ภาพรวมที่ละเอียดมากขึ้น: https://switzernet.com/people/emin-gabrielyan/060112-capilla...
LT code ถูกใช้เป็น outer code ใน RaptorQ encoding แบบเวลาเชิงเส้นที่ระบุไว้ใน RFC6330: https://www.rfc-editor.org/rfc/rfc6330
อย่างที่สอง ตัวอัลกอริทึมจริง ๆ แบ่งเป็นสองส่วน โดยส่วนที่สองคือการสร้าง recovery block ซึ่งเป็นเชิงเส้น แต่ส่วนแรกใช้เวลา กำลังสาม ตามจำนวนข้อความที่รวมไว้ในหนึ่งบล็อก ซึ่งแทบจะเทียบได้กับ Gaussian elimination ของเมทริกซ์
แม้จะ cache บางส่วนของ encoding และ decoding ได้ แต่ linear-time encoding ของ RaptorQ ก็ดูเป็นคำโฆษณาทางการตลาดมากกว่า
เมื่อก่อนมีคนเสนออัลกอริทึม erasure coding แบบน่ารักที่อาศัย เครือข่ายหลายเส้นทาง แทนดิสก์หมุน
น่าจะเรียกว่า network coding เป็นแนวคิดที่ว่าในเครือข่ายที่มีหลายเส้นทาง แทนที่จะรอไฟล์เต็มจากเซิร์ฟเวอร์หลัก ก็รับไฟล์สองส่วนจาก upstream หนึ่งแห่ง หรือรับ erasure code ที่ผสมสองไฟล์เข้าด้วยกัน เพื่อให้ได้ไฟล์เร็วขึ้น
เดาว่าเบื้องหลัง S3 หรือระบบ cloud storage อื่น ๆ ก็น่าจะใช้วิธีคล้ายกันอยู่มาก โดยเฉพาะในชั้นจัดเก็บข้อมูลที่เข้าถึงไม่บ่อย แต่ก็ไม่ได้รู้ระบบภายในของ AWS หรือ GCP จริง ๆ
อ้างอิงไว้ว่า Freenet อย่างน้อยก็ใช้ไฟล์ที่เข้ารหัสด้วย FEC ทำให้ยืดหยุ่นขึ้นว่าจะรับชิ้นไหน และลดโอกาสที่ไฟล์ทั้งไฟล์จะเสียเพราะชิ้นเดียวหายไป
erasure coding มีมานานมากแล้ว จำไฟล์ PAR2 ของ Usenet ได้ไหม? https://en.wikipedia.org/wiki/Parchive
ถ้าสนใจ erasure coding ก็ควรพิจารณากรณีแบบ หลายมิติ ที่ใหญ่กว่าด้วย ไม่ใช่แค่เข้ารหัสข้ามหลายดิสก์ แต่รวมถึงโดเมนความเสียหายอื่น ๆ อย่างแร็ก ห้อง ดาต้าเซ็นเตอร์ และรีเจียนด้วย
เป้าหมายคือการทนต่อทั้งความล้มเหลวของชิ้นส่วนร่วมกันและความล้มเหลวหรือการแบ่งแยกระดับระบบที่ใหญ่กว่า บทความเริ่มต้นที่ดี: https://chameleoncloud.org/blog/2023/12/12/design-considerat...
ถ้าสายเคเบิลใยแก้วใต้น้ำข้ามมหาสมุทรมีได้แค่ 1Tbps การย้ายข้อมูลทั้งหมดอาจใช้เวลา มากกว่า 6 เดือน
อยากรู้ว่ามีใครเคยใช้ Wirehair ในโปรเจกต์บ้างไหม: https://github.com/catid/wirehair
สงสัยว่ามันถูกนิยามไว้ดีพอที่จะใช้เป็นฐานมาตรฐานสำหรับโปรเจกต์เก็บถาวรไฟล์ขนาดใหญ่/กู้คืนข้อมูลที่คิดมาเกือบ 10 ปีได้หรือไม่ แม้จะไม่ใช่มาตรฐานทางการ ก็อยากรู้ว่าสามารถใช้เป็นมาตรฐานโดยพฤตินัยได้ไหม
จากบรรดา large-block deletion code ที่หาเจอจนถึงตอนนี้ มีแค่นี่ตัวเดียวที่มีทั้งประสิทธิภาพของอัลกอริทึมและ API ที่อยู่ในระดับอุดมคติหรือเกือบอุดมคติ เลยทำให้มันเป็น black box ที่ดีสำหรับงานของผม ต่างจาก RaptorQ ที่มีรายละเอียดจุกจิกเล็ดรอดออกมาหลายจุดจนเพิ่มความซับซ้อนและความแข็งทื่อให้กับสแต็กส่วนที่เหลือ
แต่ Wirehair ไม่ใช่สเปก มันเป็น implementation ของแนวคิดหนึ่ง และยังดูเหมือน implementation เชิงทดลองด้วย มันดูเสถียรดีอยู่หรอก แต่ก็ยังกังวลว่าจะย้ายไปใช้สเปกที่เชื่อถือได้หรือ implementation ตัวที่สองได้ง่ายหรือไม่ จนกว่าจะได้ลองเขียนตัวที่สองเอง หรือมีการใช้งานแพร่หลายพอให้มุมคมของอัลกอริทึมถูกเปิดเผย
แต่ Qualcomm อาจอ้างได้ว่ามันติดสิทธิบัตร RaptorQ เพราะมีความเกี่ยวข้องกันในเชิงแนวคิด สิทธิบัตรที่เก่าที่สุดในชุดนั้นน่าจะใกล้หมดอายุหรือหมดอายุไปแล้ว แต่ผมยังไม่ได้เช็ก file wrapper ชุดล่าสุด Qualcomm เคยให้คำมั่นบางส่วนว่าจะไม่บังคับใช้สิทธิบัตร RaptorQ นอกงานไร้สาย แต่จำไม่ได้ว่าครอบคลุมเฉพาะ implementation ที่ทำตามมาตรฐานหรือเปล่า
ถ้าจะใช้ในตัวโปรโตคอล Bitcoin เอง ก็จำเป็นต้องทำให้เป็นสเปก เลยเคยลองดูว่าต้องใช้อะไรบ้าง ผมกับนักพัฒนา Bitcoin อีกหลายคนค่อนข้างคุ้นกับทฤษฎีจำนวนและ error-correcting code แต่ก็ไม่ได้รู้สึกอยากทำงานนั้นมากนัก เพราะโครงสร้างของ Wirehair มี รายละเอียดแบบแก้ขัดเฉพาะหน้า อยู่พอสมควร และด้วยนิสัยของพวกเรา อาจเผลอพยายามปรับปรุงมันจนตกหลุมพรางได้
ฝั่ง Bitcoin อาจกลับมาสนใจการใช้ fountain code อย่างแพร่หลายอีกครั้ง ดังนั้นถ้ารอสักหน่อยก็อาจมีใครสักคนเขียนสเปกให้
แล้วแต่ use case ที่แน่ชัด https://github.com/catid/fecal ก็อาจน่าสนใจเช่นกัน ถ้าจำนวน erasure ที่คาดไว้ต่ำมาก มันอาจเร็วกว่า Wirehair
ส่วน Leopard ที่กล่าวถึงในบทความไม่ใช่ fountain code แต่มีขนาดบล็อกค่อนข้างใหญ่ ในแง่การทำเป็นสเปกนี่เป็นข้อดี เพราะมันเป็นแค่ Reed-Solomon code แบบเรียบง่ายที่ทำให้เร็วมาก ดังนั้นในสเปกอาจต้องเอกสารเพียงการเลือก field กับ generator เท่านั้น
ใช่ นี่คือเทคโนโลยีหลักที่อยู่เบื้องหลัง Erasure Code pool ของ Ceph: https://docs.ceph.com/en/latest/rados/operations/erasure-cod...
แต่ก็ไม่ได้ฟรีทั้งหมด ภายหลังคุณไม่สามารถเปลี่ยนพารามิเตอร์การเข้ารหัสอย่าง k, m ได้ จึงต้องมั่นใจว่าค่าเหล่านั้นจะยังเหมาะไปอีกนาน ไม่อย่างนั้นก็ต้องเริ่มใหม่ตั้งแต่ต้น
เพราะความไม่ยืดหยุ่นแบบนี้ ในงานจัดเก็บข้อมูลที่ต้องทนทานต่อความขัดข้องและมีความพร้อมใช้งานสูง การทำสำเนายังเป็นตัวเลือกหลักอยู่ดี
มันแค่ใช้
--forceแล้วทิ้ง ไฟล์ซิสเต็มที่เสียหาย ไว้คงเป็นความน่าขำประเภท “ถ้าอยู่ตรงนั้นคงขำ แต่ถ้าเป็นฉันเจอเองคงไม่ขำ” มากกว่า
ถ้าผลลัพธ์ที่สร้างขึ้นในสภาวะที่มีได้เพียง M จาก N ความขัดข้อง ถูกเข้ารหัสต่างจากตอนที่ N พร้อมครบทั้งหมด แบบนั้นก็น่าจะควรมี บิตแฟล็ก ที่บอกว่า “ถ้า N กลับมาครบแล้วต้อง re-encode” ใช่ไหม
ไม่อย่างนั้นก็จะเหลือไฟล์ที่เมื่อมีการสูญหายแบบสุ่มในชุด N แล้ว ความสามารถในการกู้คืนจะไม่ค่อยดีนัก
ทุกระบบสตอเรจแบบกระจายต้องมีบรรณารักษ์สักประเภทหนึ่งที่คอยตรวจสอบและจัดระเบียบ stripe เพื่อพามันออกจากสภาวะเสี่ยง
ทำให้นึกถึง Information Dispersal Algorithm ของ Rabin ด้วย มีอธิบายไว้ในงานวิจัยนี้:
https://dl.acm.org/doi/10.1145/62044.62050
ในทางปฏิบัติ มันใช้ได้จริงเฉพาะกับงานที่ อ่านอย่างเดียว หรือมีภาระงานแบบอ่านหนักมากเท่านั้นหรือ?