KV database based on raft consensus protocol

be based on Raft Consensus agreement KV database

Project introduction

Distributed consistency is the basis of building fault-tolerant systems , It enables some machines to work in clusters , And allow some of these nodes to fail .Raft It is a common distributed consensus protocol ,Raft First, elect a server As Leader, Then give it full responsibility for managing logs .Leader Receive log entries from the client , Copy to other server, And tell them when they can safely apply log entries to their state machine . To have a Leader Can be simplified replicated log Management of . for example ,leader You can decide where to put new log entries , Without asking other nodes , Data is always simple from leader Flow to other nodes .Leader May fail or disconnect , In this case, a new one will be selected leader. Specific algorithm details can refer to the paper 《In search of an Understandable Consensus Algorithm》.

This project is based on Raft Distributed consensus protocol , Implement a simple KV database . This database supports 3 Operations , namely GET、PUT、APPEND.GET Operation can get a Key Corresponding Value.PUT Operation can make a Key Corresponding Value write in .APPEND The operation can set Value Append a written Key Corresponding Value On .

System architecture

every last server There is a log that stores a series of instructions ,state machine Will execute these instructions in sequence . Each log holds the same instructions in the same order , So every one state machine Process the same instructions ,state machine It's the same , Therefore, it will eventually reach the same state and output .

Guarantee replicated log Consistency is the task of consistency algorithm .server The consistency module in receives the instructions from the client and adds them to its own log , It can also be compared with other server The consistency module in the communication to ensure that every log Can have the same content and order , Even if some of them server Downtime . Once the instruction is copied correctly , It can be called committed. every last server The state machine in is processed in log order committed Instructions , And return the output to the client .

Source code analysis

Client code ：

With GET Operation as an example . Because in a cluster , Only to be Leader Our server can handle user requests , So the client will cache when sending requests to the server Leader Information about . If the error returned is NotLeader, Will try again , Send the request to other servers .

Server code ：

The same to GET Operation as an example , The server is receiving Get When asked , Will check whether you are Leader, If so, register a callback function . In another cycle , The server will listen successfully Commit Of Raft journal , And back to GET The result to the client .

Raft Module code ：

Raft Modules are the most complex place , It implements the description in the reference paper ：

stay Raft layer , There are three RPC call , namely sendRequestVote, sendAppendEntries, sendInstallSnapshot. among sendRequestVote For election Leader,sendAppendEntries Used to synchronize Raft Log and send heartbeat sendInstallSnapshot For fast recovery .

Test part

In order to verify Raft The correctness of the implementation of distributed consensus algorithm has enabled the server to correctly handle requests from clients , There are a lot of test cases in the project . These tests simulate various server outages , Network isolation . The KV The database can all pass these tests .
The test will simulate various server downtime , Network isolation . The KV The database can all pass these tests .