raft

package module
v0.0.0-...-90e4854 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Sep 10, 2020 License: MIT Imports: 20 Imported by: 0

README

raft

根据 MIT 6.824 学习，实现raft

raft的应用

一致性kv

简单实现一致性kv数据库

相关资料

Raft论文中文翻译

raft 论文中文翻译

Raft图像演示

看下这个Raft的可视化介绍，先直观的了解一下。

Raft视频

哔哩哔哩2020 MIT 6.824 分布式系统，翻译。

Raft论文

广为流传的Raft精简版论文。这篇论文主要介绍了Raft的工作原理，简单提及但没有详细介绍Cluster Membership changes和Log Compaction高级主题。

Raft算法作者ongardie的博士论文

Raft作者的博士论文，250多页，精髓在前70页，包含了精简版论文的内容，同时又详细介绍了Cluster Membership changes和Log Compaction高级主题。从70页开始，主要跟Raft实践有关：Raft的易学习性、选举超时时间评估、性能等。

Raft官网

Raft官网，汇总了一些资料，大部分都是一些其他人介绍Raft的talk，内容重复又不系统，没有太多借鉴的意义，网站下面介绍了Raft的各种实现。两个可视化工具比较有用，工具一，介绍了Raft大概工具原理，比较简单，主要了解概念。工具二，也就是Raft官网的Raft Visualization部分，模拟5个节点Raft集群的情况。可以手动操作让节点宕机、复制数据，让请求超时、丢失等，这里对于了解Raft的选举、复制机制比较有用。

Fault-Tolerant Virtual Machines

与Raft没有太大的关系，可以加深了解复制状态机模型(RSM,Replicated State Machine)模型。Raft是基于应用层的RSM，这篇文介绍了VM层面的RSM实现，通过机器指令级别的复制，一个虚拟机的状态被完整地复制到另外一台虚拟机上。最终，两台虚拟机执行一样的指令，每条指令又产生相同的结果，即使是随机函数。

MIT6.824课程

MIT的分布式课程，比较经典。读论文+实践的方式授课。先介绍了MapReduce，然后实现Raft，接着在Raft基础上实现一个分布式KV系统，实现是用go。这个课程助教写了一篇文章对于Raft实现常见的坑做了一个整理：Students' Guide to Raft 。

Tidb的博客

Tidb是基于Raft实现，看过几篇博客，有工程上的借鉴意义，但还没有仔细研究。

Raft Refloated: Do We Have Consensus?

Raft的一种实现，论文分析了Raft，并做了一点工程上的优化，借鉴意义不是很大。

Zookeeper

提出ZK的论文，ZK作为类似成功应用的案例，值得借鉴。

Documentation

Index

Constants

View Source 
const NULL string = "null"

Variables

View Source 
var (
	ErrNotLeader = fmt.Errorf("raft is not leader")
)

Functions

func RegisterCommand 

func RegisterCommand(command Command)

注册命令类型

Types

type AppendEntriesReq 

type AppendEntriesReq struct {
	Term                 uint64      `protobuf:"varint,1,opt,name=Term,proto3" json:"Term,omitempty"`
	LeaderName           string      `protobuf:"bytes,2,opt,name=LeaderName,proto3" json:"LeaderName,omitempty"`
	PrevLogIndex         uint64      `protobuf:"varint,3,opt,name=PrevLogIndex,proto3" json:"PrevLogIndex,omitempty"`
	PrevLogTerm          uint64      `protobuf:"varint,4,opt,name=PrevLogTerm,proto3" json:"PrevLogTerm,omitempty"`
	LeaderCommit         uint64      `protobuf:"varint,5,opt,name=LeaderCommit,proto3" json:"LeaderCommit,omitempty"`
	Entries              []*LogEntry `protobuf:"bytes,6,rep,name=Entries,proto3" json:"Entries,omitempty"`
	XXX_NoUnkeyedLiteral struct{}    `json:"-"`
	XXX_unrecognized     []byte      `json:"-"`
	XXX_sizecache        int32       `json:"-"`
}

func (*AppendEntriesReq) Descriptor 

func (*AppendEntriesReq) Descriptor() ([]byte, []int)

func (*AppendEntriesReq) GetEntries 

