日誌分類演算法

『壹』 RAFT與PBFT

【一．raft演算法】

因為網上已經有大量文章對raft演算法進行過詳細的介紹，因此這部分只會簡單的闡述演算法的基本原理和流程。raft演算法包含三種角色，分別是：跟隨者（follower），候選人（candidate）和領導者（leader）。集群中的一個節點在某一時刻只能是這三種狀態的其中一種，這三種角色是可以隨著時間和條件的變化而互相轉換的。

raft演算法主要有兩個過程：一個過程是領導者選舉，另一個過程是日誌復制，其中日誌復制過程會分記錄日誌和提交數據兩個階段。raft演算法支持最大的容錯故障節點是（N-1）/2，其中N為 集群中總的節點數量。

國外有一個動畫介紹raft演算法介紹的很透徹，鏈接地址在這里[1]。這個動畫主要包含三部分內容，第一部分介紹簡單版的領導者選舉和日誌復制的過程，第二部分內容介紹詳細版的領導者選舉和日誌復制的過程，第三部分內容介紹的是如果遇到網路分區（腦裂），raft演算法是如何恢復網路一致的。有興趣的朋友可以結合這個動畫來更好的理解raft演算法。

【二．pbft演算法】

pbft演算法的提出主要是為了解決拜占庭將軍問題。什麼是拜占庭將軍問題呢？拜占庭位於如今的土耳其的伊斯坦布爾，是古代東羅馬帝國的首都。拜占庭羅馬帝國國土遼闊，為了達到防禦目的，每塊封地都駐扎一支由將軍統領的軍隊，每個軍隊都分隔很遠，將軍與將軍之間只能靠信差傳遞消息。 在戰爭的時候，拜占庭軍隊內所有將軍必需達成一致的共識，決定是否有贏的機會才去攻打敵人的陣營。但是，在軍隊內有可能存有叛徒和敵軍的間諜，左右將軍們的決定影響將軍們達成一致共識。在已知有將軍是叛徒的情況下，其餘忠誠的將軍如何達成一致協議的問題，這就是拜占庭將軍問題。

下圖列出了raft演算法和pbft演算法在適用環境，通信復雜度，最大容錯節點數和流程上的對比。

關於兩個演算法的適用環境和最大容錯節點數，前文已經做過闡述，這里不再細說。而對於演算法通信復雜度，為什麼raft是o（n），而pbft是o（n^2）呢？這里主要考慮演算法的共識過程。

對於raft演算法，核心共識過程是日誌復制這個過程，這個過程分兩個階段，一個是日誌記錄，一個是提交數據。兩個過程都只需要領導者發送消息給跟隨者節點，跟隨者節點返回消息給領導者節點即可完成，跟隨者節點之間是無需溝通的。所以如果集群總節點數為 n，對於日誌記錄階段，通信次數為n-1，對於提交數據階段，通信次數也為n-1，總通信次數為2n-2，因此raft演算法復雜度為O（n）。

對於pbft演算法，核心過程有三個階段，分別是pre-prepare（預准備）階段，prepare（准備）階段和commit（提交）階段。對於pre-prepare階段，主節點廣播pre-prepare消息給其它節點即可，因此通信次數為n-1；對於prepare階段，每個節點如果同意請求後，都需要向其它節點再 廣播parepare消息，所以總的通信次數為n （n-1），即n^2-n；對於commit階段，每個節點如果達到prepared狀態後，都需要向其它節點廣播commit消息，所以總的通信次數也為n （n-1），即n ^{2-n。所以總通信次數為（n-1）+（n} 2-n）+（n ^{2-n），即2n} 2-n-1，因此pbft演算法復雜度為O（n^2）。

流程的對比上，對於leader選舉這塊，raft演算法本質是誰快誰當選，而pbft演算法是按編號依次輪流做主節點。對於共識過程和重選leader機制這塊，為了更形象的描述這兩個演算法，接下來會把raft和pbft的共識過程比喻成一個團隊是如何執行命令的過程，從這個角度去理解raft演算法和pbft的區別。

一個團隊一定會有一個老大和普通成員。對於raft演算法，共識過程就是：只要老大還沒掛，老大說什麼，我們（團隊普通成員）就做什麼，堅決執行。那什麼時候重新老大呢？只有當老大掛了才重選老大，不然生是老大的人，死是老大的鬼。

