key-value数据库中的数据压缩方法、存储方法、访问方法和系统

摘要

本发明提供一种key‑value数据库中的数据压缩方法、存储方法、访问方法和系统，该数据压缩方法包括：从key‑value数据库中的多个已存储key‑value条目的value域数据中抽取用户地址数据，基于用户地址数据统计平均用户key‑value条目数量；在所述平均用户key‑value条目数量高于预定阈值时，在key‑value数据库中创建二级哈希表来存储各key‑value条目的初始哈希表中的用户地址数据，使得用户地址数据相同的key‑value条目对应同一个二级哈希表；将各key‑value条目的初始哈希表中的用户地址数据替换为指向相应二级哈希表中的用户地址数据的指针，将用户地址数据被替换后的初始哈希表作为各key‑value条目的一级哈希表存储在key‑value数据库中。本发明的方法和系统，能够提高区块链数据库中的访存性能。

说明书

技术领域

本发明涉及计算机技术领域，尤其涉及面向区块链应用的数据处理技术，更具体地涉及一种key-value数据库中的数据压缩方法、存储方法、访问方法和系统。

背景技术

区块链是随着比特币等数字加密货币的日益普及而逐渐兴起的一种全新技术，它提供了一种去中心化的、无需信任积累的信用建立范式，目前已经引起金融行业、科研机构、政府部门和投资公司的高度重视与广泛关注。

区块链起源于比特币，作为比特币的底层技术，本质上是一个去中心化的数据库。区块链技术是一种不依赖第三方、通过自身分布式节点进行网络数据的存储、验证、传递和交流的一种技术方案。区块链技术被认为是互联网发明以来最具颠覆性的技术创新，它依靠密码学和数学巧妙的分布式算法，在无法建立信任关系的互联网上，无需借助任何第三方中心的介入就可以使参与者达成共识，以极低的成本解决了信任与价值的可靠传递难题。

在区块链中，节点通过特定的共识算法以及交易验证算法实现去中心化交易。交易数据被分为两类，一类是块数据(block)，里面包含了已经被确认的交易，这类数据以区块的形式存储至数据库中，区块以链的方式组成区块链；另一类数据是未花费交易数据(UTXO，Unspent Transaction Output)，它是块数据的子集，是专门为提高交易验证速度而设立的数据。交易数据都被存储在数据库中，交易数据在写入区块前需要执行一系列的验证过程，在这些过程中需要访问和更新数据库，因此数据库的效率，尤其是存储UTXO 的数据库效率，对区块链的交易性能至关重要。

UTXO数据是验证交易签名的必不可少的数据，大多数区块链系统采用key-value数据库来存储UTXO数据，key-value数据库包括key域数据和value域数据，其中key域数据与交易ID相关，value域数据与节点地址相关，每一个(key，value)对(可简称为(K， V)对、(K，V)数据)被称为一个key-value条目或一条key-value数据，区块链系统可以根据key值(简称K)快速映射到存储对应(key，value)条目中的节点地址(用户地址)。以比特币为例，其key域数据由交易ID和输出索引组成，其value域数据由节点地址、交易金额等组成。key-value条目可以以哈希表的形式存储在key-value数据库中。对应 key-value数据库，如果其数据在内存中，则可以很快的存取数据(～20us/opr)，但如果数据在硬盘中，其访存速度会变得降低接近3个数量级(～10ms/opr)，由于区块链巨大的交易量，数据库所存储的UTXO数据已达到3GB左右，而且还在继续增长，目前的内存容量越来越难以满足UTXO数据的增长，导致部分数据被放置于硬盘中，从而极大地降低了数据库的访存性能。

另外，由于key-value数据库的地址映射机制(哈希映射)，在数据访存时会有一定数量的冲突产生，即不同key值的条目会被映射到相同的地址。这种冲突主要通过开放地址法或链表法解决，但是如果冲突率过高，数据库处理冲突的事件开销就会增大，从而也会降低数据库的访存性能。

如何提高区块链数据库的访存性能，是一个有待解决的问题。

发明内容

鉴于此，本发明实施例提供了一种key-value数据库中的数据压缩方法、装置和系统，以消除或改善现有技术中存在的一个或更多个缺陷。

本发明的技术方案如下：

根据本发明的一方面，提供一种针对区块链数据库的数据压缩方法，该方法包括以下步骤：

从key-value数据库中的多个已存储key-value条目的value域数据中抽取用户地址数据，基于用户地址数据统计平均用户key-value条目数量；

