Backblaze nyílt forráskódúvá tette az általuk használt saját RAID tömbjeiket védő Reed-Solomon implementáció Java forráskódját. A Reed-Solomon algoritmus egy hibajavító eljárás, amelyet Irvin S. Reed és Gustave Solomon bácsik dolgoztak ki 1960-ban. A módszert a Backblaze a RAID adattömbjei védelmére használja, de ugyanez az algoritmus “óvja” az optikai lemezeinken tárolt adatokat csakúgy, mint az (A|S)DSL átviteli technológiákban mozgatott adatcsomagokat, vagy épp a QR kódokat, sőt, a Voyager 2 űrszonda is egyfajta Reed-Solomon származékot használt! A világban rengeteg adaton alkalmaznak hibafelismerő módszereket és valamivel kevesebbszer hibajavító algoritmusokat. Hibafelismerés szinte mindenben van: a személyi számodtól kezdve a számlaszámodon át a TAJ azonosítódig minden hivatalos adat tartalmaz ilyet. Míg a hibát csak felismerni képes algoritmusok arra jók, hogy az adathibát detektáljuk, addig a hibajavító algoritmusok az adathibát akár korrigálni is képesek. Hibafelismerő algoritmus a mezei ismétlő módszer, a paritásteszte, a leggyakrabban használt CRC és a különböző hash algoritmusok is, de ezeket hagyjuk most, mert minket a Reed-Solomon cucc hozott lázba! A Reed-Solomon algoritmus úgynevezett “előremutató hibajavító” (=FEC, Forward Error Correction) algoritmus. Az “előremutató” jelzőt azzal érdemelte ki, hogy a hibajavításhoz nem kell a hibásan érkezett adatcsomagot újraküldeni. Az egész posztot az indukálta, hogy végigolvastam a fent már linkelt Backblaze bejegyzést, amiben Brian Beach baromi közérthetően el is magyarázza, hogy néz ki a hibajavító implementációjuk belül. Arra buzdítalak, hogy ezt te is tedd meg – ám ahhoz, hogy értsd is amit Brian magyaráz, nem baj ha fejben van, amit középsuliban a mátrixokkal kapcsolatban próbáltak meg beletömni. Mivel mint említettem, engem anno nem hozott kifejezetten lázba a lineáris algebra, Sipi minden igyekezetének ellenére sem (ellentétben pl. a jód-aziddal), így nekem is kutakodnom kellett, hogy megértsem a magyarázatot. Így találtam rá Horváth Dániel remek mátrixos előadásaira. Ebből nekünk mindenekelőtt a mátrixok szorzására lesz szükségünk: Majd kelleni fog a mátrix inverzének kiszámítása is, ahhoz viszont előbb fel kell fogni a determinánst (ahhoz meg a kifejtési tételt, de ezek egy videóban lesznek): Végül a mátrix inverzének számítása: Végignéztem a videókat és a determináns számításnál azért csak beugrott, hogy az a jó az endusernek, ha a legtöbb nullát tartalmazó sorral|oszloppal kezdi a kifejtést, szóval Sipi, csak megmaradt valami!-) Ha neked is megvolt a fenti 3 videó (vagy kened-vágod a mátrixműveleteket amúgy is), akkor most nyomás a Backblaze posztot olvasni! ]]>