對於pbft演算法，共識過程就是：老大向我發送命令時，當我認為老大的命令是有問題時，我會拒絕執行。就算我認為老大的命令是對的，我還會問下團隊的其它成員老大的命令是否是對的，只有大多數人（2f+1）都認為老大的命令是對的時候，我才會去執行命令。那什麼時候重選老大呢？老大掛了當然要重選，如果大多數人都認為老大不稱職或者有問題時，我們也會重新選擇老大。

『貳』 日誌實體類信息包括哪些內容

tomcat 日誌信息
前言

tomcat的日誌信息。

tomcat如何查看日誌信息。

tomcat的日誌信息包括哪些部分。

tomcat的日誌信息包括哪些部分

1、啟動/關閉tomcat時的日誌信息，這里指的是tomcat本身的日誌信息，往往是tomcat本身的問題。

比如，啟動tomcat時，埠被佔用。

2、訪問網站時出現的日誌信息，這里往往是代碼程序出現bug。

tomcat如何查看日誌信息

tomcat的日誌信息文件，是放在安裝目錄/logs/目錄下的。最常用的包括兩部分，就是前面說的2種類型。

1、啟動/關閉tomcat時的日誌信息，在 catalina.2015-12-02.log文件里。

每天都會生成一個新的單獨的文件。

2、訪問網站時的日誌信息，在localhost.2015-12-02.log文件里。

只要那天有訪問，就會生成一個新的單獨的日誌文件。

收起全文
一個日誌系統需要具備哪些功能

『叄』 一個日誌解析的演算法Drain

論文名稱：
Drain: An Online Log Parsing Approach with Fixed Depth Tree

drain演算法的全稱是depth tree based online log parsing

這種解決方案非常慢，因為隨著日誌組的增加，解析時間增長的非常迅速。

根節點是頂層節點，葉子節點是底層節點，其餘都叫做內部節點。

根節點和內部節點的編碼是特殊設計過的規則用來引導整個搜索過程

parse tree的一個特殊設計就是所有的葉子節點的深度都是相同的（取決於你預先設定的參數depth），這個參數會限制演算法在搜索過程中訪問到的葉子節點，但是會大幅度的提升效率。

根據先驗知識設定一些正則表達式

一個數據集通常只需要很少，且很簡單的正則。

解析樹的第一層節點表示日誌組，他們是日誌消息長度不同的分組。日誌消息長度，這里指的是一個日誌消息裡面tokens的個數。

這個做法依賴於一個假設：相同的log event具有相同的日誌信息長度。即便是這個假設不成立，也可以通過簡單的後續處理來控制，即便是後續不處理，Drain這個演算法的表現也很好。（換句話來說就是，管他假設成立不成立，老子就是要這么做，你能把我咋地）

我們還設定了一個參數maxChild，最大子節點數，用以約束一個節點的最大子節點數。如果一個節點已經有了maxChild個子節點，那麼任何沒有被匹配的tokens都將會被匹配為內部特殊符號*

注意一點：如果depth是2，那麼Drain值考慮第一層（step2中提到的）也就是說只考慮長度那一層，不考慮第一個token。原因如下：

在這一步驟中，Drain將會從日誌組的列表裡面選擇最合適日誌組。

我們計算每個日誌組中日誌消息和日誌事件之間的相似度simSeq（公式一）。

其中seq1和seq2分別表示日誌消息和日誌事件。

Log event是最適合描述該組日誌消息的模板，它由日誌消息的常量部分組成。（這里的log event可以理解成模板，但是問題來了，我們解析完成時才會生成結構化日誌和模板，那麼這個時候的模板是怎麼來的？什麼樣子的？）

seq(i)表示這個sequence中的第i個token，n是信息的長度。方程equ的定義如公式二。

t1和t2是兩個token。在找到simSeq最大的日誌組之後，我們將其與預定義的相似度閾值st進行比較。如果simSeq ≥ st，那麼就返回這個分組作為最相似的日誌組。否則，就返回一個flag（python是None）來表示沒有合適的日誌組。

如果在上一個步驟中找到了合適的日誌組，就把當前日誌的ID添加到日誌組的後面。

