【幹貨】整理分布式技術架構常用的算法及政策

将一些零散的知識點進行整理， 以便加深了解，友善查閱，也希望能幫到大家。

一、負載均衡算法

1. 随機

1. 完全随機

通過系統随機函數，根據後端伺服器清單的大小值來随機選擇其中一台進行通路。由機率統計理論可以得知，随着調用量的增大，其實際效果越來越接近于平均配置設定流量到每一台後端伺服器，也就是輪詢的效果。

1. 權重随機

   雖然還是采用的随機算法，但是為每台伺服器根據不同的配置和負載情況來配置不同的權重，權重大的伺服器獲得的機率大一些，權重小的伺服器獲得的機率小一些。

2. 輪詢

1. 完全輪詢

   将請求按順序輪流地配置設定到伺服器上，它均衡地對待後端的每一台伺服器，而不關心伺服器實際的連接配接數和目前的系統負載情況。

2. 權重輪詢

   根據伺服器的不同處理能力，給每個伺服器配置設定不同的權重值，使其能夠将請求順序的按照權重配置設定到後端伺服器上，權重越大，對應的伺服器每輪所獲得的請求數量越多。

3. 平滑權重輪詢

   每個伺服器都有兩個權重變量：

   　　a：weight，配置檔案中指定的該伺服器的權重，這個值是固定不變的；

   　　b：current_weight，伺服器目前的權重（非固定權重）。一開始為0，之後會動态調整。

   　　每次當請求到來，選取伺服器時，會周遊數組中所有伺服器。對于每個伺服器，讓它的current_weight增加它的weight；同時累加所有伺服器的weight，并儲存為total。

   　　周遊完所有伺服器之後，如果該伺服器的current_weight是最大的，就選擇這個伺服器處理本次請求。最後把該伺服器的current_weight減去total。

3. 哈希（Hash）法

先将後端伺服器清單（如：按照位址IP）計算出哈希值，然後映射到HASH環上（如果伺服器執行個體節點較少可以增加虛拟節點），當接收請求時，根據請求的資訊（如請求的用戶端IP、使用者ID等）計算出哈希值，最後将請求資訊的哈希值映射到HASH環上，按順時針方向，确定落在哪個區間中，則選擇區間的下一個伺服器節點作為處理此次請求的伺服器。

4. 最小連接配接數（Least Connections）法

由于後端伺服器的配置不盡相同，對于請求的處理有快有慢，根據後端伺服器目前的連接配接情況，動态地選取其中目前積壓連接配接數最少的一台伺服器來處理目前請求，盡可能地提高後端伺服器的利用效率，将負載合理地分流到每一台機器。

可參見網上文章：淺談負載均衡算法與實作 、一緻性hash算法釋義

二、限流算法

1. 計數器（固定視窗）算法

計數器算法是使用計數器在周期内累加通路次數，當達到設定的限流值時，觸發限流政策。下一個周期開始時，進行清零，重新計數。

2. 滑動視窗算法

滑動視窗算法是将時間周期分為N個小周期，分别記錄每個小周期内通路次數，并且根據時間滑動删除過期的小周期。

3. 漏桶算法

漏桶算法是通路請求到達時直接放入漏桶，如目前容量已達到上限（限流值），則進行丢棄（觸發限流政策）。漏桶以固定的速率進行釋放通路請求（即請求通過），直到漏桶為空。

4. 令牌桶算法

令牌桶算法是程式以r（r=時間周期/限流值）的速度向令牌桶中增加令牌，直到令牌桶滿，請求到達時向令牌桶請求令牌，如擷取到令牌則通過請求，否則觸發限流政策。

可參見網上文章：

常用4種限流算法介紹及比較

限流相關的算法

三、緩存淘汰（過期）政策

1. FIFO（First In First out）

先進先出，淘汰最先緩存的資料，新加入的緩存資料最遲被淘汰，完全符合隊列。

2. LRU（Least recently used）

最近最少使用，淘汰一定時期内被通路次數最少的緩存資料，以次數作為參考。

3. LFU（Least frequently used）

最近使用次數最少，淘汰最長時間未被使用的頁面，以時間作為參考。

4. Two queues（2Q）

