[Golang]gomobile 讓你在iOS/Android上面使用Golang(更新:11/17)

前言

其實Go 1.5的正式公布後,最吸引人的就是與其他語言的相互合作.透過的可能是編譯成c-shared library.但是其實我個人最期待的,當然就是使用go mobile

最近他們把相關的範例跟工具都弄的差不多,並且有一了份相當詳細的教學在這裡

簡單流程:

由於教學寫得很清楚,我這裡簡單的把事情都跑過一次.注意:你需要有Go1.5


//抓取go mobile tool
go get golang.org/x/mobile/cmd/gomobile

//初始化gomobile,可能會花一點時間
gomobile init

//編譯gomobile裡面的範例
//這會在本地端直接編譯出 basic.app 只要透過xcode 複製到手機上即可(需要有開發者付費帳號)
gomobile build -target=ios golang.org/x/mobile/example/basic


//如果要把go package編譯成iOS可以用的framework
//這會在本地端編譯出一個hello.framework
cd $GOPATH/src/golang.org/x/mobile/example/bind
gomobile bind -target=ios golang.org/x/mobile/example/bind/hello

//直接在xcode拿來使用即可
open ios/bind.xcodeproj

來個iOS簡單範例 (11/17更新)

這裡提供一個簡單的範例,主要也是測試一下幾個主要的疑慮:

簡單的範例程式碼在這裡,這裡有直接的playgroud

package gomobile01

import (
	"fmt"
)

type Goomobile struct {
	Data string
}

//記得要有constructor 不然到時候你無法自行透過 NSObject init 來建立這個物件
func New() *Goomobile {
	return &Goomobile{Data: "Default test"}
}

func (g *Goomobile) GetData() string {
	fmt.Println("test go ")
	return g.Data
}

這時候建立這個iOS framework 指令是 (假設專案寫在kkdai/gomobile01)

$ gomobile bind -target=ios github.com/kkdai/gomobile01

然後會產生一個gomobile01.framework 把他拉進xcode專案. 以下提供如何使用的方式:


//載入該framework	
#import "gomobile01/Gomobile01.h"

這裡是使用的方式,切記要使用Constructor不要使用 [[xx alloc] init]

    GoGomobile01Goomobile *gb = GoGomobile01New();
    //Default data is @"Default test"
    [gb setData:@"Data...."];
    NSString * str = [gb GetData];
    //str = @"Data..."

已知可以支援的部分

  • 基礎的運算與簡單的資料格式當初參數 (int, string)
  • 支援structure跟method
  • 可以跑net/http但是記得別直接拿rpc.Client或是http.Client當作public

相關限制

目前試著編譯幾個有在使用的package發現有以下的問題,可能需要解決.

  • []slice, map, interface{} 比較進階的資料格式不支援 (可能也不能轉換到iOS)
    • 同理可證,一些package裡面的變數也不要放在parameter裡面.只支援基礎資料格式.
  • 即便是簡單的string, int不支援public global variable.
    • var TestVariable string 不被允許
    • 但是var testVariable string 是可以允許的
  • const目前還不支援 (gomobile: not yet supported, name for const)
  • structure need public: 如果要使用某些物件,要能夠在Objective C上面使用就必須要記得改成public (big-case)
    • 這會發生問題imported and not used: YOUR_PACKETGE
    • 一般而言,public寫法是正確的,但是把struct改成private其實也不是不可以.
  • 無法同時bind兩個package: 由於裡面的記憶體處理或是其他處理的問題.
    • 一般而言如果你跑了 gomobile bind target=ios A_PACKAGE 然後把a.framework拉近xcode在跑gomobile bind target=ios B_PACKAGE再把b.framework拉進專案,前面一個a.framework就會出現問題(不能跑). 詳細的解釋在這裡issue 12245.還沒有比較好的解法.
  • [11/17] 如果要在Structure 必須要建立相關的constructor (NewXXX()).

##參考文章

[iOS]使用iOS Xcode編譯static library一些筆記

image

