將一些零散的知識點進行整理， 以便加深理解，方便查閱，也希望能幫到大家。 一、負載均衡演算法 1. 隨機 完全隨機 通過系統隨機函數，根據後端伺服器列表的大小值來隨機選擇其中一臺進行訪問。由概率統計理論可以得知，隨著調用量的增大，其實際效果越來越接近於平均分配流量到每一臺後端伺服器，也就是輪詢的效果。 ...
將一些零散的知識點進行整理， 以便加深理解，方便查閱，也希望能幫到大家。
一、負載均衡演算法
1. 隨機
- 完全隨機
通過系統隨機函數，根據後端伺服器列表的大小值來隨機選擇其中一臺進行訪問。由概率統計理論可以得知，隨著調用量的增大，其實際效果越來越接近於平均分配流量到每一臺後端伺服器，也就是輪詢的效果。
-
加權隨機
雖然還是採用的隨機演算法，但是為每台伺服器根據不同的配置和負載情況來配置不同的權重，權重大的伺服器獲得的概率大一些，權重小的伺服器獲得的概率小一些。
2. 輪詢
-
完全輪詢
將請求按順序輪流地分配到伺服器上，它均衡地對待後端的每一臺伺服器，而不關心伺服器實際的連接數和當前的系統負載情況。
-
加權輪詢
根據伺服器的不同處理能力，給每個伺服器分配不同的權重值，使其能夠將請求順序的按照權重分配到後端伺服器上，權重越大，對應的伺服器每輪所獲得的請求數量越多。
-
平滑加權輪詢
每個伺服器都有兩個權重變數：
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=時間周期/限流值）的速度向令牌桶中增加令牌，直到令牌桶滿，請求到達時向令牌桶請求令牌，如獲取到令牌則通過請求，否則觸發限流策略。
可參見網上文章：
三、緩存淘汰（過期）策略
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. 分庫分表方式
-
垂直分庫
以表為依據，按照業務歸屬不同，將不同的表拆分到不同的庫中。
結果：
- 每個庫的結構都不一樣；
- 每個庫的數據也不一樣，沒有交集；
- 所有庫的並集是全量數據；
-
垂直分表
以欄位為依據，按照欄位的活躍性，將表中欄位拆到不同的表（主表和擴展表）中。
結果：
-
每個表的結構都不一樣；
-
每個表的數據也不一樣，一般來說，每個表的欄位至少有一列交集，一般是主鍵，用於關聯數據；
-
所有表的並集是全量數據；
-
-
水平分庫
以欄位為依據，按照一定策略（hash、range等），將一個庫中的數據拆分到多個庫中。
結果：
- 每個庫的結構都一樣；
- 每個庫的數據都不一樣，沒有交集；
- 所有庫的並集是全量數據；
-
水平分表
以欄位為依據，按照一定策略（hash、range等），將一個表中的數據拆分到多個表中。
結果：
- 每個表的結構都一樣；
- 每個表的數據都不一樣，沒有交集；
- 所有表的並集是全量數據；
2. 分庫分表策略
-
hash取模
對指定的路由key（如：id）按分表總數進行取模，得到的結果即為對應的表序號
- 優點：訂單數據可以均勻的放到那4張表中，這樣此訂單進行操作時，就不會有熱點問題。
- 缺點：將來的數據遷移和擴容，會很難。
-
range範圍
按一定範圍路由key（如：id，時間戳）把對應的記錄存放到同一張表中，多個範圍區間則存放多張表【即：每個範圍區間對應一張表】
- 優點：有利於將來的擴容，不需要做數據遷移
- 有熱點問題，在某一個時間範圍內某個表的IO壓力可能會非常大
-
range+hash分組
首先用range方案讓數據落地到一個範圍裡面（即：分組區間）。這樣以後id再變大，那以前的數據是不需要遷移的。然後在這個範圍裡面（即：分組區間）再根據路由key（如：id）按分表總數（註意含所有分組中的所有分表總數）進行取模，得到的結果即為對應的表序號【即：在一定範圍內均勻分佈數據】
- 優點：避免熱問題，擴容相對容易
- 缺點：實現較複雜
-
一致性hash
通過哈希函數，每個節點都會被分配到環上的一個位置，每個鍵值也會被映射到環上的一個位置。這個鍵值最終被放置在距離該它的位置最近的，且位置編號大於等於該值的節點上面，即放置到順時針的下一個節點上面。
-
優點：避免熱問題，擴容相對容易
-
缺點：實現較複雜
-
可參見網上文章：
海量數據分庫分表方案（一）演算法方案
資料庫怎麼分庫分表，垂直？水平？
分庫分表？如何做到永不遷移數據和避免熱點？
