松花皮蛋的黑板報
  • 分享在京東工作的技術感悟,還有JAVA技術和業內最佳實踐,大部分都是務實的、能看懂的、可復現的

掃一掃
關注公眾號

ARTS-4-分布式系統之Raft共識算法

博客首頁文章列表 松花皮蛋me 2019-04-07 17:20

ARTS的初衷

Algorithm: 主要是為了編程訓練和學習。

Review:主要是為了學習英文

Tip:主要是為了總結和歸納在是常工作中所遇到的知識點。學習至少一個技術技巧。在工作中遇到的問題,踩過的坑,學習的點滴知識。

Share:主要是為了建立影響力,能夠輸出價值觀。分享一篇有觀點和思考的技術文章

https://www.zhihu.com/question/301150832

一、Algorithm

Generate Parentheses

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

[
“((()))”,
“(()())”,
“(())()”,
“()(())”,
“()()()”
]

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList();
        help(res,"",0,0,n);
        return res;
    }

    public void help(List<String> res,String str,int leftN,int rightN,int n)
    {
        if(rightN==n) {
            res.add(str);
            return;
        }
        if(leftN==n){
            help(res,str+")",leftN,++rightN,n);
            return;
        }
        if(leftN>rightN) {
            int l =  leftN;
            int r = rightN;
            help(res,str+")",leftN,++rightN,n);
            help(res,str+"(",++l,r,n);
        } else {
            help(res,str+"(",++leftN,rightN,n);
        }
    }
}

二、Review

分布式系統除了提升整個體統的性能外還有一個重要特征就是提高系統的可靠性。提供可靠性可以理解為系統中一臺或多臺的機器故障不會使系統不可用或者丟失數據。保證系統可靠性的關鍵就是多副本,一旦有多副本,那么就面臨多副本之間的一致性問題一致性算法正是用于解決分布式環境下多副本之間數據一致性的問題的。業界最著名的一致性算法就是大名鼎鼎的Paxos,但Paxos是出了名的難懂,而Raft正是為了探索一種更易于理解的一致性算法而產生的,它將一致性拆分為leader選舉、日志復制、安全性三個關鍵元素

1、leader選舉
        Raft算法將時間劃分成為任意不同長度的任期(term),任期用連續的數字表示,每一個任期的開始都是一次選舉。如果一個侯選人贏得了選舉,它就會在該任期的余下時間擔任領導人,如果沒有選出領導人,將會開始另一個任期,并且立刻開始下一次選舉

       那么什么時候開始選舉呢?實際上leader會向所有follower周期性發送心跳,來保證它們的leader地位,如果一個follower在一個周期內沒有收到heartbeat信息,那么它就會假定沒有可用的leader,自已就轉換狀態成為候選人,并且開始一次選舉來選出一個新的leader             

 Raft選舉過程有三個規則
     (1)、規則:如果請求投票的服務器任期比自己的任期大,則給該服務器投票

    (2)、規則:在一個任期內,一臺服務器最多能給一個侯選人投票,按照先到先得的原則

  (3)、規則:隨機選舉超時     

為了避免選票被平分,沒有服務器成為leader,每臺服務器在一個固定的范圍內隨機選取,從而使每臺服務器的選舉超時時間均不相同,這種機制使得在大多數情況下只有一個服務器會率先超時,它會在其他服務器超時之前贏得選舉并且向其它服務器發送heartbeat信息

當候選人收到大多數節點的選票則轉換為leader;發現leader或者收到更高任期的請求則轉換為follower,在角色轉換的時候遵守選舉安全原則,一個任期(term)內最多允許有一個leader被選上

2、日記復制   

  要理解為日記復制得先搞明白日記匹配原則和可被提交的日記這兩個概念
日記匹配原則描述的是,如果在不同日記中的兩個條目有著相同的索引和任期號,則它們存儲的命令是相同的。如果在不同日記中的兩個條目有著相同的索引和任期號,則它們之間的所有條目都是完全相同的
可被提交的日記描述的是,一旦被leader創建的條目已經復制到了大多數服務器上,這個日記就稱為可被提交的。leader日記中之前的條目都是可被提交的,包括由之前的leader創建的條目

在日記復制流程中,leader需要找到follower同它的日記一致的地方,然后刪除follower在該位置之后的條目,然后將自己在該位置之后的條目發送給follower

完整流程是,client向leader發出請求,leader將日記條目加入到它的日志中,并行向follower服務器發起日記復制請求,leader確認日記條目被安全復制后,將該條目應用到狀態機,然后向client返回結果,向follower發出可以提交該日記條目的請求。當一個服務器已經將給它索引位置的日記條目應用到狀態機中,則所有其他服務器不會在該索引位置應用不同的條目

在日記復制中,可能會出現各種各樣的異常
(1)、異常:數據發送到leader,但未復制到follower

leader異常,client接收不到ack,重新選舉后,client可重新向leader發出請求
(2)、異常:數據到達leader節點,成功復制到follower所有節點,但未向leader響應接收

重新選舉后,雖然數據在follower節點處于未提交狀態但保持一致,重新選舉出leader后可完成數據提交,由于原leader異常,client無法接收到ack,會重新向leader發出請求,Raft要求RPC冪等,所以服務器要實現去重機制
(3)、異常:數據到達leader節點,成功復制到follower所有或多數節點,數據在leader處于已提交狀態,但在follower處于未提交狀態

