theory

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 解決這個問題...

在 Hacker News 上看到選擇公理

沒想到會在 Hacker News 的首頁上看到這麼硬核的主題，選擇公理 (Axiom of choice，通常縮寫成 AC)：「What is the Axiom of Choice?」，對應的討論在「What is the Axiom of Choice? (jaydaigle.net)」。

出自「xkcd: Set Theory」

應該是大一教集合論的時候學到的，算是一個非常重要的公設，雖然的確有些數學系統是可以假定 AC 不成立，但用起來會不太好用，主要是因為「對於集合 $S$ ，取出任意一個元素」這類用法太常出現，在沒有 AC 的情況下這件事情就不一定能操作了...

我們目前常用的數學一般是建立在 Zermelo-Fraenkel Set Theory (ZF) 這個公理系統加上 AC，簡寫變成 ZFC。而 AC 在集合論常常會被拿出來說明，主要還是因為在歷史上花了不少力氣才證明 ZF 與 AC 的相對協調性 (ZF 與 AC 不衝突)，以及 ZF 與 AC 獨立性 (ZF 無法推導出 AC)。

有了 AC 後就會再解釋連續統假設 (Continuum hypothesis，簡稱 CH)，也就是 $\mathbb{N}$ 與 $2^{\mathbb{N}}$ 之間存不存在一個集合 $S$ 使得 $|\mathbb{N}| < |S| < |2^{\mathbb{N}}|$ 。

然後再打臉一次，說明 ZFC 與 CH 的協調性 (ZFC 與 CH 不衝突)，與獨立性 (ZFC 無法推導出 CH)。

當時學的時候的確是很頭痛，不過現在回頭看倒是覺得很有趣：在數學上你可以證明「某個敘述無法被證明」，這點應該是以前沒想過的...

遊戲捲頁的理論與實作

文章的標題「Scroll Back: The Theory and Practice of Cameras in Side-Scrollers」，裡面圖又大又多，20Mbps 的光世代全速下載要跑滿一分鐘才能抓完。

順便測一下 Imgur 的 mp4，以及 HTML5 的 video tag。

裡面考了不少古啊，把捲頁的方式分成許多類別...