func (m *AppendEntriesReq) GetEntries() []*LogEntry

func (*AppendEntriesReq) GetLeaderCommit 

func (m *AppendEntriesReq) GetLeaderCommit() uint64

func (*AppendEntriesReq) GetLeaderName 

func (m *AppendEntriesReq) GetLeaderName() string

func (*AppendEntriesReq) GetPrevLogIndex 

func (m *AppendEntriesReq) GetPrevLogIndex() uint64

func (*AppendEntriesReq) GetPrevLogTerm 

func (m *AppendEntriesReq) GetPrevLogTerm() uint64

func (*AppendEntriesReq) GetTerm 

func (m *AppendEntriesReq) GetTerm() uint64

func (*AppendEntriesReq) ProtoMessage 

func (*AppendEntriesReq) ProtoMessage()

func (*AppendEntriesReq) Reset 

func (m *AppendEntriesReq) Reset()

func (*AppendEntriesReq) String 

func (m *AppendEntriesReq) String() string

func (*AppendEntriesReq) XXX_DiscardUnknown 

func (m *AppendEntriesReq) XXX_DiscardUnknown()

func (*AppendEntriesReq) XXX_Marshal 

func (m *AppendEntriesReq) XXX_Marshal(b []byte, deterministic bool) ([]byte, error)

func (*AppendEntriesReq) XXX_Merge 

func (m *AppendEntriesReq) XXX_Merge(src proto.Message)

func (*AppendEntriesReq) XXX_Size 

func (m *AppendEntriesReq) XXX_Size() int

func (*AppendEntriesReq) XXX_Unmarshal 

func (m *AppendEntriesReq) XXX_Unmarshal(b []byte) error

type AppendEntriesResp 

type AppendEntriesResp struct {
	Term                 uint64   `protobuf:"varint,1,opt,name=Term,proto3" json:"Term,omitempty"`
	Success              bool     `protobuf:"varint,2,opt,name=Success,proto3" json:"Success,omitempty"`
	ConflictTerm         int64    `protobuf:"varint,3,opt,name=ConflictTerm,proto3" json:"ConflictTerm,omitempty"`
	ConflictIndex        int64    `protobuf:"varint,4,opt,name=ConflictIndex,proto3" json:"ConflictIndex,omitempty"`
	XXX_NoUnkeyedLiteral struct{} `json:"-"`
	XXX_unrecognized     []byte   `json:"-"`
	XXX_sizecache        int32    `json:"-"`
}

func (*AppendEntriesResp) Descriptor 

func (*AppendEntriesResp) Descriptor() ([]byte, []int)

func (*AppendEntriesResp) GetConflictIndex 

func (m *AppendEntriesResp) GetConflictIndex() int64

func (*AppendEntriesResp) GetConflictTerm 

func (m *AppendEntriesResp) GetConflictTerm() int64

func (*AppendEntriesResp) GetSuccess 

func (m *AppendEntriesResp) GetSuccess() bool

func (*AppendEntriesResp) GetTerm 

func (m *AppendEntriesResp) GetTerm() uint64

func (*AppendEntriesResp) ProtoMessage 

func (*AppendEntriesResp) ProtoMessage()

func (*AppendEntriesResp) Reset 

func (m *AppendEntriesResp) Reset()

func (*AppendEntriesResp) String 

func (m *AppendEntriesResp) String() string

func (*AppendEntriesResp) XXX_DiscardUnknown 

func (m *AppendEntriesResp) XXX_DiscardUnknown()

func (*AppendEntriesResp) XXX_Marshal 

func (m *AppendEntriesResp) XXX_Marshal(b []byte, deterministic bool) ([]byte, error)

func (*AppendEntriesResp) XXX_Merge 

func (m *AppendEntriesResp) XXX_Merge(src proto.Message)

func (*AppendEntriesResp) XXX_Size 

func (m *AppendEntriesResp) XXX_Size() int

func (*AppendEntriesResp) XXX_Unmarshal 

func (m *AppendEntriesResp) XXX_Unmarshal(b []byte) error

type ApplyMsg 

