一种高性能数据存储引擎的实现方法

摘要

本发明提供了一种高性能数据存储引擎的实现方法。本引擎主要用于批量追加数据，数据更新操作较少，且仅需基于键值的等值查询的使用场景。因而，并发访问方面，本引擎支持单写多读，即一个写操作可以和多个读操作并发，多个写操作之间只能串行执行。本引擎中存储的每一条数据都需要一个键值，多条数据的键值可以重复，读取数据时，只能基于该键值进行等值查询。性能方面，数据入库性能与增量数据的数据量呈线性关系，且仅与增量数据量有关，即使存量数据达到千亿行的规模，入库性能也不会呈现明显衰减。

主权项

一种高性能数据存储引擎的实现方法，其特征在于，包括如下步骤：1.1本引擎使用Key‑value方式存储数据；基于Key的哈希值，组织value的存储结构；存储结构以页面为单位，包括元数据和数据两部分；1.2所述元数据分为哈希散列表和删除标记两部分，每个哈希值对应一个散列表元素；1.3所述每个散列表元素存储发生哈希冲突的数据，包括哈希冲突链的起始页面编号、冲突链尾页编号，以及尾页的空闲空间的偏移量；1.4数据存储空间中，存储的每一条数据均包括以下内容：(一)Key值；(二)本条数据的入库次序号；(三)本条数据的value；1.5所述删除标记由一个位图表示，位图的每一个比特对应一个入库次序号，为0表示数据有效，为1表示数据已删除；1.6数据存储空间中，每个页面都在固定位置存储下一个页面的编号，从而构成页面链表；链表的最后一个页面在页面编号位置存储一个结束标记，用于标识链表尾；1.7所述元数据分两个版本，一个称元数据1，另一个称元数据2，其中一个为读版本，另一个为写版本；1.8读取数据时，每个读数据请求均获得一个当前元数据读版本的只读快照，并依此快照访问数据存储空间；1.9写数据时，在元数据的写版本上进行操作，写版本是当前读版本的一个可写快照；写数据时，只允许串行写入，当一个写操作正在被处理时，其他写请求将被阻塞；1.10写操作在提交时，将当前的写版本元数据切换为当前读版本；提交结束后，再发起的读请求都使用新的读版本元数据；1.11更新和删除操作，都被定义为写操作，与数据追加操作互斥；1.12删除数据时，更新写版本元数据的删除标记；提交时将当前写版本元数据切换为读版本；1.13更新数据时，将更新操作转化成一个删除操作和一个写操作；提交时将当前写版本元数据切换为读版本。