CN112181287B 基于键值存储数据的存储设备及其操作方法 （三星电子株式会社）

KR20170141538A,2017.US2018225315A1,2018.0基于键值存储数据的存储设备及其操作方法通过合并从多个键值对分离的多个键生成第一2及通过合并从所述多个键值对分离的多个键生成第一键流；以及非易其中，所述第一键流与从所述多个键值对中的每一个分离的其中，所述控制器响应于来自主机的压缩命令从非易失性其中，所述控制器通过合并所述第一键流的第一有效键和所述第二键流的第二有效其中，所述第一有效键和所述第二有效键中的每一个对所述控制器还被配置为通过将所述多个键值对中的对应一个的键与对应于所述多个键值对中的对应一个的值的索引进行合并来生成所述所述控制器还被配置为通过合并从所述多个键值对分离的多个值来生所述值流与所述第一键流分开存储在所述非易失性存所述控制器通过从所述多个键值对中的每一个中提取键来生从所述非易失性存储器中读取所述第一键流和通过从所述第一键流中提取第一有效键和从所述第二键流中提取第二有效键来生成3其中，所述第一有效键和所述第二有效键中的每一个对应将所述多个键值对中的对应一个的键与所述所述控制器将所述值流存储在所述非易失性存所述控制器生成哈希表，所述哈希表包括关于所述第一键流至所述控制器用与主机向其发出擦除命令的无效值相对应的无效键来更所述控制器生成值表，所述值表包括所述多个值的物理地址和每一个所述控制器用与所述无效键相对应的值的有效性比特来所述控制器通过使用所述值表的至少一个有效性比特，对与所述无4[0002]本申请要求于2019年7月5日向韩国知识产权局提交的第10-2019-0081522号韩国者可以在与外部存储设备或存储系统进行通信的同时存[0008]本发明构思还提供一种对键和值有效地执行压缩的存储设备以及该存储设备的一键流。第一键流与从多个键值对中的每一个分离的值分开地被存储在非易失性存储器5[0015]图3是示出根据本发明构思的示例实施例的包括在存储器单元阵列中的存储器块6存储设备，并且可以应用于以对象为单位管理数据的任何对象缓存系统或对象存储系统。以将多个值VALUE存储在数据缓冲器1值管理器120可以在非易失性存储器140中将存储的多个键KEY作为键流存储。当存在多达一定数量或一定量的数据的多个值VALUE存储在数据缓冲器130中时，键值管理器120可以流可以分别存储在非易失性存储器140的不键值管理器120可以分离键值对并且分别管理键KEY和值VALUE，由此可以减少对于非易失[0039]数据缓冲器130可以包括至少一个用于存储键KEY和值VALUE的存储器设备，并且在一个示例中，数据缓冲器130可以包括易失性存储器设备，诸如动态随机访问存储器(dynamicrandomaccessmemory，DRAM)或静态随机访问存储器(staticrandomaccess[0040]非易失性存储器140可以包括存储器单元阵列MCA、存储器单元阵列MCA可以包括如电阻RAM(resistiveRAM，ReRAM)、相变RAM(phase-changeRAM，PRAM)或磁性RAM7[0041]存储系统10可以被实现为例如个人计算机(personalcomputer，PC)、数据服务设备可以包括膝上型计算机、移动电话、智能电话、平板PC、个人数字助理(personal态相机、数字摄像机、音频设备、便携式多媒体播放器(portablemultimediaplayer，[0046]当存储在键缓冲器131中的多个键KEY具有一定量或更多的数据时，键值提取器与分别对应于多个键KEY的值VALUE的索引进行合并来生成键流ST_KEY。键值提取器121可以将生成的键流ST_KEY存储在非易失性存储器140的第一区域[0049]压缩模块122可以对存储在第一区域AR1中的至少一个键流ST_KEY执行压缩操8在此，压缩操作可以指通过删除与非易失性存储器140中存储的无效值(例如，陈旧值)定无效键(例如，陈旧键)。在一个示例中，无效键可以是与主机向其发出删除命令的值VALUE相对应的键KEY。压缩模块122可以仅通过使用至少一个键流ST_KEY中包括的有效键[0052]压缩模块122可以更新与作为压缩操作的目标的无效键KEY相对应的值VALUE的有[0054]图3是示出根据本发明构思的示例实施例的包括在存储器单元阵列中的存储器块元串NS12、NS22和NS32布置在第二位线BL2和公共源极线CSL之间，并且NAND单元串NS13、[0057]共同连接到一个位线的NAND单元串构成一列。例如，共同连接到第一位线BL1的NAND单元串NS11、NS21和NS31可以对应于第一列，共同连接到第二位线BL2的NAND单元串NS12、NS22和NS32可以对应于第二列，并且共同连接到第三位线BL3的NAND单元串NS13、NS23和NS33可以对应于第三列。[0059]单元串选择晶体管SST分别连接到对应的单元串选择线SSL1至SSL3。多个存储器9单元MC1至MC8分别连接到对应的字线WL1至WL8。地选择晶体管GST分别连接到对应的地选择线GSL1至GSL3。单元串选择晶体管SST连接到对应的位线BL1至BL3，并且地选择晶体管NS11、NS12和NS13中的存储器单元被编程时，第一字线WL1和第一单元串选择线SSL1被选[0061]根据本发明构思的一个实施例的存储设备可以将键和值分别存储在存储器单元WL8以及三个位线BL1至BL3，但是存储器块中包括的每一个组件的数量实际上可以大于或电荷俘获层和阻挡绝缘层。例如，电荷存储层CS可以具有氧化物-氮化物-氧化物(oxide-如选择线GSL和SSL以及字线WL1至WL8)布置在电荷存储层CS的且根据本发明构思的一个实施例的键流ST_KEY可以包括多个索引键对，其中索引Idx分别[0071]键值管理器120可以通过使用非易失性存储器140的第一区域AR1中存储键流ST_括键流ST_KEY的键和存储键流ST_KEY的键的非易失性存储器140的物理地址的排序字符串表HT可以存储SS表的文件名和存储SS表的键[0072]键值管理器120可以将与键值对KVP分离的值存储在数据缓冲器130中，可以通过合并存储在数据缓冲器130中的多个值来生成值流ST_VAL，并且可以将生成的值流ST_VAL[0073]键值管理器120可以通过使用非易失性存储器140中的存储值流ST_VALPPN来生成[0075]参照图2和图6，键值管理器120可以接收包括多个键KEY和多个值VALUE的数据器120可以将生成的键流ST_KEY和生成的值流ST_VAL存储在非易失性存储器140中(S140)。值流ST_VAL可以被存储在非易失性存储器140的第二区域[0076]根据本发明构思的一个实施例，键值管理器120可以将键KEY和值VALUE彼此分开地存储在非易失性存储器140中，并且可以通过分别管理键KEY和值VALUE来有效地管理数[0078]参照图2和图7，键值管理器120可以从非易失性存储器140的第一区域AR1读取无120可以用与第一值相对应的第一键来更新哈希表HT，使得第一键可以基于与之耦合的索[0079]键值管理器120可以通过合并无效键流ST_IK来生成至少一个合并键流ST_MK。在一个示例中，键值管理器120可以通过基于哈希表HT删除无效键并仅提取有效键来生成合[0080]键值管理器120可以将生成的合并键流ST_MK写入非易失性存储器140的第一区域[0081]在一个实施例中，键值管理器120可以基于值表VT的有效性比特对无效值执行垃[0082]当执行压缩操作时，根据本发明构思的一个实施例的键值管理器120可以通过读取和重写具有相对少量数据的键而不执行具有相对大量数据的值的数据输入/输出来对无[0083]图8是示出根据本发明构思的示例实施例的键值管理器的操作方法的流程图。特[0084]参照图2和图8，键值管理器120可以从非易失性存储器140读取多个键流(S210过去除包括在多个键流中的无效键并且仅在其中合并有效键[0087]参照图9A，块BLK可以包括分别具有不同的PPN的多个存储器单元(在图9A中由四边形标记)，并且多个存储器单元中的每一个可以具有存储在其中的有效数据VD或无效数[0089]参照图9B，可以通过使用多映射表MMT根据其存储位置来识别图9A中写入的数据址(例如，PPN)，以及指示在上述地址存储的连续数据片段的有效性的有效性比特VD1至为与第二地址PPN2相对应的有效性比特VD1[0092]在一个实施例中，键值管理器120(图2)可以通过使用多映射表MMT来执行垃圾收值流)有效，并且可以通过对无效数据执行垃圾收集来确保非易失性存储器140(图2)的有可以向控制器110输出用于写入第一键KEY1和第一值VAL1的第一命令CMD1(S310)。控制器110可以将第一键KEY1和第一值VAL[0095]控制器110可以通过使用先前存储在数据缓冲器130(图2)中的第一键KEY1和第二键KEY2生成键流ST_KEY，并且可以通过使用先前存储在数据缓冲器130(图2)中的第一值[0096]非易失性存储器140可以将第一键KEY1存储在第一地址PPN1，并且可以将第二键[0097]控制器110可以在键表KT中使第一键KEY1的存储位置对应于第一地址PPN1，并且[0098]控制器110可以将第三地址PPN3写入值表VT，使得第三地址PPN3对应于与第一值的，所以控制器110可以通过写入两个“1”作为与之相对应的有效性比特来更新值表VT[0099]根据本发明构思的一个实施例的控制器110可以不将连续写入的第一值VAL1和第可以向控制器110输出用于擦除第二键KEY2和第二值VAL2的第二命令CMD2(S410)。响应于第二命令CMD2，控制器110可以通过删除键表KT的与第二键KEY2相对应的部分来更新键表[0102]为了执行压缩操作，控制器110可以从非易失性存储器140读取键流ST_KEY(S440)。控制器110可以通过将键流ST_KEY与单独的键流合并来生成合并键流ST_KEY'过使用包括在键流ST_KEY中的第一键KEY1和包括在单独的键流中的第三键KEY3两者来生成合并键流ST_KEY'。[0103]控制器110可以将合并键流ST_KEY'存储在非易失性存储器140中(S460)，并且非取具有相对少量数据的键流ST_KEY，而不从非易失性存储器140读取具有相对大量数据的可以向控制器110输出用于擦除第一键KEY1和第一值VAL1的第三命令CMD3(S510)。响应于第三命令CMD3，控制器110可以通过删除键表KT的与第一键KEY1相对应的部分来更新键表垃圾收集以删除对应的值流ST_VAL和对应的键流(S540)。响应于控制器110的垃圾收集请求，非易失性存储器140可以删除分别存储第一键KEY1和第二键KEY2的第一地址PPN1和第[0109]控制器110可以通过使用先前存储在数据缓冲器130(图2)中的第一键KEY1和第二键KEY2来生成第一键流ST_KEY1，并且可以通过使用先前存储在数据缓冲器130(图2)中的第一值VAL1和第二值VAL2来生成第一值[0110]非易失性存储器140可以第一键KEY1存储在第一地址PPN1，并且可以将第二键存储在第三地址PPN3，并且可以将第二值VAL2存储在第三地址PPN3的下一个地址(S650)。在第二地址PPN2，并且将与第二键流ST_KEY2相对应的第二值流ST_VAL2存储在第四地址[0111]控制器110可以在哈希表HT中使第一SS表SST1的存储位置对应于第一地址PPN1，[0112]控制器110可以将第三地址PPN3写入值表VT，使得第三地址PPN3对应于与第一值的，所以控制器110可以通过写入两个“1”作为与之相对应的有效性比特来更新值表VT可以向控制器110输出用于合并第一SS表SST1和第二SS表SST2的合并命令(或压缩命令)(S710)。控制器110可以从非易失性存储器140读取第一键流ST_KEY1和第二键流ST_KEY2[0115]控制器110可以合并第一键流ST_KEY1和第二键流ST_KEY2以生成第三键流ST_KEY3(S730)。在一个示例中，控制器110可以从自非易失性存储器140读取的第一键流ST_一键流ST_KEY1和第二键流ST_KEY2中的有效键来生成第三键流ST_KEY3(例如，第一键流ST_KEY1的第一键KEY1和第二键流[0116]控制器110可以将第三键流ST_KEY3存储在非易失性存储器140中(S740)，并且非(USB)、多媒体卡(MMC)、外围组件互连快速连接(PeripheralComponentInterconnectExpress，PCI-E)、AT附接(ATAttachment，ATA)、串行AT附接(SerialATAttachment，SATA)、并行AT附接(ParallelATAttachment，PATA)、小型计算机系统接口(Small[0122]易失性