Nothing Special   »   [go: up one dir, main page]

CN104142958B - 一种键值对系统中数据的存储方法和相关装置 - Google Patents

一种键值对系统中数据的存储方法和相关装置 Download PDF

Info

Publication number
CN104142958B
CN104142958B CN201310172455.7A CN201310172455A CN104142958B CN 104142958 B CN104142958 B CN 104142958B CN 201310172455 A CN201310172455 A CN 201310172455A CN 104142958 B CN104142958 B CN 104142958B
Authority
CN
China
Prior art keywords
data
key
value
fragment
information
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Active
Application number
CN201310172455.7A
Other languages
English (en)
Other versions
CN104142958A (zh
Inventor
潘锋烽
张子刚
熊劲
岳银亮
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Huawei Technologies Co Ltd
Institute of Computing Technology of CAS
Original Assignee
Huawei Technologies Co Ltd
Institute of Computing Technology of CAS
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Huawei Technologies Co Ltd, Institute of Computing Technology of CAS filed Critical Huawei Technologies Co Ltd
Priority to CN201310172455.7A priority Critical patent/CN104142958B/zh
Publication of CN104142958A publication Critical patent/CN104142958A/zh
Application granted granted Critical
Publication of CN104142958B publication Critical patent/CN104142958B/zh
Active legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Classifications

    • GPHYSICS
    • G06COMPUTING; CALCULATING OR COUNTING
    • G06FELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/20Information retrieval; Database structures therefor; File system structures therefor of structured data, e.g. relational data
    • G06F16/22Indexing; Data structures therefor; Storage structures
    • G06F16/2228Indexing structures
    • G06F16/2246Trees, e.g. B+trees
    • GPHYSICS
    • G06COMPUTING; CALCULATING OR COUNTING
    • G06FELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/20Information retrieval; Database structures therefor; File system structures therefor of structured data, e.g. relational data
    • G06F16/22Indexing; Data structures therefor; Storage structures
    • G06F16/2219Large Object storage; Management thereof

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Software Systems (AREA)
  • Data Mining & Analysis (AREA)
  • Databases & Information Systems (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Information Retrieval, Db Structures And Fs Structures Therefor (AREA)

Abstract

本发明实施例公开了一种键值对系统中数据的存储方法和相关装置,可提高对Value数据的存储操作效率。该方法包括:判断键值对中Value数据的数据量是否超过数据阈值;若Value数据的数据量没有超过数据阈值,对Value数据进行切片,得到M个分片内容;根据M个分片内容对N个分片内容生成分片信息,分片信息包括:对Value数据分片的个数、N个分片内容中每个分片内容的偏移地址、N个分片内容中每个分片内容的序列号ID、(M-N)个分片内容;将Key数据和分片信息存储在基于日志结构的合并树LSM‑Tree中,将N个分片内容存储在键值对数据库中,Key数据与分片信息相对应。

Description

一种键值对系统中数据的存储方法和相关装置
技术领域
本发明涉及计算机技术领域,尤其涉及一种键值对系统中数据的存储方法和相关装置。
背景技术
LSM-Tree(The Log-Structured Merge-Tree,基于日志结构的合并树)是在键值对(K-V,Key-Value)存储系统中针对频繁更新Value(例如频繁插入或删除)而引入的索引机制,可以应用于查询Value的频率远低于更新Value的频率的场景,例如历史记录表和日志文件等。
LSM-Tree的实现方法是:将对Value数据的更新保存在内存中,当内存中保存的Value达到指定的阈值后将这些更新内容批量地写入到磁盘中。如图1-a和图1-b所示,具体来说,LSM-Tree通过两层有序数据集(C0树和C1树)或者多层有序数据集(C0树,C1树,…,Ck树)对索引变更进行延迟及批量处理,并通过类似于归并排序的方式高效地将磁盘上的多个有序数据集进行合并。其中两层结构和多层结构的LSM-Tree工作原理是相同的,即通过延迟和批处理,将最近更新的数据记录优先放到C0树(全内存数据结构)中去,只有当某一层次的大小达到一定阈值后,才会把其中一部分记录迁移到更高一级的层次中去,这个过程为轮询合并(rolling merge),因此在所有的层次之间,即(Ci-1,Ci)之间都有一个异步的rolling merge过程负责在Ci-1树超过阈值大小时,将它的部分数据记录移到Ci树中,从而更新高一级层次中旧的、过时的数据记录,因此较新的数据记录会在多个层次的树间移动,直至被更新的数据记录被替代或删除。
在现有的键值对存储系统中,通常采用如上说明的LSM-Tree的索引数据结构,但是现有的这种LSM-Tree中一个Ci树(i为小于k的任意一个值)在更新Value数据时都会带来输入输出(I/O,Input/Output)端口的开销,当一个Value数据的数据量很大时,大数据量的Value数据在rolling merge过程中需要在不同层次的数据集之间移动,由此将产生很大的I/O端口的开销,必然降低对整体的Value数据的存储操作效率。
发明内容
本发明实施例提供了一种键值对系统中数据的存储方法和相关装置,用于以较小的I/O端口的开销来存储Value数据,提高对Value数据的存储操作效率。
为解决上述技术问题,本发明实施例提供以下技术方案:
第一方面,本发明实施例提供一种键值对系统中数据的存储方法,包括:
判断键值对中Value数据的数据量是否超过数据阈值,所述键值对包括Key数据和与所述Key数据对应的Value数据;
若所述Value数据的数据量没有超过数据阈值,对所述Value数据进行切片,得到M个分片内容,所述M为大于1的自然数,所述M个分片内容为分片后的所述Value数据的数据内容信息;
根据所述M个分片内容对N个分片内容生成分片信息,所述分片信息包括:对所述Value数据分片的个数、所述N个分片内容中每个分片内容的偏移地址、所述N个分片内容中每个分片内容的序列号ID、(M-N)个分片内容,所述N为大于0自然数,且所述N小于或等于所述M;
将所述Key数据和所述分片信息存储在基于日志结构的合并树LSM-Tree中,将所述N个分片内容存储在键值对数据库中,所述Key数据与所述分片信息相对应。
结合第一方面,在第一方面的第一种可能的实现方式中,所述方法还包括:
若所述Value数据的数据量超过数据阈值,将所述键值对存储在所述LSM-Tree中。
结合第一方面,在第一方面的第二种可能的实现方式中,所述将所述Key数据和所述分片信息存储在基于日志结构的合并树LSM-Tree中包括:
将所述Key数据和所述分片信息存储在第一有序数据集中,所述第一有序数据集位于内存memory中;
当所述第一有序数据集超过合并阈值时,将第二有序数据集中Key数据对应的分片信息更新为所述第一有序数据集中与所述Key数据对应的分片信息,所述第二有序数据集位于磁盘中。
结合第一方面的第二种可能的实现方式,在第一方面的第三种可能的实现方式中,所述将第二有序数据集中所述Key数据对应的分片信息更新为所述第一有序数据集中与所述Key数据对应的分片信息,之后还包括:
将所述第一有序数据集中的所述Key数据以及与所述Key数据对应的分片信息删除。
结合第一方面,在第一方面的第四种可能的实现方式中,所述将所述N个分片内容存储在键值对数据库中之后还包括:
获取第一Value数据中需要读取的数据长度、所述第一Value数据中需要读取的数据偏移地址、所述第一Value数据对应的第一Key数据,所述第一Value数据为当前需要读取的Value数据;
根据所述第一Key数据在所述LSM-Tree中查找所述第一Key数据对应的第一分片信息;
根据所述第一Value数据中需要读取的数据偏移地址、所述第一Value数据中需要读取的数据长度和所述第一Key数据对应的第一分片信息从所述LSM-Tree和/或所述键值对数据库中读取出所述第一Value数据中需要读取的数据。
结合第一方面的第四种可能的实现方式,在第一方面的第五种可能的实现方式中,所述根据所述第一Value数据中需要读取的数据偏移地址、所述第一Value数据中需要读取的数据长度和所述第一Key数据对应的第一分片信息从所述LSM-Tree和/或所述键值对数据库中读取出所述第一Value数据中需要读取的数据之后还包括:
在已经读取出的数据所在的分片内容中将所述已经读取出的数据替换为更新数据;
对所述第一Value数据中已经更新后的各个分片内容重新生成第一分片信息;
将重新生成的第一分片信息存储在所述LSM-Tree中。
结合第一方面,在第一方面的第六种可能的实现方式中,所述将所述N个分片内容存储在键值对数据库中之后还包括:
获取第二Value数据中需要插入的数据长度、所述第二Value数据中需要插入的数据偏移地址、所述第二Value数据对应的第二Key数据;
根据所述第二Key数据在所述LSM-Tree中查找所述第二Key数据对应的第二分片信息;
根据所述第二Value数据中需要插入的数据偏移地址和所述第二Key数据对应的第二分片信息从所述LSM-Tree和/或所述键值对数据库中读取出所述第二Value数据中需要插入的数据偏移地址所在的分片内容;
在所述第二Value数据中需要插入的数据偏移地址所在的分片内容中插入需要插入的数据;
对第二Value数据中插入数据后的各个分片内容重新生成第二分片信息,将插入数据后的第二Value数据中需要插入的数据偏移地址所在的分片内容携带在重新生成的第二分片信息中,将重新生成的第二分片信息存储到所述LSM-Tree中;或,执行以下步骤:对第二Value数据中插入数据后的各个分片内容重新生成第二分片信息,将重新生成的第二分片信息存储在所述LSM-Tree中,将插入数据后的第二Value数据中需要插入的数据偏移地址所在的分片内容存储到所述键值对数据库中。
第二方面,本发明实施例还提供了一种键值对系统中数据的存储装置,包括:
判断模块,用于判断键值对中Value数据的数据量是否超过数据阈值,所述键值对包括Key数据和与所述Key数据对应的Value数据;
切片模块,用于当所述Value数据的数据量没有超过数据阈值时,对所述Value数据进行切片,得到M个分片内容,所述M为大于1的自然数,所述M个分片内容为分片后的所述Value数据的数据内容信息;
获取模块,用于根据所述M个分片内容对N个分片内容生成分片信息,所述分片信息包括:对所述Value数据分片的个数、所述N个分片内容中每个分片内容的偏移地址、所述N个分片内容中每个分片内容的序列号ID、(M-N)个分片内容,所述N为大于0自然数,且所述N小于或等于所述M;
存储模块,用于将所述Key数据和所述分片信息存储在基于日志结构的合并树LSM-Tree中,将所述N个分片内容存储在键值对数据库中,所述Key数据与所述分片信息相对应。
结合第二方面,在第二方面的第一种可能的实现方式中,所述存储模块,还用于当所述Value数据的数据量超过数据阈值时,将所述键值对存储在所述LSM-Tree中。
结合第二方面,在第二方面的第二种可能的实现方式中,所述存储模块包括:
存储子模块,用于将所述Key数据和所述分片信息存储在第一有序数据集中,所述第一有序数据集位于内存memory中;
合并子模块,用于当所述第一有序数据集超过合并阈值时,将第二有序数据集中Key数据对应的分片信息更新为所述第一有序数据集中与所述Key数据对应的分片信息,所述第二有序数据集位于磁盘中。
结合第二方面的第二种可能的实现方式,在第二方面的第三种可能的实现方式中,所述装置还包括:删除模块,用于将所述第一有序数据集中的所述Key数据以及与所述Key数据对应的分片信息删除。
结合第二方面,在第二方面的第四种可能的实现方式中,所述装置还包括:查找模块、读取模块,其中,
所述获取模块,还用于获取第一Value数据中需要读取的数据长度、所述第一Value数据中需要读取的数据偏移地址、所述第一Value数据对应的第一Key数据,所述第一Value数据为当前需要读取的Value数据;
所述查找模块,用于根据所述第一Key数据在所述LSM-Tree中查找所述第一Key数据对应的第一分片信息;
所述读取模块,用于根据所述第一Value数据中需要读取的数据偏移地址、所述第一Value数据中需要读取的数据长度和所述第一Key数据对应的第一分片信息从所述LSM-Tree和/或所述键值对数据库中读取出所述第一Value数据中需要读取的数据。
结合第二方面的第四种可能的实现方式,在第二方面的第五种可能的实现方式中,所述装置还包括:更新模块,其中,
所述更新模块,用于在已经读取出的数据所在的分片内容中将所述已经读取出的数据替换为更新数据;
所述获取模块,还用于对所述第一Value数据中已经更新后的各个分片内容重新生成第一分片信息;
所述存储模块,还用于将重新生成的第一分片信息存储在所述LSM-Tree中。
结合第二方面,在第二方面的第六种可能的实现方式中,所述装置还包括:查找模块、读取模块、插入模块,其中,
所述获取模块,还用于获取第二Value数据中需要插入的数据长度、所述第二Value数据中需要插入的数据偏移地址、所述第二Value数据对应的第二Key数据;
所述查找模块,用于根据所述第二Key数据在所述LSM-Tree中查找所述第二Key数据对应的第二分片信息;
所述读取模块,用于根据所述第二Value数据中需要插入的数据偏移地址和所述第二Key数据对应的第二分片信息从所述LSM-Tree和/或所述键值对数据库中读取出所述第二Value数据中需要插入的数据偏移地址所在的分片内容;
所述插入模块,用于在所述第二Value数据中需要插入的数据偏移地址所在的分片内容中插入需要插入的数据;
所述获取模块,还用于对第二Value数据中插入数据后的各个分片内容重新生成第二分片信息,将插入数据后的第二Value数据中需要插入的数据偏移地址所在的分片内容携带在重新生成的第二分片信息中;所述存储模块,还用于将重新生成的第二分片信息存储到所述LSM-Tree中;或,所述获取模块,还用于对第二Value数据中插入数据后的各个分片内容重新生成第二分片信息;所述存储模块,还用于将重新生成的第二分片信息存储在所述LSM-Tree中,将插入数据后的第二Value数据中需要插入的数据偏移地址所在的分片内容存储到所述键值对数据库中。
从以上技术方案可以看出,本发明实施例具有以下优点:
在本发明实施例中,首先判断键值对中Value数据的数据量是否超过数据阈值,当Value数据的数据量超过数据阈值时,对Value数据进行切片,得到M个分片内容,针对M个分片内容的部分分片内容生成分片信息,将其余的分片内容携带在分片信息,最后将分片信息和Key数据存储在LSM-Tree中,将生成有分片信息的部分分片内容存储在键值对数据库中。由于分片内容可以存储在键值对数据库中,那么这些分片内容就不需要在rollingmerge过程中在不同层次的数据集之间移动,由此降低了I/O端口的开销,提高对Value数据的存储操作效率。并且本发明实施例中可以灵活将分片后的分片内容存储在键值对数据库中,也可以以分片信息的方式存储在LSM-Tree中,提高了键值对系统的存储灵活性,便于用户的使用。
附图说明
为了更清楚地说明本发明实施例中的技术方案,下面将对实施例描述中所需要使用的附图作简单地介绍,显而易见地,下面描述中的附图仅仅是本发明的一些实施例,对于本领域的技术人员来讲,还可以根据这些附图获得其他的附图。
图1-a为现有技术中存在的LSM-Tree通过两层有序数据集对索引变更进行延迟及批量处理的示意图;
图1-b为现有技术中存在的LSM-Tree通过多层有序数据集对索引变更进行延迟及批量处理的示意图;
图2为本发明实施例中提供的一种键值对系统中数据的存储方法的流程方框示意图;
图3-a为本发明实施例中提供的另一种键值对系统中数据的存储方法的流程方框示意图;
图3-b为本发明实施例中提供的一种键值对系统中数据的存储方法的流程方框示意图;
图4-a为现有技术中将将键值对存储在LSM-Tree中的示意图;
图4-b为本发明实施例中对Key数据、分片信息和分片内容分别进行存储的一种实现方式示意图;
图4-c为本发明实施例中对Key数据、分片信息和分片内容分别进行存储的另一种实现方式示意图;
图4-d为本发明实施例中大对象的分片信息参与rolling merge过程的实现方式示意图;
图5-a为本发明实施例提供的一种键值对系统中数据的存储装置的组成结构示意图;
图5-b为本发明实施例提供的另一种键值对系统中数据的存储装置的组成结构示意图;
图5-c为本发明实施例提供的另一种键值对系统中数据的存储装置的组成结构示意图;
图6为本发明实施例提供的另一种键值对系统中数据的存储装置的组成结构示意图。
具体实施方式
本发明实施例提供了一种键值对系统中数据的存储方法和相关装置,用于以较小的I/O端口的开销来存储Value数据,提高对Value数据的存储操作效率。
为使得本发明的发明目的、特征、优点能够更加的明显和易懂,下面将结合本发明实施例中的附图,对本发明实施例中的技术方案进行清楚、完整地描述,显然,下面所描述的实施例仅仅是本发明一部分实施例,而非全部实施例。基于本发明中的实施例,本领域的技术人员所获得的所有其他实施例,都属于本发明保护的范围。
本发明的说明书和权利要求书及上述附图中的术语“第一”、“第二”等是用于区别类似的对象,而不必用于描述特定的顺序或先后次序。应该理解这样使用的术语在适当情况下可以互换,这仅仅是描述本发明的实施例中对相同属性的对象在描述时所采用的区分方式。
以下分别进行详细说明。
本发明键值对系统中的数据的存储方法的一个实施例,可以包括:判断键值对中Value数据的数据量是否超过数据阈值,上述键值对包括Key数据和与上述Key数据对应的Value数据;若上述Value数据的数据量没有超过数据阈值,对上述Value数据进行切片,得到M个分片内容,上述M为大于1的自然数,上述M个分片内容为分片后的上述Value数据的数据内容信息;根据上述M个分片内容对N个分片内容生成分片信息,上述分片信息包括:对上述Value数据分片的个数、上述N个分片内容中每个分片内容的偏移地址、上述N个分片内容中每个分片内容的序列号ID、(M-N)个分片内容,上述N为大于0自然数,且上述N小于或等于上述M;将上述Key数据和上述分片信息存储在基于日志结构的合并树LSM-Tree中,将上述N个分片内容存储在键值对数据库中,上述Key数据与上述分片信息相对应。
请参阅图2所示,本发明一个实施例提供的键值对系统中数据的存储方法,可以包括:
201、判断键值对中Value数据的数据量是否超过数据阈值。
其中,上述键值对包括Key数据和与上述Key数据对应的Value数据。
在本发明的一些实施例中,键值对系统中每一个键值对通常可以表示为(Key/Value),每一个键值对包括Key数据和与上述Key数据对应的Value数据。另外,一个Key/Value对也可以称之为一个对象。通常Key数据占用的数据量较少,但是对于Value数据则可能占用较少的数据量,也可能占用较多的数据量,本发明实施例中可以针对Value数据预设一个数据阈值,针对Value数据的数据量与数据阈值的关系,采用灵活的存储方式,以提高键值对系统中数据的存储效率,其中数据阈值可以根据用户的需求来灵活设定该阈值的取值大小,也可以根据系统的内存(memory)容量来设置,还可以基于Value数据的属性信息来设定,并且设定数据阈值之后,还可以根据各种信息灵活的调整该阈值的大小,此处仅作说明,不做限定。
202、若上述Value数据的数据量没有超过数据阈值,对上述Value数据进行切片,得到M个分片内容。
其中,上述M为大于1的自然数,上述M个分片内容为分片后的上述Value数据的数据内容信息。
在本发明的一些实施例中,若上述Value数据的数据量没有超过数据阈值,可以将Value数据分切为多个片,从而得到多个分片内容,为了便于描述,表示为切片得到M个分片内容,并且指明M为大于1的自然数,则这M个分片内容就是Value数据的数据内容信息。其中,对Value数据做数据切片可以有多种,例如,可以设置切片大小(FRAGMENT_SIZE),则对Value数据就可以按照这个切片大小分割为多个分片内容,另外还可以预先设置切片算法,根据该切片算法对Value数据进行切片。
203、根据上述M个分片内容对N个分片内容生成分片信息。
其中,生成的上述分片信息包括:对上述Value数据分片的个数、上述N个分片内容中每个分片内容的偏移地址、上述N个分片内容中每个分片内容的序列号ID、(M-N)个分片内容,上述N为大于0自然数,且上述N小于或等于上述M。
在本发明的实施例中,通过上述指明的切片信息包括的内容描述了步骤202中如何生成分片信息。需要说明的是,本发明实施例中,为了提高键值对系统中存储数据的灵活性,根据M个分片内容对N个分片内容生成分片信息,并且指明N为大于零的自然数,N同时满足小于或者等于M。也就是说,当N的取值与M相等时,本发明实施例中步骤202具体可以描述为对M个分片内容生成分片信息,即对切片后得到的全部数据内容都生成了分片信息,当N的取值小于M时,本发明实施例中步骤202具体可以描述为对M个分片内容中的部分分片内容生成分片信息,而对于其余部分的分片内容,则可以携带在分片信息中。例如,Value数据的数据量为3.2MB,并且设定FRAGMENT_SIZE的取值为1MB,则该Value数据可以被分为4个片,前3个分片内容的大小都是1MB,第4个分片内容的大小为0.2MB,则本发明实施例中可以针对4个分片内容生成分片信息,也可以针对前3个分片内容生成分片信息,而将第4个分片内容(数据量为0.2MB,也可以称之为“尾部数据”)携带在针对前3个分片内容生成的分片信息中,故本发明实施例中可以灵活的实现生成分片信息。
在本发明的一些实施例中,分片信息中包括有Value数据分片的个数,并且也包括有N个分片内容中每个分片内容的序列号(ID,IDentity),通过ID可以方便的查找到各个分片内容,并且在分片信息中还包括有N个分片内容中每个分片内容的偏移地址(offset),通过偏移地址就可以在键值对数据库中准确的获取到分片内容。
204、将上述Key数据和上述分片信息存储在基于日志结构的合并树(LSM-Tree,The Log-Structured Merge-Tree)中,将上述N个分片内容存储在键值对数据库中。
其中,上述Key数据与上述分片信息相对应。
在本发明实施例中,生成分片信息之后,将Key数据和Value数据分开存储,将Key数据和分片信息存储在LSM-Tree中,而将N个分片内容存储在键值对数据库中,由于只有Key数据和分片信息存储在LSM-Tree中,而N个分片内容存储在键值对数据库(DB,DataBase)中,故N个分片内容不会参与rolling merge过程,而只有Key数据和分片信息会参与rolling merge过程,故N个分片内容就不需要在不同层次的数据集之间移动,从而可以避免对I/O端口造成的较大开销,提高了对Value数据的存储操作效率。
在本发明的一些实施例中,键值对数据库可以存储在裸设备或者文件系统中,或者直接存储在磁盘中。
在本发明的一些实施例中,将Key数据和分片信息存储在LSM-Tree中,具体可以按照如下方式方式:将上述Key数据和上述分片信息存储在第一有序数据集中,上述第一有序数据集位于内存(memory)中;当上述第一有序数据集超过合并阈值时,将第二有序数据集中Key数据对应的分片信息更新为上述第一有序数据集中与上述Key数据对应的分片信息,上述第二有序数据集位于磁盘中。如前述的图1-a所示,第一有序数据集具体可以指的是C0树,第二有序数据集具体可以指的是C1树,Key数据和分片信息首先存储在C0树中,然后当C0树满足合并阈值的条件时,将C1树中Key数据对应的分片信息更新为C0树中该Key数据对应的分片信息。若在磁盘中还存储在有多个有序数据集例如第三有序数据集和第四有序数据集时,可以按照前述的方式对Key数据和分片信息进行rolling merge过程,从而将Key数据和分片信息迁移到更高一级的有序数据集中。
在本发明的另一些实施例中,将第二有序数据集中Key数据对应的分片信息更新为上述第一有序数据集中与上述Key数据对应的分片信息之后,还可以将上述第一有序数据集中的上述Key数据以及与上述Key数据对应的分片信息删除。以此方式对第一有序数据集中的“旧数据”进行删除,从而提高空间利用率。
由上可见,首先判断键值对中Value数据的数据量是否超过数据阈值,当Value数据的数据量超过数据阈值时,对Value数据进行切片,得到M个分片内容,针对M个分片内容的部分分片内容生成分片信息,将其余的分片内容携带在分片信息,最后将分片信息和Key数据存储在LSM-Tree中,将生成有分片信息的部分分片内容存储在键值对数据库中。由于分片内容可以存储在键值对数据库中,那么这些分片内容就不需要在rolling merge过程中在不同层次的数据集之间移动,由此降低了I/O端口的开销,提高对Value数据的存储操作效率。并且本发明实施例中可以灵活将分片后的分片内容存储在键值对数据库中,也可以以分片信息的方式存储在LSM-Tree中,提高了键值对系统的存储灵活性,便于用户的使用。
接下来介绍本发明键值对系统中的数据的存储方法的另一个实施例,如图3-a所示,可以包括:
301、判断键值对中Value数据的数据量是否超过数据阈值,若上述Value数据的数据量超过数据阈值执行步骤302,若上述Value数据的数据量没有超过数据阈值执行步骤303。
302、若Value数据的数据量超过数据阈值,将键值对存储在LSM-Tree中。
303、若上述Value数据的数据量没有超过数据阈值,对上述Value数据进行切片,得到M个分片内容。
304、根据上述M个分片内容对N个分片内容生成分片信息。
305、将上述Key数据和上述分片信息存储在LSM-Tree中,将上述N个分片内容存储在键值对数据库中。
其中,步骤303至305与前述实施例中步骤202至204的实现方式相类似,此处不再赘述。
306、获取第一Value数据中需要读取的数据长度、上述第一Value数据中需要读取的数据偏移地址、上述第一Value数据对应的第一Key数据。
其中,上述第一Value数据为当前需要读取的Value数据。
步骤301至305描述的本发明实施例对数据的存储过程,当存储过程完成之后,当需要读取Value数据时,可以按照本发明实施例中描述的步骤306至308实现对Value数据的读取。并且需要说明的是,现有技术中,由于整个Value数据都被存储在LSM-Tree中,当每次需要读取Value数据中的部分字段内容时,必须要把整个Value数据都从LSM-Tree中读出,造成I/O端口的较大开销,本发明实施例中由于对Value数据做了切片处理,故每次在读取Value数据的部分字段内容时不需要将整个Value数据都读出,而是可以精确定位需要读取数据的位置按照需要读取的数据的长度来实现局部范围内的读取,如此就可以减小使用I/O端口带来的开销,从而提高数据的读取效率。
在本发明实施例中,为了便于描述需要被读取的Value数据,将其定义为第一Value数据,故可以首先获取到第一Value数据中需要读取的数据长度、需要读取的数据偏移地址、该第一Value数据对应的第一Key数据。
307、根据上述第一Key数据在上述LSM-Tree中查找上述第一Key数据对应的第一分片信息。
在本发明的一些实施例中,由于Key数据和分片信息都存储在LSM-Tree中,故获取到第一Value数据中需要读取的数据长度、需要读取的数据偏移地址之后,就可以根据第一Key数据在LSM-Tree中查找其对应的第一分片信息,其中,第一Key数据指的就是与第一Value所对应的Key数据,为便于描述将其定义为“第一Key数据”,同样的第一分片信息也指的是与第一Key数据对应分片信息,为了便于描述将其定义为“第一分片信息”。
308、根据上述第一Value数据中需要读取的数据偏移地址、上述第一Value数据中需要读取的数据长度和上述第一Key数据对应的第一分片信息从上述LSM-Tree和/或上述键值对数据库中读取出上述第一Value数据中需要读取的数据。
当查找到第一分片信息之后,就可以根据第一Value数据中需要读取的数据偏移地址、上述第一Value数据中需要读取的数据长度、第一分片信息从LSM-Tree和/或上述键值对数据库中读取出第一Value数据中需要读取的数据了。其中,在本发明实施例中,由于分片内容可以灵活的存储在键值对数据库中,也可以灵活的以分片信息的形式存储在LSM-Tree中,故当需要读取的第一Value数据所涉及的数据分片内容被存储在键值对数据库中时,此处就需要从键值对数据库中读取到第一Value数据了;故当需要读取的第一Value数据所涉及的数据分片内容被存储在LSM-Tree中时,此处就需要从LSM-Tree中读取到第一Value数据了;故当需要读取的第一Value数据所涉及的数据分片内容被存储在键值对数据库和LSM-Tree中时,此处就需要从键值对数据库和LSM-Tree中读取到第一Value数据了。
在本发明实施例中,描述的步骤306至308描述的是对Value数据中部分数据内容的读取,那么在读取到第一Value数据之后,当还需要将已经读取出的数据进行更新时,还可以包括如下步骤:
309、在已经读取出的数据所在的分片内容中将上述已经读取出的数据替换为更新数据。
其中,读取出第一Value数据中需要读取的数据后,在已经读取出的数据所在的分片内容中将已经读取出的数据替换为更新数据,若已经读取出的数据所在的分片内容存储在LSM-Tree中,则更新数据被写入已经读取出的数据所在的分片内容后,也同样的存储在LSM-Tree中,若已经读取出的数据所在的分片内容存储在键值对数据库中,则更新数据被写入已经读取出的数据所在的分片内容后,也同样的存储在键值对数据库中。
310、对上述第一Value数据中已经更新后的各个分片内容重新生成第一分片信息;
311、将重新生成的第一分片信息存储在上述LSM-Tree中。
由于已经读取出的数据所在的分片内容中已经读取出的数据被替换为更新数据了,也就是说已经读取出的数据所在的分片内容的数据内容发生了改变,故需要对上述第一Value数据中已经更新后的各个分片内容重新生成分片信息,即需要对上述第一Value数据中已经更新后的各个分片内容重新生成第一分片信息,并存储在LSM-Tree中,并且还可以将原来第一Value数据对应的第一分片信息从LSM-Tree中删除掉,以节省存储空间,提高空间利用率。
接下来介绍本发明键值对系统中的数据的存储方法的另一个实施例,如图3-b所示,可以包括:步骤301至305、312至317,其中,
步骤301至305,可参阅前述实施例的描述,此处不再赘述。
步骤312、获取第二Value数据中需要插入的数据长度、上述第二Value数据中需要插入的数据偏移地址、上述第二Value数据对应的第二Key数据。
其中,步骤301至305描述的本发明实施例对数据的存储过程,当存储过程完成之后,当需要在原来的Value数据中插入新的数据内容时,可以按照本发明实施例中描述的步骤312至319实现对Value数据的插入。并且需要说明的是,现有技术中,由于整个Value数据都被存储在LSM-Tree中,当每次需要在原来存储在LSM-Tree中的Value数据插入新的Value数据时,必须要把原来的整个Value数据都从LSM-Tree中读出,造成I/O端口的较大开销,本发明实施例中由于对Value数据做了切片处理,故每次在需要插入新的数据内容时不需要将整个Value数据都读出,而是可以精确定位需要插入新数据内容的位置按照需要插入的新数据内容的长度来实现局部范围内的插入,如此就可以减小使用I/O端口带来的开销,从而提高数据的读取效率。
在本发明实施例中,为了便于描述需要被插入的Value数据,将其定义为第二Value数据,故可以首先获取到第二Value数据中需要插入的数据长度、第二Value数据中需要插入的数据偏移地址、第二Value数据对应的第二Key数据。
313、根据上述第二Key数据在上述LSM-Tree中查找上述第二Key数据对应的第二分片信息。
在本发明的一些实施例中,由于Key数据和分片信息都存储在LSM-Tree中,故获取到第二Value数据中需要插入的数据长度、需要插入的数据偏移地址之后,就可以根据第二Key数据在LSM-Tree中查找其对应的第二分片信息,其中,第二Key数据指的就是与第二Value所对应的Key数据,为便于描述将其定义为“第二Key数据”,同样的第二分片信息也指的是与第二Key数据对应分片信息,为了便于描述将其定义为“第二分片信息”。
314、根据上述第二Value数据中需要插入的数据偏移地址和上述第二Key数据对应的第二分片信息从上述LSM-Tree和/或上述键值对数据库中读取出上述第二Value数据中需要插入的数据偏移地址所在的分片内容。
其中,在本发明实施例中,由于分片内容可以灵活的存储在键值对数据库中,也可以灵活的以分片信息的形式存储在LSM-Tree中,故当第二Value数据中需要插入的数据偏移地址所涉及的数据分片内容被存储在键值对数据库中时,此处就需要从键值对数据库中读取到相应的分片内容了;故当第二Value数据中需要插入的数据偏移地址所涉及的数据分片内容被存储在LSM-Tree中时,此处就需要从LSM-Tree中读取到相应的分片内容了;故当第二Value数据中需要插入的数据偏移地址所涉及的数据分片内容被存储在键值对数据库和LSM-Tree中时,此处就需要从键值对数据库和LSM-Tree中读取到相应的分片内容了。
315、在上述第二Value数据中需要插入的数据偏移地址所在的分片内容中插入需要插入的数据。
按照第二Value数据中需要插入的数据偏移地址所在的分片内容中插入需要插入的数据之后,可以执行步骤316和317,也可以执行步骤318和319。
316、对第二Value数据中插入数据后的各个分片内容重新生成第二分片信息,将插入数据后的第二Value数据中需要插入的数据偏移地址所在的分片内容携带在重新生成的第二分片信息中。
其中,若第二Value数据中需要插入的数据偏移地址所在的分片内容原来存储在LSM-Tree中,则执行步骤316,将插入数据后的第二Value数据中需要插入的数据偏移地址所在的分片内容携带在重新生成的第二分片信息中,然后执行步骤317。
317、将重新生成的第二分片信息存储到所述LSM-Tree中。
318、对第二Value数据中插入数据后的各个分片内容重新生成第二分片信息。
其中,若第二Value数据中需要插入的数据偏移地址所在的分片内容原来存储在键值对数据库中,则执行步骤318,对第二Value数据中插入数据后的各个分片内容重新生成第二分片信息。
319、将重新生成的第二分片信息存储在上述LSM-Tree中,将插入数据后的第二Value数据中需要插入的数据偏移地址所在的分片内容存储到上述键值对数据库中。
由上可见,首先判断键值对中Value数据的数据量是否超过数据阈值,当Value数据的数据量超过数据阈值时,对Value数据进行切片,得到M个分片内容,针对M个分片内容的部分分片内容生成分片信息,将其余的分片内容携带在分片信息,最后将分片信息和Key数据存储在LSM-Tree中,将生成有分片信息的部分分片内容存储在键值对数据库中。由于分片内容可以存储在键值对数据库中,那么这些分片内容就不需要在rolling merge过程中在不同层次的数据集之间移动,由此降低了I/O端口的开销,提高对Value数据的存储操作效率。并且本发明实施例中可以灵活将分片后的分片内容存储在键值对数据库中,也可以以分片信息的方式存储在LSM-Tree中,提高了键值对系统的存储灵活性,便于用户的使用。
为便于更好的理解和实施本发明实施例的上述方案,下面举例几个应用场景来进行具体说明。
请参阅如图4-a、图4-b、图4-c所示,本发明键值对系统中数据的存储方法的另一个实施例,可以包括:
假设键值对中Value数据的数据量为4.7MB,假设设定的数据阈值为2MB,则该键值对中Value数据可以定义为大对象,如图4-a为按照现有技术的存储方法,直接将大对象的Value数据与Key数据一起存入到LSM-Tree中。
在本发明实施例中,按照以下处理方法:将该对象的Value数据切分成5个分片内容,其中FRAGMENT_SIZE为1MB,将前4个分片内容存入键值对数据库中,键值对数据库保存在裸设备或者文件系统中,而对第5个分片内容即剩余0.7MB的尾部数据可以按照如下两种方式进行处理:
(1)、针对这5个分片内容生成分片信息,并将Key数据和分片信息一起保存在LSM-Tree中,将前4个分片内容连同尾部数据0.7MB分别作为一个分片内容存储到键值对数据库中,即切片得到的5个分片内容都存储到了键值对数据库中,如图4-b所示,为在LSM-Tree中大对象的索引组织方式,其中包括有Key数据和分片信息,该分片信息具体指的是分片信息1、分片信息2、分片信息3、分片信息4、分片信息5,而各个分片信息对应的分片内容则存储在键值对数据库中,其中,分片信息1对应的是分片内容1、分片信息2对应的是分片内容2、分片信息3对应的是分片内容3、分片信息4对应的是分片内容4、分片信息5对应的是分片内容5(也就是尾部数据)。故在LSM-Tree中存储的数据量是小于4.7MB的,故在LSM-Tree中进行rollingmerge过程时可以减少I/O接口的使用开销,提高对数据的存储效率。
(2)、针对前4个分片内容生成分片信息,并直接将尾部数据携带在针对前4个分片内容生成的分片信息中,并将Key数据和分片信息一起保存在LSM-Tree中,将前4个分片内容存储到键值对数据库中,即切片得到的前4个分片内容存储到了键值对数据库中,而尾部数据被携带在分片信息中存储在LSM-Tree中,如图4-c所示,为在LSM-Tree中大对象的索引组织方式,其中包括有Key数据和分片信息,该分片信息具体指的是分片信息1、分片信息2、分片信息3、分片信息4和尾部数据,而各个分片信息对应的分片内容则存储在键值对数据库中,其中,分片信息1对应的是分片内容1、分片信息2对应的是分片内容2、分片信息3对应的是分片内容3、分片信息4对应的是分片内容4。故在LSM-Tree中存储的数据量是小于4.7MB的,故在LSM-Tree中进行rolling merge过程时可以减少I/O接口的使用开销,提高对数据的存储效率。
以上实施例介绍了对数据的存储过程,当存储过程完成之后,当需要读取Value数据时,请参阅如下对数据的读取过程的说明:
仍以Value数据为大对象时为例,需要读取对象A中的Value数据1,需要读取的Value数据1的offset=3M+50K开,需要读取的Value数据1的长度为16KB,需要读取的Value数据1对应的Key数据为k1,具体的可以调用如下接口实现:get(k1,&buffer,3196928,16384)实现,该读取操作过程如下:
首先在LSM-Tree中查找Key数据为k1的对象,获取该对象对应的分片信息为信息a;
然后,根据提供的offset(3M+50K)、需要读取的数据长度(16KB)以及信息a,确定需要从哪些分片内容上读取,若存储的数据如前述图4-b所示,此处仅需要读取分片信息4所对应的分片内容4。
接下来,获取分片信息4之后,从键值对数据库中读取分片内容4中从offset(3M+50K)开始,读取数据长度为16KB所对应的数据内容。
在现有技术中,都会将大对象的整个Value数据都读取出,上层应用程序只有通过自身的操作才能获取相应范围的数据内容,导致读取数据时在效率上是非常低效的。而本发明实施例中可以实现局部范围读操作,其中局部范围主要指的是Value数据中的某一个范围。当用户需要读取一个较大Value数据中的某一个范围内的数据内容时,本发明实施例就可以实现局部范围读操作,从而可以减少使用I/O接口带来的开销。
当读取了16KB所对应的数据内容后,本发明实施例中,若需要对16KB所对应的数据内容进行修改,修改完之后,将修改后的16KB所对应的数据内容存储到键值对数据库中,由于内容发生了修改,故需要重新生成分片信息,假设为信息b,则需要信息b存储在LSM-Tree中,由此就可以实现对Value数据中局部范围内数据内容的修改替换。
以上实施例介绍了对数据的存储过程,当存储过程完成之后,当需要在原来的Value数据中插入Value数据时,请参阅如下对数据的更新过程的说明:
仍以Value数据为大对象时为例,假设该大对象的数据量是3MB+1KB,需要插入的数据长度为20KB数据,需要插入的位置是该大对象的末尾,该大对象的Key数据为k2,具体可以调用如下接口实现:update(k2,&buffer,3146752),该插入操作过程如下:
首先在LSM-Tree中查找Key为k2的对象,获取该对象对应的分片信息为信息c;
然后,如图4-c所示,将分片信息即信息c中的尾部数据与新添加的20KB数据进行拼接,由于此例中拼接完成后的数据的数据量为90KB,小于FRAGMENT_SIZE,因此将其作为新的尾部数据,需要值的是,若拼接之后得到的数据的数据量大于FRAGMENT_SIZE,则会产生一个新的分片内容和新的尾部数据,故需要重新对大对象被分片后各个分片内容重新生成分片信息,重新生成的分片信息中携带有新的尾部数据,将重新生成的分片信息存储到LSM-Tree中,将新的分片内容存储到键值对数据库中。
在现有技术中,都会将大对象的整个Value数据都读取出,然后与新添加的数据进行拼接之后,再将其重新写入,导致插入数据时在效率上是非常低效的。而本发明实施例中可以实现局部范围写操作,其中局部范围主要指的是Value数据中的某一个范围。当用户需要在一个较大Value数据中的某一个范围内插入新的数据时,本发明实施例就可以实现局部范围写操作,从而可以减少使用I/O接口带来的开销。
以上实施例介绍了对数据的存储过程,接下来对大对象的合并(merge)过程进行举例说明,请参阅如下对大对象的合并过程的说明,请参阅如图4-d所示,大对象的分片信息参与rolling merge过程,即Ci-1树的分片信息会更新到Ci树中,从而更新旧的大对象中的分片信息。
首先,对于Ci-1树和Ci树中相同的Key1,将Ci-1树中大对象的分片信息(分别为分片信息1′和分片信息2′)与Ci树中大对象的分片信息(分别为分片信息1、分片信息2、分片信息3)进行比较,将Ci树中大对象原来的旧的分片信息删除,即将Ci-1树中分片信息1′和分片信息2′删除掉,将Ci-1树中的分片信息更新为分片信息1、分片信息2、分片信息3。
其中,LSM-Tree中数据存储的方式为如图4-b中所示,即在LSM-Tree中Ci-1树中只保存有分片信息1、分片信息2、分片信息3,而没有尾部数据。
由上可知,首先判断键值对中Value数据的数据量是否超过数据阈值,当Value数据的数据量超过数据阈值时,对Value数据进行切片,得到M个分片内容,针对M个分片内容的部分分片内容生成分片信息,将其余的分片内容携带在分片信息,最后将分片信息和Key数据存储在LSM-Tree中,将生成有分片信息的部分分片内容存储在键值对数据库中。由于分片内容可以存储在键值对数据库中,那么这些分片内容就不需要在rolling merge过程中在不同层次的数据集之间移动,由此降低了I/O端口的开销,提高对Value数据的存储操作效率。并且本发明实施例中可以灵活将分片后的分片内容存储在键值对数据库中,也可以以分片信息的方式存储在LSM-Tree中,提高了键值对系统的存储灵活性,便于用户的使用。
需要说明的是,对于前述的各方法实施例,为了简单描述,故将其都表述为一系列的动作组合,但是本领域技术人员应该知悉,本发明并不受所描述的动作顺序的限制,因为依据本发明,某些步骤可以采用其他顺序或者同时进行。其次,本领域技术人员也应该知悉,说明书中所描述的实施例均属于优选实施例,所涉及的动作和模块并不一定是本发明所必须的。
为便于更好的实施本发明实施例的上述方案,下面还提供用于实施上述方案的相关装置。
请参阅图5-a所示,本发明实施例提供的一种键值对系统中数据的存储装置500,可以包括:判断模块501、切片模块502、获取模块503、存储模块504,其中,
判断模块501,用于判断键值对中Value数据的数据量是否超过数据阈值,所述键值对包括Key数据和与所述Key数据对应的Value数据;
切片模块502,用于根据判断模块501的判断结果当所述Value数据的数据量没有超过数据阈值时,对所述Value数据进行切片,得到M个分片内容,所述M为大于1的自然数,所述M个分片内容为分片后的所述Value数据的数据内容信息;
获取模块503,用于根据切片模块502得到的所述M个分片内容对N个分片内容生成分片信息,所述分片信息包括:对所述Value数据分片的个数、所述N个分片内容中每个分片内容的偏移地址、所述N个分片内容中每个分片内容的序列号ID、(M-N)个分片内容,所述N为大于0自然数,且所述N小于或等于所述M;
存储模块504,用于将所述Key数据和所述获取模块503获取到的分片信息存储在基于日志结构的合并树LSM-Tree中,将所述切片模块503得到的N个分片内容存储在键值对数据库中,所述Key数据与所述分片信息相对应。
在本发明的一些实施例中,存储模块504,还用于当所述Value数据的数据量超过数据阈值时,将所述键值对存储在所述LSM-Tree中。
请参阅图5-b所示,在本发明的一些实施例中,键值对系统中数据的存储装置500还可包括:查找模块505、读取模块506,其中,
所述获取模块503,还用于获取第一Value数据中需要读取的数据长度、所述第一Value数据中需要读取的数据偏移地址、所述第一Value数据对应的第一Key数据,所述第一Value数据为当前需要读取的Value数据;
所述查找模块505,用于根据所述第一Key数据在所述LSM-Tree中查找所述第一Key数据对应的第一分片信息;
所述读取模块506,用于根据所述第一Value数据中需要读取的数据偏移地址、所述第一Value数据中需要读取的数据长度和所述第一Key数据对应的第一分片信息从所述LSM-Tree和/或所述键值对数据库中读取出所述第一Value数据中需要读取的数据。
在本发明的一些实施例中,键值对系统中数据的存储装置500还可包括:更新模块507,其中,
所述更新模块507,用于在已经读取出的数据所在的分片内容中将所述已经读取出的数据替换为更新数据;
所述获取模块503,还用于对所述第一Value数据中已经更新后的各个分片内容重新生成第一分片信息;
所述存储模块504,还用于将重新生成的第一分片信息存储在所述LSM-Tree中。
在本发明的一些实施例中,存储模块504可包括:
存储子模块5041,用于将所述Key数据和所述分片信息存储在第一有序数据集中,所述第一有序数据集位于内存memory中;
合并子模块5042,用于当所述第一有序数据集超过合并阈值时,将第二有序数据集中Key数据对应的分片信息更新为所述第一有序数据集中与所述Key数据对应的分片信息,所述第二有序数据集位于磁盘中。
在本发明的一些实施例中,键值对系统中数据的存储装置500还可包括:删除模块508,用于将所述第一有序数据集中的所述Key数据以及与所述Key数据对应的分片信息删除。
请参阅图5-c所示,在本发明的一些实施例中,键值对系统中数据的存储装置500还可包括:查找模块505、读取模块506、插入模块509,其中,
所述获取模块503,还用于获取第二Value数据中需要插入的数据长度、所述第二Value数据中需要插入的数据偏移地址、所述第二Value数据对应的第二Key数据;
所述查找模块505,用于根据所述第二Key数据在所述LSM-Tree中查找所述第二Key数据对应的第二分片信息;
所述读取模块506,用于根据所述第二Value数据中需要插入的数据偏移地址和所述第二Key数据对应的第二分片信息从所述LSM-Tree和/或所述键值对数据库中读取出所述第二Value数据中需要插入的数据偏移地址所在的分片内容;
所述插入模块509,用于在所述第二Value数据中需要插入的数据偏移地址所在的分片内容中插入需要插入的数据;
所述获取模块503,还用于对第二Value数据中插入数据后的各个分片内容重新生成第二分片信息,将插入数据后的第二Value数据中需要插入的数据偏移地址所在的分片内容携带在重新生成的第二分片信息中;所述存储模块504,还用于将重新生成的第二分片信息存储到所述LSM-Tree中;或,所述获取模块503,还用于对第二Value数据中插入数据后的各个分片内容重新生成第二分片信息;所述存储模块504,还用于将重新生成的第二分片信息存储在所述LSM-Tree中,将插入数据后的第二Value数据中需要插入的数据偏移地址所在的分片内容存储到所述键值对数据库中。
由上可知,首先判断键值对中Value数据的数据量是否超过数据阈值,当Value数据的数据量超过数据阈值时,对Value数据进行切片,得到M个分片内容,针对M个分片内容的部分分片内容生成分片信息,将其余的分片内容携带在分片信息,最后将分片信息和Key数据存储在LSM-Tree中,将生成有分片信息的部分分片内容存储在键值对数据库中。由于分片内容可以存储在键值对数据库中,那么这些分片内容就不需要在rolling merge过程中在不同层次的数据集之间移动,由此降低了I/O端口的开销,提高对Value数据的存储操作效率。并且本发明实施例中可以灵活将分片后的分片内容存储在键值对数据库中,也可以以分片信息的方式存储在LSM-Tree中,提高了键值对系统的存储灵活性,便于用户的使用。
发明实施例还提供一种计算机存储介质,其中,该计算机存储介质存储有程序,该程序执行包括上述方法实施例中记载的部分或全部布置。
接下来介绍本发明实施例提供的另一种键值对系统中数据的存储装置,请参阅图6所示,键值对系统中数据的存储装置600包括:
输入装置601、输出装置602、处理器603和存储器604(其中存储装置600中的处理器603的数量可以一个或多个,图6中以一个处理器为例)。在本发明的一些实施例中,输入装置601、输出装置602、处理器603和存储器604可通过总线或其它方式连接,其中,图6中以通过总线连接为例。
其中,
处理器603,用于执行如下步骤:判断键值对中Value数据的数据量是否超过数据阈值,所述键值对包括Key数据和与所述Key数据对应的Value数据;若所述Value数据的数据量没有超过数据阈值,对所述Value数据进行切片,得到M个分片内容,所述M为大于1的自然数,所述M个分片内容为分片后的所述Value数据的数据内容信息;根据所述M个分片内容对N个分片内容生成分片信息,所述分片信息包括:对所述Value数据分片的个数、所述N个分片内容中每个分片内容的偏移地址、所述N个分片内容中每个分片内容的序列号ID、(M-N)个分片内容,所述N为大于0自然数,且所述N小于或等于所述M;将所述Key数据和所述分片信息存储在基于日志结构的合并树LSM-Tree中,将所述N个分片内容存储在键值对数据库中,所述Key数据与所述分片信息相对应。
在本发明的一些实施例中,处理器603还用于执行以下步骤:若所述Value数据的数据量超过数据阈值,将所述键值对存储在所述LSM-Tree中。
在本发明的一些实施例中,处理器603还用于执行以下步骤:获取第一Value数据中需要读取的数据长度、所述第一Value数据中需要读取的数据偏移地址、所述第一Value数据对应的第一Key数据,所述第一Value数据为当前需要读取的Value数据;根据所述第一Key数据在所述LSM-Tree中查找所述第一Key数据对应的第一分片信息;根据所述第一Value数据中需要读取的数据偏移地址、所述第一Value数据中需要读取的数据长度和所述第一Key数据对应的第一分片信息从所述LSM-Tree和/或所述键值对数据库中读取出所述第一Value数据中需要读取的数据。
在本发明的一些实施例中,处理器603还用于执行以下步骤:在已经读取出的数据所在的分片内容中将所述已经读取出的数据替换为更新数据;对所述第一Value数据中已经更新后的各个分片内容重新生成第一分片信息;将重新生成的第一分片信息存储在所述LSM-Tree中。
在本发明的一些实施例中,处理器603还用于执行以下步骤:获取第二Value数据中需要插入的数据长度、所述第二Value数据中需要插入的数据偏移地址、所述第二Value数据对应的第二Key数据;根据所述第二Key数据在所述LSM-Tree中查找所述第二Key数据对应的第二分片信息;根据所述第二Value数据中需要插入的数据偏移地址和所述第二Key数据对应的第二分片信息从所述LSM-Tree和/或所述键值对数据库中读取出所述第二Value数据中需要插入的数据偏移地址所在的分片内容;在所述第二Value数据中需要插入的数据偏移地址所在的分片内容中插入需要插入的数据;对第二Value数据中插入数据后的各个分片内容重新生成第二分片信息,将插入数据后的第二Value数据中需要插入的数据偏移地址所在的分片内容携带在重新生成的第二分片信息中;将重新生成的第二分片信息存储到所述LSM-Tree中;或,对第二Value数据中插入数据后的各个分片内容重新生成第二分片信息;将重新生成的第二分片信息存储在所述LSM-Tree中,将插入数据后的第二Value数据中需要插入的数据偏移地址所在的分片内容存储到所述键值对数据库中。
本领域普通技术人员可以理解实现上述实施例方法中的全部或部分步骤是可以通过程序来指令相关的硬件完成,所述的程序可以存储于一种计算机可读存储介质中,上述提到的存储介质可以是只读存储器,磁盘或光盘等。
以上对本发明所提供的一种键值对系统中数据的存储方法和相关装置进行了详细介绍,对于本领域的一般技术人员,依据本发明实施例的思想,在具体实施方式及应用范围上均会有改变之处,综上所述,本说明书内容不应理解为对本发明的限制。

Claims (14)

1.一种键值对系统中数据的存储方法,其特征在于,包括:
判断键值对中Value数据的数据量是否超过数据阈值,所述键值对包括Key数据和与所述Key数据对应的Value数据;
若所述Value数据的数据量没有超过数据阈值,对所述Value数据进行切片,得到M个分片内容,所述M为大于1的自然数,所述M个分片内容为分片后的所述Value数据的数据内容信息;
根据所述M个分片内容对N个分片内容生成分片信息,所述分片信息包括:对所述Value数据分片的个数、所述N个分片内容中每个分片内容的偏移地址、所述N个分片内容中每个分片内容的序列号ID、(M-N)个分片内容,所述N为大于0自然数,且所述N小于或等于所述M;
将所述Key数据和所述分片信息存储在基于日志结构的合并树LSM-Tree中,将所述N个分片内容存储在键值对数据库中,所述Key数据与所述分片信息相对应,所述Key数据和所述分片信息参与所述LSM-Tree的轮询合并过程,所述N个分片内容不参与所述轮询合并过程。
2.根据权利要求1所述的方法,其特征在于,所述方法还包括:
若所述Value数据的数据量超过数据阈值,将所述键值对存储在所述LSM-Tree中。
3.根据权利要求1所述的方法,其特征在于,所述将所述Key数据和所述分片信息存储在基于日志结构的合并树LSM-Tree中包括:
将所述Key数据和所述分片信息存储在第一有序数据集中,所述第一有序数据集位于内存memory中;
当所述第一有序数据集超过合并阈值时,将第二有序数据集中Key数据对应的分片信息更新为所述第一有序数据集中与所述Key数据对应的分片信息,所述第二有序数据集位于磁盘中。
4.根据权利要求3所述的方法,其特征在于,所述将第二有序数据集中所述Key数据对应的分片信息更新为所述第一有序数据集中与所述Key数据对应的分片信息,之后还包括:
将所述第一有序数据集中的所述Key数据以及与所述Key数据对应的分片信息删除。
5.根据权利要求1所述的方法,其特征在于,所述将所述N个分片内容存储在键值对数据库中之后还包括:
获取第一Value数据中需要读取的数据长度、所述第一Value数据中需要读取的数据偏移地址、所述第一Value数据对应的第一Key数据,所述第一Value数据为当前需要读取的Value数据;
根据所述第一Key数据在所述LSM-Tree中查找所述第一Key数据对应的第一分片信息;
根据所述第一Value数据中需要读取的数据偏移地址、所述第一Value数据中需要读取的数据长度和所述第一Key数据对应的第一分片信息从所述LSM-Tree和/或所述键值对数据库中读取出所述第一Value数据中需要读取的数据。
6.根据权利要求5所述的方法,其特征在于,所述根据所述第一Value数据中需要读取的数据偏移地址、所述第一Value数据中需要读取的数据长度和所述第一Key数据对应的第一分片信息从所述LSM-Tree和/或所述键值对数据库中读取出所述第一Value数据中需要读取的数据之后还包括:
在已经读取出的数据所在的分片内容中将所述已经读取出的数据替换为更新数据;
对所述第一Value数据中已经更新后的各个分片内容重新生成第一分片信息;
将重新生成的第一分片信息存储在所述LSM-Tree中。
7.根据权利要求1所述的方法,其特征在于,所述将所述N个分片内容存储在键值对数据库中之后还包括:
获取第二Value数据中需要插入的数据长度、所述第二Value数据中需要插入的数据偏移地址、所述第二Value数据对应的第二Key数据;
根据所述第二Key数据在所述LSM-Tree中查找所述第二Key数据对应的第二分片信息;
根据所述第二Value数据中需要插入的数据偏移地址和所述第二Key数据对应的第二分片信息从所述LSM-Tree和/或所述键值对数据库中读取出所述第二Value数据中需要插入的数据偏移地址所在的分片内容;
在所述第二Value数据中需要插入的数据偏移地址所在的分片内容中插入需要插入的数据;
对第二Value数据中插入数据后的各个分片内容重新生成第二分片信息,将插入数据后的第二Value数据中需要插入的数据偏移地址所在的分片内容携带在重新生成的第二分片信息中,将重新生成的第二分片信息存储到所述LSM-Tree中;或,执行以下步骤:对第二Value数据中插入数据后的各个分片内容重新生成第二分片信息,将重新生成的第二分片信息存储在所述LSM-Tree中,将插入数据后的第二Value数据中需要插入的数据偏移地址所在的分片内容存储到所述键值对数据库中。
8.一种键值对系统中数据的存储装置,其特征在于,包括:
判断模块,用于判断键值对中Value数据的数据量是否超过数据阈值,所述键值对包括Key数据和与所述Key数据对应的Value数据;
切片模块,用于当所述Value数据的数据量没有超过数据阈值时,对所述Value数据进行切片,得到M个分片内容,所述M为大于1的自然数,所述M个分片内容为分片后的所述Value数据的数据内容信息;
获取模块,用于根据所述M个分片内容对N个分片内容生成分片信息,所述分片信息包括:对所述Value数据分片的个数、所述N个分片内容中每个分片内容的偏移地址、所述N个分片内容中每个分片内容的序列号ID、(M-N)个分片内容,所述N为大于0自然数,且所述N小于或等于所述M;
存储模块,用于将所述Key数据和所述分片信息存储在基于日志结构的合并树LSM-Tree中,将所述N个分片内容存储在键值对数据库中,所述Key数据与所述分片信息相对应,所述Key数据和所述分片信息参与所述LSM-Tree的轮询合并过程,所述N个分片内容不参与所述轮询合并过程。
9.根据权利要求8所述的装置,其特征在于,所述存储模块,还用于当所述Value数据的数据量超过数据阈值时,将所述键值对存储在所述LSM-Tree中。
10.根据权利要求8所述的装置,其特征在于,所述存储模块包括:
存储子模块,用于将所述Key数据和所述分片信息存储在第一有序数据集中,所述第一有序数据集位于内存memory中;
合并子模块,用于当所述第一有序数据集超过合并阈值时,将第二有序数据集中Key数据对应的分片信息更新为所述第一有序数据集中与所述Key数据对应的分片信息,所述第二有序数据集位于磁盘中。
11.根据权利要求10所述的装置,其特征在于,所述装置还包括:删除模块,用于将所述第一有序数据集中的所述Key数据以及与所述Key数据对应的分片信息删除。
12.根据权利要求8所述的装置,其特征在于,所述装置还包括:查找模块、读取模块,其中,
所述获取模块,还用于获取第一Value数据中需要读取的数据长度、所述第一Value数据中需要读取的数据偏移地址、所述第一Value数据对应的第一Key数据,所述第一Value数据为当前需要读取的Value数据;
所述查找模块,用于根据所述第一Key数据在所述LSM-Tree中查找所述第一Key数据对应的第一分片信息;
所述读取模块,用于根据所述第一Value数据中需要读取的数据偏移地址、所述第一Value数据中需要读取的数据长度和所述第一Key数据对应的第一分片信息从所述LSM-Tree和/或所述键值对数据库中读取出所述第一Value数据中需要读取的数据。
13.根据权利要求12所述的装置,其特征在于,所述装置还包括:更新模块,其中,
所述更新模块,用于在已经读取出的数据所在的分片内容中将所述已经读取出的数据替换为更新数据;
所述获取模块,还用于对所述第一Value数据中已经更新后的各个分片内容重新生成第一分片信息;
所述存储模块,还用于将重新生成的第一分片信息存储在所述LSM-Tree中。
14.根据权利要求8所述的装置,其特征在于,所述装置还包括:查找模块、读取模块、插入模块,其中,
所述获取模块,还用于获取第二Value数据中需要插入的数据长度、所述第二Value数据中需要插入的数据偏移地址、所述第二Value数据对应的第二Key数据;
所述查找模块,用于根据所述第二Key数据在所述LSM-Tree中查找所述第二Key数据对应的第二分片信息;
所述读取模块,用于根据所述第二Value数据中需要插入的数据偏移地址和所述第二Key数据对应的第二分片信息从所述LSM-Tree和/或所述键值对数据库中读取出所述第二Value数据中需要插入的数据偏移地址所在的分片内容;
所述插入模块,用于在所述第二Value数据中需要插入的数据偏移地址所在的分片内容中插入需要插入的数据;
所述获取模块,还用于对第二Value数据中插入数据后的各个分片内容重新生成第二分片信息,将插入数据后的第二Value数据中需要插入的数据偏移地址所在的分片内容携带在重新生成的第二分片信息中;所述存储模块,还用于将重新生成的第二分片信息存储到所述LSM-Tree中;或,所述获取模块,还用于对第二Value数据中插入数据后的各个分片内容重新生成第二分片信息;所述存储模块,还用于将重新生成的第二分片信息存储在所述LSM-Tree中,将插入数据后的第二Value数据中需要插入的数据偏移地址所在的分片内容存储到所述键值对数据库中。
CN201310172455.7A 2013-05-10 2013-05-10 一种键值对系统中数据的存储方法和相关装置 Active CN104142958B (zh)

Priority Applications (1)

Application Number Priority Date Filing Date Title
CN201310172455.7A CN104142958B (zh) 2013-05-10 2013-05-10 一种键值对系统中数据的存储方法和相关装置

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
CN201310172455.7A CN104142958B (zh) 2013-05-10 2013-05-10 一种键值对系统中数据的存储方法和相关装置

Publications (2)

Publication Number Publication Date
CN104142958A CN104142958A (zh) 2014-11-12
CN104142958B true CN104142958B (zh) 2018-03-13

Family

ID=51852132

Family Applications (1)

Application Number Title Priority Date Filing Date
CN201310172455.7A Active CN104142958B (zh) 2013-05-10 2013-05-10 一种键值对系统中数据的存储方法和相关装置

Country Status (1)

Country Link
CN (1) CN104142958B (zh)

Families Citing this family (30)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN105989129B (zh) * 2015-02-15 2019-03-26 腾讯科技(深圳)有限公司 实时数据统计方法和装置
CN106156197A (zh) * 2015-04-22 2016-11-23 中兴通讯股份有限公司 一种数据库的查询方法和装置
CN104809237B (zh) * 2015-05-12 2018-12-14 百度在线网络技术(北京)有限公司 LSM-tree索引的优化方法和装置
CN105138622B (zh) * 2015-08-14 2018-05-22 中国科学院计算技术研究所 用于lsm树存储系统的插入操作及负载的读取和合并方法
US10496614B2 (en) * 2015-10-07 2019-12-03 Oracle International Corporation DDL processing in shared databases
CN105487820B (zh) * 2015-11-30 2018-11-16 中国科学院信息工程研究所 一种基于时间片轮转机制的树状存储结构写放大优化方法
CN105447200A (zh) * 2015-12-30 2016-03-30 金蝶软件(中国)有限公司 一种数据处理方法及数据处理装置
CN106227769B (zh) * 2016-07-15 2019-11-26 北京奇虎科技有限公司 数据存储方法及装置
CN106682184B (zh) * 2016-12-29 2019-12-20 华中科技大学 一种基于日志合并树结构的轻量级合并方法
CN107038206B (zh) * 2017-01-17 2021-04-27 创新先进技术有限公司 Lsm树的建立方法、lsm树的数据读取方法和服务器
CN106844650A (zh) * 2017-01-20 2017-06-13 中国科学院计算技术研究所 一种日志合并树的合并方法及系统
CN106874459B (zh) * 2017-02-14 2020-07-10 北京奇虎科技有限公司 流式数据存储方法及装置
US10783186B2 (en) * 2017-08-31 2020-09-22 Micron Technology, Inc. Heterogenous key-value sets in tree database
CN107526550B (zh) * 2017-09-06 2020-01-17 中国人民大学 一种基于日志结构合并树的两阶段合并方法
CN108052643B (zh) * 2017-12-22 2021-02-23 北京奇虎科技有限公司 基于LSM Tree结构的数据存储方法、装置及存储引擎
CN108153911B (zh) * 2018-01-24 2022-07-19 广西师范学院 数据的分布式云存储方法
CN109684334A (zh) * 2018-12-26 2019-04-26 百度在线网络技术(北京)有限公司 键值对存储系统的数据存储方法、装置、设备和存储介质
CN109656886B (zh) * 2018-12-26 2021-11-09 百度在线网络技术(北京)有限公司 基于键值对的文件系统实现方法、装置、设备和存储介质
CN111444138B (zh) * 2019-01-16 2024-03-15 深圳市茁壮网络股份有限公司 一种文件局部修改方法及系统
CN110309110A (zh) * 2019-05-24 2019-10-08 深圳壹账通智能科技有限公司 一种大数据日志监控方法及装置、存储介质和计算机设备
CN110377227B (zh) * 2019-06-13 2020-07-07 阿里巴巴集团控股有限公司 一种数据分块存储方法、装置及电子设备
CN110704453B (zh) * 2019-10-15 2022-05-06 腾讯音乐娱乐科技(深圳)有限公司 一种数据查询方法、装置、存储介质及电子设备
CN112783417A (zh) * 2019-11-01 2021-05-11 华为技术有限公司 数据缩减的方法、装置、计算设备和存储介质
CN111104403B (zh) * 2019-11-30 2022-06-07 北京浪潮数据技术有限公司 一种lsm树数据处理方法、系统、设备及计算机介质
CN111046041B (zh) * 2019-12-09 2024-02-27 珠海格力电器股份有限公司 数据处理方法和装置、存储介质及处理器
CN111241108B (zh) * 2020-01-16 2023-12-26 北京百度网讯科技有限公司 基于键值对kv系统的索引方法、装置、电子设备和介质
CN112527804B (zh) * 2021-01-27 2022-09-16 中智关爱通(上海)科技股份有限公司 文件存储方法、文件读取方法和数据存储系统
US12033003B2 (en) 2021-07-27 2024-07-09 International Business Machines Corporation Dynamic workload distribution for data processing
US11513704B1 (en) 2021-08-16 2022-11-29 International Business Machines Corporation Selectively evicting data from internal memory during record processing
US11675513B2 (en) 2021-08-16 2023-06-13 International Business Machines Corporation Selectively shearing data when manipulating data during record processing

Citations (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US7697518B1 (en) * 2006-09-15 2010-04-13 Netlogic Microsystems, Inc. Integrated search engine devices and methods of updating same using node splitting and merging operations
CN102541968A (zh) * 2010-12-31 2012-07-04 百度在线网络技术(北京)有限公司 一种索引方法

Patent Citations (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US7697518B1 (en) * 2006-09-15 2010-04-13 Netlogic Microsystems, Inc. Integrated search engine devices and methods of updating same using node splitting and merging operations
CN102541968A (zh) * 2010-12-31 2012-07-04 百度在线网络技术(北京)有限公司 一种索引方法

Non-Patent Citations (2)

* Cited by examiner, † Cited by third party
Title
The partitioned exponential file for database storage management;Jermaine C.等;《The VLDB Journal》;20060726;第417-437页 *
一个高性能Key/Value数据库XDB的设计与实现;胡昊 等;《计算机工程与科学》;20121215;第34卷(第12期);第140-143页 *

Also Published As

Publication number Publication date
CN104142958A (zh) 2014-11-12

Similar Documents

Publication Publication Date Title
CN104142958B (zh) 一种键值对系统中数据的存储方法和相关装置
US10515064B2 (en) Key-value storage system including a resource-efficient index
US10678654B2 (en) Systems and methods for data backup using data binning and deduplication
US8719237B2 (en) Method and apparatus for deleting duplicate data
CN104978151B (zh) 基于应用感知的重复数据删除存储系统中的数据重构方法
US11093471B2 (en) Large range lookups for Bϵ-tree
CN108446376B (zh) 数据存储方法与装置
CN105117415B (zh) 一种优化的ssd数据更新方法
US9442694B1 (en) Method for storing a dataset
CN103581331B (zh) 虚拟机在线迁移方法与系统
CN107704202B (zh) 一种数据快速读写的方法和装置
CN112597739B (zh) 修复电路中的保持时间违例的方法和装置
US10169391B2 (en) Index management
EP4105793A1 (en) Signature-based cache optimization for data preparation
US10983909B2 (en) Trading off cache space and write amplification for Bε-trees
US9646043B1 (en) Combining data matches from multiple sources in a deduplication storage system
US20240028560A1 (en) Directory management method and system for file system based on cuckoo hash and storage medium
CN111126625B (zh) 一种可扩展的学习索引方法及系统
US10515055B2 (en) Mapping logical identifiers using multiple identifier spaces
CN113535670B (zh) 一种虚拟化资源镜像存储系统及其实现方法
US10664460B2 (en) Index B-tree maintenance for linear sequential insertion
EP4064070A1 (en) Cache optimization for data preparation
CN107423321B (zh) 适用大批量小文件云存储的方法及其装置
US9703642B2 (en) Processing of tracked blocks in similarity based deduplication of snapshots data
US20120259823A1 (en) Partitioning a directory while accessing the directory

Legal Events

Date Code Title Description
C06 Publication
PB01 Publication
C10 Entry into substantive examination
SE01 Entry into force of request for substantive examination
GR01 Patent grant
GR01 Patent grant