哨兵演算法
㈠ redis主從和哨兵
主從復制：主節點負責寫數據，從節點負責讀數據，主節點定期把數據同步到從節點保證數據的一致性
a,配置主從復制方式一、新增redis6380.conf, 加入 slaveof 192.168.152.128 6379, 在6379啟動完後再啟6380，完成配置；
b,配置主從復制方式二、redis-server --slaveof 192.168.152.128 6379 臨時生效
c,查看狀態：info replication
d,斷開主從復制：在slave節點，執行6380:>slaveof no one
e,斷開後再變成主從復制：6380:> slaveof 192.168.152.128 6379
f,數據較重要的節點，主從復制時使用密碼驗證： requirepass
e, 從節點建議用只讀模式slave-read-only=yes, 若從節點修改數據，主從數據不一致
h,傳輸延遲：主從一般部署在不同機器上，復制時存在網路延時問題，redis提供repl-disable-tcp-nodelay參數決定是否關閉TCP_NODELAY,默認為關閉
參數關閉時：無論大小都會及時發布到從節點，占帶寬，適用於主從網路好的場景，
參數啟用時：主節點合並所有數據成TCP包節省帶寬，默認為40毫秒發一次，取決於內核，主從的同步延遲40毫秒，適用於網路環境復雜或帶寬緊張，如跨機房
a)一主一從：用於主節點故障轉移從節點，當主節點的「寫」命令並發高且需要持久化，可以只在從節點開啟AOF（主節點不需要），這樣即保證了數據的安全性，也避免持久化對主節點的影響
b)一主多從：針對「讀」較多的場景，「讀」由多個從節點來分擔，但節點越多，主節點同步到多節點的次數也越多，影響帶寬，也加重主節點的穩定
c)樹狀主從：一主多從的缺點（主節點推送次數多壓力大）可用些方案解決，主節點只推送一次數據到從節點B，再由從節點B推送到C，減輕主節點推送的壓力。
redis 2.8版本以上使用psync命令完成同步，過程分「全量」與「部分」復制
全量復制：一般用於初次復制場景（第一次建立SLAVE後全量）
部分復制：網路出現問題，從節點再次連接主節點時，主節點補發缺少的數據，每次數據增量同步
心跳：主從有長連接心跳，主節點默認每10S向從節點發ping命令，repl-ping-slave-period控制發送頻率
a)主從復制，若主節點出現問題，則不能提供服務，需要人工修改配置將從變主
b)主從復制主節點的寫能力單機，能力有限
c)單機節點的存儲能力也有限
a)主節點(master)故障，從節點slave-1端執行 slaveof no one後變成新主節點；
b)其它的節點成為新主節點的從節點，並從新節點復制數據；
c)需要人工干預，無法實現高可用。
1. 為什麼要有哨兵機制？
原理：當主節點出現故障時，由Redis Sentinel自動完成故障發現和轉移，並通知應用方，實現高可用性。
其實整個過程只需要一個哨兵節點來完成，首先使用Raft演算法（選舉演算法）實現選舉機制，選出一個哨兵節點來完成轉移和通知
任務1：每個哨兵節點每10秒會向主節點和從節點發送info命令獲取最拓撲結構圖，哨兵配置時只要配置對主節點的監控即可，通過向主節點發送info，獲取從節點的信息，並當有新的從節點加入時可以馬上感知到
任務2：每個哨兵節點每隔2秒會向redis數據節點的指定頻道上發送該哨兵節點對於主節點的判斷以及當前哨兵節點的信息，同時每個哨兵節點也會訂閱該頻道，來了解其它哨兵節點的信息及對主節點的判斷，其實就是通過消息publish和subscribe來完成的
任務3：每隔1秒每個哨兵會向主節點、從節點及其餘哨兵節點發送一次ping命令做一次心跳檢測，這個也是哨兵用來判斷節點是否正常的重要依據
客觀下線：當主觀下線的節點是主節點時，此時該哨兵3節點會通過指令sentinel is-masterdown-by-addr尋求其它哨兵節點對主節點的判斷，當超過quorum（選舉）個數，此時哨兵節點則認為該主節點確實有問題，這樣就客觀下線了，大部分哨兵節點都同意下線操作，也就說是客觀下線
a)每個在線的哨兵節點都可以成為領導者，當它確認（比如哨兵3）主節點下線時，會向其它哨兵發is-master-down-by-addr命令，徵求判斷並要求將自己設置為領導者，由領導者處理故障轉移；
b)當其它哨兵收到此命令時，可以同意或者拒絕它成為領導者；
c)如果哨兵3發現自己在選舉的票數大於等於num(sentinels)/2+1時，將成為領導者，如果沒有超過，繼續選舉…………
a)由Sentinel節點定期監控發現主節點是否出現了故障
sentinel會向master發送心跳PING來確認master是否存活，如果master在「一定時間范圍」內不回應PONG 或者是回復了一個錯誤消息，那麼這個sentinel會主觀地(單方面地)認為這個master已經不可用了
b) 當主節點出現故障，此時3個Sentinel節點共同選舉了Sentinel3節點為領導，負載處理主節點的故障轉移
c) 由Sentinel3領導者節點執行故障轉移，過程和主從復制一樣，但是自動執行
流程：
1. 將slave-1脫離原從節點，升級主節點，
d) 故障轉移後的redis sentinel的拓撲結構圖
a) 過濾掉不健康的（下線或斷線），沒有回復過哨兵ping響應的從節點
b) 選擇salve-priority從節點優先順序最高（redis.conf）的
c) 選擇復制偏移量最大，指復制最完整的從節點
以3個Sentinel節點、2個從節點、1個主節點為例進行安裝部署
1. 前提： 先搭好一主兩從redis的主從復制，和之前的主從復制搭建一樣，搭建方式如下：
A）主節點6379節點（/usr/local/bin/conf/redis6379.conf）：
修改 requirepass 12345678，注釋掉#bind 127.0.0.1
B) 從節點redis6380.conf和redis6381.conf: 配置都一樣
修改 requirepass 12345678 ,注釋掉#bind 127.0.0.1,
加上訪問主節點的密碼masterauth 12345678 ,加上slaveof 192.168.152.128 6379
2. redis sentinel哨兵機制核心配置 (也是3個節點)：
將三個文件的埠改成: 26379 26380 26381
然後：sentinel monitor mymaster 192.168.152.128 6379 2 //監聽主節點6379
三個配置除埠外，其它一樣。
3. 哨兵其它的配置 ：只要修改每個sentinel.conf的這段配置即可：
sentinel monitor mymaster 192.168.152.128 6379 2
//監控主節點的IP地址埠，sentinel監控的master的名字叫做mymaster，2代表，當集群中有2個sentinel認為master死了時，才能真正認為該master已經不可用了
sentinel auth-pass mymaster 12345678 //sentinel連主節點的密碼
sentinel config-epoch mymaster 2 //故障轉移時最多可以有2從節點同時對新主節點進行數據同步
sentinel leader-epoch mymaster 2
sentinel failover-timeout mymasterA **180000 **//故障轉移超時時間180s，
a,如果轉移超時失敗，下次轉移時時間為之前的2倍；
b,從節點變主節點時，從節點執行slaveof no one命令一直失敗的話，當時間超過 180S 時，則故障轉移失敗
c,從節點復制新主節點時間超過 180S 轉移失敗
sentinel down-after-milliseconds mymasterA 300000 //sentinel節點定期向主節點ping命令，當超過了 300S 時間後沒有回復，可能就認定為此主節點出現故障了……
sentinel parallel-syncs mymasterA 1 //故障轉移後， 1 代表每個從節點按順序排隊一個一個復制主節點數據，如果為3，指3個從節點同時並發復制主節點數據，不會影響阻塞，但存在網路和IO開銷
4. 啟動redis服務和sentinel服務:
a)先把之前安裝的redis裡面的標綠色的文件都拷貝到 usr/local/bin目錄下，然後再再bin目錄下新建一個conf文件夾存放配置好的redis主從配置文件和哨兵配置文件
b)啟動主從復制服務，先啟動主再啟動從
主：./redis-server conf/redis6379.conf &
從：
./redis-server conf/redis6380.conf &
./redis-server conf/redis6381.conf &
c）啟動sentinel服務:
./redis-sentinel conf/sentinel_26381.conf &
到此服務全部啟動完畢
連接到6379的redis的服務，可看到6379就是主節點，他有6380和6381兩個從節點
5. 測試： kill -9 6379 殺掉6379的redis服務
可以看到殺掉6379以後6380變為了主節點，6381變為了6380的從節點
重新啟動6379以後變為6380的從節點
看日誌是分配6380 是6381的主節點，當6379服務再啟動時，已變成從節點
假設6380升級為主節點:進入6380>info replication 可以看到role:master
打開sentinel_26379.conf等三個配置，sentinel monitor mymaster 192.168.152.128 6380 2
打開redis6379.conf等三個配置, slaveof 192.168.152.128 6380,也變成了6380
注意：生產環境建議讓redis Sentinel部署到不同的物理機上。
a，sentinel節點應部署在多台物理機（線上環境）
b，至少三個且奇數個sentinel節點
c，通過以上我們知道，3個sentinel可同時監控一個主節點或多個主節點
sentinel參考資料：
redis sentinel的機制與用法一： https://segmentfault.com/a/1190000002680804
redis sentinel的機制與用法二： https://segmentfault.com/a/1190000002685515
㈡ @數據結構大神，（3）的失敗後的查找長度為啥是n+1求解釋！
首先，這里的順序查找演算法應該是包含哨兵的演算法（就是令數組下標為0的元素的值為你要查找的關鍵字）。查找失敗意味著n個元素都比較過了，接下來會比較下一個元素，即最後的哨兵元素（注意是從後往前查找的），然後跳出查找的循環語句。所以一共比較了n+1次。
平均查找長度公式是概率乘比較次數的求和。假設每個元素查找概率為1/n，而失敗時每個元素都相當於比較n+1次，即查找失敗時每個元素的查找長度一樣，都是（n+1）/n。不算哨兵元素，一共有n個元素進行了查找，故ASL=n*（n+1/n）=n+1