type ApplyMsg struct {
	CommandValid bool // true为log，false为snapshot

	// 向应用层提交日志
	Command      Command
	CommandIndex uint64
	CommandTerm  uint64

	// 向应用层安装快照
	Snapshot []byte
}

type ClientEnd 

type ClientEnd struct {
	sync.Mutex
	// contains filtered or unexported fields
}

type Command 

type Command interface {
	CommandName() string
}

type CommandEncoder 

type CommandEncoder interface {
	Encode(w io.Writer) error
	Decode(r io.Reader) error
}

type InstallSnapshotReq 

type InstallSnapshotReq struct {
	Term                 uint64   `protobuf:"varint,1,opt,name=Term,proto3" json:"Term,omitempty"`
	LeaderName           string   `protobuf:"bytes,2,opt,name=LeaderName,proto3" json:"LeaderName,omitempty"`
	LastIncludedIndex    uint64   `protobuf:"varint,3,opt,name=LastIncludedIndex,proto3" json:"LastIncludedIndex,omitempty"`
	LastIncludedTerm     uint64   `protobuf:"varint,4,opt,name=LastIncludedTerm,proto3" json:"LastIncludedTerm,omitempty"`
	Offset               uint64   `protobuf:"varint,5,opt,name=Offset,proto3" json:"Offset,omitempty"`
	Data                 []byte   `protobuf:"bytes,6,opt,name=Data,proto3" json:"Data,omitempty"`
	Done                 bool     `protobuf:"varint,7,opt,name=Done,proto3" json:"Done,omitempty"`
	XXX_NoUnkeyedLiteral struct{} `json:"-"`
	XXX_unrecognized     []byte   `json:"-"`
	XXX_sizecache        int32    `json:"-"`
}

func (*InstallSnapshotReq) Descriptor 

func (*InstallSnapshotReq) Descriptor() ([]byte, []int)

func (*InstallSnapshotReq) GetData 

func (m *InstallSnapshotReq) GetData() []byte

func (*InstallSnapshotReq) GetDone 

func (m *InstallSnapshotReq) GetDone() bool

func (*InstallSnapshotReq) GetLastIncludedIndex 

func (m *InstallSnapshotReq) GetLastIncludedIndex() uint64

func (*InstallSnapshotReq) GetLastIncludedTerm 

func (m *InstallSnapshotReq) GetLastIncludedTerm() uint64

func (*InstallSnapshotReq) GetLeaderName 

func (m *InstallSnapshotReq) GetLeaderName() string

func (*InstallSnapshotReq) GetOffset 

func (m *InstallSnapshotReq) GetOffset() uint64

func (*InstallSnapshotReq) GetTerm 

func (m *InstallSnapshotReq) GetTerm() uint64

func (*InstallSnapshotReq) ProtoMessage 

func (*InstallSnapshotReq) ProtoMessage()

func (*InstallSnapshotReq) Reset 

func (m *InstallSnapshotReq) Reset()

func (*InstallSnapshotReq) String 

func (m *InstallSnapshotReq) String() string

func (*InstallSnapshotReq) XXX_DiscardUnknown 

func (m *InstallSnapshotReq) XXX_DiscardUnknown()

func (*InstallSnapshotReq) XXX_Marshal 

func (m *InstallSnapshotReq) XXX_Marshal(b []byte, deterministic bool) ([]byte, error)

func (*InstallSnapshotReq) XXX_Merge 

func (m *InstallSnapshotReq) XXX_Merge(src proto.Message)

func (*InstallSnapshotReq) XXX_Size 

func (m *InstallSnapshotReq) XXX_Size() int

func (*InstallSnapshotReq) XXX_Unmarshal 

func (m *InstallSnapshotReq) XXX_Unmarshal(b []byte) error

type InstallSnapshotResp 

type InstallSnapshotResp struct {
	Term                 uint64   `protobuf:"varint,1,opt,name=Term,proto3" json:"Term,omitempty"`
	XXX_NoUnkeyedLiteral struct{} `json:"-"`
	XXX_unrecognized     []byte   `json:"-"`
	XXX_sizecache        int32    `json:"-"`
}

func (*InstallSnapshotResp) Descriptor 

func (*InstallSnapshotResp) Descriptor() ([]byte, []int)

func (*InstallSnapshotResp) GetTerm 