如果沒有找到，就要創建一個新的日誌組，並且更新解析樹

這里有一點要注意一下：首先根據日誌內容的長度分類，構建根節點，然後再根據設定的deepth，比如深度是2，第一層就是根節點root，第二層就是長度。比如深度是3，第三層就是第一個單詞。以此類推。以深度為3為例，如果root（第一層），長度（第二層），第一個單詞（第三層）都相同，就是一個節點。然後在經過step4的計算，遍歷所有長度相同第一個單詞也相同的日誌，來計算step4中的相似度，並且和設定好的相似度閾值對比，如果符合就合並到一個group里，如果不符合就分裂成兩個葉子節點。
如果第三層不同，則分裂成兩個節點。

『肆』 Raft 演算法（詳細版）

在分布式系統中，一致性演算法至關重要。在所有一致性演算法中，Paxos 最負盛名，它由萊斯利·蘭伯特（Leslie Lamport）於 1990 年提出，是一種基於消息傳遞的一致性演算法，被認為是類似演算法中最有效的。

Paxos 演算法雖然很有效，但復雜的原理使它實現起來非常困難，截止目前，實現 Paxos 演算法的開源軟體很少，比較出名的有 Chubby、LibPaxos。此外，Zookeeper 採用的 ZAB（Zookeeper Atomic Broadcast）協議也是基於 Paxos 演算法實現的，不過 ZAB 對 Paxos 進行了很多改進與優化，兩者的設計目標也存在差異——ZAB 協議主要用於構建一個高可用的分布式數據主備系統，而 Paxos 演算法則是用於構建一個分布式的一致性狀態機系統。

由於 Paxos 演算法過於復雜、實現困難，極大地制約了其應用，而分布式系統領域又亟需一種高效而易於實現的分布式一致性演算法，在此背景下，Raft 演算法應運而生。

Raft 演算法在斯坦福 Diego Ongaro 和 John Ousterhout 於 2013 年發表的《In Search of an Understandable Consensus Algorithm》中提出。相較於 Paxos，Raft 通過邏輯分離使其更容易理解和實現，目前，已經有十多種語言的 Raft 演算法實現框架，較為出名的有 etcd、Consul 。

根據官方文檔解釋，一個 Raft 集群包含若干節點，Raft 把這些節點分為三種狀態：Leader、 Follower、Candidate，每種狀態負責的任務也是不一樣的。正常情況下，集群中的節點只存在 Leader 與 Follower 兩種狀態。

• Leader（領導者） ：負責日誌的同步管理，處理來自客戶端的請求，與Follower保持heartBeat的聯系；

• Follower（追隨者） ：響應 Leader 的日誌同步請求，響應Candidate的邀票請求，以及把客戶端請求到Follower的事務轉發（重定向）給Leader；

• Candidate（候選者） ：負責選舉投票，集群剛啟動或者Leader宕機時，狀態為Follower的節點將轉為Candidate並發起選舉，選舉勝出（獲得超過半數節點的投票）後，從Candidate轉為Leader狀態。

通常，Raft 集群中只有一個 Leader，其它節點都是 Follower。Follower 都是被動的，不會發送任何請求，只是簡單地響應來自 Leader 或者 Candidate 的請求。Leader 負責處理所有的客戶端請求（如果一個客戶端和 Follower 聯系，那麼 Follower 會把請求重定向給 Leader）。

為簡化邏輯和實現，Raft 將一致性問題分解成了三個相對獨立的子問題。

• 選舉（Leader Election） ：當 Leader 宕機或者集群初創時，一個新的 Leader 需要被選舉出來；

• 日誌復制（Log Replication） ：Leader 接收來自客戶端的請求並將其以日誌條目的形式復制到集群中的其它節點，並且強制要求其它節點的日誌和自己保持一致；

• 安全性（Safety） ：如果有任何的伺服器節點已經應用了一個確定的日誌條目到它的狀態機中，那麼其它伺服器節點不能在同一個日誌索引位置應用一個不同的指令。

