Tag: xor

RAID6 的 Erasure code 實作

Daily Hacker News 上看到的紋章，「Erasure Coding for Distributed Systems」這篇討論了 Erasure code。

以前在學校裡面學 coding theory 的時候有學到一些經典的演算法，尤其是一定會教到 Reed-Solomon error correction 這個演算法，不過實務上 Reed-Solomon 因為用到 finite field 運算 (又稱 Galois field，所以簡寫常用 GF)，所以效率並不算好，在 RAID 系統上面除非 controller 的 CPU 或是晶片對 GF 運算加速，不然大多都會用替代算法。

For the special cases of 1-3 parity chunks (m \in {1,2,3}), there are algorithms not derived from Reed-Solomon and which use only XORs:

允許掛一顆的演算法就是 RAID 5，這邊用 XOR 就很容易導出來，並且分析證明。

開始有難度的是允許掛兩顆的演算法，也就是一般熟知的 RAID 6，在這篇文章裡面提到了好幾個演算法，不過有些有專利問題：

m=2 is also known as RAID-6, for which I would recommend Liberation codes[8][9] as nearly optimal with an implementation available as part of Jerasure, and HDP codes[10] and EVENODD[11] as notable but patented. If k+m+2 is prime, then X-Codes[12] are also optimal.

允許掛三顆的則是提到 STAR coding：

m=3 can be done via STAR coding

算是留個記錄好了，這些演算法又讓我想到先前剛進 Migo 的時候還學到 Raptor code，但使用場景不對反而遇到問題，又是另外一個故事了...

回到開頭的 Reed-Solomon，會印象很深還是因為當初在數學系的集合論學了 finite field 好幾年後，在資工系第一次看到居然可以用 finite field 解決這個問題...

利用 XOR 處理 time series data 壓縮資料

在「The simple beauty of XOR floating point compression (clemenswinter.com)」這邊看到的內容，原文在「The Simple Beauty of XOR Floating Point Compression」這邊。這也是上一篇文章「Golomb coding」的延續。

文章作者在處理 time series data 時預先用 XOR 處理過 (對上一筆資料做)，因為 time series data 的特性，通常 XOR 出來的結果會有很多都是 0 (表示相同的 bit)，然後再用自己設計的演算法讓 raw data 變小。

以作者拿的第一個範例可以看到變小很多 (開原圖可以看比較清楚)，不過這邊 low bit 都是 0 有點作弊：

後面有 unix timestamp 的部分，這個部分的資料就比較接近實際情況，也可以看出來效果不錯：

這邊似乎也可以選擇套 Golomb coding 或是 Rice coding (i.e. M 是 2 的冪次的特殊情況，2^n，這時候 Truncated binary encoding 剛好就是 Binary encoding)。

算是個有趣的處理法... 不過我猜大多數人為了方便處理，還是只會用 framework 提供的壓縮演算法，在底層透明地處理掉，像是 LZ4、gzip 或是 zstd。

比 Bloom filter 與 Cuckoo filter 再更進一步的 Xor filter

Bloom filter 算是教科書上的經典演算法之一，在實際應用上有更好的選擇，像是先前提到的 Cuckoo filter：「Cuckoo Filter：比 Bloom Filter 多了 Delete」。

現在又有人提出新的資料結構，號稱又比 Bloom filter 與 Cuckoo filter 好：「Xor Filters: Faster and Smaller Than Bloom Filters」。

不過並不是完全超越，其中馬上可以看到的差異就是不支援 delete：

Deletions are generally unsafe with these filters even in principle because they track hash values and cannot deal with collisions without access to the object data: if you have two objects mapping to the same hash value, and you have a filter on hash values, it is going to be difficult to delete one without the other.

論文的預印本可以在 arXiv 上下載：「Xor Filters: Faster and Smaller Than Bloom and Cuckoo Filters」。