####將所有m透過預設Object C++來編譯:

  • 設定->LLVM 7.0 -> Compile Source As -> Object-C++

這裏的設定比起單獨點選每個.m再來改成ObjectC++更有優先權.

設定額外的Include Path
  • 設定-> HEADER_SEARCH_PATHS (記得改HEADER_SEARCH_PATHS就好).
  • 記得要使用 $(PROJECT_DIR)/../../../include,而不是單純的 ../../../include不然會找不到.

避免發生 Undefined symbols for architecture x86_64

這是因為你嘗試要跑模擬器的編譯而你編譯出來的static library並沒有x86_64的選項.這邊的修改方式有幾個:

  • 增加x86_64 到”Build Setting”->”Artchitectures”跟”Valid Artchitectures”
  • 或是修改”Build Setting”->”Build Active Architecture Only”改成No

Bitcode enableing

Bitcode是xcode7新的功能.但是如果使用xcode新的專案都會遇到warning,關閉的方法就是在App去關閉,當然如果要使用這個功能,就得每個library都要打開bitcode.

[Coursera][Automata] 自動機理論-Automata筆記-第一週Finite Automata

image

前言

主要是因為有大師推薦,然後發現這堂課的教授就是所謂的Compiler恐龍課本的作者Jeffrey Ullman(Compiler Design的聖經). 加上自動機本身不僅僅實作牽扯到regular expression之外,更在分散式系統中的狀態機(state machine)扮有相當重要的部分. 所以需要來好好學習.

課程鏈結在這裡https://class.coursera.org/automata-004

相關文章

第一週課程

DFA(Deterministic Finite Automata)基本定義

  • alphabet:
    • 任何有限的符號集合. (可以是ASCII也可以是Unicode)
    • ex: {0,1} (binary alphabet), {a,b} {s,p} 都是alphabet
  • string:
    • 透過alphabet產生的list,其中每一個元素都要是該alphabet其中一個元素.
    • length代表的是該string有的個數.
      • ex alphabet {0, 1} 其 string {01} length=2
    • ε 代表是empty string其中他的length=0
  • language:
    • alphabedt產生出所有string的subset.
  • DFA: Deterministic Finite Automata: A formalism for defining languages.由以下組成:
    • 有限的狀態(states) 表示為 Q
    • 固定的input alphabet 表示為 Σ
    • 一個起始狀態 (start state) 表示為q0
    • 至少一個結束狀態 (final state) (這裏指的final state也是指可接受的狀態) 表示為 F
    • 一個transition function 表示為 δ(Q, A)其中 A 代表是一個輸入的 alphabet
      • transition function代表的是,一個輸入所要進入的一個狀態.
      • δ(Q, A) 代表是從狀態Q透過輸入A來計算下一個狀態會是哪裡.

範例:

{0, 1} 是一個alphabet

{0, 1}* = {ε, 0, 1, 00, 01, 10, 11, 010, …} 是alphabet {0,1}為可能出現的string組合,其中

  • {e} length=0
  • {0} length=1
  • {00} {01} {10} {11} length=2

如果要討論language,我們可以說 {ε, 0, 1,00,01,10,11} 是我們將要用到的language

image

(pic: from coursera automata course lecture)

以上的圖,代表一個簡單的DFA,其中:

  • 輸入alphabet為{0, 1}
  • final state為 B
  • dead state為 C (dead node: 也就是只走到C後不論怎麼輸入都無法到達final note)
  • start state為 A
  • transition function可以表示以下方式: A -> δ(B, 1) -> δ(C, 1)

根據以上的圖形,其實可以表示成另外一種表格方式(Transition Table):

image

(pic: from coursera automata course lecture)

左邊為所在的狀態節點,右邊為透過輸入0或是1將要到的狀態節點.

Transition Table 簡單範例

  • 在A狀態輸入0會回到A狀態,輸入1會到B狀態.
  • 狀態A輸入1, 1 會到狀態C。
Transitio Function 運算範例:
  • δ(B, 011) -> δ(δ(B, 01), 1) -> δ(δ(δ(B, 0), 1), 1) -> δ(δ(A, 1), 1) -> δ(B, 1) -> C
  • δ(A, 0) -> A