func (m *InstallSnapshotResp) GetTerm() uint64

func (*InstallSnapshotResp) ProtoMessage 

func (*InstallSnapshotResp) ProtoMessage()

func (*InstallSnapshotResp) Reset 

func (m *InstallSnapshotResp) Reset()

func (*InstallSnapshotResp) String 

func (m *InstallSnapshotResp) String() string

func (*InstallSnapshotResp) XXX_DiscardUnknown 

func (m *InstallSnapshotResp) XXX_DiscardUnknown()

func (*InstallSnapshotResp) XXX_Marshal 

func (m *InstallSnapshotResp) XXX_Marshal(b []byte, deterministic bool) ([]byte, error)

func (*InstallSnapshotResp) XXX_Merge 

func (m *InstallSnapshotResp) XXX_Merge(src proto.Message)

func (*InstallSnapshotResp) XXX_Size 

func (m *InstallSnapshotResp) XXX_Size() int

func (*InstallSnapshotResp) XXX_Unmarshal 

func (m *InstallSnapshotResp) XXX_Unmarshal(b []byte) error

type LogEntry 

type LogEntry struct {
	Index                uint64   `protobuf:"varint,1,opt,name=Index,proto3" json:"Index,omitempty"`
	Term                 uint64   `protobuf:"varint,2,opt,name=Term,proto3" json:"Term,omitempty"`
	CommandName          string   `protobuf:"bytes,3,opt,name=CommandName,proto3" json:"CommandName,omitempty"`
	Command              []byte   `protobuf:"bytes,4,opt,name=Command,proto3" json:"Command,omitempty"`
	XXX_NoUnkeyedLiteral struct{} `json:"-"`
	XXX_unrecognized     []byte   `json:"-"`
	XXX_sizecache        int32    `json:"-"`
}

func (*LogEntry) Descriptor 

func (*LogEntry) Descriptor() ([]byte, []int)

func (*LogEntry) GetCommand 

func (m *LogEntry) GetCommand() []byte

func (*LogEntry) GetCommandName 

func (m *LogEntry) GetCommandName() string

func (*LogEntry) GetIndex 

func (m *LogEntry) GetIndex() uint64

func (*LogEntry) GetTerm 

func (m *LogEntry) GetTerm() uint64

func (*LogEntry) ProtoMessage 

func (*LogEntry) ProtoMessage()

func (*LogEntry) Reset 

func (m *LogEntry) Reset()

func (*LogEntry) String 

func (m *LogEntry) String() string

func (*LogEntry) XXX_DiscardUnknown 

func (m *LogEntry) XXX_DiscardUnknown()

func (*LogEntry) XXX_Marshal 

func (m *LogEntry) XXX_Marshal(b []byte, deterministic bool) ([]byte, error)

func (*LogEntry) XXX_Merge 

func (m *LogEntry) XXX_Merge(src proto.Message)

func (*LogEntry) XXX_Size 

func (m *LogEntry) XXX_Size() int

func (*LogEntry) XXX_Unmarshal 

func (m *LogEntry) XXX_Unmarshal(b []byte) error

type Raft 

type Raft struct {
	sync.Mutex
	// contains filtered or unexported fields
}

func Make 

func Make(name string, peers map[string]string, applyMsgCh chan<- ApplyMsg) (rf *Raft)

func (*Raft) AppendEntries 

func (rf *Raft) AppendEntries(req *AppendEntriesReq, resp *AppendEntriesResp) (err error)

func (*Raft) InstallSnapshot 

func (rf *Raft) InstallSnapshot(req *InstallSnapshotReq, resp *InstallSnapshotResp) (err error)

func (*Raft) MakeSnapshot 

func (rf *Raft) MakeSnapshot(commitIdx uint64, snapshot []byte)

func (*Raft) RequestVote 

func (rf *Raft) RequestVote(req *RequestVoteReq, resp *RequestVoteResp) (err error)

func (*Raft) Stop 

func (rf *Raft) Stop()

func (*Raft) Submit 

func (rf *Raft) Submit(command Command) (isLeader bool, err error)

type RequestVoteReq 