2Q算法有兩個緩存隊列，一個是FIFO隊列，一個是LRU隊列。當資料第一次通路時，2Q算法将資料緩存在FIFO隊列裡面，當資料第二次被通路時，則将資料從FIFO隊列移到LRU隊列裡面，兩個隊列各自按照自己的方法淘汰資料。

常用緩存政策

Redis的過期政策和記憶體淘汰政策

四、緩存更新政策

1. Cache Aside

應用在查詢資料的時候，先從緩存Cache中讀取資料，如果緩存中沒有，則再從資料庫中讀取資料，得到資料庫的資料之後，将這個資料也放到緩存Cache中。如果應用要更新某個資料，也是先去更新資料庫中的資料，更新完成之後，則通過指令讓緩存Cache中的資料失效。

2. Read/Write Through

應用要讀資料和更新資料都直接通路緩存服務，緩存服務同步的将資料更新到資料庫，在應用的眼中隻有緩存服務。

3. Write Behind

應用要讀資料和更新資料都直接通路緩存服務，緩存服務異步的将資料更新到資料庫（通過異步任務）

4. refresh-ahead

在緩存資料過期前，能自動的重新整理緩存資料（在緩存過期前剩餘時間區間内【可自定義】取資料時，緩存先将之前緩存的結果傳回給外部應用程式，然後異步的再從資料庫去更新緩存中的值，以盡可能的保證緩存的值是最新的。如果取資料的的時候超過了緩存的過期時間，就安裝read-through的方式執行）

Caching漫談--關于Cache的幾個理論

緩存服務的更新政策有哪些？

五、分庫分表方式與政策

1. 分庫分表方式

1. 垂直分庫

   以表為依據，按照業務歸屬不同，将不同的表拆分到不同的庫中。

   結果：

   • 每個庫的結構都不一樣；
   • 每個庫的資料也不一樣，沒有交集；
   • 所有庫的并集是全量資料；

2. 垂直分表

   以字段為依據，按照字段的活躍性，将表中字段拆到不同的表（主表和擴充表）中。

   • 每個表的結構都不一樣；
   • 每個表的資料也不一樣，一般來說，每個表的字段至少有一列交集，一般是主鍵，用于關聯資料；
   • 所有表的并集是全量資料；

3. 水準分庫

   以字段為依據，按照一定政策（hash、range等），将一個庫中的資料拆分到多個庫中。

   • 每個庫的結構都一樣；
   • 每個庫的資料都不一樣，沒有交集；

4. 水準分表

   以字段為依據，按照一定政策（hash、range等），将一個表中的資料拆分到多個表中。

   • 每個表的結構都一樣；
   • 每個表的資料都不一樣，沒有交集；

2. 分庫分表政策

1. hash取模

   對指定的路由key（如：id）按分表總數進行取模，得到的結果即為對應的表序号

   • 優點：訂單資料可以均勻的放到那4張表中，這樣此訂單進行操作時，就不會有熱點問題。
   • 缺點：将來的資料遷移和擴容，會很難。

2. range範圍

   按一定範圍路由key（如：id，時間戳）把對應的記錄存放到同一張表中，多個範圍區間則存放多張表【即：每個範圍區間對應一張表】

   • 優點：有利于将來的擴容，不需要做資料遷移
   • 有熱點問題，在某一個時間範圍内某個表的IO壓力可能會非常大

3. range+hash分組

   首先用range方案讓資料落地到一個範圍裡面（即：分組區間）。這樣以後id再變大，那以前的資料是不需要遷移的。然後在這個範圍裡面（即：分組區間）再根據路由key（如：id）按分表總數（注意含所有分組中的所有分表總數）進行取模，得到的結果即為對應的表序号【即：在一定範圍内均勻分布資料】

   • 優點：避免熱問題，擴容相對容易
   • 缺點：實作較複雜

4. 一緻性hash

   通過哈希函數，每個節點都會被配置設定到環上的一個位置，每個鍵值也會被映射到環上的一個位置。這個鍵值最終被放置在距離該它的位置最近的，且位置編号大于等于該值的節點上面，即放置到順時針的下一個節點上面。

​ 可參見網上文章：

海量資料分庫分表方案（一）算法方案

資料庫怎麼分庫分表，垂直？水準？

分庫分表？如何做到永不遷移資料和避免熱點？