在所述平均用户key-value条目数量高于预定阈值时，在key-value数据库中创建二级哈希表来存储各key-value条目的初始哈希表中的用户地址数据，使得用户地址数据相同的key-value条目对应同一个二级哈希表；

将各已存储key-value条目的初始哈希表中的用户地址数据替换为指向相应二级哈希表中的用户地址数据的指针，将用户地址数据被替换后的初始哈希表作为各key-value条目的一级哈希表存储在key-value数据库中。

优选地，各key-value条目的初始value域数据中的用户地址数据作为对应二级哈希表中的key域数据，二级哈希表中的value域数据为空。

优选地，针对要存入key-value数据库的key-value条目，所述方法还包括：对要存储的key-value条目中的初始key值进行哈希运算，得到key-value数据库中与一级哈希表对应的数据桶的地址，如果数据桶内有数据，则按照预定的冲突解决法寻找新的用于存储一级哈希表的存储地址，将要存储的key-value条目中的value域数据分解为用户地址数据和非用户地址数据，将用户地址数据作为二级哈希表的key域数据存储在key-value数据库中创建的二级哈希表中，并将指向二级哈希表中的用户地址数据的指针以及非用户地址数据存储在对应的一级哈希表中。

优选地，所述将用户地址数据存储在key-value数据库中创建的二级哈希表中的步骤包括：对要存储的key-value条目的二级哈希表的key值进行哈希运算，得到二级哈希表所对应的数据桶的地址，如果数据桶中已经存在数据，则将当前用户地址数据和已存在的地址数据进行比较，如果二者一致，将数据桶中当前二级哈希表作为要存储的key-value数据对应的二级哈希表；如果二者不一致，则按照预定的冲突解决法寻找新的用于存储二级哈希表的存储地址。

根据本发明的另一方面，提供一种针对区块链数据库的数据存储方法，该方法包括以下步骤：

利用一级哈希表和二级哈希表来在key-value数据库中存储多个key-value条目；

其中，具有相同用户地址数据的key-value条目对应同一个二级哈希表，各key-value 条目的初始value域数据中的用户地址数据作为对应二级哈希表中的key域数据存储在二级哈希表中，所述二级哈希表中的value域数据为空；并且

每个key-value条目对应一个一级哈希表，各一级哈希表中的key域数据为对应key-value条目中的初始key值，各一级哈希表中的value域数据包括指向对应二级哈希表中的用户地址数据的指针以及非用户地址数据。

优选地，针对要存入key-value数据库的key-value条目，所述利用一级哈希表和二级哈希表来在key-value数据库中存储多个key-value条目的步骤包括：对要存储的key-value 条目中的初始key值进行哈希运算，得到key-value数据库中与一级哈希表对应的数据桶的地址，如果数据桶内有数据，则按照预定的冲突解决法寻找新的用于存储一级哈希表的存储地址，并将要存储的key-value条目中的value域数据分解为用户地址数据和非用户地址数据，将用户地址数据存储在key-value数据库中创建的二级哈希表中，并将指向用户地址数据的指针以及非用户地址数据存储在对应的一级哈希表中。

优选地，所述将用户地址数据存储在key-value数据库中创建的二级哈希表中的步骤包括：如果当前二级哈希表中已经存在数据，则将当前用户地址数据和二级哈希表中的地址数据进行比较，如果二者一致，将当前二级哈希表作为要存储的key-value数据对应的二级哈希表；如果二者不一致，则按照预定的冲突解决法寻找新的用于存储二级哈希表的存储地址。

优选地，所述一级哈希表和所述二级哈希表存储在内存中。

根据本发明是另一方面，还提供一种基于如前所述的数据存储方法的数据访问方法，该数据访问方法包括以下步骤：

对给定的key值进行哈希映射，得到key-value数据库中一级哈希表对应的数据桶的地址；

在对应的数据桶中存在数据的情况下，根据一级哈希表中的指针指向的地址，从二级哈希表中获得用户地址数据，将获得的用户地址数据和一级哈希表中的非用户地址数据组合成所述给定的key值对应的value值。

优选地，在对应的数据桶中不存在一级哈希表的情况下，返回访问结果为空。

根据本发明的另一方面，还提供一种存储区块链数据的数据库系统，该系统包括处理器和存储器，所述存储器包括内存和硬盘，所述存储器存储有key-value数据库，所述存储器还用于存储计算机指令，所述处理器用于执行所述存储器中存储的计算机指令，当所述计算机指令被处理器执行时该系统实现如前所述数据存储方法和/或数据访问方法的步骤。

