Teknologi Erasure Coding untuk Sistem Terdistribusi
(transactional.blog)- Erasure Coding adalah teknik kompromi antara efisiensi penyimpanan dan toleransi kesalahan, yang membagi data menjadi fragmen dan paritas agar tetap tahan terhadap kegagalan dengan ruang penyimpanan lebih sedikit dibanding replikasi penuh
- Model dasarnya adalah k+m=n; k adalah jumlah fragmen data yang diperlukan untuk pemulihan, m adalah jumlah fragmen paritas sekaligus jumlah kegagalan yang dapat ditoleransi, dan n adalah jumlah total fragmen
- Pada object/blob storage, alih-alih replikasi penuh 3 kali, konfigurasi seperti 10+5 dapat digunakan untuk menempatkan fragmen kecil di lebih banyak server dan mengurangi volume penyimpanan
- Sistem quorum memiliki penghematan penyimpanan yang terbatas jika hanya memakai mayoritas sederhana; jika diubah menjadi 3+2, 2+2, 1+2 sesuai jumlah replika yang tersedia seperti HRaft, muncul beban re-encoding dan provisioning kapasitas
- Dalam adopsi nyata, perlu memverifikasi variasi biaya decoding akibat kombinasi fragmen respons dan perbedaan kebutuhan metadata serta alignment pada Jerasure, ISA-L, dan liberasurecode
Kompromi dasar antara efisiensi penyimpanan dan toleransi kegagalan
- Ada dua cara ekstrem untuk menyimpan file di N server
- Jika replika file lengkap ditempatkan di semua server, file tidak akan hilang meski N-1 server menghilang, tetapi biaya penyimpanannya paling besar
- Jika file dibagi menjadi N fragmen berukuran sama dan masing-masing disimpan satu per server, efisiensi penyimpanannya paling baik, tetapi saat membaca diperlukan semua N fragmen
- Erasure Coding mengatur efisiensi penyimpanan dan toleransi kegagalan di antara dua ekstrem tersebut
- Kode dapat disusun sesuai tujuan: “membagi file menjadi N fragmen, tetapi tetap bisa dipulihkan meski M fragmen rusak”
- Teknik ini menyediakan fragmen dengan ukuran minimum yang diperlukan untuk memenuhi tujuan tersebut
- Intuisi paling sederhana adalah contoh mendapatkan seluruh file dengan membaca sembarang 2 dari 3 server
- File dibagi menjadi dua fragmen A dan B
- Fragmen ketiga C dibuat sebagai A ⊕ B
- Jika A dan B dibaca, keduanya langsung digabungkan; jika A dan C atau B dan C dibaca, fragmen yang hilang dipulihkan dengan XOR
- Semua Erasure Code menggeneralisasi pola ini dengan membagi fragmen data dan fragmen paritas
Model k+m=n dan overhead penyimpanan
- Konfigurasi Erasure Code dinyatakan sebagai k + m = n
- k: jumlah fragmen pembagian data; untuk memulihkan nilai, minimal k fragmen harus dibaca
- m: jumlah fragmen paritas yang akan dibuat; juga jumlah kegagalan baca yang tidak harus selesai atau jumlah toleransi kegagalan
- n: jumlah total fragmen yang dihasilkan
- Ukuran satu fragmen hasil adalah 1/k dari file asli
- Erasure Code biasanya disebut sebagai tuple
k+m- Nama variabel tidak selalu konsisten di berbagai literatur
x+yberarti x fragmen data dan y fragmen paritas
- Alasan teknik ini menarik bagi penyedia penyimpanan adalah karena toleransi kegagalan dapat diperoleh dengan overhead penyimpanan yang rendah
- Backblaze B2 memakai 17+3 dan menoleransi 3 kegagalan dengan ruang penyimpanan 1,18 kali
- OVH Cloud memakai kode 8+4 dan menoleransi 4 kegagalan dengan ruang penyimpanan 1,5 kali
- Scaleway memakai kode 6+3 dan menoleransi 3 kegagalan dengan ruang penyimpanan 1,5 kali
- Biaya utamanya adalah pertukaran antara pengurangan ruang penyimpanan dan peningkatan jumlah permintaan baca
- Alih-alih membaca sebesar ukuran file dari satu disk, permintaan dikirim ke k+m disk
- Sistem penyimpanan untuk data yang jarang diakses cocok karena beban IOPS tambahan relatif kecil dan efek penghematan penyimpanannya besar
Cakupan algoritme dan kode MDS
- “Erasure Coding” bukan satu algoritme tertentu, melainkan keluarga algoritme
- Kode Reed-Solomon umumnya dapat digunakan untuk mengimplementasikan Erasure Code dengan konfigurasi k+m arbitrer
- Ada juga padanannya dengan RAID
- RAID-0 adalah Erasure Coding k+0
- RAID-1 adalah Erasure Coding 1+m
- RAID-4 dan RAID-5 adalah Erasure Coding k+1 yang sedikit berbeda
- RAID-6 adalah Erasure Coding k+2
- Cakupan tulisan ini adalah Erasure Code MDS(Minimum Distance Separable)
- Kode MDS menyediakan properti mirip quorum yang dapat menoleransi kehilangan sembarang m fragmen
- Keluarga Erasure Code lain pada sebagian kombinasi bisa memulihkan dengan fragmen lebih sedikit dari m, tetapi pada kombinasi lain mungkin memerlukan fragmen lebih banyak dari m
- Jika pola kegagalan yang diperkirakan diketahui, akan menguntungkan jika kegagalan yang sering terjadi dipulihkan dengan lebih sedikit fragmen, sementara kegagalan pengecualian dipulihkan dengan lebih banyak fragmen
- Local Reconstruction Codes dan SD Codes dari Azure Storage dibahas sebagai contoh arah ini
Penerapan pada object storage dan cache
- Penerapan paling langsung adalah mengurangi biaya penyimpanan dan meningkatkan durability pada sistem yang memiliki kumpulan replika tetap
- Contohnya blob/object storage atau NFS storage
- Layanan metadata memetakan path file ke server yang menyimpan file tersebut
- Alih-alih 3 replika masing-masing menyimpan file lengkap, 15 replika dapat menyimpan fragmen file Erasure Coded 10+5
- Total jumlah data yang disimpan menjadi setengah
- Toleransi kegagalan meningkat lebih dari dua kali lipat
- Pola yang lebih umum adalah “alih-alih menyimpan data di X server, simpan dengan X+m Erasure Code di X+m replika”
- Contoh sistem caching dari Marc Brooker menerapkan pola ini pada cache
- Alih-alih memilih satu dari k server cache dengan consistent hashing, gunakan k+m Erasure Code pada k+m server cache
- Tidak perlu menunggu m respons paling lambat
- Ruang penyimpanan dan tail latency dapat diperbaiki sekaligus
- Penghematan ini disertai biaya berupa peningkatan IOPS/QPS atau CPU
- Perlu asumsi bahwa sumber daya pembatas sistem adalah kapasitas penyimpanan dan masih ada kelonggaran CPU
- Pada sistem yang sudah mendekati batas CPU, ini mungkin bukan ide penghematan biaya
Batasan sistem quorum dan HRaft
- Quorum mayoritas sederhana pada 5 replika, yang membutuhkan minimal 3 replika untuk baca maupun tulis, cocok dengan Erasure Code 3+2 dari sisi baca
- Karena pembacaan dapat diselesaikan dengan hasil dari sembarang 3 replika
- Penulisan dapat selesai jika diterima oleh sembarang 3 replika, sehingga pada Erasure Code tetap hanya kode 1+2 yang dapat digunakan
- 1+2 sama dengan 3 replikasi penuh file
- Dengan penerapan sederhana saja, tidak ada penghematan penyimpanan
- RS-Paxos memandang bahwa saat menerapkan Erasure Code pada Paxos, manfaat hanya muncul jika irisan dua quorum lebih besar dari 1 replika
- Misalnya, jika pada 7 replika baca dan tulis sama-sama membutuhkan minimal 5 replika, toleransi kegagalannya 2 dan kode 3+2 dapat diterapkan
- Secara umum, jika ada N replika dan toleransi kegagalan f yang diinginkan, hasil terbaik yang mungkin dengan Erasure Coding tetap adalah (N-2f)+f
- HRaft menyesuaikan coding dengan jumlah replika yang tersedia bahkan pada quorum mayoritas sederhana
- Jika semua 5 tersedia: 3+2
- Jika 4 tersedia: 2+2
- Jika 3 tersedia: 1+2
- Pendekatan adaptif punya ruang perbaikan, tetapi juga banyak batasan operasional
- Setiap penulisan memperkirakan secara optimistis jumlah replika yang saat ini tersedia
- Jika satu replika secara tak terduga tidak menyetujui penulisan, penulisan harus di-code ulang dan dikirim lagi ke semua replika
- Agar ketersediaan tidak rusak akibat kekurangan ruang disk atau throughput saat beroperasi dengan konfigurasi 1+2 setelah dua kegagalan, konfigurasi replika harus di-provision agar mampu menyimpan seluruh nilai
- Jika kegagalan jarang terjadi dan cepat pulih, encoding adaptif HRaft memberikan peningkatan yang cukup besar
Library dan contoh penggunaan
- Untuk perhitungan Erasure Coding, ada library standar matang bernama Jerasure
- Pada prosesor Intel modern, Intel Intelligent Storage Acceleration Library adalah library beroptimasi SIMD dan secara konsisten berada di peringkat atas benchmark
- Di Python, implementasi Erasure Coding dapat diakses lewat pyeclib
- Contohnya memakai driver
liberasurecode_rs_vand - Setiap fragmen diberi metadata di bagian depan untuk identifikasi posisi
- Ada juga beberapa byte tambahan
- Contohnya memakai driver
- Hasil contoh HRaft menurut jumlah replika yang tersedia adalah sebagai berikut
- 3+2, sumber 10000 byte: 5 fragmen, 3355 byte per fragmen, total aktual 16775 byte, efisiensi 59,61%
- 2+2, sumber 10000 byte: 4 fragmen, 5021 byte per fragmen, total aktual 20084 byte, efisiensi 49,79%
- 1+2, sumber 10000 byte: 3 fragmen, 10021 byte per fragmen, total aktual 30063 byte, efisiensi 33,26%
- Erasure Encoding 1+2 sama dengan 3 replika data penuh, sehingga setara dengan tidak menerapkan Erasure Encoding
Biaya decoding dan perbedaan antarimplementasi
- Performa decoding bergantung pada jumlah fragmen data yang harus dipulihkan
- Decoding kode 3+2 dengan 3 fragmen data secara komputasi hampir sederhana
- Untuk men-decode file yang sama dengan 2 fragmen data dan 1 fragmen paritas, sistem persamaan linear harus diselesaikan dengan Gaussian elimination
- Semakin banyak jumlah fragmen paritas yang diperlukan, semakin besar jumlah komputasinya
- Jika Erasure Code dipakai dalam sistem quorum, biaya CPU dapat berbeda tergantung tepatnya replika mana yang merespons
- liberasurecode mengabstraksikan library implementasi Erasure Coding yang umum, tetapi itu tidak berarti implementasi-implementasi tersebut setara
- Meski dua kode sama-sama 3+2, itu tidak berarti keduanya disusun dengan matematika yang sama
- liberasurecode menambahkan metadata yang diperlukan untuk konfigurasi dan penggunaan decoder, bukan hanya operasi aljabar linear
- Metadata ini tidak dapat dinonaktifkan atau diubah
- Jika memakai Jerasure atau ISA-L secara langsung, hanya data Erasure Coded yang dapat ditangani
- Namun, pada level API, setiap fragmen harus disertai informasi apakah itu fragmen data ke-N atau fragmen paritas, sehingga indeks harus dipertahankan sebagai metadata dengan cara apa pun
- Jerasure dan ISA-L juga berbeda dalam kebutuhan alignment
- Jerasure menerapkan permutasi terhadap output aljabar linear yang diharapkan
- Jerasure tidak dapat membaca subset atau superset dari hasil encoding secara tidak terurut
- ISA-L tidak menerapkan permutasi, sehingga memungkinkan decoding subset atau superset yang tidak terurut
- Implementasi lain juga termasuk opsi
- tahoe-lafs/zfec
- catid/cm256
- catid/longhair
- catid/leopard
- Jika menjadi bottleneck, library yang lebih dioptimalkan untuk use case tertentu dapat dicari, tetapi ISA-L umumnya sudah cukup baik
Pemilihan algoritme dan konstruksi matematis
- Erasure Code dapat diperlakukan seperti fungsi ajaib yang mengubah 1 file menjadi n fragmen lalu memulihkannya kembali; untuk penggunaan praktis ini tidak menjadi masalah
- Konstruksi n fragmen umumnya dilakukan dengan aljabar linear menggunakan Galois Field
- Tidak wajib memahami matematika ini untuk menggunakan Erasure Code secara produktif
- Sebagian besar kode MDS dihitung dengan perkalian matriks
- Penjumlahan diganti dengan XOR
- Perkalian diganti dengan perkalian yang lebih mahal di atas GF(256)
- Untuk kasus khusus dengan jumlah fragmen paritas 1–3, ada algoritme khusus XOR yang bukan Reed-Solomon
- m=1: satu fragmen paritas berupa XOR dari semua fragmen data
- m=2: setara RAID-6; Liberation codes, HDP codes, EVENODD, X-Codes, dan lainnya disebutkan
- m=3: dapat dilakukan dengan STAR coding
- Untuk kasus umum, keluarga Reed-Solomon digunakan
- Konstruksi matriks Vandermonde atau matriks Cauchy digunakan
- Tujuannya adalah agar k×k bagian atas menjadi matriks identitas sehingga setiap fragmen data dipertahankan, dan invers matriks tetap ada setelah m baris dihapus
- Encoding adalah mengalikan matriks ini, dan decoding adalah menghapus baris yang sesuai dengan fragmen yang hilang lalu menyelesaikan sistem persamaan linear
- Gaussian elimination yang digunakan ISA-L adalah metode decoding paling sederhana tetapi paling lambat
- Pada matriks Cauchy, metode ini dapat diperbaiki, dan catid/cm256 menggunakannya
- Metode tercepat saat ini tampaknya diimplementasikan di catid/leopard, yang menggunakan Fast Fourier Transform untuk encoding dan decoding
Tahapan efisiensi implementasi
- Ada beberapa tahapan untuk membuat implementasi Erasure Code yang berjalan pada konfigurasi k+m arbitrer menjadi cepat
- Tahap pertama adalah mengimplementasikan algoritme dalam C dan mengandalkan auto-vectorization compiler
- Paling sederhana dan portabilitasnya tinggi
- Penggunaan
restrictdan penentuan flag kompilasi spesifik arsitektur seperti-march=nativepenting
- Tahap kedua adalah mengabstraksikan detail platform dengan library vectorization atau compiler intrinsic
- google/highway
- xtensor-stack/xsimd
std::experimental::simd- GCC vector extension builtins
- Inti encoding dan decoding adalah perkalian dan penjumlahan Galois Field
- catid/gf256 dan James Plank’s Fast Galois Field Arithmetic Library disebut sebagai library yang dioptimalkan
- Tahap ketiga adalah menulis sendiri fungsi inti encoding/decoding yang divektorkan
- Proyek PARPAR membahas operasi GF(256) cepat dalam fast-gf-multiplication dan xor_depends work
- Dirangkum bahwa ada konsensus bahwa perkalian GF khusus XOR lebih cepat daripada perkalian berbasis tabel
- Lebih jauh lagi, kode dapat dispesialisasikan untuk konfigurasi k+m tertentu
- Mencari matriks coding dan jadwal XOR optimal yang sesuai dengan polinomial GF dan matriks encoding tertentu
- Menerapkan optimasi operasi, memori, dan cache
- Menelusuri jadwal instruksi optimal untuk arsitektur tertentu secara programatis
- Implementasi dan materi terkait yang disajikan adalah yuezato/xorslp_ec, Thesys-lab/tvm-ec, dan "Fast Erasure Coding for Data Storage: A Comprehensive Study of the Acceleration Techniques"
Materi untuk pendalaman lebih lanjut
- Tautan berikut berguna sebagai pengantar aljabar linear Erasure Coding
- Pengantar dasar dari Backblaze
- "A Gentle Introduction to Erasure Codes" dari Fred Akalin
- "Reed-Solomon Error Correcting Codes from the Bottom Up"
- Tutorial on Reed-Solomon Error Correction Coding dari NASA
- Untuk mendalami lebih luas, disarankan mulai dengan meninjau publikasi James S. Plank
1 komentar
Komentar Hacker News
Terkejut karena rateless fountain code tidak disebut. Kalau Anda suka topik seperti ini, Luby Transform Code akan menarik: https://en.wikipedia.org/wiki/Luby_transform_code
Makalah ini juga bagus sebagai ikhtisar yang lebih rinci: https://switzernet.com/people/emin-gabrielyan/060112-capilla...
LT code digunakan sebagai outer code dalam encoding RaptorQ waktu linear yang ditetapkan di RFC6330: https://www.rfc-editor.org/rfc/rfc6330
Kedua, algoritmanya sebenarnya terbagi menjadi dua bagian: bagian kedua, pembuatan blok pemulihan, memang linear, tetapi bagian pertama memakan waktu kubik terhadap jumlah pesan yang digabungkan dalam satu blok. Ini nyaris setara dengan eliminasi Gauss pada matriks
Sebagian encoding dan decoding bisa di-cache, tetapi menurut saya encoding waktu linear RaptorQ pada dasarnya hanyalah slogan pemasaran
Dulu ada yang mengusulkan algoritma erasure code yang lucu, yang mengandalkan multipath networking alih-alih disk berputar
Sepertinya dulu disebut network coding; idenya, pada jaringan dengan banyak jalur, alih-alih menunggu seluruh file dari server utama, kita menerima erasure code dari satu upstream yang mencampur dua bagian file, atau dua file, sehingga file bisa diperoleh lebih cepat
Saya rasa banyak pendekatan seperti ini juga ada di balik S3 atau sistem cloud storage lain, terutama pada tier storage yang jarang diakses. Meski begitu, saya tidak benar-benar tahu sistem internal AWS atau GCP
Sebagai catatan, Freenet setidaknya memakai file yang dikodekan dengan FEC, sehingga ada fleksibilitas dalam potongan mana yang diterima dan mengurangi kemungkinan seluruh file rusak hanya karena satu potongan hilang
Erasure coding sudah ada sejak lama sekali. Ingat file PAR2 di Usenet? https://en.wikipedia.org/wiki/Parchive
Jika tertarik pada erasure coding, ada baiknya juga mempertimbangkan kasus multidimensi yang lebih besar. Bukan hanya encoding di banyak disk, tetapi juga memikirkan domain kegagalan lain seperti rack, ruangan, data center, dan region secara bersamaan
Tujuannya adalah bertahan bukan hanya dari kegagalan komponen umum, tetapi juga kegagalan sistem atau partisi yang lebih besar. Tulisan pengantar yang bagus: https://chameleoncloud.org/blog/2023/12/12/design-considerat...
Jika kabel serat optik lintas samudra hanya 1Tbps, memindahkan seluruh data bisa memakan waktu lebih dari 6 bulan
Saya penasaran apakah ada yang pernah memakai Wirehair di proyek: https://github.com/catid/wirehair
Saya penasaran apakah ini sudah cukup terdefinisi dengan baik untuk dijadikan basis standar bagi proyek arsip file berukuran besar/pemulihan data yang sudah saya pikirkan selama hampir 10 tahun. Meski bukan standar resmi, saya ingin tahu apakah bisa dipakai seperti standar tidak resmi
Dari kode erasure blok besar yang saya temukan sejauh ini, hanya ini yang memiliki performa algoritme ideal atau nyaris ideal sekaligus API yang baik. Jadi, tidak seperti RaptorQ yang detail-detail kecilnya bocor ke sana-sini dan meningkatkan kompleksitas serta kekakuan seluruh stack, untuk kebutuhan saya ini menjadi black box yang bagus
Namun Wirehair bukan spesifikasi, melainkan implementasi dari sebuah ide, dan juga tampak seperti implementasi eksperimental. Kelihatannya stabil, tetapi sampai saya mencoba menulis implementasi kedua sendiri atau sampai ini cukup luas digunakan sehingga sisi-sisi tajam algoritmenya terlihat, saya khawatir apakah ini bisa dengan mudah dipindahkan ke spesifikasi yang dapat dipercaya atau implementasi kedua
Namun Qualcomm bisa saja mengklaim bahwa ini terkena paten RaptorQ, karena secara konseptual terkait. Paten-paten paling awal di antaranya seharusnya segera kedaluwarsa atau sudah kedaluwarsa, tetapi saya belum memeriksa wrapper file yang lebih baru. Qualcomm pernah membuat beberapa janji untuk tidak menerapkan paten RaptorQ di luar nirkabel, tetapi saya tidak ingat apakah itu hanya berlaku untuk implementasi yang sesuai
Jika ingin dipakai di inti protokol Bitcoin, ini perlu dispesifikasikan, jadi saya pernah meninjau apa yang diperlukan. Saya dan beberapa developer Bitcoin cukup akrab dengan teori bilangan dan kode koreksi kesalahan, tetapi pekerjaan itu tidak terlalu menarik bagi kami. Struktur Wirehair punya cukup banyak detail ad hoc, dan dengan kecenderungan kami, kami bisa terjebak saat mencoba memperbaikinya
Mungkin minat untuk memakai fountain code secara luas di sisi Bitcoin akan muncul kembali, jadi kalau menunggu sebentar, ada kemungkinan seseorang akan menulis spesifikasinya
Bergantung pada penggunaan persisnya, https://github.com/catid/fecal juga bisa menarik. Jika jumlah erasure yang diperkirakan sangat rendah, ini bisa lebih cepat daripada Wirehair
Leopard yang disebut dalam tulisan bukan fountain code, tetapi ukuran bloknya cukup besar. Dari sisi spesifikasi, ada keunggulan: karena itu hanya implementasi sangat cepat dari kode Reed-Solomon yang membosankan, mungkin spesifikasinya cukup mendokumentasikan pilihan field dan generator
Betul. Ini adalah teknologi inti di balik pool Erasure Code Ceph: https://docs.ceph.com/en/latest/rados/operations/erasure-cod...
Namun ini bukannya tanpa biaya. Parameter coding, yaitu k, m, tidak bisa diubah belakangan, jadi Anda harus yakin nilai-nilai itu akan tetap cocok dalam jangka panjang, atau harus mulai ulang dari awal
Karena ketidakelastisan seperti ini, replikasi masih menjadi pilihan dominan untuk penyimpanan data toleran gangguan dengan ketersediaan tinggi
Itu hanya menggunakan
--forcedan meninggalkan filesystem yang rusakMungkin ini hanya jenis kelucuan “lucu kalau Anda ada di sana, dan bukan saya yang mengalaminya”
Apakah benar bahwa keluaran yang dibuat dalam kondisi kegagalan saat hanya M dari N yang tersedia dikodekan berbeda dibanding saat semua N tersedia? Jika demikian, sepertinya perlu ada bit flag yang menandakan “perlu re-encoding saat N pulih”
Kalau tidak, akan tersisa file-file yang tidak terlalu tangguh ketika terjadi kehilangan acak dari himpunan N
Setiap sistem penyimpanan terdistribusi memerlukan semacam pustakawan yang memeriksa dan merapikan stripe agar keluar dari keadaan berisiko
Saya juga teringat algoritme penyebaran informasi Rabin. Ini dijelaskan di makalah berikut:
https://dl.acm.org/doi/10.1145/62044.62050
Dalam praktiknya, apakah ini hanya praktis untuk workload yang read-only atau sangat dominan baca?