tiedot阅读笔记(一)

2018/01/22

tiedot

Tiedot是一个完全使用go实现的文档型的NoSQL,项目地址是:GitHub - HouzuoGuo/tiedot

项目结构

使用命令tree -L 1查看目录结构:

.
├── Dockerfile
├── LICENSE
├── README.md
├── benchmark
├── data
├── db
├── dberr
├── distributable
├── doc
├── docker-compose.yml
├── examples
├── extra
├── gommap
├── httpapi
├── main.go
├── tdlog
├── test-and-coverage-report.sh
└── vendor

如何存储数据

文件结构与条件编译

存储数据的代码全部在data里面,这篇文章先只关注这个 tree data | grep -v '_test.go' 数据:

data
├── collection.go
├── collection32.go
├── collection64.go
├── config.go
├── file.go
├── hash32.go
├── hash64.go
├── hashtable.go
├── partition.go

其中*32.go*64.go是针对不同的os进行兼容的代码,可以通过文件头部build tag指定编译条件:

// *32.go
// +build 386 arm

// *64.go
// +build !386,!arm

如何存储字节数据(下面两个数据的基础)

代码:tiedot/file.go 这部分代码借鉴了:edsrzf/mmap-go,主要的作用就是将数据从文件读入内存。 其中定义了一个数据结构:

type DataFile struct {
	Path   string // 文件路径,没什么好解释的
	Used   int // 已经使用的大小,单位字节。但是这个还有一个作用,下面会介绍
	Size   int // 文件大小
	Growth int // 当使用的数据大小超过了文件的大小的时候,就需要增加文件的大小。这个数据就是一次所增加的大小
	Fh     *os.File // 文件指针,没什么好解释的
	Buf gommap.MMap // 重点,内存数据,字节数组!下面操作数据,都是通过操作这个字段来实现的。
}

Buf中读取数据

如果数据是数字的话:

room, _ := binary.Varint(col.Buf[id+1: id+11])

如果就是字节的话:

docCopy := make([]byte, length)
copy(docCopy, col.Buf[x:y])

写入数据到Buf

如果数据是数字的话:

binary.PutVarint(Buf[x:y], int64Data)

如果就是字节的话:

copy(Buf[x:y], data)

如何存储doc(文档)

在tiedot里面定义了一个叫做Collection的东西,这个将作为doc的数据载体,Collection内嵌了DataFile数据接口。 它实现了这么几个方法,前四个是增删查改,第五个是一个map函数。

insert doc

函数签名

Insert(data []byte) (id int, err error)

Collection中的Buf数据以doc组成,doc是不连续的,每一个doc的数据结构是:

+------------------------------------+
| flag | doc length |    doc data    |
0------1-----------11-----...------end
col.Used += docSize

update doc

函数签名

Update(id int, data []byte) (newID int, err error)

分两种情况

Delete(id int) error

将标志位置为0就行了

read doc

Read(id int) []byte

先读出来doc length这个数据(2-11字节) 然后用这个数据长度去读buf的数据(第12个到11+len个字节)

如何存储index(索引,哈希表)

总览

使用了bucket和entry实现了一个哈希表,每一个bucket拥有固定数量的entry,每一个entry存储了一对键值对。 当一个bucket满了的时候,会有一个新的bucket链接到这个bucket后面,形成一个bucket链。 因为是索引,所以没有修改接口,只有增删查。

bucket

结构是

+----------------------------------------------------+
| next bucket addr | entry1 | entry2 | ... | entry16 |
0 ---------------- 10------31-------52-------------346

entry

结构是,共21字节

+--------------------+
| flag | key | value |
0------1----11------21

因为一个bucket会有若干个entry,所以知道了bucket的地址,那么就可以计算出所有的entry的地址:

entryAddr := bucket*ht.BucketSize + BucketHeader + entry*EntrySize
// ht.BucketSize = BucketHeader + conf.PerBucket*EntrySize = 10 + 16 * 21 = 346 字节
// BucketHeader 记录了下一个bucket的地址,10 字节
// entry 第几个entry,从0开始
// EntrySize entry大小,21字节

哈希函数HashKey

函数签名

HashKey(key int) int

返回值是一个0-65535之间的整数(这个也是bucket初始化的时候的范围)

函数签名

Put(key, val int)

通过哈希表找到那个数据,然后将标志位置为0

一样的

doc与index的结合

数据结构

type Partition struct {
	// 是这个par对应的doc存储地方
	col *Collection

	// 哈希表
	lookup *HashTable

	// 访问 doc 加锁
	DataLock *sync.RWMutex // guard against concurrent document updates
}

方法

函数签名

Insert(id int, data []byte) (physID int, err error)

第一个参数id是一个随机数,在生成之后是不变的(也就是更新doc仍然不变) * 先将数据插入col,返回一个真实数据的id * 然后把doc id 和真实id存在哈希表

函数签名

Delete(id int) (err error)

函数签名

Read(id int) ([]byte, error)

函数签名

Update(id int, data []byte) (err error)