根据本发明的另一方面，还提供一种计算机可读存储介质，其上存储有计算机程序，该程序被处理器执行时实现如前所述方法的步骤。

本发明实施例的方法和系统，能够利用系统的存储空间存储更多的key-value数据(如 UTXO)，从而可以改善key-value数据库的访存性能。

本领域技术人员将会理解的是，能够用本发明实现的目的和优点不限于以上具体所述，并且根据以下详细说明将更清楚地理解本发明能够实现的上述和其他目的。

附图说明

此处所说明的附图用来提供对本发明的进一步理解，构成本申请的一部分，并不构成对本发明的限定。在附图中：

图1为本发明一实施例中value域数据的压缩方法示意图。

图2示出了本发明实施例的数据库系统中一级哈希表和二级哈希表的示意图。

图3为本发明另一实施例中数据库系统存入操作流程图。

图4为本发明一实施例中数据库系统访问操作流程图。

图5为本发明一实施例中数据库系统的示意性框图。

具体实施方式

为使本发明的目的、技术方案和优点更加清楚明白，下面结合实施方式和附图，对本发明做进一步详细说明。在此，本发明的示意性实施方式及其说明用于解释本发明，但并不作为对本发明的限定。

在此，还需要说明的是，为了避免因不必要的细节而模糊了本发明，在附图中仅仅示出了与根据本发明的方案密切相关的结构和/或处理步骤，而省略了与本发明关系不大的其他细节。

应该强调，术语“包括/包含”在本文使用时指特征、要素、步骤或组件的存在，但并不排除一个或更多个其它特征、要素、步骤或组件的存在或附加。

在此，还需要说明的是，在不冲突的情况下，本申请中的实施例及实施例中的特征可以相互结合。

本发明实施例提供了一种key-value数据库中的数据压缩方法，如图1所示，本方法可以对现有key-value数据库中的key-value条目进行压缩，以使得相同的系统空间能够存储更多的key-value条目。该数据压缩方法包括以下步骤：

步骤S110，从key-value数据库中的多个已存储key-value条目的value域数据中抽取用户地址数据，基于用户地址数据统计平均用户key-value条目数量。

key-value数据库的多个已存储key-value条目可以指现有的key-value数据库中存储的传统格式的key-value条目，它们具备初始哈希表而不具备二级哈希表。下文将区块链比特币中UTXO条目作为key-value条目的示例，但本发明并不限于此，key-value条目还可以是其他类型的数据，如物联网区块链中的交易数据。

对于这些key-value条目，本步骤可从其value域的数据中抽取出用户地址数据，相同的用户地址数据合并，统计平均用户key-value条目数量，表示平均每用户的key-value 条目数量。本实施例中平均用户key-value条目数量为平均用户UTXO条目数量，即UTXO 条目数量/用户地址数量。

步骤S120，在平均用户key-value条目数量高于预定阈值时，在key-value数据库中创建二级哈希表来存储各key-value条目的初始哈希表中的用户地址数据，使得用户地址数据相同的key-value条目对应同一个二级哈希表。

因为value域数据压缩会带来一定内存开销，这部分开销在平均用户UTXO条目数量较低时带来的压缩效果较差，因此可以先判断平均用户UTXO条目数量是否高于某一阈值，如果高于该阈值，则执行压缩，否则，则不执行压缩。

以比特币为例，其在数据库中的UTXO条目数量约50M，用户地址数量约23M，平均用户UTXO条目数量约为2.2。可假设阈值为2，由于平均用户UTXO条目数量2.2大于阈值，则比特币的UTXO条目可以执行value域数据压缩。在此，阈值2仅为示例，在不同的区块链应用中，可以合理设置不同的阈值。

在本步骤中，将步骤S110中的用户地址数据作为key值，NULL作为value值(即value值为空)，建立新的哈希表，在本发明中称之为二级哈希表，二级哈希表的构造方法和哈希函数可以和初始哈希表一致，也可以采取独立配置。对二级哈希表中的key值哈希，变可以得到二级哈希表的数据桶的位置。以比特币为例，其用户地址数据是长度为20字节的数据，相应地在新建的二级哈希表中，该20字节的用户地址数据作为key值，NULL 作为value值。