NFA(Nondeterministic Finite Automata)基本定義

NFA跟DFA有些許的不同,這裡先列出幾個幾本定義

  • NFA中,可以同時存在多個狀態中,也就是說δ(Q1, A)有可能出現不僅僅一個狀態Q2,而是δ(Q1, A)-> {Q2, Q3}.這代表這裡有路可以從Q1透過路線A可以到達Q2跟Q3
  • 跟DFA一樣,NFA一樣開始在一個start state
  • 跟DFA一樣,NFA一樣結束在一個以上的final state

image

(pic: from coursera automata course lecture)

    NFA 表現起來,比較像是棋盤式.每一個狀態(格子)同一個輸入有不僅僅一個可以走得下一步(狀態)

如何把NFA轉化成DFA

從基本定義可以看得出來,NFA跟DFA的差異最大的就是:

  • DFA: 每一次transition function會到唯一一個狀態,也就是: δ(Q1, A)-> Q2
  • NFA: 每一個transition function不一定只會指向一個狀態,所以: δ(Q1, A)-> {Q2, Q3, ...}

也就是說,我們可以說任何一個DFA也可以說是一個NFA,也就是說只要DFA收到同樣的語言(language)由於輸入會是一連串,也就是說輸出也會是不僅僅一個狀態.也可以說DFA透過同一個language input可以轉換成NFA.

    δD(Q1, A) -> P
    δN(Q1, A) -> {P} 可以視為 P 為 所有輸出集合的其中一個

那麼要如何反過來將NFA轉換成DFA呢?

先就定義上的轉換

其實某種角度來說,如果把NFA的結果當成一個language的話,其實就可以被視為是DFA. 也就是說:

    δD(Q1, A) -> P     //一般習慣的DFA表示方式
    δN(Q1, A) -> {P}   //一般習慣的NFA表示方式

如果把{p}當成是一種state而非是一群state,這樣就可以把NFA表示式看成是另外一種DFA。 只是那麼transition function與transition table要如何運算呢? 這時候就需要用到subset construction.

Subset construction

δD({q1, q2, q3, ... qk}, A) 為一個將NFA轉換成DFA的transition function,而結果就是將所有結果的聯集合(union) i = 1, 2, 3 … k是 δN(qi, A)

也就是

    δD({q1, q2, q3, ... qk}, A) = union(δN(qi, A))  其中 i = 1, 2, 3 ... k

Subset construction的範例

透過以下的方式,我們可以將NFA的transition table,轉換成DFA的.

image

以下將每個流程,用文字敘述:

  • 首先走到state {1} 這時候會透過 r 跟 b 走到 2,4 跟5 . 由於我們要取每個結果的聯集.所以 {2,4} {5} 會被當作是我們的一個State
  • 接下來先走到 {2,4}, 這時候要查看 {2} 與 {4}的結果,也就是 將 {4,6}{2,8}做聯集{2,4,6,8}為r的結果,而將{1,3,5}跟{1,5,7}做聯集{1,3,5,7}.
  • 並且將以上兩個結果當作新的state加入之後要走的路途
  • 接下來走 {1,3,5,7} 於是又繼續看 {1} {3} {5} {7}的結果.以此類推….

會得到以下結果

image

ε-NFA 的基本定義

對於NFA,其實是可以允許不需要任何輸入的情況下狀態(state)自己改變. 這時候我們可以說是輸入為ε (因為 ε為空字串,代表的是沒有輸入). 如此一來,所出現的NFA就稱為 ε-NFA.

image (pic: from coursera automata course lecture)

最後我們會導出一個定義是

    每一個NFA都是ε-NFA

Closure of States : CL(q)