根據 Raft 協議，一個應用 Raft 協議的集群在剛啟動時，所有節點的狀態都是 Follower。由於沒有 Leader，Followers 無法與 Leader 保持心跳（Heart Beat），因此，Followers 會認為 Leader 已經下線，進而轉為 Candidate 狀態。然後，Candidate 將向集群中其它節點請求投票，同意自己升級為 Leader。如果 Candidate 收到超過半數節點的投票（N/2 + 1），它將獲勝成為 Leader。

第一階段：所有節點都是 Follower。

上面提到，一個應用 Raft 協議的集群在剛啟動（或 Leader 宕機）時，所有節點的狀態都是 Follower，初始 Term（任期）為 0。同時啟動選舉定時器，每個節點的選舉定時器超時時間都在 100~500 毫秒之間且並不一致（避免同時發起選舉）。

第二階段：Follower 轉為 Candidate 並發起投票。

沒有 Leader，Followers 無法與 Leader 保持心跳（Heart Beat），節點啟動後在一個選舉定時器周期內未收到心跳和投票請求，則狀態轉為候選者 Candidate 狀態，且 Term 自增，並向集群中所有節點發送投票請求並且重置選舉定時器。

注意，由於每個節點的選舉定時器超時時間都在 100-500 毫秒之間，且彼此不一樣，以避免所有 Follower 同時轉為 Candidate 並同時發起投票請求。換言之，最先轉為 Candidate 並發起投票請求的節點將具有成為 Leader 的「先發優勢」。

第三階段：投票策略。

節點收到投票請求後會根據以下情況決定是否接受投票請求（每個 follower 剛成為 Candidate 的時候會將票投給自己）：

請求節點的 Term 大於自己的 Term，且自己尚未投票給其它節點，則接受請求，把票投給它；

請求節點的 Term 小於自己的 Term，且自己尚未投票，則拒絕請求，將票投給自己。

第四階段：Candidate 轉為 Leader。

一輪選舉過後，正常情況下，會有一個 Candidate 收到超過半數節點（N/2 + 1）的投票，它將勝出並升級為 Leader。然後定時發送心跳給其它的節點，其它節點會轉為 Follower 並與 Leader 保持同步，到此，本輪選舉結束。

注意：有可能一輪選舉中，沒有 Candidate 收到超過半數節點投票，那麼將進行下一輪選舉。

在一個 Raft 集群中，只有 Leader 節點能夠處理客戶端的請求（如果客戶端的請求發到了 Follower，Follower 將會把請求重定向到 Leader） ，客戶端的每一個請求都包含一條被復制狀態機執行的指令。Leader 把這條指令作為一條新的日誌條目（Entry）附加到日誌中去，然後並行得將附加條目發送給 Followers，讓它們復制這條日誌條目。

當這條日誌條目被 Followers 安全復制，Leader 會將這條日誌條目應用到它的狀態機中，然後把執行的結果返回給客戶端。如果 Follower 崩潰或者運行緩慢，再或者網路丟包，Leader 會不斷得重復嘗試附加日誌條目（盡管已經回復了客戶端）直到所有的 Follower 都最終存儲了所有的日誌條目，確保強一致性。

第一階段：客戶端請求提交到 Leader。

如下圖所示，Leader 收到客戶端的請求，比如存儲數據 5。Leader 在收到請求後，會將它作為日誌條目（Entry）寫入本地日誌中。需要注意的是，此時該 Entry 的狀態是未提交（Uncommitted），Leader 並不會更新本地數據，因此它是不可讀的。

第二階段：Leader 將 Entry 發送到其它 Follower

Leader 與 Followers 之間保持著心跳聯系，隨心跳 Leader 將追加的 Entry（AppendEntries）並行地發送給其它的 Follower，並讓它們復制這條日誌條目，這一過程稱為復制（Replicate）。

有幾點需要注意：

1. 為什麼 Leader 向 Follower 發送的 Entry 是 AppendEntries 呢？

因為 Leader 與 Follower 的心跳是周期性的，而一個周期間 Leader 可能接收到多條客戶端的請求，因此，隨心跳向 Followers 發送的大概率是多個 Entry，即 AppendEntries。當然，在本例中，我們假設只有一條請求，自然也就是一個Entry了。

2. Leader 向 Followers 發送的不僅僅是追加的 Entry（AppendEntries）。