type RequestVoteReq struct {
	Term                 uint64   `protobuf:"varint,1,opt,name=Term,proto3" json:"Term,omitempty"`
	LastLogIndex         uint64   `protobuf:"varint,2,opt,name=LastLogIndex,proto3" json:"LastLogIndex,omitempty"`
	LastLogTerm          uint64   `protobuf:"varint,3,opt,name=LastLogTerm,proto3" json:"LastLogTerm,omitempty"`
	CandidateName        string   `protobuf:"bytes,4,opt,name=CandidateName,proto3" json:"CandidateName,omitempty"`
	XXX_NoUnkeyedLiteral struct{} `json:"-"`
	XXX_unrecognized     []byte   `json:"-"`
	XXX_sizecache        int32    `json:"-"`
}

func (*RequestVoteReq) Descriptor 

func (*RequestVoteReq) Descriptor() ([]byte, []int)

func (*RequestVoteReq) GetCandidateName 

func (m *RequestVoteReq) GetCandidateName() string

func (*RequestVoteReq) GetLastLogIndex 

func (m *RequestVoteReq) GetLastLogIndex() uint64

func (*RequestVoteReq) GetLastLogTerm 

func (m *RequestVoteReq) GetLastLogTerm() uint64

func (*RequestVoteReq) GetTerm 

func (m *RequestVoteReq) GetTerm() uint64

func (*RequestVoteReq) ProtoMessage 

func (*RequestVoteReq) ProtoMessage()

func (*RequestVoteReq) Reset 

func (m *RequestVoteReq) Reset()

func (*RequestVoteReq) String 

func (m *RequestVoteReq) String() string

func (*RequestVoteReq) XXX_DiscardUnknown 

func (m *RequestVoteReq) XXX_DiscardUnknown()

func (*RequestVoteReq) XXX_Marshal 

func (m *RequestVoteReq) XXX_Marshal(b []byte, deterministic bool) ([]byte, error)

func (*RequestVoteReq) XXX_Merge 

func (m *RequestVoteReq) XXX_Merge(src proto.Message)

func (*RequestVoteReq) XXX_Size 

func (m *RequestVoteReq) XXX_Size() int

func (*RequestVoteReq) XXX_Unmarshal 

func (m *RequestVoteReq) XXX_Unmarshal(b []byte) error

type RequestVoteResp 

type RequestVoteResp struct {
	Term                 uint64   `protobuf:"varint,1,opt,name=Term,proto3" json:"Term,omitempty"`
	VoteGranted          bool     `protobuf:"varint,2,opt,name=VoteGranted,proto3" json:"VoteGranted,omitempty"`
	XXX_NoUnkeyedLiteral struct{} `json:"-"`
	XXX_unrecognized     []byte   `json:"-"`
	XXX_sizecache        int32    `json:"-"`
}

func (*RequestVoteResp) Descriptor 

func (*RequestVoteResp) Descriptor() ([]byte, []int)

func (*RequestVoteResp) GetTerm 

func (m *RequestVoteResp) GetTerm() uint64

func (*RequestVoteResp) GetVoteGranted 

func (m *RequestVoteResp) GetVoteGranted() bool

func (*RequestVoteResp) ProtoMessage 

func (*RequestVoteResp) ProtoMessage()

func (*RequestVoteResp) Reset 

func (m *RequestVoteResp) Reset()

func (*RequestVoteResp) String 

func (m *RequestVoteResp) String() string

func (*RequestVoteResp) XXX_DiscardUnknown 

func (m *RequestVoteResp) XXX_DiscardUnknown()

func (*RequestVoteResp) XXX_Marshal 

func (m *RequestVoteResp) XXX_Marshal(b []byte, deterministic bool) ([]byte, error)

func (*RequestVoteResp) XXX_Merge 

func (m *RequestVoteResp) XXX_Merge(src proto.Message)

func (*RequestVoteResp) XXX_Size 

func (m *RequestVoteResp) XXX_Size() int

func (*RequestVoteResp) XXX_Unmarshal 

func (m *RequestVoteResp) XXX_Unmarshal(b []byte) error

type State 

type State int
const (
	Follower State = iota
	Candidate
	Leader
)

func (State) String 

func (this State) String() string

Source Files

View all Source files

Directories

Path Synopsis
kv
client command
server command

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.