memlink-------又一个key-value型nosql数据库诞生
Memlink简介¶
Memlink 是一个高性能、持久化、分布式的Key-list/queue数据引擎。正如名称中的memlink所示，所有数据都建构在内存中，保证了系统的高性能 (大约是redis几倍)，同时使用了redo-log技术保证数据的持久化。Memlink还支持主从复制、读写分离、List过滤操作等功能。
特点：
- 内存数据引擎，性能极为高效
- List块链结构，精简内存，优化查找效率
- Node数据项可定义，支持多种过滤操作
- 支持redo-log，数据持久化，非Cache模式
- 分布式，主从同步
与Redis区别¶
redis同样也提供key-list 存储功能，memlink与redis区别有：
- redis比较消耗内存。每个存储节点，在不支持vm的情况下要额外消耗12字节内存，在支持vm的情况下，每个节点额外消耗24字节内存。对于存储上亿条数据来说，额外消耗的内存太大。
- redis redo-log不够完善。redis redo-log机制:每隔一段时间同步磁盘（此期间重启就好丢失数据）;追加log方式，会使log文件越来越大，而且性能不够优化。
- 主从同步不完善。如果从节点因为网络原因丢失了部分同步数据，需要重新完全获取一份主节点的所有数据。在大数据量的情况下，不太合适。
- 网络处理主事件循环只有一个线程，不能很好的利用多核；同时读写没有分离，没有进行写优先处理。
- list节点没有mask表，不能进行一些属性过滤。
DesignDocument
1 工作方式¶
MemLink是一个独立的服务程序，类似于memcached，不同的是它并不是提供key-value数据的存储，而是在内存中存储的是列表数据。
2 具体结构¶
这里我们借用了memcached的网络框架，在他的基础上来增加我们想要的列表功能。见下图：
在 网络处理部分，我们使用memcached的代码。他是专门用一个线程来接受连接，然后把连接给各个处理线程。我们自己的列表功能就体现在处理线程里面。 这里每个列表项都有一个名字，也就是一个唯一的列表名字对应一个列表数据，我们使用hash来存储。列表数据部分（图中红色框部分）是我们真实的数据存储 结构。任何的对列表数据的写操作都必须要获得写锁，写操作和dump的操作不能同时进行。
线程工作方式¶
目 前，一共有4种线程。分别为读线程，写线程，同步线程，dump线程。读线程是可以有多个的。其他的线程都只有一个。写线程用来完成数据的修改，同步线程 专门用来主从同步。Dump线程用来dump数据到硬盘。写线程和同步线程分别对应有一个网络事件处理机制来接受网络连接，需要监听独立的端口，他们的处 理操作由网络请求来触发。而dump线程由时间来触发，动态产生一个线程来处理。
Hash¶
图 中的蓝色框部分为hash表的数据结构。Hash采用的是链表法。Hash的数据节点包含4个数据，在图中是 key, used, all count, data。其中key为列表名，used为该列表实际消耗了多少存储（这里是计算数据块的使用情况，比如总共可以存储数据1000个，使用了342个，那 么就是342），all count为实际分配了多少存储，data为实际数据的指针。
数据存储¶
红 色框为我们列表实际的数据结构。我们并不是每次为1个数据分配一块内存，然后链接起来。而是每次分配一定数据量的连续块（假设我们每次分配100块的连续 数据，实际上我们可以配置的）。同时，在这一个连续块中还有两个额外的数据，分别为“已经使用非标记删除的数量（无符号2字节短整型）”和“指向下一个数 据块的指针（指针）”。在每个内部的小数据区中，包括一个mask占用的空间和实际的数据占用的空间。Mask用来标示数据的属性。 Mask中有一个保留位，用来表示标记删除或者标记恢复。
数据操作¶
对数据块的操作，我们的原则是写操作尽量不影响读操作，这样就要避免数据块内的数据移动，取而代之的是拷贝数据到新的数据块。目前有以下几种涉及写的操作：
插入一个数据¶
如果是在列表的头部插入，那就是操作数据链中第一块，第一块内当前位置有空就可以插入，否则需要创建出一个新数据块，把数据写入其中最后一个位置，然后在作为头部链入数据链中。写入最后一个位置的目的是让下次插入头部就不需要再创建新数据块了。如下图：
如 果是在数据链的中间插入，如果当前位置为空，那么直接插入数据。如果不为空，那么我们要新分配一个数据块，将当前要插入的数据块中的数据拷贝到新块，如果 新数据块不能完全存储（因为插入了一个），那么就要再分配一个新数据块，把溢出的数据放到这个数据块中，然后链接入数据链。见下图：
由于有新的数据块替代了原来的数据块。原来的数据块要被释放掉，但不是马上释放，而是加入一个链表。此链表保存所有要示范班的数据块，当以后我们要新分配数据块的时候，我们就从里面取。
删除一个数据¶
删除数据只把数据所在的位置0，并且修改该数据块的“已使用数量”以及hash节点中的“总使用数量”
修改一个数据的mask¶
Mask是数据的属性，直接修改即可。
Mask是数据的属性，直接修改即可¶
修改位置实际上是删除数据，以及新插入数据到某个位置。
读操作¶
读 操作，这里主要就是取列表中的某个范围的数据。还有一个mask条件。读操作分两种情况，一是mask为空，二是mask为其他值的读。如果为空，那么从 每个数据块中的记录该块使用数量，可以很容易的计算出这个范围涉及到那几个数据块，直接到这几个数据块中读取就可以了。如果不是空就只能挨个判断，全部循 环一遍，直到得到这个范围的数据。
数据存储空间的回收¶
由 于我们在删除数据的时候只是把那个位置给置0，所以会出现一些空间浪费。运行时间越长，空间的浪费就越严重。因此，我们需要在一定的时候对存储空间重排， 让数据更加紧凑，以去除空间中的空洞。 触发这个动作的条件是，空间的利用率小于等于50%（这个值可以配置）。这个检测在每次写操作的时候进行。计算方法是hash节点中的 已使用存储数/分配的存储数 这个结果和50%来比较。一旦符合条件这个写操作完成后就马上进行空间的重排。但并不是一次性就把整个数据链全部重排，而是分批进行，一次进行100个数 据块（这个值可以配置）。剩下的块由event调度，在下次事件循环的时候接着进行。
重排的方法是这样，我们分配出新的数据块，然后把老的100个全部拷贝到新的数据块中，完成后把数据链重新链起来。老的数据块重新链接到一个空闲链表中，等待下次分配后再使用。下图用两个数据块做了个简单说明：
数据dump¶
所有列表数据会定时dump一份到硬盘上。这个过程由一个线程来独立进行。在dump之前，需要在持有写锁，这样侯不允许同时还有写操作。Dump完成后要生成新的日志文件。流程如下图：
Dump文件名dump.dat。在dump过程中，并不直接dump到这个文件，而是dump到名为dump.dat.tmp的文件，当dump过程成功完成后，才把文件名改为dump.dat。 Dump文件的格式为二进制的格式：
| Dump格式版本号（2字节） | Dump文件版本号（4字节） | 对应的log版本（4字节） | 是否为master生成(1字节) | dump文件大小（8字节） | 数据区 |
前 2字节是dump格式版本号，无符号短整型，现在默认为1，每次格式变更才修改此值。Dump文件版本号在每次dump文件生成都要自增1后面4个字节为 log日志版本，是个无符号整型。数据区，是由所有的列表项紧挨着组成，其中一个列表项格式如下，整个数据区就是由N个列表项组成：
| Key长度（1字节） | Key | Value长度（1字节） | Mask长度（1字节） | Mask项数（1字节） | Mask格式（长度由mask项数决定） | Mask Value数量（4字节） | Value | Mask |
3 日志记录¶
日志记录方式为记录所有的写操作的日志。在写操作完成的时候记录，记录成功后才给客户端返回成功。
日志文件名为bin.log.xxx。其中的xxx为自增的版本号。日志文件在dump操作完成后会新生成一个日志文件，文件名中版本号自动加一。如果日志文件中的索引号用完，也会新生成一个日志文件。
日志文件格式如下：
| 日志格式版本（2字节） | 日志文件版本号（4字节） | 是否为master生成（1字节） | 日志块数（4字节） | 索引区 | 数据区 |
日 志格式版本为2字节无符号整型，目前默认为1，只有格式变更才修改此值。日志文件版本，在每次新生成log文件的时候都自增1。日志块数表示里面可以记录 的日志的命令数，其实就是索引区的大小。索引区为日志索引号，这里面是一个很大的数组，刚开始就全部创建出来，现在我们认为默认有10万个数组项，每个项 是四字节，里面存储的是日志命令在此文件中的偏移。数据区就是实际的命令。
数据区记录的是一条条命令。开头为整个命令的长度，然后是命令 编号，最后是命令参数。命令参数中的字符串表示为: 1字节字符串长度+字符串数据。数字型直接表示。参数中的value比较特别，它有可能是字符串或者整型，所以在值的前面还有1个字节表示类型。（详细命 令协议看下面的“客户端协议描述”）数据区格式如下：
| 数据长度（2字节） | 命令编号（1字节） | 命令参数 |
涉及写操作的命令有以下几个，他们会记录到日志文件中：
| 命令 | 命令参数 | 编号 | 说明 | 例子 |
| Create | Key valuelen mask | 4 | Valuelen为1字节，mask用1个字节项数+N字节数据。 | Create haha 1 4:3:2 表示为 \x0c\x00\x04\x04haha\x01\x03\x04\x03\x04 |
| Del | Key value | 5 | Value前面要有一个1字节表示类型 | Del haha vvv 表示为 \x0b\x00\x05\x04haha\x01\x03vvv |
| Insert | Key value pos | 6 | Pos为4字节 | Insert haha gogo 1 表示为 \x10\x00\x06\x04haha\x01\x04gogo\x02\x00\x00\x00 |
| Update | Key value pos | 7 | Pos为4字节 | Update haha aaa 2 表示为 \x0f\x00\x07\x04haha\x01\x03aaa\x02\x00\x00\x00 |
| Mask | Key value mask | 8 | Mask为1字节 | Mask haha bbb 3 表示为 \x0c\x00\x08\x04haha\x01\x03bbb\x03 |
| Tag | Key value del/reverse | 9 | Del用1表示，reverse用0表示。1字节 | Tag haha xxx1 del 表示为 \x0d\x00\x09\x04haha\x01\x04xxx1\x01 |
以上表格中的命令都会被记录在日志文件中。
日志需要在server启动时进行格式效验。确认日志的完整性。效验方法为：
- 读取日志块数
- 根据日志块数，可以确定索引区有多少索引。找到索引区的最后一个索引。
- 根据索引区最后一个索引，找到对应的数据区。
- 跳过最后这个索引指向的数据区，判断后面是否还有数据。如果有数据，通过数据的前面两个字节，我们可以知道这个数据块有多大，这样就可以确定数据是否完整。如果是完整的，就添加索引到索引区。如果不完整就清除掉。
4 主从同步¶
MemLink支持一个主，多个从的同步模式。主和从的区别：
| 功能 | 主 | 从 |
| 读请求 | yes | yes |
| 写请求 | yes | no |
| dump请求 | yes | yes |
| 更新log | yes | yes |
| 同步 | 同步线程监听从的同步请求 | 同步线程和主建立连接，接收同步数据 |
从的同步线程流程：
主的同步线程流程：
命令协议为二进制交互协议，和其他命令的方法一样。
具体的交互命令如下：
1. sync {log version} {log line}
发送数据的格式为：
| 长度(2字节） | 命令编号（1字节） | log version（4字节） | log line（4字节） |
描述：表示同步数据。长度为后面所有数据的长度（字节数），比如这里长度应该是9。Sync的命令编号为100，log version为主上log版本号，4字节整型，log line为行号，也是4字节整型。
返回数据的格式如下：
| 长度（4字节） | 返回值（２字节） |
长 度为后面所有数据的长度（字节数），这里应该是2。如果返回值为0，主会开始向从发送log记录。从把接收的log记录应用到hash table上，然后把log记录保存到本地的log文件。从的log文件的每条记录前都保存主的log version和log line。
如果返回值为1，表示从需要发送dump请求。这时候需要使用getdump的命令还获取dump文件。
2. getdump {dumpversion} {size}
发送命令数据格式：
| 长度(2字节) | 命令编号(1字节) | dump version(4字节) | size （4字节） |
描述：getdump命令编号为101。Dumpversion为dump版本号，是4字节，size为已同步文件大小，为8字节。
返回数据格式：
| 长度(4字节） | 返回值（2字节） | dump version (4字节) | dump size (8字节) |
返回：是否是原dump文件，1表示是，0表示不是，需要1字节。如果为1，主接着发送原dump文件。如果为0，主开始发送新的dump文件。
如果需要发送dump文件，主紧接着开始发送dump文件。
在dump文件期前，主工作的流程：
- 打开dump文件。
- 读取并发从固定长度的数据（例如1024字节）直到dump文件结束。
在dump文件期前，从工作的流程：
- 把主从dump文件同步标志置为1。
- 创建一个dump文件。
- 不断把从主接收到的数据写入dump文件。
从在接收完dump数据后，更新hash table, 生成新的log文件。
在发送完dump文件之后，主开始向从发送log记录。
我们可以通过tcp keep-alive来保持主从同步用的TCP连接。
5 客户端协议描述¶
客户端协议是指使用者用php，c等语言写的程序连接上MemLink进行操作使用的协议。我们这里支持的是文本方式的协议，基本结构类似memcached的客户端协议。协议的基本结构如下：
命令 参数1 参数2 参数3\r\n value数据
开 头要以命令开头，命令都为小写英文字母，然后有一个空格，后面跟的是此命令的参数，根据命令的不同，可能参数的数目也是不同的，他们都以一个空格分隔开。 最后是\r\n。最后的value数据紧跟\r\n，该项只有在命令中有value的时候才存在。在命令中value只提供一个长度，对应就是后面 value数据的长度。
服务器端的应答也是纯文本，结构如下：
状态 [描述字符串]\r\n
状态表示命令执行结果，有这些返回可能：
| 状态 | 说明 |
| 200 | 表示命令成功执行 |
| 300 | 表示客户端命令格式有问题 |
| 400 | 表示服务器端临时错误，可以重试 |
| 500 | 表示服务器端处理有问题 |
| 600 len | 表示后面还有数据，数据的长度为len。 |
状态后面的描述字符串为人可读的一个描述字符串，是可选的（600没有描述字符串）。状态和描述字符串以一个空格分隔。
具体我们支持的命令如下： 1. Dump
描述：让MemLink立即把内存中的数据存储一份到硬盘
2. Clean key
描述：立即开始回收该key对应的链表中的内存
3. Stat key
描述：显示统计信息。后面的key这个参数是可选的，如果有，表示显示该key 下对应的链表的使用情况。
如果不带参数返回：
| 返回项 | 类型 | 说明 |
| count | 整型 | 存储的所有项 |
| All_block | 整型 | 所有分配额块数 |
| All_data | 整型 | 所有分配的数据块可容纳多少数据 |
| all_mem | 整型 | 所有分配的内存 |
| used_mem | 整型 | 已使用的内存 |
带参数key返回：
| 返回项 | 类型 | 说明 |
| count | 整型 | 该key下的data数 |
| All_block | 整型 | 所有分配的块数 |
| All_data | 整型 | 所有分配的数据块可容纳多少数据 |
| All_mem | 整型 | 所有分配的内存 |
| Used_mem | 整型 | 所有使用的内存 |
4. Create key valuelen maskformat
描 述：创建一个列表项，key为列表项名字。valuelen为数据块中存储的每个value的大小，字符串就是它的长度，整型为0。Maskformat 为mask的格式。表示方式为xx:xx:xx。是用：分隔的多个数字，每个数字表示占用几bit。比如1:4:3表示mask分为三部分，第一部分 1bit，第二部分4bit，第三部分3bit。
5. Del key value
描述：真实删除一个key下的某一项。注意这里的value只是value的长度，数据跟在命令\r\n后面的。以下的命令都一样。
6. Insert key value mask pos
描述：插入一条新的条目。Pos为新插入条路在列表中的位置。0表示第一位，以此类推。
7. Update key value pos
描述：更新一个条目的位置。key为列表名，value为该条目的名字，pos为新的位置。
8. Mask key value mask
描述：修改一个条目对应的掩码。Mask表示掩码修改值，格式为xx:xx:xx。是用：分隔的多
9. Tag key value del/reverse
描述：对数据做标记。Del表示标记删除。Reverse表示标记恢复。
10. Range key mask frompos len
描 述：取对应的某个key下，某个范围的条目。Key为列表名，mask为条件，frompos为要取的开始位置，len为取的长度。Mask的表示方式为 xx:xx:xx，这个和create的定义里面的mask是对应的。Xx表示条件值，必须和这个值相等，才符合条件。如果对应的位置没有条件，那就为 空。比如第二个位置无条件，那么写为xx::xx。 返回数据格式：
6 命令编号¶
所有客户端命令以及同步命令，对应都有一个命令编号，如下：
| 命令 | 编号 |
| Dump | 1 |
| Clean | 2 |
| Stat | 3 |
| Create | 4 |
| Del | 5 |
| Insert | 6 |
| Update | 7 |
| Mask | 8 |
| Tag | 9 |
| range | 10 |
| Sync | 100 |
| Getdump | 101 |
7 启动流程¶
下面是server启动要执行的一些流程：
8 配置信息¶
程序应该可以配置项有如下几个
| 名称 | 类型 | 描述 | 默认值 |
| block_data_count | 整型 | 数据块的容量 | 100 |
| block_clean_cond | 浮点数 | 数据重排条件 | 0.5 |
| dump_interval | 整型 | Dump数据间隔时间，单位为分钟 | 60 |
| read_port | 整型 | 读线程占用端口 | 11001 |
| write_port | 整型 | 写线程占用端口 | 11002 |
| sync_port | 整型 | 同步线程占用端口 | 11003 |
| data_dir | 字符串 | Dump和log数据文件目录 | |
| log_level | 整型 | 日志输出等级：0-3。 0：无日志 1：只输出错误 2：只输出错误和警告 3：只输出错误，警告和普通信息 | 3 |
| timeout | 整型 | ||
| role | 整型 | 节点角色：1表示主；0表示从 | |
| master_addr | 字符串 | 主IP地址 | |
| sync_interval | 整型 | 主发送给从更新log的时间间隔，单位是毫秒 |