這裏同時會有一個新的函式 CL(q) : 其中CL(q)代表的就是 q 狀態的closure 也就是說透過q 所有不需要input能夠到達的state.(換句話說,也就是透過q 能夠透過輸入 ε 來到達的狀態. 也就是說 CL(q) = δN(q, ε).

Example of Closure Starte

以上圖來說,這裡有一些Closure of States的範例:

  • CL(A) = {A} 因為沒有任何ε 的輸入可以到達的狀態.
  • CL(B) = {B, D} ,這裡δN(B, ε) -> D
  • CL(E) = {B, C, D, E}

更多在ε-NFA關於transition function 的運算

  • δ(q, w)在NFA中代表由狀態q開始透過輸入w,可以到達的狀態集合.
  • δ(q, ε) = CL(q) 也就是說由狀態q 在沒有輸入(也就是說輸入為空集合ε)可以到達的狀態.
  • δ(q, A) = δ(q, Aε) = δ(δ(q, A), ε) 所以可以推導出以下
  • δ(q, A) = δ(δ(q, A), ε)) = CL(δ(q, A)) = CL({E}) (假設δ(q, A)={E})

關於第一週作業

這次作業主要都是一些基本觀念跟圖形來推到transition function 的結果. 主要是多看幾次就會找出來其中的規律性.(似乎也沒有方法論可以快速找到).

相關程式

由於根據定義NFA與ε-NFA其實是無法去Implement的最後,我也把DFA的概念加以實現成一個小工具.放在https://github.com/kkdai/dfa

參考網址

[Docker] 再來玩玩Docker,在Windows上遇到的困難與筆記

image

##前言

其實Docker一直是我一個很想玩但是玩不起的技術.主要是因為我的MBA空間太小,隨便一個docker image 就有3~5G.小小128G MBA實在無法來順利成行. 最近有要跨平台跑東西的需求,決定弄幾個docker image可以幫助我處理一些令人討厭的設定.

這次主要是用到Windows桌機,裡面至少有足夠的硬碟空間可以讓我做這件事情.

Docker Windows 可能遇到的困難與筆記

####Docker Quickstart Terminal的console 顯示實在令人搖頭

Windows 上的Docker Quicktstart Terminal 使用MingW Console本來也是還好,但是在我電腦實在就有console顯示的問題. 建議使用ssh login來跑.

方法如下:

  • 跑”Docker Quickstart Terminal” 來將docker VM 跑起來
  • 你會看到 "default" machine with IP 192.168.99.100 (每個人IP不同)
  • 使用putty來登入SSH putty.exe -ssh [email protected]:2376 -pw tcuser 帳號跟密碼都是docker預設,沒有改過應該就可以正常跑.

把以上的指令弄成捷徑在桌面,就可以登入數個docker console

Docker Quickstart Terminal console 會遇到的 volume mount問題

Docker -v提供一個很好的方式可以讓本地端的檔案跟docker container去對應與操作.但是在Windows上面會遇到永遠找不到的路徑問題.(詳細可以參考這裡 還有這個)

    ##這樣在Windows boot2docker 跟 docker quickstart terminal 都會失敗
    docker run -v /c/Users/USER/TEST:/OUTPUT --rm=true DOCKER_IMAGE_NAME
    
    
    ##必須使用以下的指令  注意是"//c"  而非 "/c"
    docker run -v //c/Users/USER/TEST:/OUTPUT --rm=true DOCKER_IMAGE_NAME

這個問題在我剛剛提到使用SSH console是不會有這樣的問題的,所以我強烈建議各位使用docker SSH console.

建立Dockerfile

想要建立一個Docker Hub可以讓人家可以下載的Image或是 Dockerfile,其實不難.步驟以下:

  • 先建立一個github repository裡面只需要有Dockerfile (當然有README.md 更好 :) )
  • Docker Hub (記得要先註冊帳號) 的 Dashboard 選取 [Create] -> [Create Automated Build]
  • 輸入Github帳號去鏈結,選取剛剛建立的github repository
  • 他就會抓取Dockerfile自動跑

建立一些成果分享

Docker image for building OpenSSL for Android

其實會使用這些前提,如果你跟我一樣是:

  • 在Windows 上寫Android App
  • 極度討厭 Cygwin跟MinGW
  • 對於build module一向講求,build完就不需要那些環境

