作者介紹：錢坤，騰訊背景開發工程師，從事領域為流媒體CDN相關，參與騰訊TVideo平台開發維護。
原文是《Algorithmic Nuggets in Content Delivery》。這篇文章是akamai15年的文章，裡面介紹了一些akamai在内容分發網絡中的算法研究，下面對論文中的這些算法進行簡單的總結。水準有限有限，有了解錯誤的還望指正。
ps：并不是所有的算法都已經投入到了實用階段。
Bloom filters的研究主要用在akamai的CDN中的兩個場景：1）索引管理優化；2）内容過濾。
Bloom filters是hash算法的一個變種，有非常優秀的空間效率（使用位數組）和時間效率（插入的時間複雜度穩定為常數），但是會有一定的錯誤率。直覺的說，bloom算法類似一個hash set，用來判斷某個元素（key）是否在某個集合中。和一般的hash set不同的是，這個算法無需存儲key的值，對于每個key，隻需要k個比特位，每個存儲一個标志，用來判斷key是否在集合中。其基本算法如下：
1）首先需要k個hash函數，每個函數可以把key散列成為1個整數
2） 初始化時，需要一個長度為n比特的數組，每個比特位初始化為0
3） 某個key加入集合時，用k個hash函數計算出k個散列值，并把數組中對應的比特位置為1。
4） 判斷某個key是否在集合時，用k個hash函數計算出k個散列值，并查詢數組中對應的比特位，如果所有的比特位都是1，認為在集合中。
通過一系列balabala的數學證明，可以得出最優hash函數個數k、位數組的位數m、存儲的最元素數n關系如下：
再通過一系列balabala的數學證明，可以得出正向錯誤率、位數組的位數m、存儲的最元素數n關系如下：
根據這兩個公式，可以進行參數調整以達到預期目标。Bloom filters的主要場景如下：
1）索引管理優化：有些cache系統的索引查詢可能由于通路慢裝置導緻查詢操作較慢，可以在索引查詢之前用使用Bloom filters搭建一層索引cache提升索引查詢速度，如果Bloom filters中無法查到該檔案，則認為該檔案不存在，如果Bloom filters中可以查到該檔案，則請求索引系統。在這種場景中由于存在元素删除操作，Bloom filters不能使用位數組，每一位需要用一個數字變量來代替，當多個檔案共用一位時使用遞增。
2）内容過濾：akamai統計了一個server cluster兩天中web檔案通路次數，如下圖，可以發現，在總共4億左右的檔案中，有74%的檔案僅被通路過一次，90%檔案通路次數少于4次。
僅有單次通路的檔案是沒有必要落盤的，對于這種檔案落盤會占用磁盤io和存儲，并且可能會将更熱的檔案擠掉，進而降低cache命中率導緻回源帶寬增高。
以此為基礎，akamai實作了“Cache-on-second-hit rule.”算法，即檔案被第二次通路才落盤，而記錄是否有過第一次通路所使用的算法就是Bloom filters。
由于cdn上被通路的檔案數趨近于無窮，是以可以使用兩個Bloom filters交替來記錄檔案第一次被通路，當第一個Bloom filters已經到了能記錄的上限，就使用第二個Bloom filters，如果第二個也到了上限，則清空第一個Bloom filters重新使用第一個，每次查詢檔案是否曾經被通路需要查詢兩個Bloom filters。
Akamai實作了這個元件之後在測試環境進行了測試，從下面的測試結果來看，測試環境緩存命中率從74%上升到了83%，磁盤寫資料量下降了44%，磁盤操作時延下降了24%。
穩定配置設定問題的研究主要被用于全局負載均衡。
在cdn中的網絡中可以抽象出兩個概念。
1）map unit，map unit包含兩個元素，第一個元素是使用者ip的集合，第二個元素是map unit的類型（比如video、web等）
2）server cluster，akamai的伺服器叢集最小機關是cluster，一個cluster中包含若幹伺服器。通過對map unit和server cluster進行穩定配置設定，可以實作全局負載均衡。
Akamai對Gale-Shapley算法進行研究拓展以用于解決全局負載均衡問題。标準的Gale-Shapley算法是被提出用來解決“穩定婚姻問題”的：為n個男性和n個女性互相找到最合适的配偶。算法的基本思路為，先對所有男士進行落選标記，稱其為自由男。且每個男士和每個女士均有一份排序，在排序中标記心儀的異性排名。當存在自由男時，進行以下操作：
（1）每一位自由男在所有尚未拒絕她的女士中選擇一位被他排名最優先的女士；
（2）每一位女士将正在追求她的自由男與其目前男友進行比較，選擇其中排名優先的男士作為其男友，即若自由男優于目前男友，則抛棄前男友；否則保留其男友，拒絕自由男。
（3）若某男士被其女友抛棄，重新變成自由男。
把這個算法基于以下的點進行拓展用于對map unit和server cluster進行比對，也就是全局負載均衡。
（1）map unit和server cluster數目并不相等。在正常的cdn場景中，map unit的數目是要多于server cluster的數目。
（2）排序清單可以不完整。沒有必要建立一個map unit到所有的server cluster的性能分數排序，隻需要選擇出該使用者組可能被排程到的伺服器叢集并進行打分排序即可。
（3）每個server cluster擁有不确定的任意的容量。估算server cluster的容量，并讓它為多個使用者組進行服務。
有了拓展的Gale-Shapley算法作為架構，再對機器的資源進行細化，一個server cluster中一台機器的資源可以具體分為兩種：網絡資源和非網絡資源（如記憶體、cpu能力等）。網絡資源消耗用BPS來表示，非網絡資源消耗用FPS來表示。那麼可以用如下一個分層的資源樹來對一個機器的資源進行表示：
Node A代表機器的可用網絡資源為50BPS，node B代表機器可用的非網絡資源為30FPS，葉子節點代表不同的請求類型可以使用的FPS上限。
如果這時收到20機關video請求，每機關請求占用0.25FPS和1BPS，那麼資源樹剩餘資源如上圖中藍字所示，node A剩餘30BPS，node B剩餘25 FPS，node C剩餘25 FPS。
假設接下來收到26機關的web請求，每個請求消耗1FPS和0.2BPS，總共需要消耗26FPS和6.2BPS，這時發現目前機器的資源不足以承受全部的web請求，這時會根據Scoring（akamai用來評估用戶端和伺服器的服務性能的元件）的輸出判斷該cluster和哪種map unit之間有更好的性能，如果結果是更适合于服務新來的web請求，則按照Gale-Shapley算法會驅逐4機關的舊video請求，并接納新來的web請求。反複進行這種驅逐操作可以讓全局實作最優配置設定。
感覺這個算法在具體的實作細節上還存在着很多挑戰。
一緻性hash的研究被用來實作akamai的cdn局部負載均衡。感覺一緻性hash應該和akamai有着千絲萬縷的聯系，比如兩者都是來源于MIT，一緻性hash的提出人曾經在akamai工作等等。
當使用者被配置設定到一個server cluster之後，需要盡可能通過一緻性hash将同樣的檔案請求盡可能的hash到某台已經在cache中緩存了該檔案的機器上。是以可以通過一緻性hash提升cache命中率，來達到提升性能和增加資源有效使用率的目的。
關于最基本的一緻性hash算法網上有很多講解，一緻性hash解決了當分布式系統中某台cache down掉了或者新加入一台cache可能會導緻所有cache内容要重新洗牌的問題。并引入虛拟節點來優化算法結果。這些内容網上有很多，就不在重複了。下面說一些論文提到的akamai對于一緻性hash的特性化改造：
1）對于熱點檔案，為了防止請求壓在伺服器組内同一台機器上，需要将一個熱點檔案映射到k台伺服器上進行分流，比較友善的方式為将檔案映射在原本的hash出來的機器上以及之後的（k-1）台機器上。不同的熱點檔案集合在做一緻性hash的時候，需要變換hash桶的排列，以防止由于hash值接近導緻不同檔案所映射的k台機器大部分重合，進而導緻機器高負載的問題。
2）使用者所使用業務也是做一緻性hash需要考慮的輸入之一。對于一個在akamai上注冊的業務，會得到一個或多個統一配置設定的序列号，akamai可以按照序列号對對象存儲，并将對于同樣序列号的不同檔案請求hash到cluster同一個機器（或集合），以盡可能滿足某些用戶端複用連接配接下載下傳多個對象的需求（比如盡可能的把同一個web界面上的小對象存儲到一台機器上）。
即使兩個機器上的運作程式完全相同，由于運作時的分别獨立收集輸入資料可能導緻輸出結果不相同的情況，這種情況需要leader election來在伺服器組裡選擇一個leader來向其他的伺服器分發運算結果，以統一輸出。Leader的選擇過程中會遇到資料一緻性的問題，這種一緻性的問題可以通過paxos或者raft算法來解決。我找到以下的兩個位址，感覺對兩個算法講的比較容易了解：
Paxos：paxos和分布式系統
Raft：Understandable Distributed Consensus
leader election有兩種：
1）At-Least-One Leader Election：至少要選擇一個leader。
2）At-Most-One Leader Election：最多隻有一個leader被選擇出來。
比如當網絡出現問題導緻一個叢集出現兩個子網，如果使用At-Most-One Leader Election類的算法不會允許選擇出兩個leader，而是選擇甯可放棄leader選舉的過程，使用比較舊的決策資料。比如akamai使用者組劃分的過程，如果網絡中出現兩份使用者組劃分的結果，會引發全局負載均衡運算出現問題，是以在這種情況下不能選舉出兩個leader，甯可使用舊一點的使用者組劃分結果。