在發送追加日誌條目的時候，Leader 會把新的日誌條目緊接著之前條目的索引位置（prevLogIndex）， Leader 任期號（Term）也包含在其中。如果 Follower 在它的日誌中找不到包含相同索引位置和任期號的條目，那麼它就會拒絕接收新的日誌條目，因為出現這種情況說明 Follower 和 Leader 不一致。

3. 如何解決 Leader 與 Follower 不一致的問題？

在正常情況下，Leader 和 Follower 的日誌保持一致，所以追加日誌的一致性檢查從來不會失敗。然而，Leader 和 Follower 一系列崩潰的情況會使它們的日誌處於不一致狀態。Follower可能會丟失一些在新的 Leader 中有的日誌條目，它也可能擁有一些 Leader 沒有的日誌條目，或者兩者都發生。丟失或者多出日誌條目可能會持續多個任期。

要使 Follower 的日誌與 Leader 恢復一致，Leader 必須找到最後兩者達成一致的地方（說白了就是回溯，找到兩者最近的一致點），然後刪除從那個點之後的所有日誌條目，發送自己的日誌給 Follower。所有的這些操作都在進行附加日誌的一致性檢查時完成。

Leader 為每一個 Follower 維護一個 nextIndex，它表示下一個需要發送給 Follower 的日誌條目的索引地址。當一個 Leader 剛獲得權力的時候，它初始化所有的 nextIndex 值，為自己的最後一條日誌的 index 加 1。如果一個 Follower 的日誌和 Leader 不一致，那麼在下一次附加日誌時一致性檢查就會失敗。在被 Follower 拒絕之後，Leader 就會減小該 Follower 對應的 nextIndex 值並進行重試。最終 nextIndex 會在某個位置使得 Leader 和 Follower 的日誌達成一致。當這種情況發生，附加日誌就會成功，這時就會把 Follower 沖突的日誌條目全部刪除並且加上 Leader 的日誌。一旦附加日誌成功，那麼 Follower 的日誌就會和 Leader 保持一致，並且在接下來的任期繼續保持一致。

第三階段：Leader 等待 Followers 回應。

Followers 接收到 Leader 發來的復制請求後，有兩種可能的回應：

寫入本地日誌中，返回 Success；

一致性檢查失敗，拒絕寫入，返回 False，原因和解決辦法上面已做了詳細說明。

需要注意的是，此時該 Entry 的狀態也是未提交（Uncommitted）。完成上述步驟後，Followers 會向 Leader 發出 Success 的回應，當 Leader 收到大多數 Followers 的回應後，會將第一階段寫入的 Entry 標記為提交狀態（Committed），並把這條日誌條目應用到它的狀態機中。

第四階段：Leader 回應客戶端。

完成前三個階段後，Leader會向客戶端回應 OK，表示寫操作成功。

第五階段，Leader 通知 Followers Entry 已提交

Leader 回應客戶端後，將隨著下一個心跳通知 Followers，Followers 收到通知後也會將 Entry 標記為提交狀態。至此，Raft 集群超過半數節點已經達到一致狀態，可以確保強一致性。

需要注意的是，由於網路、性能、故障等各種原因導致「反應慢」、「不一致」等問題的節點，最終也會與 Leader 達成一致。

前面描述了 Raft 演算法是如何選舉 Leader 和復制日誌的。然而，到目前為止描述的機制並不能充分地保證每一個狀態機會按照相同的順序執行相同的指令。例如，一個 Follower 可能處於不可用狀態，同時 Leader 已經提交了若乾的日誌條目；然後這個 Follower 恢復（尚未與 Leader 達成一致）而 Leader 故障；如果該 Follower 被選舉為 Leader 並且覆蓋這些日誌條目，就會出現問題，即不同的狀態機執行不同的指令序列。

鑒於此，在 Leader 選舉的時候需增加一些限制來完善 Raft 演算法。這些限制可保證任何的 Leader 對於給定的任期號（Term），都擁有之前任期的所有被提交的日誌條目（所謂 Leader 的完整特性）。關於這一選舉時的限制，下文將詳細說明。