由于平均用户UTXO条目数量约为2.2，即用户地址数据存在重复，因此本发明实施例中，将二级哈希表用于存储原UTXO中重复的数据，即用户地址数据。通过将重复用户地址合并，每个用户地址数据都是唯一的，然后将唯一的用户地址数据作为key域数据存储在二级哈希表中，这样做的目的是提高读写的速度，而二级哈希表中的value域数据被设为空(NULL)，这样可以避免不必要的内存开销。也就是说，本发明中，用户地址数据相同的不同key-value条目可对应同一个二级哈希表，从而可以节约内存开销从而提高系统访问性能。

步骤S130，将各key-value条目的初始哈希表中的用户地址数据替换为指向相应二级哈希表中的用户地址数据的指针，将用户地址数据被替换后的初始哈希表作为各key-value条目的一级哈希表存储在key-value数据库中。

即，将初始哈希表的value域中的用户地址数据提取并替换为指针，该指针实际上指向用户地址数据在内存中的地址。初始哈希表的value域中包括用户地址数据和非用户地址数据(如交易金额、区块高度等)。在将用户地址数据替换为指针后，该指针和非用户地址数据组合成为新的value域数据，和初始哈希表原有key值组合成新的一级哈希表。

上述可见，一级哈希表存储原UTXO条目的非重复数据，包括原有key值和改动的value值。改动value值包括：指向用户地址数据的指针以及非用户地址数据。以比特币为例，其用户地址数据是长度为20字节的数据，其非用户地址数据为8字节，包括金额，区块高度等。本实施例中，指向用户地址数据的指针例如可以是4字节或8字节的数据。这种情况下，初始哈希表的value域数据包括20字节的用户地址数据和8字节的非用户地址数据，改动value值后的一级哈希表的value域数据包括4或8字节的指针和8字节的非用户地址数据，节约了内存空间。

本发明实施例中一级哈希表和二级哈希表的形式如图2所示，每个key-value条目对应一个一级哈希表，一级哈希表中的key域数据为初始哈希表中的初始key值，value域数据包括指向对应二级哈希表中的用户地址数据的指针以及非用户地址数据。在一级哈希表中，具有相同用户地址数据的条目其指针将指向二级哈希表中的相同地址。每个二级哈希表中包括的用户地址数据都是唯一的，具有相同用户地址数据的key-value条目对应同一个二级哈希表。

本发明实施例中，一级哈希表和二级哈希表优选地存储在内存中，同样存储空间的内存可以存储更多的key-value数据条目，从而可以大大提高数据的访存速度。

针对数据库中的每一key-value条目，在通过一级哈希表和二级哈希表对条目压缩后，针对后续的未压缩的key-value条目，系统可以判断其用户地址数据是否与已有的二级哈希表中的用户地址数据重复，如果是重复的，压缩过程中就无需建立新的二级哈希表，仅需将一级哈希表中的指针指向相应的二级哈希表即可。

基于如上所述的key-value数据库中的数据压缩方法，本发明相应提供了一种key-value数据库中的数据存储方法，即利用一级哈希表和二级哈希表来在key-value数据库中存储多个key-value条目，其中一级哈希表和二级哈希表的形式如前所述。该方法不限于比特币应用，还可以是其它将用到key-value数据库的新的应用。基于本发明实施例的数据存储方法，在事先已知用户地址数据重复率较高的情况下，即key-value条目数量高于预定阈值的情况下，基于该存储方法存储的key-value条目将占用更少的内存，从而使同样的内存空间可以存储更多的key-value条目，提高了数据库的访存性能。

图3示出了本发明一实施例中向key-value数据库存入key-value条目的示意性流程图。如图3所示，给定key值K和value值V，将该(K,V)数据存储到数据库系统中的存入操作流程包括：对K哈希，得到一级哈希表中对应数据桶的地址，如果桶里没有数据，说明对于K没有冲突，可存储K、指针与非用户地址数据到数据桶中，在此指针的初始值可以是指向二级哈希表对应的数据桶地址的数据，二级哈希表对应的数据桶地址可以通过对其key值哈希得到。如果一级哈希表的桶里有数据，说明发生冲突，根据开放地址法等冲突处理算法定位到新的内存地址上，然后将value值V分解成用户地址数据和非用户地址数据，并通过指针获取到二级哈希表对应的数据桶的地址，以把用户地址数据存储在二级哈希表中。对于二级哈希表，如果对应内存地址(数据桶内)没有数据，即数据桶为空，则直接将用户地址数据作为二级哈希表的key值存储至该数据桶中，如果对应内存地址(对应数据桶内)已有数据，说明可能发生冲突，进一步比较用户地址数据和已有数据 (桶内二级哈希表的key值)，如果比较结果一致，说明没有发生冲突，并且数据桶内已有二级哈希表，此时可不进行任何操作或者存储用户地址数据至桶内，如果比较结果不一致，说明发生冲突，需要根据开放地址法等冲突处理算法将二级哈希表的数据写在新的内存地址上。用户地址数据在二级哈希表上存储后，将其内存地址返回，该内存地址实际上就是用户地址数据的指针，将该指针和V中的非用户地址数据组合写在一级哈希表的 value域，即更新一级哈希表的value域。

