shardkv

package
v0.0.0-...-ea8e5dc Latest Latest
Warning

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

 Go to latest Published: Jul 4, 2020 License: MIT Imports: 16 Imported by: 0

README

老司机带你用 Go 语言实现分布式数据库

该分布式数据使用了 Raft 协议作为一致性协议为基础，Raft 协议的实现在 《老司机带你用 Go 语言实现 Raft 分布式一致性协议》。

一个良好的分布式数据实现包括以下几个方面：

  1. 可用性，即在一些机器各种故障的情况下是否能够继续提供服务(A)；
  2. 在分布式环境中，机器之间通过网络通信，它们是否能容忍网络分区(P）；
  3. 在数据分布到各个机器之中，他们的数据是否能够保持一致（C）；
  4. 在之前的大数据环境之中，对于分布式是否支持水平扩展（Shard）也成为了一个必不可少的功能；

上述是 CAP 理论和分布式拓展的必要功能。在很多系统里面，一致性上面做了一些妥协，使用了弱一致性协议。当然像 Dynamo 这样提供 W + R > N 这种协议的，让用户选择一致性也是一种新的思路，对应的开源版本：Cassandra。

Shard

分区作为分布式里面一个重要的的特性，它可以通过增加机器来达到增加吞吐量的目的。与此同时，也带来了一些对于每一个 Shard 的负载挑战。 所以通用的做法是，客户端通过提供一个 Partition 接口，让用户自己决定分为的规则。

架构

分布式数据库架构

Sharemaster 主要负责根据 Client 提供的分区规则，将数据储存在不同的 Group 中，为了 Sharemaster 有多台机器组成，他们之间使用 Raft 协议来保证一致性。每一个 Group 由多台机器组成，他们之间也是通过 Raft 协议来保证一致性。

在实现分布式数据之中为了简单起见，将数据直接放入到一个 Map 之中，这里只是想告诉你整个流程是这样的。 持续更新中，后续会把 LSM 融入进来。

源码注释地址。

扫描二维码，关注我的个人微信公众号：

公众号

Documentation

Index

Constants

View Source 
const (
	OK             = "OK"
	ErrNoKey       = "ErrNoKey"
	ErrWrongGroup  = "ErrWrongGroup"
	ErrNotReady    = "ErrNotReady"
	ErrWrongConfig = "ErrWrongCOnfig"
)
View Source 
const (
	Get         = "Get"
	Put         = "Put"
	Append      = "Append"
	PutAppend   = "PutAppend"
	Reconfigure = "Configure"
)
View Source 
const Debug = 0

Variables

This section is empty.

Functions

func DPrintln 

func DPrintln(a ...interface{})

Types

type Clerk 

type Clerk struct {
	// contains filtered or unexported fields
}

func MakeClerk 

func MakeClerk(masters []*labrpc.ClientEnd, make_end func(string) *labrpc.ClientEnd) *Clerk

the tester calls MakeClerk.

masters[] is needed to call shardmaster.MakeClerk().

make_end(servername) turns a server name from a Config.Groups[gid][i] into a labrpc.ClientEnd on which you can send RPCs.

func (*Clerk) Append 

func (ck *Clerk) Append(key string, value string)

func (*Clerk) Get 

func (ck *Clerk) Get(key string) string

fetch the current value for a key. returns "" if the key does not exist. keeps trying forever in the face of all other errors. You will have to modify this function.

func (*Clerk) Put 

func (ck *Clerk) Put(key string, value string)

func (*Clerk) PutAppend 

func (ck *Clerk) PutAppend(key string, value string, op string)

shared by Put and Append. You will have to modify this function.

type Err 

type Err string

type GetArgs 

type GetArgs struct {
	Key string
	// You'll have to add definitions here.
	ClientId  int64
	RequestId int
}

type GetReply 

type GetReply struct {
	WrongLeader bool
	Err         Err
	Value       string
}

type Op 

type Op struct {
	// Your definitions here.
	// Field names must start with capital letters,
	// otherwise RPC will break.
	OpType string
	Args   interface{}
}

type PutAppendArgs 

type PutAppendArgs struct {
	// You'll have to add definitions here.
	Key   string
	Value string
	Op    string // "Put" or "Append"
	// You'll have to add definitions here.
	// Field names must start with capital letters,
	// otherwise RPC will break.
	ClientId  int64
	RequestId int
}

Put or Append

type PutAppendReply 

type PutAppendReply struct {
	WrongLeader bool
	Err         Err
}

type ReconfigureArgs 

type ReconfigureArgs struct {
	Cfg        shardmaster.Config
	StoreShard [shardmaster.NShards]map[string]string
	Ack        map[int64]int
}

--------------Add by Yang---------------------- send to follower server in group

type ReconfigureReply 

type ReconfigureReply struct {
	Err Err
}

type Result 

type Result struct {
	// contains filtered or unexported fields
}

type ShardKV 

type ShardKV struct {
	// contains filtered or unexported fields
}

func StartServer 

func StartServer(servers []*labrpc.ClientEnd, me int, persister *raft.Persister, maxraftstate int, gid int, masters []*labrpc.ClientEnd, make_end func(string) *labrpc.ClientEnd) *ShardKV

servers[] contains the ports of the servers in this group.

me is the index of the current server in servers[].

the k/v server should store snapshots with persister.SaveSnapshot(), and Raft should save its state (including log) with persister.SaveRaftState().

the k/v server should snapshot when Raft's saved state exceeds maxraftstate bytes, in order to allow Raft to garbage-collect its log. if maxraftstate is -1, you don't need to snapshot.

gid is this group's GID, for interacting with the shardmaster.

pass masters[] to shardmaster.MakeClerk() so you can send RPCs to the shardmaster.

make_end(servername) turns a server name from a Config.Groups[gid][i] into a labrpc.ClientEnd on which you can send RPCs. You'll need this to send RPCs to other groups.

look at client.go for examples of how to use masters[] and make_end() to send RPCs to the group owning a specific shard.

func (*ShardKV) ApplyGet 

func (kv *ShardKV) ApplyGet(args GetArgs) GetReply

func (*ShardKV) ApplyOp 

func (kv *ShardKV) ApplyOp(request Op) interface{}

---------------------- Apply Operation ------------------------

func (*ShardKV) ApplyPutAppend 

func (kv *ShardKV) ApplyPutAppend(args PutAppendArgs) PutAppendReply

func (*ShardKV) ApplyReconfigure 

func (kv *ShardKV) ApplyReconfigure(args ReconfigureArgs) ReconfigureReply

! Attention: use poll approach to get shards

func (*ShardKV) CheckDuplicated 

func (kv *ShardKV) CheckDuplicated(clientId int64, requestId int) bool

!!! be careful that where to check duplicated and valid

func (*ShardKV) CheckSnapshot 

func (kv *ShardKV) CheckSnapshot(index int)

func (*ShardKV) CheckValidKey 

func (kv *ShardKV) CheckValidKey(key string) bool

func (*ShardKV) Get 

func (kv *ShardKV) Get(args *GetArgs, reply *GetReply)

func (*ShardKV) GetReconfigure 

func (kv *ShardKV) GetReconfigure(nextCfg shardmaster.Config) (ReconfigureArgs, bool)

func (*ShardKV) Kill 

func (kv *ShardKV) Kill()

----------------------Main Body------------------------

the tester calls Kill() when a ShardKV instance won't be needed again. you are not required to do anything in Kill(), but it might be convenient to (for example) turn off debug output from this instance.

func (*ShardKV) PollConfig 

func (kv *ShardKV) PollConfig()

func (*ShardKV) PutAppend 

func (kv *ShardKV) PutAppend(args *PutAppendArgs, reply *PutAppendReply)

func (*ShardKV) SendResult 

func (kv *ShardKV) SendResult(index int, result Result)

func (*ShardKV) SendTransferShard 

func (kv *ShardKV) SendTransferShard(gid int, args *TransferArgs, reply *TransferReply) bool

func (*ShardKV) SyncReconfigure 

func (kv *ShardKV) SyncReconfigure(args ReconfigureArgs) bool

func (*ShardKV) TransferShard 

func (kv *ShardKV) TransferShard(args *TransferArgs, reply *TransferReply)

func (*ShardKV) UpdateOp 

func (kv *ShardKV) UpdateOp()

func (*ShardKV) UseSnapShot 

func (kv *ShardKV) UseSnapShot(snapshot []byte)

---------------------- SnapShot and Result ------------------------

type TransferArgs 

type TransferArgs struct {
	ConfigNum int
	Shards    []int
}

send to another group leader

type TransferReply 

type TransferReply struct {
	StoreShard  [shardmaster.NShards]map[string]string
	Ack         map[int64]int
	WrongLeader bool
	Err         Err
}

Source Files

View all Source files

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.