在所有基於 Leader 機制的一致性演算法中，Leader 都必須存儲所有已經提交的日誌條目。為了保障這一點，Raft 使用了一種簡單而有效的方法，以保證所有之前的任期號中已經提交的日誌條目在選舉的時候都會出現在新的 Leader 中。換言之，日誌條目的傳送是單向的，只從 Leader 傳給 Follower，並且 Leader 從不會覆蓋自身本地日誌中已經存在的條目。

Raft 使用投票的方式來阻止一個 Candidate 贏得選舉，除非這個 Candidate 包含了所有已經提交的日誌條目。Candidate 為了贏得選舉必須聯系集群中的大部分節點。這意味著每一個已經提交的日誌條目肯定存在於至少一個伺服器節點上。如果 Candidate 的日誌至少和大多數的伺服器節點一樣新（這個新的定義會在下面討論），那麼它一定持有了所有已經提交的日誌條目（多數派的思想）。投票請求的限制中請求中包含了 Candidate 的日誌信息，然後投票人會拒絕那些日誌沒有自己新的投票請求。

Raft 通過比較兩份日誌中最後一條日誌條目的索引值和任期號，確定誰的日誌比較新。如果兩份日誌最後條目的任期號不同，那麼任期號大的日誌更加新。如果兩份日誌最後的條目任期號相同，那麼日誌比較長的那個就更加新。

如同 4.1 節介紹的那樣，Leader 知道一條當前任期內的日誌記錄是可以被提交的，只要它被復制到了大多數的 Follower 上（多數派的思想）。如果一個 Leader 在提交日誌條目之前崩潰了，繼任的 Leader 會繼續嘗試復制這條日誌記錄。然而，一個 Leader 並不能斷定被保存到大多數 Follower 上的一個之前任期里的日誌條目 就一定已經提交了。這很明顯，從日誌復制的過程可以看出。

鑒於上述情況，Raft 演算法不會通過計算副本數目的方式去提交一個之前任期內的日誌條目。只有 Leader 當前任期里的日誌條目通過計算副本數目可以被提交；一旦當前任期的日誌條目以這種方式被提交，那麼由於日誌匹配特性，之前的日誌條目也都會被間接的提交。在某些情況下，Leader 可以安全地知道一個老的日誌條目是否已經被提交（只需判斷該條目是否存儲到所有節點上），但是 Raft 為了簡化問題使用了一種更加保守的方法。

當 Leader 復制之前任期里的日誌時，Raft 會為所有日誌保留原始的任期號，這在提交規則上產生了額外的復雜性。但是，這種策略更加容易辨別出日誌，即使隨著時間和日誌的變化，日誌仍維護著同一個任期編號。此外，該策略使得新 Leader 只需要發送較少日誌條目。

raft 的讀寫都在 leader 節點中進行，它保證了讀的都是最新的值，它是符合強一致性的（線性一致性），raft 除了這個還在【客戶端交互】那塊也做了一些保證，詳情可以參考論文。但是 zookeeper 不同，zookeeper 寫在 leader，讀可以在 follower 進行，可能會讀到了舊值，它不符合強一致性（只考慮寫一致性，不考慮讀一致性），但是 zookeeper 去 follower 讀可以有效提升讀取的效率。

對比於 zab、raft，我們發現他們選舉、setData 都是需要過半機制才行，所以他們針對網路分區的處理方法都是一樣的。

一個集群的節點經過網路分區後，如一共有 A、B、C、D、E 5個節點，如果 A 是 leader，網路分區為 A、B、C 和 D、E，在A、B、C分區還是能正常提供服務的，而在 D、E 分區因為不能得到大多數成員確認（雖然分區了，但是因為配置的原因他們還是能知道所有的成員數量，比如 zk 集群啟動前需要配置所有成員地址，raft 也一樣），是不能進行選舉的，所以保證只會有一個 leader。

如果分區為 A、B 和 C、D、E ，A、B 分區雖然 A 還是 leader，但是卻不能提供事務服務（setData），C、D、E 分區能重新選出 leader，還是能正常向外提供服務。

1）我們所說的日誌（log）與狀態機（state machine）不是一回事，日誌指還沒有提交到狀態機中的數據。
2）新 leader 永遠不會通過計算副本數量提交舊日誌，他只能復制舊日誌都其他 follower 上，對於舊日誌的提交，只能是新 leader 接收新的寫請求寫新日誌，順帶著把舊日誌提交了。