वितरित सिस्टम के लिए Erasure Coding तकनीक
(transactional.blog)- Erasure Coding डेटा को टुकड़ों और parity में बांटकर, पूरी replication की तुलना में कम storage space में failures सहने वाला storage efficiency और fault tolerance का trade-off तरीका है
- मूल मॉडल k+m=n है, जहाँ k recovery के लिए जरूरी data chunks की संख्या, m parity chunks की संख्या और सहन किए जा सकने वाले failures की संख्या, और n कुल chunks की संख्या है
- object/blob storage में 3-way full replication की जगह 10+5 जैसी configuration का उपयोग कर छोटे chunks को अधिक servers पर रखा जा सकता है और storage मात्रा घटाई जा सकती है
- Quorum systems में सिर्फ साधारण majority voting से storage बचत सीमित रहती है; HRaft की तरह उपलब्ध replicas की संख्या के अनुसार 3+2, 2+2, 1+2 में बदलने पर re-encoding और capacity provisioning का बोझ आता है
- वास्तविक adoption में response chunks के combination के अनुसार decoding cost variation और Jerasure·ISA-L·liberasurecode की metadata/alignment requirements में अंतर को verify करना चाहिए
storage efficiency और failure tolerance का मूल trade-off
- N servers पर file store करने के दो extreme तरीके हैं
- अगर हर server पर पूरी file replica रखी जाए, तो N-1 servers गायब होने पर भी file नहीं खोती, लेकिन storage cost सबसे ज्यादा होती है
- file को N समान आकार के chunks में बांटकर हर server पर एक-एक store किया जाए, तो storage efficiency सबसे अच्छी होती है, लेकिन पढ़ते समय सभी N chunks चाहिए होते हैं
- Erasure Coding इन दोनों extremes के बीच storage efficiency और failure tolerance को adjust करता है
- “file को N chunks में बांटना है, लेकिन M chunks नष्ट होने पर भी recovery संभव रखनी है” इस लक्ष्य के अनुसार code बनाया जा सकता है
- यह इस लक्ष्य को पूरा करने के लिए जरूरी न्यूनतम आकार के chunks देता है
- सबसे सरल intuition 3 servers में से कोई भी 2 पढ़कर पूरी file पाने के उदाहरण से मिलती है
- file को दो chunks A, B में बांटें
- तीसरा chunk C को A ⊕ B से बनाएं
- A और B पढ़ें तो उन्हें वैसे ही जोड़ दें, और A और C या B और C पढ़ें तो XOR से missing chunk recover करें
- सभी Erasure Codes data chunks और parity chunks को अलग करके इसी pattern को generalize करते हैं
k+m=n मॉडल और storage overhead
- Erasure Code configuration को k + m = n से व्यक्त किया जाता है
- k: data को बांटने वाले chunks की संख्या; value recover करने के लिए कम से कम k chunks पढ़ने होंगे
- m: बनाए जाने वाले parity chunks की संख्या; यह incomplete रह सकने वाली read failures या failure tolerance की संख्या है
- n: बनाए गए कुल chunks की संख्या है
- result का एक chunk original file के 1/k आकार का होता है
- Erasure Code को आम तौर पर
k+mtuple कहा जाता है- literature में variable names consistent नहीं होते
x+yका मतलब x data chunks और y parity chunks होता है
- storage providers के लिए यह इसलिए आकर्षक है क्योंकि कम storage overhead में failure tolerance मिलती है
- Backblaze B2 17+3 का उपयोग करता है और 1.18x storage space में 3 failures सहता है
- OVH Cloud 8+4 code से 1.5x storage space में 4 failures सहता है
- Scaleway 6+3 code से 1.5x storage space में 3 failures सहता है
- मुख्य cost storage space घटाने और read requests की संख्या बढ़ने के बीच का exchange है
- एक disk से file size जितना पढ़ने के बजाय k+m disks को requests भेजी जाती हैं
- कम access किए जाने वाले data के लिए storage systems उपयुक्त हैं, क्योंकि extra IOPS burden अपेक्षाकृत छोटा और storage saving बड़ी होती है
algorithms का scope और MDS code
- “Erasure Coding” कोई एक specific algorithm नहीं, बल्कि algorithms की family है
- Reed-Solomon codes को सामान्य तौर पर किसी भी k+m configuration वाले Erasure Code implementation में इस्तेमाल किया जा सकता है
- RAID से भी इसका संबंध है
- RAID-0 k+0 Erasure Coding है
- RAID-1 1+m Erasure Coding है
- RAID-4 और RAID-5 थोड़े अलग k+1 Erasure Coding हैं
- RAID-6 k+2 Erasure Coding है
- इस article का scope MDS(Minimum Distance Separable) Erasure Code है
- MDS code किसी भी m chunks के loss को सहने वाली quorum जैसी property देता है
- दूसरी Erasure Code families कुछ combinations में m से कम chunks से recover कर सकती हैं, लेकिन दूसरे combinations में m से अधिक chunks चाहिए हो सकते हैं
- अगर expected failure pattern पता हो, तो frequent failures को कम chunks से recover करना और exceptional failures को अधिक chunks से recover करना फायदेमंद हो सकता है
- Azure Storage के Local Reconstruction Codes और SD Codes को इस दिशा के examples के रूप में देखा जाता है
object storage और cache में application
- सबसे direct application fixed replica set वाले systems में storage cost घटाकर durability बढ़ाने का है
- उदाहरण blob/object storage या NFS storage हैं
- metadata service file path को उस file को store करने वाले servers से map करती है
- जहाँ 3 replicas में हर एक पूरी file store करता है, उसकी जगह 15 replicas 10+5 Erasure Coded file chunks store कर सकते हैं
- कुल stored data amount आधी हो जाती है
- failure tolerance दोगुनी से अधिक हो जाती है
- अधिक सामान्य pattern है “X servers पर data store करने के बजाय, X+m replicas पर X+m Erasure Code से store करना”
- Marc Brooker के caching system का example इस pattern को cache पर apply करता है
- consistent hashing से k cache servers में से एक चुनने के बजाय k+m cache servers पर k+m Erasure Code का उपयोग करता है
- सबसे धीमे m responses का इंतजार नहीं करना पड़ता
- storage space और tail latency दोनों सुधर सकते हैं
- इस saving के साथ IOPS/QPS या CPU बढ़ने की cost आती है
- यह assumption चाहिए कि system का limiting resource storage capacity है और CPU spare है
- जो systems पहले से CPU limit के करीब हैं, उनके लिए यह cost-saving idea नहीं हो सकता
Quorum systems की सीमाएँ और HRaft
- 5 replicas में reads और writes दोनों के लिए कम से कम 3 की जरूरत वाला simple majority quorum, read के लिहाज से 3+2 Erasure Code से अच्छी तरह मेल खाता है
- क्योंकि किसी भी 3 replicas के result से read पूरा किया जा सकता है
- write किसी भी 3 replicas द्वारा accept होने पर complete हो सकता है, इसलिए fixed Erasure Code में सिर्फ 1+2 code ही इस्तेमाल किया जा सकता है
- 1+2 file की 3 full replicas जैसा है
- simple application भर से storage saving नहीं होती
- RS-Paxos मानता है कि Paxos में Erasure Code apply करते समय फायदा तभी है जब दो quorums का overlap 1 replica से बड़ा हो
- उदाहरण के लिए, 7 replicas में अगर reads/writes दोनों के लिए कम से कम 5 चाहिए हों, तो failure tolerance 2 रखते हुए 3+2 code apply किया जा सकता है
- सामान्यतः N replicas और desired failure tolerance f होने पर fixed Erasure Coding से संभव best (N-2f)+f है
- HRaft simple majority quorum में भी available replicas की संख्या के अनुसार coding adjust करता है
- सभी 5 available हों तो 3+2
- 4 available हों तो 2+2
- 3 available हों तो 1+2
- adaptive approach में improvement की गुंजाइश है, लेकिन operational constraints भी बड़े हैं
- हर write current available replicas की संख्या का optimistic estimate लगाता है
- अगर कोई replica unexpected रूप से write acknowledge नहीं करता, तो write को recode करके सभी replicas को फिर भेजना पड़ता है
- दो failures के बाद 1+2 configuration में चलते समय भी disk space या throughput की कमी से availability न टूटे, इसके लिए पूरी value store कर सकने वाली replica configuration provision करनी होती है
- failures rare हों और जल्दी recover हों, तो HRaft की adaptive encoding काफी improvement देती है
libraries और usage example
- Erasure Coding calculation के लिए mature standard library Jerasure उपलब्ध है
- latest Intel processors पर Intel Intelligent Storage Acceleration Library SIMD-optimized library है और benchmarks में लगातार शीर्ष पर रहती है
- Python में pyeclib से Erasure Coding implementations access किए जा सकते हैं
- example
liberasurecode_rs_vanddriver का उपयोग करता है - हर chunk के आगे position identification के लिए metadata जुड़ा होता है
- कुछ additional bytes भी मौजूद होते हैं
- example
- HRaft में available replicas की संख्या के अनुसार example results इस प्रकार हैं
- 3+2, original 10000 bytes: 5 chunks, 3355 bytes per chunk, actual total 16775 bytes, efficiency 59.61%
- 2+2, original 10000 bytes: 4 chunks, 5021 bytes per chunk, actual total 20084 bytes, efficiency 49.79%
- 1+2, original 10000 bytes: 3 chunks, 10021 bytes per chunk, actual total 30063 bytes, efficiency 33.26%
- 1+2 Erasure Encoding data की 3 full replicas जैसा है, इसलिए Erasure Encoding लागू न करने के बराबर है
decoding cost और implementations के अंतर
- decoding performance इस पर निर्भर करती है कि कितने data chunks recover करने हैं
- 3+2 code को 3 data chunks से decode करना computationally लगभग simple है
- 2 data chunks और 1 parity chunk से वही file decode करने के लिए Gaussian elimination से linear equation system solve करना पड़ता है
- जितने ज्यादा parity chunks चाहिए, computation उतना बढ़ता है
- Quorum system में Erasure Code इस्तेमाल करने पर कौन से replicas ने response दिया, इसके अनुसार CPU cost बदल सकती है
- liberasurecode common Erasure Coding implementation libraries को abstract करता है, लेकिन इसका मतलब यह नहीं कि implementations समान हैं
- दो codes दोनों 3+2 हैं, इसका मतलब यह नहीं कि वे एक ही mathematics से बने हैं
- liberasurecode linear algebra operations के साथ decoder setup और usage के लिए जरूरी metadata भी जोड़ता है
- इस metadata को disable या modify नहीं किया जा सकता
- Jerasure या ISA-L को directly इस्तेमाल करें तो सिर्फ Erasure Coded data handle किया जा सकता है
- हालांकि API में हर chunk को यह साथ में बताना पड़ता है कि वह Nth data chunk है या parity chunk, इसलिए index को किसी न किसी तरह metadata के रूप में बनाए रखना होगा
- Jerasure और ISA-L में alignment requirements में भी अंतर है
- Jerasure expected linear algebra output पर permutation apply करता है
- Jerasure encoded चीज़ के subset या superset को unordered तरीके से read नहीं कर सकता
- ISA-L permutation apply नहीं करता, इसलिए unordered subset या superset decoding संभव है
- दूसरे implementations भी options में शामिल हैं
- tahoe-lafs/zfec
- catid/cm256
- catid/longhair
- catid/leopard
- अगर bottleneck बने, तो specific use case के लिए अधिक optimized library मिल सकती है, लेकिन ISA-L आम तौर पर पर्याप्त अच्छी है
algorithm selection और mathematical construction
- Erasure Code को एक magic function की तरह मानना, जो 1 file को n chunks में बदलता और फिर recover करता है, practical usage में कोई समस्या नहीं है
- n chunks की construction आम तौर पर Galois Field का उपयोग करने वाली linear algebra से होती है
- Erasure Code को productively इस्तेमाल करने के लिए इस mathematics को समझना अनिवार्य नहीं है
- ज्यादातर MDS codes matrix multiplication से calculate होते हैं
- addition को XOR से replace किया जाता है
- multiplication को GF(256) पर अधिक महंगी multiplication से replace किया जाता है
- parity chunks की संख्या 1~3 होने वाले special cases में Reed-Solomon नहीं, बल्कि XOR-only algorithms हैं
- m=1: सभी data chunks का XOR, यानी single parity chunk
- m=2: RAID-6 के बराबर; Liberation codes, HDP codes, EVENODD, X-Codes आदि का उल्लेख है
- m=3: STAR coding से संभव है
- general case में Reed-Solomon family इस्तेमाल होती है
- Vandermonde matrix या Cauchy matrix construction इस्तेमाल होती है
- goal यह है कि ऊपर का k×k identity matrix हो, जिससे हर data chunk preserved रहे, और m rows delete करने के बाद भी inverse matrix मौजूद रहे
- encoding इस matrix को multiply करना है, और decoding erased chunks से संबंधित rows delete करने के बाद linear equation system solve करना है
- ISA-L द्वारा इस्तेमाल Gaussian elimination सबसे सरल लेकिन सबसे slow decoding method है
- Cauchy matrix में improvement संभव है, और catid/cm256 इसका उपयोग करता है
- अभी सबसे fast method catid/leopard में implemented लगता है, जो encoding और decoding में Fast Fourier Transform का उपयोग करता है
implementation efficiency के चरण
- arbitrary k+m configuration में काम करने वाले Erasure Code implementation को fast बनाने के तरीके कई चरणों में बंटे हैं
- पहला चरण C में algorithm implement करके compiler auto-vectorization पर निर्भर रहने का है
- यह सबसे simple और portable है
restrictका उपयोग और-march=nativeजैसे architecture-specific compile flags देना महत्वपूर्ण है
- दूसरा तरीका vectorization libraries या compiler intrinsics से platform details को abstract करना है
- google/highway
- xtensor-stack/xsimd
std::experimental::simd- GCC vector extension builtins
- encoding और decoding का core Galois Field multiplication और addition है
- optimized libraries के रूप में catid/gf256 और James Plank’s Fast Galois Field Arithmetic Library का उल्लेख है
- तीसरा तरीका core encoding/decoding functions को directly vectorize करके लिखना है
- PARPAR project का fast-gf-multiplication और xor_depends work fast GF(256) operations को cover करते हैं
- इसे इस तरह summarize किया गया है कि XOR-only GF multiplication, table-based multiplication से तेज है, इस पर consensus है
- आगे बढ़कर specific k+m configuration के हिसाब से code specialize किया जा सकता है
- specific GF polynomial और encoding matrix के लिए optimal coding matrix और XOR schedule खोजें
- operations, memory और cache optimization apply करें
- specific architecture के लिए optimal instruction schedule को programmatically search करें
- related implementations और resources के रूप में yuezato/xorslp_ec, Thesys-lab/tvm-ec, "Fast Erasure Coding for Data Storage: A Comprehensive Study of the Acceleration Techniques" दिए गए हैं
और गहराई से पढ़ने के resources
- Erasure Coding linear algebra introduction के लिए ये links उपयोगी हैं
- व्यापक रूप से गहराई में जाने के लिए James S. Plank’s publications से review शुरू करने का तरीका सुझाया गया है
1 टिप्पणियां
Hacker News की राय
हैरानी हुई कि rateless fountain codes का ज़िक्र नहीं था। अगर आपको ऐसे विषय पसंद हैं, तो Luby Transform Code दिलचस्प लगेगा: https://en.wikipedia.org/wiki/Luby_transform_code
यह पेपर भी ज्यादा विस्तृत अवलोकन के लिए अच्छा है: https://switzernet.com/people/emin-gabrielyan/060112-capilla...
LT codes का उपयोग RFC6330 में निर्दिष्ट linear-time RaptorQ encoding में outer code के रूप में होता है: https://www.rfc-editor.org/rfc/rfc6330
दूसरी बात, algorithm वास्तव में दो हिस्सों में बंटा है। दूसरा हिस्सा, यानी recovery blocks बनाना, linear है, लेकिन पहला हिस्सा एक block में बांधे गए messages की संख्या के हिसाब से cubic time लेता है। यह लगभग matrix Gaussian elimination के बराबर है
encoding और decoding के कुछ हिस्सों को cache किया जा सकता है, लेकिन RaptorQ की linear-time encoding असल में लगभग marketing copy लगती है
पहले किसी ने एक प्यारा-सा erasure code algorithm प्रस्तावित किया था, जो spinning disks के बजाय multi-path networking पर निर्भर करता था
शायद उसे network coding कहा जाता था, और विचार यह था कि कई paths वाले network में, main server से पूरी file का इंतज़ार करने के बजाय किसी upstream से file के दो हिस्से, या दो files का मिला हुआ erasure code पाकर file को जल्दी हासिल किया जा सके
लगता है S3 या दूसरे cloud storage systems के पीछे भी ऐसी तकनीक काफी इस्तेमाल होती होगी, खासकर कम-access वाले storage tiers में। हालांकि AWS या GCP के आंतरिक systems के बारे में मुझे प्रत्यक्ष जानकारी नहीं है
जानकारी के लिए, Freenet कम से कम FEC-coded files का उपयोग करता था, जिससे यह लचीलापन मिलता है कि कौन-सा chunk लिया जाए, और किसी एक chunk के गायब होने से पूरी file टूट जाने की संभावना कम होती है
erasure coding बहुत लंबे समय से मौजूद है। Usenet की PAR2 files याद हैं? https://en.wikipedia.org/wiki/Parchive
अगर आपको erasure coding में दिलचस्पी है, तो बड़े multi-dimensional use cases पर भी विचार करना चाहिए। मतलब सिर्फ कई disks पर encoding नहीं, बल्कि racks, rooms, data centers, regions जैसे अलग failure domains को भी साथ में ध्यान में रखना
लक्ष्य सिर्फ common component failures ही नहीं, बल्कि बड़े system failures या partitions को भी सहना है। शुरुआत के लिए अच्छा लेख: https://chameleoncloud.org/blog/2023/12/12/design-considerat...
अगर transoceanic fiber cable सिर्फ 1Tbps की हो, तो पूरा data स्थानांतरित करने में 6 महीने से ज्यादा लग सकते हैं
क्या किसी ने प्रोजेक्ट में Wirehair इस्तेमाल किया है?: https://github.com/catid/wirehair
मैं जानना चाहता हूँ कि क्या यह लगभग 10 साल से सोच रहे बड़े फ़ाइल archiving/data recovery प्रोजेक्ट के standard basis के रूप में अपनाने लायक पर्याप्त रूप से well-defined है। भले ही यह official standard न हो, क्या इसे एक de facto standard की तरह इस्तेमाल किया जा सकता है, यह जानना चाहता हूँ
अब तक मिले बड़े block deletion codes में ideal या लगभग ideal algorithm performance और API—दोनों रखने वाला यही एकमात्र है। इसलिए RaptorQ की तरह छोटे-छोटे details के बाकी stack में हर जगह leak होकर complexity और rigidity बढ़ाने के बजाय, मेरे use case में यह एक अच्छा black box बनता है
लेकिन Wirehair कोई specification नहीं, बल्कि किसी idea की implementation है, और कुछ हद तक experimental implementation जैसी भी लगती है। यह stable तो दिखती है, लेकिन जब तक मैं खुद दूसरी implementation न आज़मा लूँ, या यह इतना व्यापक रूप से इस्तेमाल न हो जाए कि algorithm के sharp edges सामने आ जाएँ, तब तक यह चिंता रहेगी कि क्या इसे किसी भरोसेमंद spec या दूसरी implementation में आसानी से ले जाया जा सकेगा
हालाँकि Qualcomm यह दावा कर सकता है कि यह RaptorQ patents के दायरे में आता है, क्योंकि conceptually यह उससे जुड़ा है। उनमें से शुरुआती patents शायद जल्द expire होने वाले हैं या हो चुके हैं, लेकिन मैंने हाल के file wrappers नहीं देखे हैं। Qualcomm ने कुछ हद तक यह वादा किया था कि वह RaptorQ patents को wireless के बाहर लागू नहीं करेगा, लेकिन याद नहीं कि वह केवल compliant implementations पर लागू था या नहीं
Bitcoin protocol के core में इसका उपयोग करने के लिए इसे spec करना ज़रूरी था, इसलिए मैंने देखा था कि उसके लिए क्या चाहिए। मैं और कुछ अन्य Bitcoin developers number theory और error-correcting codes से काफ़ी परिचित हैं, लेकिन वह काम बहुत आकर्षक नहीं लगा। वजह यह है कि Wirehair की बनावट में काफ़ी सारे ad-hoc details हैं, और हमारी प्रवृत्ति के हिसाब से उन्हें सुधारने की कोशिश में हम किसी जाल में फँस सकते थे
Bitcoin समुदाय में fountain codes को व्यापक रूप से इस्तेमाल करने में फिर से रुचि पैदा हो सकती है, इसलिए अगर थोड़ा इंतज़ार करें तो संभव है कि कोई इसकी specification लिख दे
आपके exact use case के अनुसार https://github.com/catid/fecal भी दिलचस्प हो सकता है। अगर expected erasure count बहुत कम है, तो यह Wirehair से तेज़ हो सकता है
पोस्ट में उल्लेख किया गया Leopard fountain code नहीं है, लेकिन उसका block size काफ़ी बड़ा है। specification के लिहाज़ से उसका फ़ायदा यह है कि वह बस काफ़ी तेज़ी से implemented, साधारण Reed-Solomon code है, इसलिए spec में शायद सिर्फ field और generator choice को document करना काफ़ी हो
सही है। यही Ceph के Erasure Code pool के पीछे की core technology है: https://docs.ceph.com/en/latest/rados/operations/erasure-cod...
लेकिन यह बिना कीमत के नहीं आता। बाद में coding parameters k, m बदले नहीं जा सकते, इसलिए या तो आपको पूरा भरोसा होना चाहिए कि ये values लंबे समय तक सही रहेंगी, या फिर शुरुआत से दोबारा शुरू करना पड़ेगा
इसी inflexibility की वजह से high-availability fault-tolerant data storage में replication अब भी प्रमुख विकल्प बना हुआ है
यह बस
--forceका उपयोग करके आपको corrupted filesystem के साथ छोड़ देता हैशायद यह सिर्फ उसी तरह का मज़ाक है जो “अगर आप वहाँ होते तो मज़ेदार लगता, लेकिन मेरे साथ हो तो नहीं”
क्या ऐसा है कि जब failure scenario में N में से केवल M उपलब्ध हों, तो उससे बना output उस स्थिति से अलग encode होता है जब N के सभी हिस्से उपलब्ध हों? अगर हाँ, तो शायद एक bit flag होना चाहिए जो दिखाए कि “N वापस आने पर re-encoding ज़रूरी है”
नहीं तो N के सेट में बाद में कोई भी random loss होने पर ऐसे files बचेंगे जिनकी recovery क्षमता बहुत अच्छी नहीं होगी
हर distributed storage system में किसी न किसी तरह का librarian होना चाहिए, जो stripes की जाँच और सफ़ाई करके उन्हें जोखिम वाली स्थिति से बाहर रखे
इससे Rabin का information dispersal algorithm भी याद आता है। यह इस paper में समझाया गया है:
https://dl.acm.org/doi/10.1145/62044.62050
क्या व्यवहार में यह केवल read-only या बहुत ज़्यादा read-heavy workloads के लिए ही practical है?