之前做法當然笨笨的使用VM建了一個超肥的VM裡面也裝了一堆不知道有什麼東西.來build一些需要的module. opencv ffmpeg都是如此.

這次我改成自己Dockerfile 參考這裡

[MBA]砍掉XCode的iPhone debug symbol 來節省MacBook Air的小SSD

##前言:

當初錯誤的決定,MBA 128GB 造就我很愛花時間找有沒有東西可以清, 分享一下我使用Mac Book Air 128G 尋找空間的心得.

查看每個程式佔多大空間

顯示隱藏資料夾

這邊需要console指令,方法為以下:

  • 開啟一個showHiddenFiles.sh vi showHiddenFiles.sh
  • 輸入以下指令:

      defaults write com.apple.finder AppleShowAllFiles TRUE
      killall Finder
    
  • 存擋,並且記得把權限打開chmod 660 showHiddenFiles.sh
  • 執行這個會把所有finder都關閉,但是可以之後可以顯示所有隱藏檔案 ( .git 也會出現)

恢復隱藏資料夾

反之,如果要把隱藏資料再次的隱藏起來,可以輸入以下的指令:

    defaults write com.apple.finder AppleShowAllFiles FALSE
    killall Finder

讓Finder裡面顯示資料夾空間

image

(圖片來自: http://www.iclarified.com/14356/how-to-display-folder-size-in-mac-os-x-finder)

主要的方式是到[Finder Menu]->[顯示方式: View]->[打開顯示方式選項: Show View Options]->[計算所有大小]

砍掉Xcode Debug Symbol

主要是參考這篇文章 提到的第四項可以清掉一些xcode debug symbol.每個OS版本也接近1G. 這樣清下去也有20~30G 空間 就算多砍也沒差,反正你手機接起來要debug又會把他都複製到電腦裡面了.

  • ~/Library/Developer/Xcode/iOS DeviceSupport/
  • 裡面會顯示許多版本的iPhone Debug Symbol (ex: 8.3 (12F70)… )
  • 移除掉比較舊的版本Debug Symbol

跟我一樣MBA SSD快爆的人來看看… 馬上又一條活龍…

[MOOCS][Golang]MIT6_824 Distributed Systems Week4- 關於Consensus協定 Raft 學習(一): 簡介,資料格式與領導者選舉

論文: Raft Paper

image

(這是Raft Consensus Algorithm 的展示工具Raft Scope)

MIT 6.824 分散式系統 系列文章

6.824: Distributed Systems

前言

持續學習MIT分散式系統課程的時候.學完了Paxos,接下來就要學習很多系統都有使用到的Raft系統. 這次一樣直接看Paper後,試著把整個邏輯實現出來.這裡先把演算法根據我瞭解的部分在記錄一下學習心得.

Raft介紹

這裏整理出一些關於Raft的介紹.

什麼是Raft Consensus

RaftPaxos一樣,都是為了讓多個log伺服器的備份機制所產生出來的溝通演算法.

不過,根據RaftPaper裡面提到的,為什麼會提出一個新的演算法.就是因為Paxos真的太難理解了(這裏引用的已經是簡化過的演算法,但是還是相當難理解).所以他們提出Raft演算法,並且針對兩個主要的目標:

  • 可理解性: 務必讓Raft的理論容易了解.
  • 容易實現: 必須讓整套系統是容易被實現並且是容易建置的.並且能達到所保證的效能.

Raft機制用在哪裡

如同前面說的,由於Paxos本身太過於困難了.所以Raft演算法在2014發布後迅速地成為許多分散式伺服器對於資料的同步協調最佳的應用. 以下列出幾個最近比較知名的伺服器架構:

  1. etcd: 相當知名的分散式key/value的資料庫
  2. cockroachdb被稱為是小強資料庫,不論有沒有連到Server都可以保證你可以使用.並且在連線後自動同步與協調相關資料.

這邊只挑出兩個最近比較紅的,其實還有相當的多. 基本上分散式資料庫近幾年都會採用Raft架構.

Raft主要關鍵:

在Raft系統裡面,主要分成三個關鍵的功能:

  • Leader Election (領導者選舉):
    • 這裏講的是關於領導者的選舉過程,還有其他角色(候選人, 跟隨者)如何轉換角色的過程.
  • Log Replication (資料複製):
    • 這裏提到對於log的相關記錄與處理方式,主要是要確保每一台伺服器的資料能夠精確同步而達到資料最少的遺失率.
  • Safty(安全性):
    • 透過Raft可以達到資料的準確性與資料可恢復性.

主要角色:

image

(圖片來自: Raft Paper,本圖主要講解三個角色關係切換示意圖)

再來要提到提到主要的角色:

  • Follower (追隨者): 基本上一開始每一台機器都被設定成為追隨者的角色.但是有一台收到來自狀態機的指令後,就會開始競選成領導者.
  • Leader (領導者): 主要接受來自於狀態機(在Raft中,狀態機就是我們的client,由狀態機發送每一個指令的log.透過Raft來達成多台同步的效果)
  • Candidate (候選人): 領導者不一定永遠都是完好的狀態等待狀態機的發送,某些狀況下如果領導者發生斷線或是系統出問題的時候.就會有一個跟隨者跳出來要競選成領導者. 相關的細項之後會提到.

關於資料結構(Log Structure) (ch. 5.3)

image

這裏先解釋一下,這一張圖主要表示的就是在多台Raft伺服器中,主要資料Log的儲存方式:

  • log index: 是一個流水號碼,代表你處理的的資料個數.
    • 產生的人:每個Server自己保留一份log index
  • term: 也就是在每個小方格上面的號碼,代表的是處理的第幾個指令集(複數個指令).
    • term的產生是由狀態機(state machine: 在這裏也可以說是client)產生出來的. 也就是說term是由 領導者收到後傳給每個跟隨者,而不是跟隨者自己產生的.
    • 這裏要注意的是一個指令集可能會有兩三個指令. 比如說 領導者的 Term 1: 就有 x <- 3, y <- 1, y <- 9. 但是他們代表的資料Index (Log Index各不相同)
  • operation: 也就是主要的log資料,代表的是Client傳過來的指令(單一個). 比如說是 x <- 3
    • 產生的人: 也是由狀態機(client)產生.

回過頭來解釋,這一張圖想要代表的意思:

  • 每個橫向代表著一台伺服器儲存資料的內容. 第一個為領導者,其餘都是跟隨者
  • 正常而言: 每一個伺服器的資料之間,如果term的數值是相同的,並且log index也相同就會認為兩個伺服器是相同的資料. 舉例而言, 領導者跟 跟隨者(2) (第三橫列)是相同的

關於資料的比對

兩個伺服器如何比較自己所擁有資料比較齊全呢?

這裏是先提到,基於這樣的資料結構,我們要怎麼說伺服器A所有的資料比伺服器B還要多,還要新呢? 以下這邊有一些原則:

  • LogIndexLogTerm組成伺服器本身的權重代表,擁有最多的LogIndex與最多的LogTerm就代表擁有教多的權重.
  • 比較上,會先比較LogTerm再去比較LogIndex

主要指令

Raft系統者要只有兩個RPC Call:

  • 一個是負責選舉領導者的RequestVote():
    • 主要是由候選人來發起.發送給所有的跟隨者來尋求大家的投票成為接下來的領導者
  • 另一個是負責傳遞資料的 AppendEntitries()
    • 主要是由領導者來發起,主要是管理Log Replicate的工作.
  • HeartBeat()負責領導者與`之間確認是否有存在的協定.
  • Request() 也就是由狀態機發送過來的資料,裡面存放著狀態機指令的log.

這邊只大概講解一下,這兩個RPC Call是做什麼的,之後每一個章節會透過這兩個指令將Raft整個系統兜出來.

領導者選舉 (Leader Election):

主要內容:

Raft 的領導者選舉,主要就是講解如何在跟隨者中讓某些人成為候選人並且順利的成為領導者的過程.由於一開始全部的伺服器都是跟隨者,有可能同時產生許多組候選人. 那麼如何要在這些候選人中挑選就是一件重要的事情.

啟動領導者選舉的時間點:

讓所有的Raft伺服器群組產生選舉的時間點,有以下幾個時機:

  • 一開始的時候,這時候每個跟隨者 權重(rank)都是相同的.只是看各個Server 何時送出訊息.
  • 領導者Hearbeat()指令間隔太久,這裡要提一下.根據論文,每個伺服器對於Heartbeat()的忍受時間間隔可以是不同的.這樣一來才不會造成一次有一堆跟隨者吵著要參加競選.

跟隨者 參加Leader Election 流程:

image

根據這張示意圖, 從跟隨者變成領導者的流程.我簡單地用條列式把該做的事情講一遍.

  • 根據剛剛提過的當跟隨者發現太久沒有收到Heartbeat()的時候,就會增加自己手上的term
  • 將自己角色由跟隨者轉換成候選人
  • 發送RequestVote()除了自己以外的跟隨者 (裡面會帶有候選人自身的termLastLogIndexLastLogTerm)
  • 等待每個跟隨者的回覆,如果同意的人超過大多數(就consensus algorithm裡面,”大多數”就剛好是 1/2m + 1其中m為總伺服器個數) 就將自己身份改成 領導者
  • 如果沒有成功,則等待這段的term時間過了,在來發送一次.

這樣的選舉機制會不會造成多人參選?無法選出領導者? 或是如何挑選出擁有最多commited log的候選人? 以下的部分會更詳細的解釋:

安全性 (Safety):

選舉(election)的限制 (5.4.1)

RequestVote 的限制與安全性

所有與具有領導者角色的溝通演算法中,領導者最重要的角色就是必須具有所以已經交付(committed)的紀錄(log). 所以如何讓選舉出來的領導者能具有越多已經交付的紀錄越好,就變得是重要的方式. 每個準備參與選舉的候選人必須要透過以下的方式來保證:

  • 每一個候選人必須透過RequestVote來顯示目前自己擁有最新(update-to-date)的紀錄.
    • 這邊使用的是RequestVote()裡面的lastLogIndexlastLogTerm來傳遞溝通.
    • 資料的比對上主要以lastLogTerm為主要比對項目.如果相同的時候,就會比對資料的總個數lastLogIndex
  • 跟隨者在回覆投票結果的時候,除了要回覆’贊成’或是’否決’外,還必須要回覆自己最新交付的紀錄(如果否決的話).

當候選人收到其他伺服器的要求

這裏有幾個例外可能性:

  • 如果候選人在發送RequestVote()的時候,忽然收到其他成為領導者的人送來的AppendEntitries()
    • 如果候選人收到的termlogIndex比自己高,這時候候選人就會轉回跟隨者的身份.
    • 反之,則候選人會繼續自己的選舉流程.
    • 最後有一種可能是都沒有候選人能夠獲得大多數的同意,所以等到time out之後就必須要重選.
  • 此外,如果候選人收到其他候選人的需求.這個時會有以下的狀態:
    • 兩個候選人會相互的比較權重(rank),這裡的權重就是前面有介紹過的LogIndexLogTerm的比較.透過這兩個數字可以比較出來哪位候選人比較有多一點的資料,也就是說獲得比較高的權重.
    • 比較低權重的候選人會轉換身份回跟隨者,而高權重的候選人會得到回應正確的投票(RequestVote()).

解決分散投票的問題

  • 每個跟隨者的time out都不相同,事實上每一個伺服器在起來的時候都會隨機從一個範圍中挑選自己的time out時間(舉例 150~300 ms).
  • 這個機制幫助我們在選舉機制裡面,大多數的狀況下只會有一個跟隨者先跳出來變成候選人並且順利地贏得選舉.

接下來:

接下來,我打算開始整理關於Log Replica部分的心得. 也順便會把一些pseudo code擺上來.

全部文章列表:

相關鏈結