Raft Leader Election

Distributed Datastorage’lerde Leader Election

Distributed storage’larda bir process’in shared resource’lara erişmek ya da diğer processlere görev verebilmek gibi farklı yetkilere sahip olması gerekir. Bu yetkileri bir process’e vermek için processler arasında liderlik oylaması yani leader election yapılır. Leader election algoritması bir zaman aralığında bir clusterda yalnızca bir lider oldugunu garanti eder. Farklı leader election algoritmaları mevcut olmakla birlikte bu yazıda raft leader election algoritmasından bahsedeceğim.

Raft Leader Election

Raft leader election algoritması üç state’ten oluşan bir state machine olarak implemente edilir.

• Follower state; başka bir processi lider olarak kabul eden processtir.
• Candidate state; kendini lider olarak önererek yeni electionu başlatan processtir.
• Leader state; lider olan processtir.

Leader election algoritması bir veya daha fazla processin kendini lider olarak önermesi ve electionun başlamasıyla başlar. Algoritma tek bir lider oldugunu garanti eder. Peki lider election süreci tam olarak nasıl başlar. Bir sistem çalışama başladığında tüm processsler follower stateinde başlar. Bir follower belirli aralıklarla lider processten heartbeat sinyali bekler. Bu sinyalin içerisinde liderin seçildiği election termi de yer alır. Eğerki follower belirli bir zaman periyodunda bu hearteati alamazsa time out fırlatır ve lider processi yok kabul eder. Bu noktada follower election termi arttırarak yeni election başlatır ve kendisi canditate state’e geçer sonra da ilk oyu kendisine verir ve sistemdeki diğer processlere kendisine oy vermesi için request yollar.

Bu process üç durumdan biri yaşanana kadar candidate state’te kalmaya devam eder. Ya electionu kazanır. Ya başka bir process electionu kazanır ya da kazanan olmadan election sonlanır.

Canditate state’in electionu kazanması durumu

Eğer processlerin çoğu ilgili candidate process için oy kullanırsa ilgili candidate process leader state’ine geçer. Her process yalnızca bir process için oy kullanabilir bu da ‘first come first served’ şeklinde ilerler. Candidate process leader state’ine geçtiğinde diğer processlere heartbeat sinyalini yollamaya başlar.

Bir başka process’in electionu kazanması durumu

Eğer candidate process, lider olduğunu iddia eden ve leader termi kendisinden büyük ya da eşit bir processten heartbeat sinyali almaya başlarsa, bu processi lider olarak kabul eder ve kendisi tekrar follower state’e geçer. Eğer bu olmazsa, canditate state’te kalmaya devam eder. Bu durum için örnek case, candidate processin bir sebepten durması ve bu sürede başka bir processin electionu başlatıp kazanması olabilir.

Hiç bir kazananın olmaması

Düşük ihtimal olmakla birlikte birden fazla follower simultane bir şekilde candidate olabilir ve hiç biri yeterli çoğunluğu sağlayamayabilir. Bu da split vote yani oy bölünmesi olarak adlandırılır. Bu durumda candidateler time out alır ve yeni election başlar.

Genel olarak kariyerimiz boyunca sıfırdan bir lider election algoritması implemente etme ihtimalimiz düşüktür. Ancak sistemin altında neler olduğunu bilmek faydalıdır.

Sistemde bir lider’e sahip olmak concurreny’i engellediği için sistemi basitleştirse de eğer lider üzerinde uygulanan operasyon sayısı çok fazla artarsa scalibility bottlenecklerine sebep olabilir. Bunun yanında leader single point of failure’a da sebep olabilir. Eğer election processi devam edemezse ya da leader beklendiği gibi çalışmazsa, tüm sistemi down olabilir. Bu gibi downları ve single point of failureları partition yöntemiyle tölere ederek hafifletip her bir partition başına bir leader atayabiliriz. Ancak, bu da sisteme ek bir complexity getirecektir. Yine de bu çoğu distributed data storage’ın  datası single node’a sığmadığı zaman kullandığı bir çözümdür.

Genel kural olarak, eğer bir leader processe sahipsek, leaderin yaptığı işi azaltmalıyız. Bunun dışında, bir diğer varsayımımızda, bu gibi data storeların fault tolerance olduğu ve node kaybına karşı toleranslı olduğudur. Aksi takdirde, tüm data single node’da çalışırsa ve node fail olursa sıkıntı daha büyük olacaktır.