Dağıtık sistemler için Erasure Coding teknolojisi
(transactional.blog)- Erasure Coding, veriyi parçalara ve parity bloklarına bölerek tam kopyalamaya göre daha az depolama alanıyla arızalara dayanmayı sağlayan, depolama verimliliği ile hata toleransı arasında bir denge kuran tekniktir
- Temel model k+m=n şeklindedir; k kurtarma için gereken veri parçası sayısı, m parity parçası sayısı ve aynı zamanda tolere edilebilen başarısızlık sayısı, n ise toplam parça sayısıdır
- Nesne·blob depolamada üçlü tam kopyalama yerine 10+5 gibi yapılandırmalar kullanılarak daha fazla sunucuya küçük parçalar yerleştirilebilir ve depolama miktarı azaltılabilir
- Quorum sistemlerinde yalnızca basit çoğunluk oylamasıyla depolama tasarrufu sınırlıdır; ancak HRaft gibi yaklaşımlarda kullanılabilir kopya sayısına göre 3+2, 2+2, 1+2 arasında geçiş yapmak yeniden kodlama ve kapasite sağlama yükü doğurur
- Gerçek kullanımda, dönen parça kombinasyonuna göre decode maliyetindeki değişimin ve Jerasure·ISA-L·liberasurecode kütüphanelerinin metadata ile hizalama gereksinimlerindeki farkların doğrulanması gerekir
Depolama verimliliği ve hata toleransı arasındaki temel denge
- Bir dosyayı N sunucuda saklamanın iki uç yöntemi vardır
- Tüm sunucularda dosyanın tam kopyasını tutarsanız N-1 sunucu kaybolsa bile dosya kaybolmaz, ancak depolama maliyeti en yüksektir
- Dosyayı eşit boyutlu N parçaya bölüp her sunucuda bir parça tutarsanız depolama verimliliği en yüksek olur, ancak okuma için tüm N parçaya ihtiyaç duyulur
- Erasure Coding, bu iki uç arasında depolama verimliliği ile hata toleransını ayarlar
- “Dosyayı N parçaya böleyim ama M parça kaybolsa da geri yüklenebilsin” hedefine uygun bir kod kurulabilir
- Bu hedefi karşılamak için gereken en küçük parça boyutunu sağlar
- En basit sezgisel örnek, 3 sunucudan rastgele herhangi 2 tanesini okuyarak tüm dosyayı elde etmektir
- Dosya iki parçaya ayrılır: A ve B
- Üçüncü parça C, A ⊕ B olarak oluşturulur
- A ve B okunursa doğrudan birleştirilir; A ve C ya da B ve C okunursa eksik parça XOR ile geri kazanılır
- Tüm Erasure Code türleri, veri parçaları ile parity parçalarına ayrılarak bu kalıbı geneller
k+m=n modeli ve depolama ek yükü
- Erasure Code yapılandırması k + m = n olarak ifade edilir
- k: verinin bölündüğü parça sayısıdır; bir değeri kurtarmak için en az k parça okunmalıdır
- m: üretilecek parity parçası sayısıdır; aynı zamanda tamamlanmasına gerek olmayan okuma hatası ya da tolere edilen arıza sayısıdır
- n: üretilen toplam parça sayısıdır
- Ortaya çıkan her bir parçanın boyutu, özgün dosyanın 1/k kadardır
- Erasure Code genellikle
k+mikilisiyle anılır- Literatürde değişken adları tutarlı değildir
x+y, x veri parçası ve y parity parçası anlamına gelir
- Depolama sağlayıcıları için çekici olmasının nedeni, düşük depolama ek yüküyle hata toleransı sağlamasıdır
- Backblaze B2, 17+3 kullanarak 1.18 kat depolama alanıyla 3 arızayı tolere eder
- OVH Cloud, 8+4 koduyla 1.5 kat depolama alanında 4 arızayı tolere eder
- Scaleway, 6+3 koduyla 1.5 kat depolama alanında 3 arızayı tolere eder
- Başlıca maliyet, depolama azalması ile okuma isteği sayısındaki artış arasındaki değiş tokuştur
- Tek bir diskten dosya boyutu kadar okuma yapmak yerine k+m diskine istek gönderilir
- Sık erişilmeyen veriler için depolama sistemlerinde ek IOPS yükü görece küçüktür, depolama tasarrufu ise büyüktür; bu yüzden uygundur
Algoritma kapsamı ve MDS kodları
- “Erasure Coding”, tek bir algoritma değil bir algoritma ailesidir
- Reed-Solomon kodları, genel olarak rastgele herhangi bir k+m yapılandırmalı Erasure Code uygulamak için kullanılabilir
- RAID ile de bir karşılığı vardır
- RAID-0, k+0 Erasure Coding’dir
- RAID-1, 1+m Erasure Coding’dir
- RAID-4 ve RAID-5, biraz farklı bir k+1 Erasure Coding’dir
- RAID-6, k+2 Erasure Coding’dir
- Bu yazının kapsamı MDS(Minimum Distance Separable) Erasure Code’dur
- MDS kodları, rastgele herhangi m parça kaybına dayanabilen quorum benzeri bir özellik sunar
- Diğer Erasure Code ailelerinde bazı kombinasyonlarda m’den az parçayla kurtarma mümkün olabilirken, başka kombinasyonlarda m’den fazla parça gerekebilir
- Beklenen arıza desenini biliyorsanız, sık görülen arızaları daha az parçayla kurtarıp istisnai arızalarda daha fazla parça kullanmak avantajlı olabilir
- Azure Storage’ın Local Reconstruction Codes ve SD Codes yaklaşımı bu yönün örnekleri olarak ele alınır
Nesne depolama ve cache’te kullanım
- En doğrudan kullanım alanı, sabit bir kopya kümesine sahip sistemlerde depolama maliyetini düşürmek ve dayanıklılığı artırmaktır
- Örnekler blob·nesne depolama ya da NFS depolamadır
- Bir metadata servisi, dosya yolunu o dosyayı saklayan sunuculara eşler
- Her biri tam dosyayı tutan 3 kopya yerine, 15 kopya 10+5 Erasure Coded dosya parçası saklayabilir
- Toplam depolanan veri miktarı yarıya iner
- Hata toleransı iki katından fazla artar
- Daha genel kalıp, “veriyi X sunucuda saklamak yerine X+m kopyaya X+m Erasure Code ile yerleştirmek”tir
- Marc Brooker’ın caching sistemi örneği, bu kalıbı cache’e uygular
- Tutarlı hashing ile k cache sunucusundan birini seçmek yerine k+m cache sunucusunda k+m Erasure Code kullanılır
- En yavaş m yanıtını beklemek gerekmez
- Depolama alanı ve tail latency birlikte iyileştirilebilir
- Bu tasarruf, IOPS/QPS ya da CPU artışı maliyetiyle gelir
- Sistemin sınırlayıcı kaynağının depolama kapasitesi olduğu ve CPU açısından pay bulunduğu varsayılmalıdır
- Zaten CPU sınırına yakın çalışan sistemlerde bu, maliyet düşürme fikri olmayabilir
Quorum sistemlerinin sınırları ve HRaft
- 5 kopyada okuma ve yazma için en az 3 gerektiren basit çoğunluk quorum’u, okuma açısından 3+2 Erasure Code ile iyi eşleşir
- Çünkü rastgele herhangi 3 kopyanın sonucu ile okuma tamamlanabilir
- Yazma, rastgele herhangi 3 kopya aldığı anda tamamlanabildiği için sabit Erasure Code’da yalnızca 1+2 kodu kullanılabilir
- 1+2, dosyanın 3 tam kopyasıyla aynıdır
- Basit uygulamayla depolama tasarrufu elde edilmez
- RS-Paxos, Paxos’a Erasure Code uygulandığında yalnızca iki quorum’un kesişimi 1 kopyadan büyükse avantaj sağlandığını söyler
- Örneğin 7 kopyada hem okuma hem yazma için en az 5 gerekiyorsa, 2 arıza toleransıyla 3+2 kodu uygulanabilir
- Genel olarak N kopya ve istenen arıza toleransı f verildiğinde, sabit Erasure Coding ile mümkün olan en iyi yapı (N-2f)+f olur
- HRaft, basit çoğunluk quorum’unda bile kodlamayı kullanılabilir kopya sayısına göre ayarlar
- 5’inin tamamı kullanılabiliyorsa 3+2
- 4’ü kullanılabiliyorsa 2+2
- 3’ü kullanılabiliyorsa 1+2
- Bu uyarlanabilir yaklaşımın iyileştirme alanı vardır, ancak işletim kısıtları da büyüktür
- Her yazma, o andaki kullanılabilir kopya sayısını iyimser biçimde tahmin eder
- Bir kopya beklenmedik biçimde yazmayı onaylamazsa, yazının yeniden kodlanıp tüm kopyalara tekrar gönderilmesi gerekir
- İki arızadan sonra 1+2 yapılandırmasıyla çalışırken bile, disk alanı ya da throughput yetersizliği nedeniyle erişilebilirliğin bozulmaması için tüm değeri saklayabilecek bir kopya düzeni sağlanmalıdır
- Arızalar seyrek ve hızlı toparlanıyorsa, HRaft’ın uyarlanabilir kodlaması önemli iyileşme sağlayabilir
Kütüphaneler ve kullanım örnekleri
- Erasure Coding hesaplamaları için olgun bir standart kütüphane olan Jerasure vardır
- Yeni Intel işlemcilerde Intel’in Intelligent Storage Acceleration Library SIMD optimize bir kütüphanedir ve benchmark’larda sürekli üst sıralarda yer alır
- Python’da pyeclib ile Erasure Coding uygulamalarına erişilebilir
- Örneklerde
liberasurecode_rs_vandsürücüsü kullanılır - Her parçanın başına, konum tanımlama için metadata eklenir
- Bazı ek baytlar da bulunur
- Örneklerde
- HRaft’ın kullanılabilir kopya sayısına göre örnek sonuçları şöyledir
- 3+2, özgün veri 10000 bayt: 5 parça, parça başına 3355 bayt, gerçek toplam 16775 bayt, verim %59.61
- 2+2, özgün veri 10000 bayt: 4 parça, parça başına 5021 bayt, gerçek toplam 20084 bayt, verim %49.79
- 1+2, özgün veri 10000 bayt: 3 parça, parça başına 10021 bayt, gerçek toplam 30063 bayt, verim %33.26
- 1+2 Erasure Encoding, verinin 3 tam kopyasıyla aynı olduğundan Erasure Encoding uygulanmamış haliyle eşdeğerdir
Decode maliyeti ve uygulamalar arası farklar
- Decode performansı, geri kazanılması gereken veri parçası sayısına göre değişir
- 3+2 kodunu 3 veri parçasıyla decode etmek hesaplama açısından neredeyse çok basittir
- Aynı dosyayı 2 veri parçası ve 1 parity parçasıyla decode etmek için Gaussian elimination ile doğrusal denklem sistemi çözmek gerekir
- Gerekli parity parçası sayısı arttıkça hesaplama miktarı artar
- Quorum sistemlerinde Erasure Code kullanıldığında, tam olarak hangi kopyaların yanıt verdiğine bağlı olarak CPU maliyeti değişebilir
- liberasurecode, yaygın Erasure Coding uygulama kütüphanelerini soyutlar; ancak bu, uygulamaların birbirine eşdeğer olduğu anlamına gelmez
- İki kod da 3+2 olsa bile aynı matematiksel yapıyla kurulduğu anlamına gelmez
- liberasurecode, doğrusal cebir işlemlerinin yanı sıra decoder kurulumu ve kullanımı için gerekli metadata’yı da ekler
- Bu metadata devre dışı bırakılamaz ya da değiştirilemez
- Jerasure ya da ISA-L doğrudan kullanılırsa yalnızca Erasure Coded veriyle çalışılabilir
- Ancak API düzeyinde her parçanın N’inci veri parçası mı yoksa parity parçası mı olduğunun da verilmesi gerekir; bu nedenle indeks bir şekilde metadata olarak tutulmalıdır
- Jerasure ile ISA-L, hizalama gereksinimlerinde de farklılık gösterir
- Jerasure, beklenen doğrusal cebir çıktısına bir permütasyon uygular
- Jerasure, encode edilen verinin bir alt kümesini ya da üst kümesini sırasız biçimde okuyamaz
- ISA-L permütasyon uygulamadığı için sırasız alt kümelerin ya da üst kümelerin decode edilmesi mümkündür
- Diğer uygulamalar da seçenekler arasındadır
- tahoe-lafs/zfec
- catid/cm256
- catid/longhair
- catid/leopard
- Darboğaz oluşursa belirli kullanım senaryosuna daha iyi optimize edilmiş bir kütüphane bulunabilir, ancak ISA-L genel olarak yeterince iyidir
Algoritma seçimi ve matematiksel yapı
- Erasure Code, tek bir dosyayı n parçaya dönüştürüp sonra geri birleştiren bir sihirli fonksiyon gibi ele alınabilir; pratik kullanımda bu yeterlidir
- n parça yapısı genellikle Galois Field kullanan doğrusal cebirle oluşturulur
- Erasure Code’u üretimde kullanmak için bu matematiği mutlaka anlamak gerekmez
- Çoğu MDS kodu matris çarpımıyla hesaplanır
- Toplama, XOR ile değiştirilir
- Çarpma, GF(256) üzerindeki daha pahalı çarpma ile değiştirilir
- 1~3 parity parçası için özel durumlarda Reed-Solomon dışı yalnızca XOR tabanlı algoritmalar vardır
- m=1: tüm veri parçalarının XOR’u olan tek parity parçası
- m=2: RAID-6’ya karşılık gelir; Liberation codes, HDP codes, EVENODD ve X-Codes anılır
- m=3: STAR coding ile mümkündür
- Genel durumda Reed-Solomon ailesi kullanılır
- Vandermonde matrisi ya da Cauchy matrisi yapıları kullanılır
- Amaç, üstteki k×k bölümün birim matris olması, böylece her veri parçasının korunması ve m satır silinse bile ters matrisin var olmasıdır
- Encode işlemi bu matrisi çarpmaktır; decode ise silinen parçalara karşılık gelen satırları kaldırdıktan sonra doğrusal denklem sistemini çözmektir
- ISA-L’nin kullandığı Gaussian elimination en basit ama en yavaş decode yöntemidir
- Cauchy matrislerinde iyileştirme mümkündür ve catid/cm256 bunu kullanır
- Şu anda en hızlı yöntem, görünüşe göre catid/leopard içinde uygulanmıştır; encode ve decode için Fast Fourier Transform kullanır
Uygulama verimliliği adımları
- Rastgele herhangi bir k+m yapılandırmasında çalışan bir Erasure Code uygulamasını hızlandırmanın birkaç aşaması vardır
- İlk aşama, algoritmayı C ile uygulayıp derleyicinin otomatik vektörleştirmesine güvenmektir
- En basit ve en taşınabilir yöntemdir
restrictkullanımı ve-march=nativegibi mimariye özel derleme bayrakları önemlidir
- İkinci aşama, vektörleştirme kütüphaneleri ya da derleyici intrinsic’leri ile platform ayrıntılarını soyutlamaktır
- google/highway
- xtensor-stack/xsimd
std::experimental::simd- GCC vektör uzantısı builtins
- Encode ve decode işlemlerinin çekirdeği Galois Field çarpması ve toplamasıdır
- Optimize kütüphaneler olarak catid/gf256 ve James Plank’s Fast Galois Field Arithmetic Library anılır
- Üçüncü aşama, çekirdek encode·decode fonksiyonlarını doğrudan vektörleştirerek yazmaktır
- PARPAR projesindeki fast-gf-multiplication ve xor_depends work, hızlı GF(256) işlemlerini ele alır
- Yalnızca XOR tabanlı GF çarpmasının tablo tabanlı çarpmadan daha hızlı olduğuna dair genel bir uzlaşı olduğu özetlenir
- Daha da ileri gidilerek kod, belirli bir k+m yapılandırmasına özel hale getirilebilir
- Belirli bir GF polinomu ve encode matrisi için en iyi kodlama matrisi ile XOR planı aranır
- İşlem, bellek ve cache optimizasyonları uygulanır
- Belirli mimarilere uygun en iyi komut planı programatik olarak taranır
- İlgili uygulamalar ve kaynaklar olarak yuezato/xorslp_ec, Thesys-lab/tvm-ec, "Fast Erasure Coding for Data Storage: A Comprehensive Study of the Acceleration Techniques" verilir
Daha derin inceleme için kaynaklar
- Erasure Coding’in doğrusal cebirine giriş için şu bağlantılar faydalıdır
- Backblaze’in temel tanıtımı
- Fred Akalin’in "A Gentle Introduction to Erasure Codes"
- "Reed-Solomon Error Correcting Codes from the Bottom Up"
- NASA’nın Tutorial on Reed-Solomon Error Correction Coding
- Konuya daha geniş dalmak için James S. Plank’s publications üzerinden başlamak önerilir
1 yorum
Hacker News yorumları
Oransız fountain kodlarından bahsedilmemesine şaşırdım. Bu tür konuları seviyorsanız Luby Transform Code ilginizi çekebilir: https://en.wikipedia.org/wiki/Luby_transform_code
Bu makale de daha ayrıntılı bir genel bakış için iyi: https://switzernet.com/people/emin-gabrielyan/060112-capilla...
LT kodları, RFC6330'da belirtilen doğrusal zamanlı RaptorQ kodlamasında dış kod olarak kullanılıyor: https://www.rfc-editor.org/rfc/rfc6330
İkinci olarak algoritma aslında iki bölüme ayrılıyor; ikincisi olan kurtarma blokları üretimi doğrusal, ama ilki bir bloğa bağlanan mesaj sayısına göre kübik zaman alıyor. Neredeyse matris Gauss eliminasyonuna denk geliyor
Kodlama ve kod çözmenin bazı kısımları önbelleğe alınabilir, ancak RaptorQ'nun doğrusal zamanlı kodlaması pratikte bir pazarlama ifadesi gibi görünüyor
Bir zamanlar biri, dönen disklere değil çok yollu ağ oluşturmaya dayanan sevimli bir erasure code algoritması önermişti
Sanırım buna network coding deniyordu; birden fazla yolu olan ağlarda, ana sunucudan dosyanın tamamını beklemek yerine bir upstream'den dosyanın iki parçasını ya da iki dosyanın karışımı olan bir erasure code alıp dosyayı daha hızlı elde etme fikriydi
S3 veya diğer bulut depolama sistemlerinin arkasında da buna benzer şeylerin çokça olduğunu tahmin ediyorum; özellikle seyrek erişilen depolama katmanlarında böyle olma ihtimali yüksek görünüyor. Ancak AWS veya GCP'nin iç sistemlerini gerçekten bildiğimden değil
Bu arada Freenet en azından FEC ile kodlanmış dosyalar kullanıyor; böylece hangi parçaların alınacağı konusunda esneklik sağlıyor ve tek bir parçanın kaybolmasıyla tüm dosyanın bozulması riskini azaltıyor
Erasure coding çok uzun zamandır var. Usenet'teki PAR2 dosyalarını hatırlıyor musunuz? https://en.wikipedia.org/wiki/Parchive
Erasure coding ile ilgileniyorsanız daha büyük çok boyutlu örnekleri de değerlendirmeye değer. Yalnızca birden fazla disk üzerinde kodlama yapmak değil; rack, oda, veri merkezi, region gibi diğer arıza etki alanlarını da birlikte düşünmek anlamına geliyor
Amaç, ortak bileşen arızalarının yanı sıra daha büyük sistem arızalarına veya partition durumlarına da dayanabilmek. İyi bir başlangıç yazısı: https://chameleoncloud.org/blog/2023/12/12/design-considerat...
Okyanus aşırı fiber optik kablo yalnızca 1 Tbps ise tüm veriyi taşımak 6 aydan fazla sürebilir
Projede Wirehair kullanmış biri var mı merak ediyorum: https://github.com/catid/wirehair
Yaklaşık 10 yıldır tasarladığım büyük dosya arşivleme/veri kurtarma projesinde standart temel olarak alınabilecek kadar iyi tanımlanmış olup olmadığını merak ediyorum. Resmî bir standart olmasa bile gayriresmî bir standart gibi kullanılıp kullanılamayacağını bilmek istiyorum.
Şimdiye kadar bulduğum büyük blok silme kodları arasında hem ideal ya da ideale yakın algoritma performansına hem de API’ye sahip olan tek şey bu. Bu yüzden, RaptorQ gibi küçük ayrıntıların her yerden sızıp yığının geri kalanının karmaşıklığını ve katılığını artırmasının aksine, benim kullanımım için iyi bir kara kutu oluyor.
Ancak Wirehair bir spesifikasyon değil, bir fikrin uygulaması; deneysel bir uygulama gibi de görünüyor. Kararlı görünüyor ama ikinci bir uygulamayı kendim yazıp denemeden ya da algoritmanın keskin köşeleri ortaya çıkacak kadar yaygın kullanılmadan, güvenilir bir spesifikasyona veya ikinci bir uygulamaya kolayca taşınıp taşınamayacağı konusunda endişeliyim.
Ancak Qualcomm, bunun RaptorQ patentlerine takıldığını iddia edebilir; çünkü kavramsal olarak ilişkili. Bunların en eski patentleri yakında sona erecek ya da zaten ermiştir, ama daha yeni dosya sarmalayıcılarını kontrol etmedim. Qualcomm, RaptorQ patentlerini kablosuz alanı dışında uygulamayacağına dair bazı taahhütlerde bulundu, ancak bunun yalnızca uyumlu uygulamalar için geçerli olup olmadığını hatırlamıyorum.
Bitcoin protokolünün kendisinde kullanmak için bunun spesifikasyonlaştırılması gerekiyordu; bu yüzden ne gerektiğine bir ara bakmıştım. Ben ve birkaç Bitcoin geliştiricisi sayı teorisine ve hata düzeltme kodlarına oldukça aşinayız, ama bu iş bize pek çekici gelmedi. Wirehair yapısında epey geçici/pratik çözüm niteliğinde ayrıntı var ve mizacımız gereği onu iyileştirmeye çalışırken tuzağa düşebiliriz.
Bitcoin tarafında fountain code’ları yaygın kullanma ilgisi yeniden doğabilir; biraz beklerseniz birinin spesifikasyon yazması mümkün.
Tam kullanım amacına bağlı olarak https://github.com/catid/fecal de ilginç olabilir. Beklenen silinme sayısı çok düşükse Wirehair’dan daha hızlı olabilir.
Yazıda bahsedilen Leopard bir fountain code değil, ama blok boyutu oldukça büyük. Spesifikasyonlaştırma açısından bir avantajı var; çünkü yalnızca çok hızlı uygulanmış sıkıcı bir Reed-Solomon kodu olduğundan, spesifikasyonda sadece alan ve üreteç seçimini belgelemek yeterli olabilir.
Doğru. Ceph’in Erasure Code havuzlarının arkasındaki temel teknoloji bu: https://docs.ceph.com/en/latest/rados/operations/erasure-cod...
Ancak bedelsiz değil. Daha sonra kodlama parametreleri olan k, m değiştirilemiyor; bu yüzden bu değerlerin uzun süre doğru kalacağından emin olmanız ya da en baştan başlamanız gerekiyor.
Bu esneklik eksikliği nedeniyle, yüksek erişilebilirlik ve arıza toleranslı veri depolamada replikasyon hâlâ baskın seçenek.
Sadece
--forcekullanıp bozuk bir dosya sistemi bırakmış oluyorsunuz.Muhtemelen yalnızca “orada olsaydın komik olurdu, ama ben olmasaydım” türünden bir eğlence.
N taneden yalnızca M tanesinin mümkün olduğu bir arıza durumunda üretilen çıktı, N tanesinin de mümkün olduğu durumdakinden farklı mı kodlanıyor? Öyleyse “N geri gelince yeniden kodlama gerekli”yi gösteren bir bit bayrağı olmalı gibi.
Aksi hâlde N kümesinde rastgele bir kayıp olduğunda dayanıklılığı pek iyi olmayan dosyalar kalır.
Tüm dağıtık depolama sistemlerinde, stripe’ları denetleyip toparlayarak tehlikeli durumdan çıkaran bir tür kütüphaneciye ihtiyaç var.
Rabin’in bilgi dağıtma algoritması da akla geliyor. Şu makalede açıklanmış:
https://dl.acm.org/doi/10.1145/62044.62050
Pratikte yalnızca salt okunur ya da okumanın çok yoğun olduğu iş yüklerinde mi kullanılabilir?