图4示出了本发明实施例中的基于如上所述的数据压缩方法和/或数据存储方法的数据访问操作。如图4所示，针对给定的key值K，想要从数据库系统中获取对应的value值，具体的数据访问操作包括：对K哈希，得到一级哈希表中对应的桶的地址，如果对应桶里没有数据，说明对于K没有条目被记录，访问操作返回空；如果有数据，则获取其value值，抽取value中的指针数据，根据指针指向的地址，得到其用户地址数据，将用户地址数据和一级哈希表中的非用户地址数据组合成完整value值返回。

通过如上所述的针对value域数据的数据压缩方法，在key-value数据库中存储相同数量的key-value数据条目，如UTXO条目，将占用更少的存储空间，这意味着同样存储空间的内存可以存储更多的key-value数据条目，从而可以大大提高数据的访存速度。

本公开的方法不仅适于区块链中比特币交易数据，同样可以应用于适于在key-value 数据库中存储的其他类型的数据，如物联网区块链中的交易数据。

与前述方法相应地，本发明还提供一种存储区块链数据的数据库系统，该系统包括处理器和存储器，所述存储器包括内存和硬盘，存储器存储有key-value数据库，该存储器还用于存储计算机指令，该处理器用于执行存储器中存储的计算机指令，当计算机指令被处理器执行时该系统实现如前所述各个方法步骤。本系统中，创建的一级哈希表和二级哈希表优选存储在内存中。

在本公开的一些实施例中，数据压缩系统可以包括收发单元，该收发单元可包括接收器和发送器，如图5所示，处理器、存储器、接收器和发送器可通过总线系统连接，处理器可控制收发单元收发key-value数据。

作为一种实现方式，本发明中接收器和发送器的功能可以考虑通过收发电路或者收发的专用芯片来实现，处理器可以考虑通过专用处理芯片、处理电路或通用芯片实现。

作为另一种实现方式，可以将实现处理器，接收器和发送器功能的程序代码存储在存储器中，通用处理器通过执行存储器中的代码来实现处理器，接收器和发送器的功能。

本公开还涉及存储介质，其上可以存储有计算机程序代码，当程序代码被执行时可以实现本发明的方法的各种实施例，该存储介质可以是有形存储介质，诸如光盘、U盘、软盘、硬盘等。

本领域普通技术人员应该可以明白，结合本文中所公开的实施方式描述的各示例性的组成部分、系统和方法，能够以硬件、软件或者二者的结合来实现。具体究竟以硬件还是软件方式来执行，取决于技术方案的特定应用和设计约束条件。专业技术人员可以对每个特定的应用来使用不同方法来实现所描述的功能，但是这种实现不应认为超出本发明的范围。当以硬件方式实现时，其可以例如是电子电路、专用集成电路(ASIC)、适当的固件、插件、功能卡等等。当以软件方式实现时，本发明的元素是被用于执行所需任务的程序或者代码段。程序或者代码段可以存储在机器可读介质中，或者通过载波中携带的数据信号在传输介质或者通信链路上传送。“机器可读介质”可以包括能够存储或传输信息的任何介质。机器可读介质的例子包括电子电路、半导体存储器设备、ROM、闪存、可擦除ROM (EROM)、软盘、CD-ROM、光盘、硬盘、光纤介质、射频(RF)链路，等等。代码段可以经由诸如因特网、内联网等的计算机网络被下载。

还需要说明的是，本发明中提及的示例性实施例，基于一系列的步骤或者装置描述一些方法或系统。但是，本发明不局限于上述步骤的顺序，也就是说，可以按照实施例中提及的顺序执行步骤，也可以不同于实施例中的顺序，或者若干步骤同时执行。

本发明中，针对一个实施方式描述和/或例示的特征，可以在一个或更多个其它实施方式中以相同方式或以类似方式使用，和/或与其他实施方式的特征相结合或代替其他实施方式的特征。

以上所述仅为本发明的优选实施例而已，并不用于限制本发明，对于本领域的技术人员来说，本发明实施例可以有各种更改和变化。凡在本发明的精神和原则之内，所作的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。