一种基于时间片轮转机制的树状存储结构写放大优化方法
一种基于时间片轮转机制的树状存储结构写放大优化方法
【技术领域】
[0001]本发明属于计算机软件技术领域，涉及到一种基于时间片轮转机制的树状存储结构写放大优化方法。
【背景技术】
[0002]LSM Tree是一种多组件的树状存储结构。总体来说，LSM Tree由内存空间和磁盘空间两部分构成。数据首先会被缓存在内存空间中，当内存空间达到一定阈值时，内存的数据会被批量地刷写到磁盘空间上。磁盘空间由多层组件构成，各层组件都有一个存储数据大小的阈值，阈值自上而下呈指数增长。刚从内存刷写到磁盘的数据会先存储在上层组件中，当组件中的数据达到阈值时，会通过合并操作将本层数据合并到下层组件中。当LSM-Tree中有多个组件的数据量达到阈值时，会根据合并选择优先级机制，选择优先级最高的组件进行合并操作。
[0003]写放大是目前影响LSM-Tree性能的主要原因。写放大表示一次合并操作的有效率，其计算公式为:写放大=写操作总10量/有效移动数据总量，可以看出，写放大越大，表明此次操作的无效10比例越大，效率就越低，性能也就越差。LSM-Tree写放大较大的原因主要是:在合并操作时，需要从待合并的上下两个组件中各读取一部分数据到内存中进行合并，合并后将结果写回下层组件，而只有上层组件的数据是有效移动数据，下层组件的数据并没有移动，所以下层组件的数据量越大，写放大就越大。现有的LSM-Tree合并选择优先级机制存在缺陷，不能保证各个组件的数据顺利向下层组件移动，一旦数据量增加，数据就会滞留在某一组件中，导致组件在合并时写放大较大，影响整体性能。
【发明内容】
[0004]本发明的主要目的在于提出一种基于时间片轮转的合并机制，通过设定的合并选择机制，选择待合并的组件，赋予其占用时间片(一种合并所需的系统资源)的权限，并根据组件当前数据量的大小，动态调整时间片的阈值大小，从而有效控制其占用时间片的时间长短，保证其在占用时间片的过程中连续进行若干次合并操作，从而有效控制组件的文件个数，降低写放大，提升系统整体吞吐量。
[0005]本发明的技术方案为:
[0006]—种基于时间片轮转机制的树状存储结构写放大优化方法，其步骤为:
[0007]1)选取磁盘空间中一待合并的组件，赋予其占用时间片的权限；其中，磁盘空间为多组件的树状存储结构；
[0008]2)根据所选组件当前数据量的大小，动态调整时间片的阈值大小；
[0009]3)所选组件在占用时间片的过程中连续进行若干次合并操作。
[0010]进一步的，选择待合并的组件需满足的条件为:组件的数据量大于该组件的数据量阈值。
[0011]进一步的，优先选择上次分配时间片的组件的相邻下个组件作为待合并的组件。
[0012]进一步的，如果相邻组件不满足组件的数据量大于该组件的数据量阈值条件时，则计算其他组件的当前数据量与对应组件的数据量阈值的比值，选取满足组件的数据量大于该组件的数据量阈值条件且比值最大的组件。
[0013]进一步的，动态调整时间片的阈值大小的方法为:T为当前分配时间片占用权限的组件Ci的时间片阈值，T=(超出组件Ci的数据量阈值的数据总量/每次合并平均移动数据量)*每次合并的平均时间；其中每次合并平均移动数据量表示为:当组件Ci参与合并且合并后的数据写回下层组件时，从该组件Ci读取的数据总量。
[0014]进一步的，将所选组件每次合并所消耗的时间进行累加，当消耗的总合并时间超过了对应时间片的阈值，则将取消所选组件的占用时间片的权限。
[0015]进一步的，当所选组件当前数据量已小于该组件的数据量阈值，则将取消所选组件的占用时间片的权限。
[0016]本发明主要包括以下三个阶段:
[0017]1)分配时间片占用权限
[0018]为LSM-Tree的某个组件分配时间片占用权限。被分配的组件需要满足以下条件:
[0019]①被分配的组件必须满足本组件的数据量大于本组件的数据量阈值。
[0020]②优先选择上次分配时间片的组件的相邻下个组件进行分配。如组件&刚刚占用完时间片，则优先选择C3进行分配。
[0021]③如果根据条件②选择的组件不满足条件①，或当前时间片的占用权限为空，则计算其他所有组件的当前数据量与对应组件阈值的比值，将满足条件①且比值最大的组件将被分配时间片的占用权限。
[0022]④如果所有组件均不满足条件①，则时间片占用权限暂时置空，即没有组件拥有时间片占用权限，等待当有组件满足条件①时再进行分配。
[0023]2)使用时间片
[0024]当时间片被新的组件占用时，将根据该组件的相关信息，通过如下公式，重新计算时间片的阈值:T=(超出组件Ci的数据量阈值的数据总量/每次合并平均移动数据量)*每次合并的平均时间；T为当前分配时间片占用权限的组件Ci的时间片阈值，其中每次合并移动数据量表示为:当本组件参与合并，且合并后的数据写回下层组件时，从本组件读取的数据总量。经过统计可以计算出每次合并的平均移动数据量。
[0025]随后，在每次合并时，会将每次合并所消耗的时间进行累加，一旦总的合并时间超过了时间片的阈值，则将取消其占用时间片的权限。
[0026]需要指出的是，当第一次为某一组件分配时间片权限时，由于该组件从未进行过合并操作，因此设置的时间片阈值为固定值。
[0027]3)取消时间片占用权限
[0028]取消组件的时间片占用权限主要有以下两种情况:
[0029]①组件在使用时间片过程中，进行合并操作的总时间大于时间片阈值。
[0030]②组件当前数据量已小于该组件的数据量阈值。
[0031]取消组件的时间片权限后，会重新进入分配时间片占用权限的阶段，进行下一次时间片的权限分配。
[0032]与现有技术相比，本发明的积极效果为:
[0033]本发明对拥有时间片的组件具有最高的合并选择优先级，不能进行合并操作的组件将自动放弃时间片，避免不必要的长期占用，导致系统资源空闲。
[0034]通过使用本发明提供的方式优化LSM-Tree，可以将LSM-Tree的整体写吞吐量提升40%以上。
【附图说明】
[0035]图1为本发明的方法流程图。
【具体实施方式】
[0036]为使本发明的目的、技术方案和优点更加清楚，下面结合附图和具体实施例对本发明做进一步说明。
[0037]实例1基于时间片轮转机制的树状存储结构写放大优化方法
[0038]本发明基于RocksDB进行实现和实验。具体的实现方法如下:
[0039]①在系统初始化时，将时间片的占用权限置空。
[0040]②当有组件(不一定是占用时间片的组件)满足本组件数据量大于本组件阈值时，判断当前时间片是否被组件占用。如果没有被占用，则执行④;如果已经被占用，则判断当前占用时间片的组件是否满足本组件数据量大于本组件阈值，如果不满足，则执行③;如果满足则判断该组件的合并时间是否已超过当前时间片的阈值，如果没有超过，则该组件继续进行合并操作，并在合并完成后执行⑤，否则执行③。
[0041]③判断当前占用时间片的组件的相邻下一组件是否满足本组件数据量大于本组件阈值，如当前占用时间片的组件为C2，则判断C3是否满足。如果满足，则根据下一组件的相关信息计算时间片阈值大小，为其分配时间片占用权限，并由该组件进行合并操作，合并操作完成后，执行⑤;如果不满足，则执行④。
[0042]④根据如下公式计算所有组件的分数:组件分数=组件数据量+组件阈值。如果分数最大的组件的分数大于1，则根据该组件信息重新计算时间片阈值大小，为其分配时间片占用权限，并由该组件进行合并操作，合并操作完成后，执行⑤;否则，将时间片占用权限置空。
[0043]⑤记录本次合并消耗的时间，并计算自该组件最近一次占用时间片以后所进行的所有合并操作的总时间。
【主权项】
1.一种基于时间片轮转机制的树状存储结构写放大优化方法，其步骤为: 1)选取磁盘空间中一待合并的组件，赋予其占用时间片的权限；其中，磁盘空间为多组件的树状存储结构； 2)根据所选组件当前数据量的大小，动态调整时间片的阈值大小； 3)所选组件在占用时间片的过程中连续进行若干次合并操作。2.如权利要求1所述的方法，其特征在于，选择待合并的组件需满足的条件为:组件的数据量大于该组件的数据量阈值。3.如权利要求2所述的方法，其特征在于，优先选择上次分配时间片的组件的相邻下个组件作为待合并的组件。4.如权利要求3所述的方法，其特征在于，如果相邻组件不满足组件的数据量大于该组件的数据量阈值条件时，则计算其他组件的当前数据量与对应组件的数据量阈值的比值，选取满足组件的数据量大于该组件的数据量阈值条件且比值最大的组件。5.如权利要求1或2所述的方法，其特征在于，动态调整时间片的阈值大小的方法为:T为当前分配时间片占用权限的组件Ci的时间片阈值，T=(超出组件Ci的数据量阈值的数据总量/每次合并平均移动数据量)*每次合并的平均时间；其中每次合并平均移动数据量表示为:当组件Ci参与合并且合并后的数据写回下层组件时，从该组件Ci读取的数据总量。6.如权利要求1所述的方法，其特征在于，将所选组件每次合并所消耗的时间进行累加，当消耗的总合并时间超过了对应时间片的阈值，则将取消所选组件的占用时间片的权限。7.如权利要求1所述的方法，其特征在于，当所选组件当前数据量已小于该组件的数据量阈值，则将取消所选组件的占用时间片的权限。
【专利摘要】本发明公开了一种基于时间片轮转机制的树状存储结构写放大优化方法。本方法为：1)选取磁盘空间中一待合并的组件，赋予其占用时间片的权限；其中，磁盘空间为多组件的树状存储结构；2)根据所选组件当前数据量的大小，动态调整时间片的阈值大小；3)所选组件在占用时间片的过程中连续进行若干次合并操作。本发明对拥有时间片的组件具有最高的合并选择优先级，不能进行合并操作的组件将自动放弃时间片，避免不必要的长期占用，导致系统资源空闲，可以将LSM-Tree的整体写吞吐量提升40％以上。
【IPC分类】G06F3/06
【公开号】CN105487820
【申请号】CN201510859463
【发明人】岳银亮, 李宇哲, 王伟平
【申请人】中国科学院信息工程研究所
【公开日】2016年4月13日
【申请日】2015年11月30日
【技术领域】
[0001]本发明属于计算机软件技术领域，涉及到一种基于时间片轮转机制的树状存储结构写放大优化方法。
【背景技术】
[0002]LSM Tree是一种多组件的树状存储结构。总体来说，LSM Tree由内存空间和磁盘空间两部分构成。数据首先会被缓存在内存空间中，当内存空间达到一定阈值时，内存的数据会被批量地刷写到磁盘空间上。磁盘空间由多层组件构成，各层组件都有一个存储数据大小的阈值，阈值自上而下呈指数增长。刚从内存刷写到磁盘的数据会先存储在上层组件中，当组件中的数据达到阈值时，会通过合并操作将本层数据合并到下层组件中。当LSM-Tree中有多个组件的数据量达到阈值时，会根据合并选择优先级机制，选择优先级最高的组件进行合并操作。
[0003]写放大是目前影响LSM-Tree性能的主要原因。写放大表示一次合并操作的有效率，其计算公式为:写放大=写操作总10量/有效移动数据总量，可以看出，写放大越大，表明此次操作的无效10比例越大，效率就越低，性能也就越差。LSM-Tree写放大较大的原因主要是:在合并操作时，需要从待合并的上下两个组件中各读取一部分数据到内存中进行合并，合并后将结果写回下层组件，而只有上层组件的数据是有效移动数据，下层组件的数据并没有移动，所以下层组件的数据量越大，写放大就越大。现有的LSM-Tree合并选择优先级机制存在缺陷，不能保证各个组件的数据顺利向下层组件移动，一旦数据量增加，数据就会滞留在某一组件中，导致组件在合并时写放大较大，影响整体性能。
【发明内容】
[0004]本发明的主要目的在于提出一种基于时间片轮转的合并机制，通过设定的合并选择机制，选择待合并的组件，赋予其占用时间片(一种合并所需的系统资源)的权限，并根据组件当前数据量的大小，动态调整时间片的阈值大小，从而有效控制其占用时间片的时间长短，保证其在占用时间片的过程中连续进行若干次合并操作，从而有效控制组件的文件个数，降低写放大，提升系统整体吞吐量。
[0005]本发明的技术方案为:
[0006]—种基于时间片轮转机制的树状存储结构写放大优化方法，其步骤为:
[0007]1)选取磁盘空间中一待合并的组件，赋予其占用时间片的权限；其中，磁盘空间为多组件的树状存储结构；
[0008]2)根据所选组件当前数据量的大小，动态调整时间片的阈值大小；
[0009]3)所选组件在占用时间片的过程中连续进行若干次合并操作。
[0010]进一步的，选择待合并的组件需满足的条件为:组件的数据量大于该组件的数据量阈值。
[0011]进一步的，优先选择上次分配时间片的组件的相邻下个组件作为待合并的组件。
[0012]进一步的，如果相邻组件不满足组件的数据量大于该组件的数据量阈值条件时，则计算其他组件的当前数据量与对应组件的数据量阈值的比值，选取满足组件的数据量大于该组件的数据量阈值条件且比值最大的组件。
[0013]进一步的，动态调整时间片的阈值大小的方法为:T为当前分配时间片占用权限的组件Ci的时间片阈值，T=(超出组件Ci的数据量阈值的数据总量/每次合并平均移动数据量)*每次合并的平均时间；其中每次合并平均移动数据量表示为:当组件Ci参与合并且合并后的数据写回下层组件时，从该组件Ci读取的数据总量。
[0014]进一步的，将所选组件每次合并所消耗的时间进行累加，当消耗的总合并时间超过了对应时间片的阈值，则将取消所选组件的占用时间片的权限。
[0015]进一步的，当所选组件当前数据量已小于该组件的数据量阈值，则将取消所选组件的占用时间片的权限。
[0016]本发明主要包括以下三个阶段:
[0017]1)分配时间片占用权限
[0018]为LSM-Tree的某个组件分配时间片占用权限。被分配的组件需要满足以下条件:
[0019]①被分配的组件必须满足本组件的数据量大于本组件的数据量阈值。
[0020]②优先选择上次分配时间片的组件的相邻下个组件进行分配。如组件&刚刚占用完时间片，则优先选择C3进行分配。
[0021]③如果根据条件②选择的组件不满足条件①，或当前时间片的占用权限为空，则计算其他所有组件的当前数据量与对应组件阈值的比值，将满足条件①且比值最大的组件将被分配时间片的占用权限。
[0022]④如果所有组件均不满足条件①，则时间片占用权限暂时置空，即没有组件拥有时间片占用权限，等待当有组件满足条件①时再进行分配。
[0023]2)使用时间片
[0024]当时间片被新的组件占用时，将根据该组件的相关信息，通过如下公式，重新计算时间片的阈值:T=(超出组件Ci的数据量阈值的数据总量/每次合并平均移动数据量)*每次合并的平均时间；T为当前分配时间片占用权限的组件Ci的时间片阈值，其中每次合并移动数据量表示为:当本组件参与合并，且合并后的数据写回下层组件时，从本组件读取的数据总量。经过统计可以计算出每次合并的平均移动数据量。
[0025]随后，在每次合并时，会将每次合并所消耗的时间进行累加，一旦总的合并时间超过了时间片的阈值，则将取消其占用时间片的权限。
[0026]需要指出的是，当第一次为某一组件分配时间片权限时，由于该组件从未进行过合并操作，因此设置的时间片阈值为固定值。
[0027]3)取消时间片占用权限
[0028]取消组件的时间片占用权限主要有以下两种情况:
[0029]①组件在使用时间片过程中，进行合并操作的总时间大于时间片阈值。
[0030]②组件当前数据量已小于该组件的数据量阈值。
[0031]取消组件的时间片权限后，会重新进入分配时间片占用权限的阶段，进行下一次时间片的权限分配。
[0032]与现有技术相比，本发明的积极效果为:
[0033]本发明对拥有时间片的组件具有最高的合并选择优先级，不能进行合并操作的组件将自动放弃时间片，避免不必要的长期占用，导致系统资源空闲。
[0034]通过使用本发明提供的方式优化LSM-Tree，可以将LSM-Tree的整体写吞吐量提升40%以上。
【附图说明】
[0035]图1为本发明的方法流程图。
【具体实施方式】
[0036]为使本发明的目的、技术方案和优点更加清楚，下面结合附图和具体实施例对本发明做进一步说明。
[0037]实例1基于时间片轮转机制的树状存储结构写放大优化方法
[0038]本发明基于RocksDB进行实现和实验。具体的实现方法如下:
[0039]①在系统初始化时，将时间片的占用权限置空。
[0040]②当有组件(不一定是占用时间片的组件)满足本组件数据量大于本组件阈值时，判断当前时间片是否被组件占用。如果没有被占用，则执行④;如果已经被占用，则判断当前占用时间片的组件是否满足本组件数据量大于本组件阈值，如果不满足，则执行③;如果满足则判断该组件的合并时间是否已超过当前时间片的阈值，如果没有超过，则该组件继续进行合并操作，并在合并完成后执行⑤，否则执行③。
[0041]③判断当前占用时间片的组件的相邻下一组件是否满足本组件数据量大于本组件阈值，如当前占用时间片的组件为C2，则判断C3是否满足。如果满足，则根据下一组件的相关信息计算时间片阈值大小，为其分配时间片占用权限，并由该组件进行合并操作，合并操作完成后，执行⑤;如果不满足，则执行④。
[0042]④根据如下公式计算所有组件的分数:组件分数=组件数据量+组件阈值。如果分数最大的组件的分数大于1，则根据该组件信息重新计算时间片阈值大小，为其分配时间片占用权限，并由该组件进行合并操作，合并操作完成后，执行⑤;否则，将时间片占用权限置空。
[0043]⑤记录本次合并消耗的时间，并计算自该组件最近一次占用时间片以后所进行的所有合并操作的总时间。
【主权项】
1.一种基于时间片轮转机制的树状存储结构写放大优化方法，其步骤为: 1)选取磁盘空间中一待合并的组件，赋予其占用时间片的权限；其中，磁盘空间为多组件的树状存储结构； 2)根据所选组件当前数据量的大小，动态调整时间片的阈值大小； 3)所选组件在占用时间片的过程中连续进行若干次合并操作。2.如权利要求1所述的方法，其特征在于，选择待合并的组件需满足的条件为:组件的数据量大于该组件的数据量阈值。3.如权利要求2所述的方法，其特征在于，优先选择上次分配时间片的组件的相邻下个组件作为待合并的组件。4.如权利要求3所述的方法，其特征在于，如果相邻组件不满足组件的数据量大于该组件的数据量阈值条件时，则计算其他组件的当前数据量与对应组件的数据量阈值的比值，选取满足组件的数据量大于该组件的数据量阈值条件且比值最大的组件。5.如权利要求1或2所述的方法，其特征在于，动态调整时间片的阈值大小的方法为:T为当前分配时间片占用权限的组件Ci的时间片阈值，T=(超出组件Ci的数据量阈值的数据总量/每次合并平均移动数据量)*每次合并的平均时间；其中每次合并平均移动数据量表示为:当组件Ci参与合并且合并后的数据写回下层组件时，从该组件Ci读取的数据总量。6.如权利要求1所述的方法，其特征在于，将所选组件每次合并所消耗的时间进行累加，当消耗的总合并时间超过了对应时间片的阈值，则将取消所选组件的占用时间片的权限。7.如权利要求1所述的方法，其特征在于，当所选组件当前数据量已小于该组件的数据量阈值，则将取消所选组件的占用时间片的权限。
【专利摘要】本发明公开了一种基于时间片轮转机制的树状存储结构写放大优化方法。本方法为：1)选取磁盘空间中一待合并的组件，赋予其占用时间片的权限；其中，磁盘空间为多组件的树状存储结构；2)根据所选组件当前数据量的大小，动态调整时间片的阈值大小；3)所选组件在占用时间片的过程中连续进行若干次合并操作。本发明对拥有时间片的组件具有最高的合并选择优先级，不能进行合并操作的组件将自动放弃时间片，避免不必要的长期占用，导致系统资源空闲，可以将LSM-Tree的整体写吞吐量提升40％以上。
【IPC分类】G06F3/06
【公开号】CN105487820
【申请号】CN201510859463
【发明人】岳银亮, 李宇哲, 王伟平
【申请人】中国科学院信息工程研究所
【公开日】2016年4月13日
【申请日】2015年11月30日
最新回复(0)