這個階段leader掛掉,重新選出新leader
(4)、異常:由于網絡”分區”導致出現雙leader
  以5個服務器節點為例,正常情況下A節點為leader,接收client的請求,并將日記同步到B、C、D、E四個follower節點。由于網絡原因,A、B節點無法與C、D、E進行通信,C、D、E重新選舉,選擇leader,假話E節點勝出,此時出現雙leader。隨后網絡恢復,A、B將做為E的follower

3、安全性
Raft通過比較日記中最后一個條目的索引和任期號來決定兩個日記哪一個更新,如果兩個日記的任期號不同,任期號大的更新,如果任期號相同,更長的日記更新
Raft為了保證安全性,約定了一些選舉限制,RequestVote RPC中包含候選人的日記信息,如果服務器自己的日記比候選人還要新,則會拒絕為該候選人投票

這個行為背后是leader完全原則,如果一個日記條目在一個給定任期內被提交,那么這個條目一定會出現在所有任期號更大的leader中。所有的日志條目都只會從leader節點往follower節點寫入,且leader節點上的日志只會增加,絕對不會刪除或者覆蓋

參考
1 、https://ramcloud.atlassian.net/wiki/download/attachments/6586375/raft.pdf (Raft一致性算法論文原文)
2、http://www.infoq.com/cn/articles/raft-paper(Raft一致性算法論文譯文)
3、http://thesecretlivesofdata.com/raft/ (Raft一致性算法演示動畫)
4、https://raft.github.io/ (Raft一致性算法官網)
5、相關BLOG
http://blog.csdn.net/cszhouwei/article/details/38374603
http://www.cnblogs.com/mindwind/p/5231986.html

三、Tips

Log4j2中的MDC,它允許你可以在日記上下文中定義字段和賦值,從而可以達到調用鏈監控的漿果,看代碼

首先定義請求上下文

/**
 * @program: workflow
 * @description: 請求上下文
 * @author: Pidan
 **/
@Data
@Builder
@AllArgsConstructor
@NoArgsConstructor
public class MdcReqContext {

/**
* @Description: 請求ID
* @Param:
* @return:
* @Author: Pidan
*/
private String requestId;

/**
 * @Description: 業務標識
 * @Param:
 * @return:
 * @Author: Pidan
 */
private String requestBusiness;


/**
* @Description: 參數
* @Param:
* @return:
* @Author: Pidan
*/
private String requestParams;

}

然后定義MDC容器

/**
 * @program: workflow
 * @description: MDC
 * @author: Pidan
 **/
public class MDC {


    public static void put(MdcReqContext mdcReqContext) {

        ReflectionUtils.doWithLocalFields(mdcReqContext.getClass(), new ReflectionUtils.FieldCallback() {
            @Override
            public void doWith(Field field) throws IllegalArgumentException, IllegalAccessException {
                field.setAccessible(true);
                ThreadContext.put(field.getName(), String.valueOf(field.get(mdcReqContext)));
            }
        });
    }

    public static void clear()
    {
        ThreadContext.clearAll();;
    }

}   

在Filter中進行綁定

/**
 * @program: workflow
 * @description: MDC-Filter
 * @author: Pidan
 **/

public class MdcFilter implements Filter {

/**
* @Description: 敏感參數不記錄在日記
* @Param: [filterConfig]
* @return: void
* @Author: Pidan
*/
private final List<String> transientParams = Arrays.asList("ticket","X-timingsoa-token");



@Override
public void init(FilterConfig filterConfig) throws ServletException {
}

@Override
public void doFilter(ServletRequest servletRequest, ServletResponse servletResponse, FilterChain filterChain) throws IOException, ServletException {
    HttpServletRequest httpServletRequest = (HttpServletRequest) servletRequest;
    String business = httpServletRequest.getRequestURI();
    MdcReqContext mdcReqContext = MdcReqContext.builder().requestId(Sequence.genRequestId()).
            requestBusiness(business).requestParams(getQueryString(httpServletRequest)).build();
    try {
        MDC.put(mdcReqContext);
        filterChain.doFilter(servletRequest,servletResponse);
    }  finally {
        MDC.clear();
    }
}

@Override
public void destroy() {

}


public String getQueryString(HttpServletRequest httpServletRequest)
{
    Map<String, String[]> parameterMap = httpServletRequest.getParameterMap();
    StringBuilder stringBuilder = new StringBuilder();
    for (Map.Entry<String,String[]> entry:parameterMap.entrySet()) {
        String s = entry.getKey();
        if(transientParams.contains(s)) continue;
        List<String> list = Arrays.asList(httpServletRequest.getParameterValues(s));
        stringBuilder.append(s).append("=").append(CollectionUtils.lastElement(list)).append("&amp;");
    }
    return stringBuilder.toString();
}}    

最后在log配置文件中設置LOG_PATTERN即可

    <Property name="LOG_PATTERN">
 %d{yyyy-MM-dd HH:mm:ss.SSS} %5p --- [%15.15t] %-40.40c{1.} : %m%n%ex 接上 reqId:%X{requestId} business:%X{requestBusiness} params:%X{requestParams}
        </Property>

另外其實log4j2獲取類名和行號等等是通過拋出異常獲取堆棧取得的

new LocationInfo(new Throwable(),log.getName());    

不過實現過程中會遇到的兩個問題:線程池中的線程會打印錯誤的traceId;調用依賴服務后會生成新的traceId,無法繼續跟蹤。我們可以封裝線程池,重寫submit方法將context透傳下去,從而解決多線程使用問題;可以實現restTemplate.setInterceptor方法將traceId通過請求頭透傳,從而解決上下游使用問題

四、Share

碼出高效JAVA代碼

黑龙江6+1开奖结果查询