TinyKV Project 1

2024-08-14 约 2345 字预计阅读 5 分钟

project1是一个热身项目，内容非常简单。项目文档中提到需要实现两部分的内容：（1）独立存储引擎；（2）原始kv服务处理程序。下面分别介绍一下基本的思路。

独立存储引擎

文档中提到该任务是对badgerDB的读写API的封装以支持列族（Column Family, CF）。通过运行grep -rIi "Your Code Here (1)."发现需要编写的代码主要在kv/storage/standalone_storage/standalone_storage.go，需要实现：

定义StandAloneStorage的数据结构
定义NewStandAloneStorage函数，根据参数Config创建一个StandAloneStorage对象
填充Start, Stop, Reader, Write四个函数

`StandAloneStorage`的定义和新建

根据项目文档，engine_util包（kv/util/engine_util）中提供了所有的读写操作，即需要封装的API。但是我们并不知道它们在哪里，kv/util/engine_util/doc.go中给出了一些信息：

1
2
3
* engines: a data structure for keeping engines required by unistore.
* write_batch: code to batch writes into a single, atomic 'transaction'.
* cf_iterator: code to iterate over a whole column family in badger.

从命名和描述可以看出engines是存储引擎、write_batch是将多个写入整合到一个batch中，cf_iterator则是在badger中迭代列族。

再来看具体的文件。

kv/util/engine_util/engines.go中定义了Engines类，包含了两个badger.DB的指针，还提供了NewEngines、WriteKV、WriteRaft、Close、Destroy、CreateDB这些函数。很显然StandAloneStorage是对Engines的封装，需要包含一个engine_util.Engines成员，NewStandAloneStorage需要进行CreateDB和NewEngines两个步骤。Start不需要修改，Stop需要调用en.Close();

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
type Engines struct {
  // Data, including data which is committed (i.e., committed across other nodes) and un-committed (i.e., only present
  // locally).
  Kv     *badger.DB
  KvPath string
  // Metadata used by Raft.
  Raft     *badger.DB
  RaftPath string
}

type StandAloneStorage struct {
  // Your Data Here (1).
  en *engine_util.Engines
}

Write

关于Write的实现，文档告诉我们参数ctx *kvrpcpb.Context暂时不用管，只剩下一个参数batch []storage.Modify，可知是接口Modify类型切片，通过观察类定义和相关函数发现，Modify中可以是类型为Put或Delete类型的Data，使用.Key().Cf().Value()取对应的字段。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
type Modify struct {
  Data interface{}
}

type Put struct {
  Key   []byte
  Value []byte
  Cf    string
}

type Delete struct {
  Key []byte
  Cf  string
}

func (m *Modify) Key() []byte {
  switch m.Data.(type) {
  case Put:
    return m.Data.(Put).Key
  case Delete:
    return m.Data.(Delete).Key
  }
  return nil
}

func (m *Modify) Value() []byte {
  if putData, ok := m.Data.(Put); ok {
    return putData.Value
  }

  return nil
}

func (m *Modify) Cf() string {
  switch m.Data.(type) {
  case Put:
    return m.Data.(Put).Cf
  case Delete:
    return m.Data.(Delete).Cf
  }
  return ""
}

因此我们在Write中需要做的应该是：声明一个空的WriteBatch wb，然后遍历参数batch，提取每一个key,val,cf，使用辅助函数添加到wb中；遍历结束后调用en.WriteKV实现写入。

通过阅读kv/util/engine_util/write_batch.go可知要用到的辅助函数是类WriteBatch的SetCF和DeleteCF接口。

Reader

Reader方法返回一个StorageReader接口，要求实现GetCF()、IterCF()、Close()三个方法

1
2
3
4
5
6
type StorageReader interface {
  // When the key doesn't exist, return nil for the value
  GetCF(cf string, key []byte) ([]byte, error)
  IterCF(cf string) engine_util.DBIterator
  Close()
}

文档中说应该使用badger.Txn来实现Reader函数，但是badger.Txn并没有GetCF()、IterCF()、Close()这三个方法，因此不能满足StorageReader接口的要求（go语言接口interface的限制），我们要对其进行封装。

我这里定义了一个StandAloneStorageReader类，包含了一个badger.Txn成员，分别使用engine_util.GetCFFromTxn、engine_util.NewCFIterator、txn.Discard实现了GetCF()、IterCF()、Close()。在Reader中只需要调用en.Kv.NewTransaction创建一个txn，然后返回一个StandAloneStorageReader即可。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
func (s *StandAloneStorage) Reader(ctx *kvrpcpb.Context) (storage.StorageReader, error) {
  // Your Code Here (1).
  txn := s.en.Kv.NewTransaction(false)
  return &StandAloneStorageReader{
    txn: txn,
  }, nil
}

type StandAloneStorageReader struct {
  txn *badger.Txn
}

实现服务处理程序

需要实现的代码在kv/server/raw_api.go当中，需要实现RawGet、RawPut、RawDelete、RawScan。前三个都很简单，没有需要自己寻找或设计的数据结构，部分接口需要查找，不过都是可以根据参数和成员得到的。

RawScan函数主要是要弄清它的功能：从startkey开始，取至多limit个kvPairs。

这样就知道需要用Reader的迭代器，首先Seek到StartKey的位置，然后取至多limit个kvPairs。

iter的使用方式参考：iter->Seek(StartKey) –>iter->Valid() –>iter.Next()

测试问题

出现一个问题

/posts/tinykv_p1/image-20231116204912-q20bqqq.png — problem

查看测试代码，发现当KeyNotFound时要求err返回nil（后面许多关卡很多都需要面向测试点编程）

/posts/tinykv_p1/image-20231116204940-tsx3alt.png — test code

解决后成功通过！完成 project 1！

目录