業務開發中你用到了哪些演算法（續）？
- 2019 年 12 月 18 日
- 筆記
上次我們一起聊了聊普通 hash 演算法在實際中的應用，但是按照一猿小講的風格，絕不能止於應用，為了能讓面試官再喝一壺，還是要稍微升華一下，話不多說，本期的分享正式開始（建議一定要讀到最後）。
01. 悶頭看程式碼
一、回首上期，提煉精華。
栗1：假如訂單表要分 3 張，首先用當前資料庫的時間與某一固定的時間計算出的相差的天數 days；然後用 days % 3 算出當前數據應該放到訂單表的下標。
庖丁解牛，解剖栗子。 步驟1：days 是當前時間（key）與某一固定的時間計算出的相差的天數，簡化為 days = function(key)； 步驟2：訂單表分 3 張，那麼訂單表的下標 = days % 3； 結論1：int position = function(key) % 3
栗2：假如資料庫要分 dbNum 節點，首先用分庫依據欄位 key 經過 crc32 加工得到值 x；然後用 x % dbNum 算出當前數據落到對應庫的下標。
庖丁解牛，解剖栗子。 步驟一：x 是經過 crc32 加工之後的值，簡化為 x = function(key)； 步驟二：資料庫分 dbNum 節點，那麼資料庫的下標 = x % dbNum； 結論2：int position = function(key) % dbNum
栗3：假如在 dbNum 個資料庫下再分 tableNum 張表，首先用分庫依據欄位 key 經過 crc32 加工得到值 x；然後用 x % tbaleNum 算出當前數據落到對應表的下標。
庖丁解牛，解剖栗子。 步驟一：x 是經過 crc32 加工之後的值，簡化為 x = function(key)； 步驟二：表共分 tableNum 張表，那麼當前數據對應表的下標 = x % tableNum； 結論3：int position = function(key) % tableNum
二、抽象共性，沉澱精華。
結論1：int position = function(key) % 3 結論2：int position = function(key) % dbNum 結論3：int position = function(key) % tableNum
通過上述栗子的三個結論，我們很容易得出如下表達式。
long position = function(key) % num
汗顏，一個非常簡單的問題，被我講的那麼複雜（實在汗顏）。
三、歸根結底、總而言之。
long position = function(key) % num
一定要牢記這個公式，真的很有用呦，後面也會反覆用！因為一行簡單的表達式，就輕鬆解決了我們實際應用中分庫分表的問題。
02. 低頭憶往昔
你有沒有經過這樣一種場景，在開發、測試環境你開發的 WEB 網站，登錄成功後訪問其它頁面都暢通無阻，但是一旦部署到生產上問題就出現了，網站登錄成功後一刷新頁面，就會跳轉到登錄頁面讓重新登錄… … 自己腦補那種鬧鬼似的場景吧（有同感的今天一定要點個「在看」）。
估計多數研發人員都遇到過，分析原因無非如下：
分析一：開發、測試環境都是部署一台 WEB 網站服務，登錄成功之後，驗證其它功能賊啦溜； 分析二：生產環境一般為了屏蔽單點故障，都會部署多份服務，導致請求到一台服務上登錄成功後，再請求到另外一台時還是提示未登錄，感覺就是見了鬼； 結論：研發人員沒有針對 Session 做共享存儲，其實也就是沒有寫到 Redis，也就是說服務端研發人員沒有維護 Session 的資訊。
但是，這口鍋誰來背？其實往往這個時候考慮的不是讓誰背鍋，而是要快速解決問題，不能讓用戶拒之於網站千里之外，臨時改程式碼肯定是來不及啦，快而穩的臨時解決方式，便是讓運維同事在 Nginx 上做一個 ip_hash，而且效果往往會很好。
但是後端研發人員還是需要儘快修復 Bug，因為 ip_hash 的方式不是很推薦使用，另外謹記一點是：研發人員能做的事情，盡量不要依賴外圍系統去做。
為什麼 ip_hash 能幫我們臨時解決會話的問題呢？因為它能夠讓用戶（某 ip）在一段時間內的請求，只請求到固定的某台 WEB 伺服器中，這樣會話就會保持，就不會再出現網站登錄成功之後，再訪問其它頁面時又重新跳轉到登錄頁面的情況啦。
但是，Nginx 是怎麼做到的呢？不妨我們舉頭望望遠方，學學人家是咋實現的。
03.舉頭望遠方
首先下載 nginx-1.17.6 版本的安裝包，來個一窺到底（你可以忽略，直接看結果就可以啦）。
下載鏈接：https://nginx.org/en/download.html?_ga=2.182537958.1901173857.1575548135-854843835.1575548135
其它的細枝末節都可以忽略，主要看圈住的重點，看似很難懂，但是回歸本質，把咱們開篇的結論拿來套用一下。
long position = function(key) % num
仔細去看，圈住的兩部分不就是在執行 function(key) % num 嗎？！只不過演算法比我們的稍微複雜了很多，但是目標卻是一致的，都是在獲取數據應該落地的位置。這裡只不過是為了找出用戶發起請求的客戶端的 IP， 對應的目標機器列表中的序號 p，然後選擇出對應的伺服器。
到這，估計你會暈菜，不過抽象去看，只要搞懂咱們開篇的那個結論，今晚就可以吃雞、大吉大利。
舉頭望遠方，遠方卻流浪，為什麼流浪，流浪遠方，流浪。鋪墊了這麼多，是該到升華的時候了。
拿出我們開篇的結論 long position = function(key) % num如果我們把 function(key) 理解成計算 key 的 hash 值（例如咱們用過的 CRC32），然後除以機器的總數（serverListSize），那麼總能得出 key 要落到的機器節點下標，進而通過下標得出對應的機器節點 targetServer。
targetServer = serverList[hash(key) % serverList.size]
此時此刻，我們應該想想分散式快取 memcached 以及上面提到的 Nginx，採用上面的表達式肯定能實現負載，而且很演算法很簡單。
但是也存在一個致命的問題，如果 server 掛掉或者增加一台節點怎麼辦呢？serverList.size 就會變化，那 key 對應的機器就要全部變化，如果是快取，則會導致快取無法命中，如果是海量數據，豈不是要地崩山摧壯士死？！怎樣讓影響範圍小一點呢，這不就有了一致性 hash。
啥是一致性 hash？說起來其實也很簡單。
第一步：先把原來的每一個機器節點鼓搗出 N 個虛擬節點；然後定義一個[0,(2^32)-1]的數值區間； 第二步：接著把機器節點（含虛擬的節點）通過 hash 演算法計算出數值，映射到[0,(2^32)-1]的數值區間中（此時腦海中要有一條線，上面鋪滿了機器節點）； 第三步：然後把請求的 key 通過 hash 演算法得到一個數值，然後在 [0,(2^32)-1] 區間中定位一個位置，然後向右找到距離最近的機器節點（此時腦海中依然要有鋪滿機器節點的那條線）。
啥是 hash環？有些時候面試的時候也會提這個玩意，其實說的還是一致性 hash，為什麼這麼說呢？因為當請求數據，通過 hash 演算法得到一個值，如果這個值超過 2^32-1，則會視為 0，也就是把腦海中的那條 [0,(2^32)-1]的線段首尾相連形成一個環，所以又叫 hash 環。
圖片來源於網路，侵之告之刪之
一致性 hash 怎麼把影響範圍降到了更小呢？由於按照上面步驟的設計，即使機器掛了一個機器節點，也只會影響這一台機器上的數據，不會讓數據全部受到影響；如果新加一台機器，大部分 key 根據一致性哈希演算法定位對應的機器節點都不會發生變化，只有那些計算出的值，離新加節點更近的 key 的數據發生了變化。
升華就到這兒吧，懂就懂了，若不懂就索性把開篇那個結論搞懂，那樣也夠面試官喝一壺的啦。
04. 遠方有希望
今天的分享就到這兒吧，主要想分享悶頭看程式碼、低頭憶往昔、舉頭望遠方三點。日常研發要學會悶頭看程式碼，多抽象多思考；事故總結要學會低頭憶往昔，多總結多提煉；鑽研技術要學會舉頭望遠方，多擴展有深度；相信遠方一定會有希望。
