[go: up one dir, main page]

CN110058806A - 用于对象存储设备的混合数据可靠性的系统和方法 - Google Patents

用于对象存储设备的混合数据可靠性的系统和方法 Download PDF

Info

Publication number
CN110058806A
CN110058806A CN201910007109.0A CN201910007109A CN110058806A CN 110058806 A CN110058806 A CN 110058806A CN 201910007109 A CN201910007109 A CN 201910007109A CN 110058806 A CN110058806 A CN 110058806A
Authority
CN
China
Prior art keywords
objects
value
storage devices
data
key
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.)
Granted
Application number
CN201910007109.0A
Other languages
English (en)
Other versions
CN110058806B (zh
Inventor
R.皮特丘马尼
奇亮奭
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.)
Samsung Electronics Co Ltd
Original Assignee
Samsung Electronics Co Ltd
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
Priority claimed from US15/876,028 external-priority patent/US10795760B2/en
Priority claimed from US15/967,302 external-priority patent/US10552062B2/en
Priority claimed from US16/165,655 external-priority patent/US11275762B2/en
Application filed by Samsung Electronics Co Ltd filed Critical Samsung Electronics Co Ltd
Publication of CN110058806A publication Critical patent/CN110058806A/zh
Application granted granted Critical
Publication of CN110058806B publication Critical patent/CN110058806B/zh
Active legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F3/00—Input arrangements for transferring data to be processed into a form capable of being handled by the computer; Output arrangements for transferring data from processing unit to output unit, e.g. interface arrangements
    • G06F3/06—Digital input from, or digital output to, record carriers, e.g. RAID, emulated record carriers or networked record carriers
    • G06F3/0601—Interfaces specially adapted for storage systems
    • G06F3/0602—Interfaces specially adapted for storage systems specifically adapted to achieve a particular effect
    • G06F3/0614—Improving the reliability of storage systems
    • G06F3/0619—Improving the reliability of storage systems in relation to data integrity, e.g. data losses, bit errors
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F3/00—Input arrangements for transferring data to be processed into a form capable of being handled by the computer; Output arrangements for transferring data from processing unit to output unit, e.g. interface arrangements
    • G06F3/06—Digital input from, or digital output to, record carriers, e.g. RAID, emulated record carriers or networked record carriers
    • G06F3/0601—Interfaces specially adapted for storage systems
    • G06F3/0602—Interfaces specially adapted for storage systems specifically adapted to achieve a particular effect
    • G06F3/0608—Saving storage space on storage systems
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F11/00—Error detection; Error correction; Monitoring
    • G06F11/07—Responding to the occurrence of a fault, e.g. fault tolerance
    • G06F11/0703—Error or fault processing not based on redundancy, i.e. by taking additional measures to deal with the error or fault not making use of redundancy in operation, in hardware, or in data representation
    • G06F11/0706—Error or fault processing not based on redundancy, i.e. by taking additional measures to deal with the error or fault not making use of redundancy in operation, in hardware, or in data representation the processing taking place on a specific hardware platform or in a specific software environment
    • G06F11/0727—Error or fault processing not based on redundancy, i.e. by taking additional measures to deal with the error or fault not making use of redundancy in operation, in hardware, or in data representation the processing taking place on a specific hardware platform or in a specific software environment in a storage system, e.g. in a DASD or network based storage system
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F11/00—Error detection; Error correction; Monitoring
    • G06F11/07—Responding to the occurrence of a fault, e.g. fault tolerance
    • G06F11/08—Error detection or correction by redundancy in data representation, e.g. by using checking codes
    • G06F11/10—Adding special bits or symbols to the coded information, e.g. parity check, casting out 9's or 11's
    • G06F11/1004—Adding special bits or symbols to the coded information, e.g. parity check, casting out 9's or 11's to protect a block of data words, e.g. CRC or checksum
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F11/00—Error detection; Error correction; Monitoring
    • G06F11/07—Responding to the occurrence of a fault, e.g. fault tolerance
    • G06F11/08—Error detection or correction by redundancy in data representation, e.g. by using checking codes
    • G06F11/10—Adding special bits or symbols to the coded information, e.g. parity check, casting out 9's or 11's
    • G06F11/1076—Parity data used in redundant arrays of independent storages, e.g. in RAID systems
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F3/00—Input arrangements for transferring data to be processed into a form capable of being handled by the computer; Output arrangements for transferring data from processing unit to output unit, e.g. interface arrangements
    • G06F3/06—Digital input from, or digital output to, record carriers, e.g. RAID, emulated record carriers or networked record carriers
    • G06F3/0601—Interfaces specially adapted for storage systems
    • G06F3/0602—Interfaces specially adapted for storage systems specifically adapted to achieve a particular effect
    • G06F3/061—Improving I/O performance
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F3/00—Input arrangements for transferring data to be processed into a form capable of being handled by the computer; Output arrangements for transferring data from processing unit to output unit, e.g. interface arrangements
    • G06F3/06—Digital input from, or digital output to, record carriers, e.g. RAID, emulated record carriers or networked record carriers
    • G06F3/0601—Interfaces specially adapted for storage systems
    • G06F3/0602—Interfaces specially adapted for storage systems specifically adapted to achieve a particular effect
    • G06F3/0614—Improving the reliability of storage systems
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F3/00—Input arrangements for transferring data to be processed into a form capable of being handled by the computer; Output arrangements for transferring data from processing unit to output unit, e.g. interface arrangements
    • G06F3/06—Digital input from, or digital output to, record carriers, e.g. RAID, emulated record carriers or networked record carriers
    • G06F3/0601—Interfaces specially adapted for storage systems
    • G06F3/0628—Interfaces specially adapted for storage systems making use of a particular technique
    • G06F3/0629—Configuration or reconfiguration of storage systems
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F3/00—Input arrangements for transferring data to be processed into a form capable of being handled by the computer; Output arrangements for transferring data from processing unit to output unit, e.g. interface arrangements
    • G06F3/06—Digital input from, or digital output to, record carriers, e.g. RAID, emulated record carriers or networked record carriers
    • G06F3/0601—Interfaces specially adapted for storage systems
    • G06F3/0628—Interfaces specially adapted for storage systems making use of a particular technique
    • G06F3/0638—Organizing or formatting or addressing of data
    • G06F3/064—Management of blocks
    • G06F3/0641—De-duplication techniques
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F3/00—Input arrangements for transferring data to be processed into a form capable of being handled by the computer; Output arrangements for transferring data from processing unit to output unit, e.g. interface arrangements
    • G06F3/06—Digital input from, or digital output to, record carriers, e.g. RAID, emulated record carriers or networked record carriers
    • G06F3/0601—Interfaces specially adapted for storage systems
    • G06F3/0628—Interfaces specially adapted for storage systems making use of a particular technique
    • G06F3/0646—Horizontal data movement in storage systems, i.e. moving data in between storage devices or systems
    • G06F3/065—Replication mechanisms
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F3/00—Input arrangements for transferring data to be processed into a form capable of being handled by the computer; Output arrangements for transferring data from processing unit to output unit, e.g. interface arrangements
    • G06F3/06—Digital input from, or digital output to, record carriers, e.g. RAID, emulated record carriers or networked record carriers
    • G06F3/0601—Interfaces specially adapted for storage systems
    • G06F3/0628—Interfaces specially adapted for storage systems making use of a particular technique
    • G06F3/0653—Monitoring storage devices or systems
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F3/00—Input arrangements for transferring data to be processed into a form capable of being handled by the computer; Output arrangements for transferring data from processing unit to output unit, e.g. interface arrangements
    • G06F3/06—Digital input from, or digital output to, record carriers, e.g. RAID, emulated record carriers or networked record carriers
    • G06F3/0601—Interfaces specially adapted for storage systems
    • G06F3/0628—Interfaces specially adapted for storage systems making use of a particular technique
    • G06F3/0662—Virtualisation aspects
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F3/00—Input arrangements for transferring data to be processed into a form capable of being handled by the computer; Output arrangements for transferring data from processing unit to output unit, e.g. interface arrangements
    • G06F3/06—Digital input from, or digital output to, record carriers, e.g. RAID, emulated record carriers or networked record carriers
    • G06F3/0601—Interfaces specially adapted for storage systems
    • G06F3/0628—Interfaces specially adapted for storage systems making use of a particular technique
    • G06F3/0662—Virtualisation aspects
    • G06F3/0664—Virtualisation aspects at device level, e.g. emulation of a storage device or system
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F3/00—Input arrangements for transferring data to be processed into a form capable of being handled by the computer; Output arrangements for transferring data from processing unit to output unit, e.g. interface arrangements
    • G06F3/06—Digital input from, or digital output to, record carriers, e.g. RAID, emulated record carriers or networked record carriers
    • G06F3/0601—Interfaces specially adapted for storage systems
    • G06F3/0668—Interfaces specially adapted for storage systems adopting a particular infrastructure
    • G06F3/0671—In-line storage system
    • G06F3/0673—Single storage device
    • G06F3/0679—Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F3/00—Input arrangements for transferring data to be processed into a form capable of being handled by the computer; Output arrangements for transferring data from processing unit to output unit, e.g. interface arrangements
    • G06F3/06—Digital input from, or digital output to, record carriers, e.g. RAID, emulated record carriers or networked record carriers
    • G06F3/0601—Interfaces specially adapted for storage systems
    • G06F3/0668—Interfaces specially adapted for storage systems adopting a particular infrastructure
    • G06F3/0671—In-line storage system
    • G06F3/0683—Plurality of storage devices
    • G06F3/0689—Disk arrays, e.g. RAID, JBOD

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • General Engineering & Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • General Physics & Mathematics (AREA)
  • Human Computer Interaction (AREA)
  • Quality & Reliability (AREA)
  • Computer Security & Cryptography (AREA)
  • Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
  • Detection And Correction Of Errors (AREA)

Abstract

提供了一种在键‑值可靠性系统中存储数据的方法，该系统包括N个存储设备，N个存储设备被分组为可靠性组作为单个逻辑单元并且由虚拟设备管理层管理，N是整数，该方法包括：确定数据是否满足与用于存储数据的可靠性机制相对应的阈值；当满足阈值时选择可靠性机制；以及根据选择的可靠性机制存储数据。

Description

用于对象存储设备的混合数据可靠性的系统和方法
技术领域
本公开的实施例的一个或多个方面总体上涉及数据存储系统，并且更具体地涉及一种用于选择用于在包括多个键-值存储设备的键-值可靠性系统中可靠地存储键-值数据的可靠性机制的方法。
背景技术
在具有多个存储设备的许多安装中，可以采用诸如擦除编码的数据可靠性机制来克服由于数据损坏和存储设备故障引起的数据丢失。
传统的固态驱动器(solid state drives，SSD)通常仅使用块接口，并且可以通过独立磁盘的冗余阵列(即RAID方法)、通过擦除编码或复制提供数据可靠性。随着对象格式在大小和非结构化方面变得可变，期望在对象和块级接口之间进行有效的数据转换。进一步地，期望在维持空间效率和快速访问时间特性的同时确保数据可靠性。
对于传统的块存储设备，已经很好地研究了诸如RAID的技术。然而，相对新的键-值存储设备可能具有与传统块设备不同的接口和不同的存储语义。因此，许多新的键-值存储设备可能潜在地受益于为键-值数据和键-值存储设备定制或采用的新的数据可靠性机制。
发明内容
本文描述的实施例提供了对存储器存储领域的改进，因为实施例的可靠性机制各自都能够进行使得虚拟设备管理层能够修复故障存储器设备中存在的所有键并将它们复制到新的存储器设备的单个键修复过程。
根据本公开的一个实施例，提供了在包括N个存储设备的键-值可靠性系统中存储数据的方法，该N个存储设备被分组为可靠性组作为单个逻辑单元并且由虚拟设备管理层管理，N是整数，该方法包括确定数据是否满足与用于存储数据的可靠性机制相对应的阈值，当满足阈值时选择该可靠性机制，并且根据选择的可靠性机制存储数据。
阈值可以基于数据的对象大小、数据的吞吐量考虑、数据的读取/写入温度以及N个存储设备的基本(underlying)擦除编码能力中的一个或多个。
该方法还可以包括使用一个或多个布隆过滤器或高速缓存用于测试用于可靠性机制的数据。
该方法还可以包括插入元数据，该元数据具有与用于记录所选择的可靠性机制的数据相对应的键、用于存储数据的N个存储设备中的每一个的一个或多个校验和、存储在存储数据的N个存储设备中的每一个中的数据的值的对象大小、以及用于指示N个存储设备中的哪些存储设备正在存储数据的N个存储设备的奇偶校验组成员的位置。
所选择的可靠性机制可以包括对象复制，并且其中存储数据包括：选择KV值；计算用于散列(hashing)与所选择的KV值相对应的键的散列；确定N个存储设备中用于存储与KV值相对应的键对象的副本的存储设备的子集；以及在相同的用户键名下将与KV值相对应的更新值写入确定的存储设备的子集中的每一个。
所选择的可靠性机制可以包括打包(packing)，并且其中存储数据包括：选择存储在可靠性组的N个存储设备的k个存储设备中的k个键对象，k是整数；检索与k个键对象相对应的k个值对象；在k个值对象中不具有k个值对象的最大值大小的值对象的末端上填充虚拟零，以使所有k个值对象的虚拟值大小相同；根据k个键对象创建r个奇偶校验对象，r为整数；将k个键对象写入到k个存储设备；以及将r个奇偶校验对象写入到N个存储设备中的r个存储设备，该r个存储设备中的每一个与k个存储设备不同，其中k+r＝N。
所选择的可靠性机制可以包括使用传统擦除编码打包，并且其中N个存储设备被配置有传统的(k，r)最大距离可分(maximum distance separable，MDS)擦除编码。
所选择的可靠性机制可以包括使用再生擦除编码打包，并且其中N个存储设备被配置有(k，r，d)再生擦除编码。
所选择的可靠性机制可以包括拆分，并且其中存储数据包括：选择KV值；将KV值拆分成k个均等大小的对象，k是整数；根据k个均等大小的对象创建r个奇偶校验对象，r是整数；计算用于散列与所选择的KV值相对应的键的散列；确定N个存储设备中的主设备，其中基于散列放置KV值；以及以连续顺序将k个对象和r个奇偶校验对象写入到N个存储设备中并且从主设备开始，r个存储设备中的每一个不同于k个存储设备，其中k+r＝N。
所选择的可靠性机制可以包括使用传统擦除编码进行拆分，并且其中N个存储设备被配置有传统的(k，r)最大距离可分(MDS)擦除编码。
所选择的可靠性机制可以包括使用再生擦除编码进行拆分，其中N个存储设备被配置有(k，r，d)再生擦除编码，并且其中存储数据还包括使用再生擦除编码将k个均等大小的对象中的每一个拆分成m个子数据包，m是整数，并且将r个奇偶校验对象中的每一个拆分成m个奇偶校验子数据包。
根据本公开的另一实施例，提供了用于基于选择的可靠性机制来存储数据的数据可靠性系统，该数据可靠性系统包括：N个存储设备，被配置为作为使用无状态数据保护的虚拟设备，N是整数；以及虚拟设备管理层，被配置为管理作为虚拟设备的存储设备以根据选择的可靠性机制将数据存储在N个存储设备中的选择的存储设备中，该虚拟设备管理层被配置为：确定数据是否满足与用于存储数据的可靠性机制相对应的阈值；当满足阈值时选择该可靠性机制；并且根据所选择的可靠性机制存储数据。
所选择的可靠性机制可以包括对象复制，并且其中虚拟设备管理层被配置为通过以下来存储数据：选择KV值；计算用于散列与选择的KV值相对应的键的散列；确定N个存储设备中用于存储与KV值相对应的键对象的副本(replicas)的存储设备的子集；以及在相同的用户键名下将与KV值相对应的更新值写入到所确定的存储设备的子集中的每一个。
所选择的可靠性机制可以包括打包，并且其中虚拟设备管理层被配置为通过以下来存储数据：选择存储在可靠性组的N个存储设备的k个存储设备中的k个键对象，k是整数；检索与k个键对象相对应的k个值对象；在k个值对象中不具有k个值对象的最大值大小的值对象的末端上填充虚拟零，以使所有k个值对象的虚拟值大小相同；根据k个键对象创建r个奇偶校验对象，r为整数；将k个键对象写入到k个存储设备；以及将r个奇偶校验对象写入N个存储设备中的r个存储设备，该r个存储设备中的每一个与k个存储设备不同，其中k+r＝N。
所选择的可靠性机制可以包括拆分，并且其中虚拟设备管理层被配置为通过以下来存储数据：选择KV值；将KV值拆分成k个均等大小的对象，k是整数；根据k个均等大小的对象创建r个奇偶校验对象，r是整数；计算用于散列与选择的KV值相对应的键的散列；确定在其中基于散列放置KV值的N个存储设备中的主设备；以及以连续顺序并从主设备开始将k个对象和r个奇偶校验对象写入N个存储设备中，r个存储设备中的每一个不同于k个存储设备，其中k+r＝N。
所选择的可靠性机制可以包括使用再生擦除编码进行拆分，其中N个存储设备被配置有(k，r，d)再生擦除编码，并且其中虚拟设备管理层进一步被配置为通过使用再生擦除编码将k个均等大小的对象中的每一个拆分成m个子数据包(m是整数)，并将r个奇偶校验对象中的每一个拆分成m个奇偶校验子数据包来存储数据。
根据本公开的又一实施例，提供了具有计算机代码的非暂时性计算机可读介质，该计算机代码在处理器上执行时实施在包括N个存储设备的键-值可靠性系统中存储数据的方法，该N个存储设备被分组为可靠性组作为单个逻辑单元并且由虚拟设备管理层管理，N是整数，该方法包括确定数据是否满足与用于存储数据的可靠性机制相对应的阈值，当满足阈值时选择该可靠性机制，并且根据所选择的可靠性机制存储数据。
所选择的可靠性机制可以包括对象复制，并且其中存储数据包括：选择KV值；计算用于散列与所选择的KV值相对应的键的散列；确定N个存储设备中用于存储与KV值相对应的键对象的副本的存储设备的子集；以及在相同的用户键名下将与KV值相对应的更新值写入确定的存储设备的子集中的每一个。
所选择的可靠性机制可以包括打包，并且其中存储数据包括：选择存储在可靠性组的N个存储设备的k个存储设备中的k个键对象，k是整数；检索与k个键对象相对应的k个值对象；在k个值对象中不具有k个值对象的最大值大小的值对象的末端上填充虚拟零，以使所有k个值对象的虚拟值大小相同；根据k个键对象创建r个奇偶校验对象，r为整数；将k个键对象写入到k个存储设备；以及将r个奇偶校验对象写入N个存储设备中的r个存储设备，该r个存储设备中的每一个与k个存储设备不同，其中k+r＝N。
所选择的可靠性机制可以包括拆分，并且其中存储数据包括：选择KV值；将KV值拆分成k个均等大小的对象，k是整数；根据k个均等大小的对象创建r个奇偶校验对象，r是整数；计算用于散列与所选择的KV值相对应的键的散列；确定在其中基于散列放置KV值的N个存储设备中的主设备；以及以连续顺序并从主设备开始将k个对象和r个奇偶校验对象写入到N个存储设备中，r个存储设备中的每一个不同于k个存储设备，其中k+r＝N。
附图说明
从以下结合附图对实施例的描述中，这些和/或其他方面将变得显而易见并且更容易理解，其中：
图1是描绘根据本公开的实施例的用于基于所选择的可靠性机制存储键-值数据的键-值可靠性系统的框图；
图2是描述根据本公开的实施例的基于与键-值对的数据的大小相对应的大小阈值来选择要由键-值可靠性系统使用的可靠性机制的流程图；
图3是描述根据本公开的实施例的一组KV存储设备的框图，该组KV存储设备被配置为根据使用传统擦除编码的K对象(k，r)擦除编码或多对象“打包”的可靠性机制来存储键-值数据；
图4是描绘根据本公开的实施例的根据使用传统擦除编码的K-对象(k，r)擦除编码或多个对象“打包”的可靠性机制来存储值对象和奇偶校验对象的框图。
图5是描绘根据本公开的实施例的一组KV存储设备的框图，该组KV存储设备被配置为根据使用传统擦除编码的单个对象(k，r)擦除编码或“拆分”的可靠性机制来存储键-值数据。
图6是描述根据本公开的实施例的一组KV存储设备的框图，该组KV存储设备被配置为根据使用再生擦除编码的单个对象(k，r，d)擦除编码或“拆分”的可靠性机制来存储键-值数据。
具体实施方式
通过参考以下实施例和附图的详细描述，可以更容易地理解本发明构思的特征和实现其的方法。在下文中，将参考附图更详细地描述实施例。然而，描述的实施例可以以各种不同的形式来体现，并且不应该被解释为仅限于本文所示的实施例。相反，提供这些实施例作为示例使得本公开将是全面的和完整的，并且将向本领域技术人员充分传达本发明构思的各方面和特征。因此，可能没有描述本领域普通技术人员对于完全理解本发明构思的方面和特征不必要的过程、元件和技术。除非另有说明，否则在整个附图和书面描述中相同的参考标记表示相同的元件，因此不再重复其描述。进一步，可能未示出与实施例的描述无关的部分以使描述清楚。在附图中，为了清楚起见，可以增大元件、层和区域的相对尺寸。
本文描述了关于截面图的各种实施例，该截面图示是实施例和/或中间结构的示意图。由此，将预期作为例如制造技术和/或公差的结果的来自图示的形状的变化。进一步，为了描述根据本公开的概念的实施例的目的，本文公开的特定结构或功能描述仅仅是说明性的。因此，本文公开的实施例不应该被解释为限于区域的特殊的示出形状，而是应该包括例如由制造导致的形状方面的偏差。例如，被示出为矩形的注入区域通常将在其边缘处具有圆形或弯曲的特征和/或注入的浓度梯度，而不是从注入区域到非注入区域的二元变化。同样地，通过注入形成的掩埋区域可能导致掩埋区域和通过其进行注入的表面之间的区域中的一些注入。因此，附图中示出的区域在本质上是示意性的，并且它们的形状不意图示出设备的区域的实际形状，并且也不意图是限制性的。另外，如本领域技术人员将认识到的，描述的实施例可以以各种不同的方式进行修改，所有这些都不脱离本发明的精神或范围。
在以下描述中，出于解释的目的，阐述了许多特定细节以提供对各种实施例的全面的理解。然而，显而易见的是，可以在没有这些特定细节的情况下或者利用一个或多个等同布置来实践各种实施例。在其他实例中，以框图形式示出了公知的结构和设备以便避免不必要地模糊各种实施例。
将理解的是，尽管本文可以使用术语“第一”、“第二”、“第三”等来描述各种元件、组件、区域、层和/或区段，但是这些元件、组件、区域、层和/或区段不应受这些术语的限制。这些术语用于将一个元件、组件、区域、层或区段与另一元件、组件、区域、层或区段区分开。因此，在不脱离本发明的精神和范围的情况下，下面描述的第一元件、组件、区域、层或区段可以被称为第二元件、组件、区域、层或区段。
本文可以使用空间相对术语(诸如“之下”、“以下”、“下面”、“下方”、“以上”、“上方”等)以便于解释来描述一个元件或特征与如图所示的(多个)另一元件或(多个)特征的关系。将理解的是，除了图中描绘的取向之外，空间相对术语意图涵括所使用的或操作中的设备的不同取向。例如，如果图中的设备被翻转，则被描述为在其他元件或特征“以下”或“之下”或“下方”的元件将被定向在其他元件或特征“以上”。因此，示例性术语“以下”和“下面”可以涵括以上和以下的取向两者。设备可以以其他方式定向(例如，旋转90度或以其他取向)，并且应当相应地解释本文使用的空间相对描述符。类似地，当第一部分被描述为被布置在第二部分“上”时，这指示第一部分被布置在第二部分的上侧或下侧处，而不限于其基于重力方向的上侧。
将理解的是，当元件、层、区域或组件被称为在另一元件、层、区域或组件“上”、“连接到”或“耦合到”另一元件、层、区域或组件时，其可以直接在另一元件、层、区域或组件上、直接连接到或耦合到另一元件、层、区域或组件，或者可以存在一个或多个中间元件、层、区域或组件。然而，“被直接连接/被直接耦合”指的是一个组件在没有中间组件的情况下直接连接或耦合另一组件。同时，可以类似地解释描述诸如“之间”、“紧邻”或“相邻”和“直接相邻”的组件之间的关系的其他表达。此外，还应理解的是，当元件或层被称为在两个元件或层“之间”时，其可以是两个元件或层之间的唯一元件或层，或者也可能存在一个或多个介于中间的元件或层。
本文使用的术语仅用于描述特定实施例的目的，并不意图限制本公开。如本文所用，单数形式“一”和“一个”也意图包括复数形式，除非上下文另有明确说明。将进一步理解的是，当在本说明书中使用术语“包括了”、“包括”、“具有了”、“具有”时，其指定表述的特征、整数、步骤、操作、元件和/或组件的存在，但不排除一个或多个其他特征、整数、步骤、操作、元件、组件和/或其组的存在或添加。如本文所使用的，术语“和/或”包括一个或多个相关联的列出项目的任何和所有的组合。
如本文所使用的，术语“基本上”、“大约”、“近似地”和类似术语被用作近似的术语而不是用作程度的术语，并且意图解释本领域普通技术人员应认识到的测量值或计算值方面的固有偏差。如本文所使用的，考虑到所讨论的测量和与特殊量的测量相关联的误差(即测量系统的限制)，“大约”或“近似”包括如本领域普通技术人员之一所确定的特殊值的偏差的可接受范围内的表述的值和含义。例如，“大约”可以意味着在一个或多个标准偏差内，或在表述的值的±30％、20％、10％、5％内。进一步，当描述本发明的实施例时，“可以”的使用指的是“本发明的一个或多个实施例”。如本文所使用的，术语“使用了”、“使用”、和“被使用”可以分别被考虑为与术语“利用了”、“利用”和“被利用”同义。并且，术语“示例性”意图指代示例或图示。
当某个实施例可以被不同地实施时，可以与描述的顺序不同地执行特定的过程顺序。例如，两个连续地描述的过程基本上可以被同时执行或者以与描述的顺序相反的顺序执行。
可以利用任何合适的硬件、固件(例如，专用集成电路)、软件或软件、固件和硬件的组合来实施本文描述的根据本公开的实施例的电气或电子设备和/或任何其他相关设备或组件。例如，这些设备的各种组件可以被形成在一个集成电路(integrated circuit，IC)芯片上或分离的IC芯片上。进一步，这些设备的各种组件可以被实施在柔性印刷电路膜、带载封装(tape carrierpackage，TCP)、印刷电路板(printed circuit board，PCB)上，或者形成在一个基底上。进一步，这些设备的各种组件可以是运行在一个或多个处理器上的、在一个或多个计算设备中的过程或线程，该过程或线程执行计算机程序指令并与用于执行本文描述的各种功能的其他系统组件交互。计算机程序指令被存储在存储器中，该存储器可以在计算设备中使用诸如例如随机存取存储器(random-access memory，RAM)的标准存储器设备来实施。该计算机程序指令还可以被存储在其它非瞬时性计算机可读介质中，诸如例如CDROM、闪速驱动器等。并且，本领域技术人员应该认识到，各种计算设备的功能可以被组合或者被集成到单个计算设备当中，或者在不脱离本发明的示范性实施例的范围的情况下特殊计算设备的功能可以分布在一个或多个其它计算设备上。
除非另外定义，否则本文使用的所有术语(包括技术和科学术语)具有与本发明构思所属领域的普通技术人员通常理解的含义相同的含义。将进一步理解的是，诸如在常用字典中定义的那些术语应被解释为具有与其在相关领域和/或本说明书的上下文中的含义一致的含义，并且不应当以理想化或过于正式的意义来解释，除非本文明确定义。
如以下将描述的，本公开的实施例提供了在键-值可靠性系统中可靠地存储键-值数据的方法，该键-值可靠性系统包括被分组为一个逻辑单元的多个键-值(key-value，KV)存储设备。此外，本公开的实施例提供无状态混合可靠性管理器来管理驱动器和控制键-值(KV)对的存储，其依赖于多个可插拔可靠性机制/技术/实施方式，包括：对象复制；K-对象(k，r)擦除编码-打包；单个对象(k，r)擦除编码-拆分；K-对象(k，r，d)再生编码-打包；单个对象(k，r，d)再生编码-拆分。
描述的实施例使能改进的存储器存储(例如，在键-值存储设备中存储键-值数据)，因为无状态混合可靠性管理器(其依赖于多个可插拔可靠性机制)可以管理设备并且可以控制KV对的存储，并且因为所公开的可靠性机制选择的方法确保不同大小的KV对的有效存储、检索和修复。
图1是描绘根据本公开的实施例的用于基于选择的可靠性机制存储键-值数据的键-值可靠性系统的框图。
参考图1，如上所提到的那样，许多新的键-值(KV)存储设备/存储器设备/驱动器/KV-SSD 130可能潜在地受益于为键-值数据和KV存储设备130定制或采用的新的数据可靠性机制。因此，用于这种KV存储设备130的混合键-值可靠性系统可以包括无状态混合可靠性管理器/虚拟设备管理器层/虚拟设备管理层120，其被配置为采用混合可靠性机制来管理KV存储设备130并且根据一个或多个可插拔可靠性机制控制其中的KV对的存储。应当注意的是，尽管固态驱动器(SSD)通常用于指代本文描述的KV存储设备，但是根据本公开的实施例可以使用其他存储设备。下面将描述根据本公开实施例的虚拟设备管理层120的设计和操作。
在本实施例中，虚拟设备管理层120可以使能将键-值数据/KV对170可靠地存储在键-值可靠性系统中的方法。键-值可靠性系统可以包括多个KV存储设备130，它们被分组在一起成为一个逻辑单元。该逻辑单元可以称为可靠性组140。
可靠性组140的KV存储设备130可以存储擦除编码的数据和/或复制的数据的相应组块(chunk)，其可以对应于键-值数据170。可靠性组140中的KV存储设备130暴露了单个虚拟设备110，键-值操作经由虚拟设备管理层120指向该单个虚拟设备110。
虚拟设备110可以具有无状态混合可靠性管理器作为虚拟设备管理层120。也就是说，虚拟设备管理层120可以以无状态方式工作(即无需维持任何键-值到设备映射)。
因此，虚拟设备110可以在N个KV存储设备130上存储键-值数据170，N是整数(例如，KV-SSD 130-1、103-2、130-3、130-4……130-N)，并且可以经由虚拟设备管理层120将键-值数据170存储在KV存储设备130中。也就是说，虚拟设备管理层120可以管理KV存储设备130，并且可以控制其中的KV对的存储。
在其他实施例中，键-值可靠性系统还可以包括高速缓存，以可选地存储与键-值数据170的键相关联的数据和/或元数据，以提高操作速度。可靠性机制可以附加KV对的值以包括与KV对相对应的元数据。也就是说，键和值两者可以被附加有与元数据标识符“MetaID”相对应的信息，以存储特定于该KV对的附加元数据。元数据可以包括校验和、用于识别用于存储数据的可靠性机制的可靠性机制标识符、擦除代码标识符、对象大小、奇偶校验组成员的位置等。
在其他实施例中，键-值可靠性系统还可以包括与以下描述的可靠性机制相对应的布隆过滤器。布隆过滤器可以存储使用对应的可靠性机制存储的键，从而在读取操作中帮助键-值可靠性系统。因此，键-值可靠性系统的一个或多个布隆过滤器或高速缓存可以使得能够快速测试现有的可靠性机制的键。
本文描述的可靠性机制中的每一个可以首先对KV存储设备130中对应的一个KV存储设备的数量的键模使用相同散列函数来存储与键-值数据170相对应的KV对的第一副本或组块。也就是说，对于可插拔可靠性机制中的每一个，可靠性机制可以使用与用户键相同的键来存储至少第一副本/组块。
如上讨论的那样，本公开的实施例提供了多个可插拔可靠性机制，用于确保在多个KV存储设备130中可靠地存储键-值数据170。因此，虚拟设备管理层120可以依赖于可靠性机制，并且可以确定使用哪种可靠性机制。
可靠性机制可以基于诸如在虚拟设备110的设定期间设置的值大小阈值和/或对象读取/写入频率的策略。因此，虚拟设备管理层120可以基于系统的规定策略来选择适当的可靠性机制。
以下描述本公开的实施例的五种可靠性机制、可靠性机制如何工作以及虚拟设备管理层120何时可以适当地使用和选择可靠性机制。这种可靠性机制可以包括可以称为对象复制、K-对象(k，r)擦除编码-打包、单个对象(k，r)擦除编码-拆分、K-对象(k，r，d)再生编码-打包和单个对象(k，r，d)再生编码-拆分的技术。
图2是描绘根据本公开的实施例的基于与键-值对的数据的大小相对应的大小阈值来选择要由键-值可靠性系统使用的可靠性机制的流程图。
参考图2，对于多达所有的基于大小阈值的支持的可靠性机制(例如，前述五个可靠性机制)，虚拟设备管理层120可以确定数据(例如，键-值数据170)的值大小，可以确定值大小是否小于与相应可靠性机制相对应的给定阈值ti并且可以选择其中满足值大小阈值要求的第一可靠性机制。
例如，在S210处，虚拟设备管理层120可以接收被支持的数量“n”个基于大小阈值的可靠性机制，n是整数。在S220处，虚拟设备管理层120可以以从1到n的顺序一次一个地简单检查可靠性机制中的每一个。在S230处，在其检查支持的可靠性机制中的每一个时，虚拟设备管理层120可以确定数据的值大小是否小于与各个可靠性机制相对应的阈值ti。
在S240处，在找到具有大于或等于数据的值大小的阈值ti的可靠性机制时，虚拟设备管理层120可以选择该可靠性机制以供使用。在S250处，在确定在S240处使用哪个可靠性机制时，或者在确定n个可靠性机制中没有一个具有适合于在S220的最后迭代处容纳值大小的阈值ti时，虚拟设备管理层120可以结束其使用哪种可靠性机制的确定。
在本实施例中，根据本文描述的实施例的五种不同的可靠性机制，“n”可以等于5。对于相对非常小的键-值(即其中值大小相对较小)，虚拟设备管理层120可以选择对象复制的可靠性机制以供使用。对于稍大的键-值，虚拟设备管理层120可以选择打包然后拆分(例如，以该顺序)的可靠性机制，同时对每个使用传统的擦除编码。然而，对于甚至更大的键-值，虚拟设备管理层120可以选择打包然后拆分，同时使用再生擦除编码而不是传统的擦除编码。
在本公开的实施例中，用于使用的可靠性机制的选择可以基于对象的对象大小、对象的吞吐量要求、对应的键-值对的读取/写入温度、多个KV存储设备的基本编码能力、和/或检测键是热还是冷的中的一个或多个。例如，“热”键(无论其值大小如何)可以使用对象复制的可靠性机制，而“冷”键可以根据其值的大小被应用于擦除编码方案的可靠性机制中的一个。作为另一示例，是否使用对象复制的可靠性机制的决定可以基于大小和写入温度两者。因此，可以在图2的流程图200中使用与对象读取/写入频率相对应的阈值(而不是与大小相对应的阈值)以确定可靠性机制。
以下讨论五种可靠性机制的相应操作。
返回参考图1，并且如前所提到的那样，当KV对的值大小相对较低时，“对象复制”的可靠性机制可能适合于被虚拟设备管理层120选择。可以对每一对象(例如，每一KV对/键-值数据170)应用对象复制。虽然对象复制的可靠性机制可能具有高存储开销，但它也具有较低的读取和恢复成本，这就是为什么它可以适用于非常小的值大小。
对象复制的可靠性机制也可以适用于具有频繁更新的键-值(例如，键-值数据170)，并且因此可以基于读取和写入频率来选择。
在对象复制期间，每当发生写入时，对象/键-值数据170被复制到一个或多个附加的KV存储设备130。键-值数据170的主副本可以被放置在KV存储设备130中的由键模N的散列指向的一个KV存储设备上。键-值数据170的主副本的复制本可以以循环方式被放置在紧邻KV存储设备130或连续KV存储设备130上。
虚拟设备管理层120或用户可以决定制作多少个键-值数据170的复制本。例如，采用虚拟设备管理层120的分布式系统可以选择3向复制，并且可以使3向复制成为默认值。然而，系统的用户能够将对象的复制本的数量配置为多于或少所选择的默认值。
因此，并且例如如果使用3向复制，如果主KV存储设备130-2具有数据(例如，键-值数据170)的主副本，则虚拟设备管理层120可以存储在后续复制本KV存储设备130-3和130-4上的数据的主副本的复制本，数据的所有副本是相同的。也就是说，数据的副本可以存储在跟随具有数据的主副本的KV存储设备130-2之后的两个(或多个)紧随其后的KV存储设备130-3和130-4上(例如，以循环方式)。
可以在与主KV存储设备130-2相同的键名/相同用户键下存储数据的副本，如在复制本KV存储设备130-3和130-4中的那样。数据的所有副本可以包含校验和和用于指示已被复制的键-值数据170的标识符。
因此，如果某个KV存储设备130故障(例如，如果KV存储设备130-3故障)，则通过针对紧接在故障的KV存储设备130之前和之后的KV存储设备130(例如，紧接在KV存储设备130之前和之后的KV存储设备130-2和KV存储设备130-3)上的键名使用恢复机制恢复该值来确保复制的键也被恢复。
为了总结对象复制的可靠性机制，虚拟设备管理层120可以接收键-值数据170，并且可以对键对象进行散列，从而确定使用哪些KV存储设备130用于存储键对象的复制本。然后，虚拟设备管理层120可以在相同的用户键名(例如，具有适当的MetaID字段)下将更新的值写入所选择的KV存储设备130(例如，选择的KV存储设备130-2、130-3和130-4)。
图3是描述根据本公开的实施例的一组KV存储设备的框图，该KV存储设备被配置为根据使用传统的擦除编码的K-对象(k，r)擦除编码(或多个对象“打包”)的可靠性机制来存储键-值数据。
参考图3，可以为具有小值大小的数据选择使用传统擦除编码的打包的可靠性机制，该数据不适合被拆分为组块(例如，为了更好的数据吞吐量)。例如，虚拟设备管理层120可以为具有大于导致选择先前描述的对象复制的可靠性机制的值大小的值大小的数据但是其仍然相对较小选择使用传统擦除编码的打包的可靠性机制。
使用传统擦除编码的打包可以被配置有传统的(k，r)最大距离可分(MDS)擦除编码，并且可以与任何系统MDS代码一起使用。作为示例，擦除代码可以默认为(4,2)里得-所罗门(Reed-Solomon)码，因为(4,2)Reed-Solomon码被相对较好地研究并且与其相对应的快速实施方式库是容易获得的。
在使用打包(其使用传统擦除编码)的可靠性机制时，挑选来自作为相同奇偶校验组/擦除代码组340的部分的k个不同KV存储设备330的队列的k个键/键对象350并将其擦除编码以打包，k是整数。
例如，虚拟设备管理层120可以为每个KV存储设备330(例如，图1的可靠性组140的每个KV存储设备130)维持最近写入的键对象350的缓冲器，以使虚拟设备管理层120能够从k个不同的KV存储设备330中选择k个键对象350以被擦除编码，从而打包对应于KV对的k个键对象350。
在本示例中，虚拟设备管理层120分别从四个不同的KV存储设备330-1、330-3、330-4和330-N中选择四个键对象350x、350y、350b和350c(即在本例中k＝4)。
图4是描绘根据本公开的实施例的根据使用传统擦除编码的K-对象(k，r)擦除编码(或多个对象“打包”)的可靠性机制来存储值对象和奇偶校验对象的框图。
参考图3和图4，再次将键对象350放置在第(键模n的散列)个KV存储设备330中。也就是说，对于每个键对象350，可以执行键模n的相应散列，其可以被传送到该特定KV存储设备330的队列。在本示例中，Keyi350-i被散列并放置在KV-SSD 1 330-1中，Keyj 350-j被散列并放置在KV-SSD 2 330-2中，并且Keyk350-k被散列并且放置在KV-SSD 4 330-4中。
存储的相应值对象450的用户值长度/值大小462与写入的相同。然而，为了对使能擦除编码的一致性，通过在其上附加“0”填补/虚拟零/虚拟零填充464，用户值/值对象450被视为全部是相同大小。也就是说，因为不同值对象450的相应用户值大小462可以变化(即值对象450可以具有变化的长度/是可变长度的键值)，所以通过实施虚拟零填充464的方法(即为了编码目的，通过用虚拟零填充464的零填充值对象450，同时避免实际重写表示值对象450的数据以包括填充的零)，奇偶校验对象460能够是与奇偶校验组340中的(多个)最大值对象470相同的大小。因此，在本示例中，值对象450“Val x”、“Val y”和“Val b”用实际上未存储在KV存储设备330中的任何一个中的虚拟零来填充，从而看起来是与值对象470“Valc”相同的大小。此后，可以计算奇偶校验对象460。
在对k个键对象350进行编码之后，虚拟设备管理层120可以从与k个键对象350相对应的k个值/k值对象450计算r个奇偶校验对象460，其中r是整数，其中k+r＝N，并且其中N是奇偶校验组340中的KV存储设备330的数量(例如，图1的可靠性组140的N个KV存储设备130)。
虚拟设备管理层120可以将r个奇偶校验对象460存储在奇偶校验组340中的剩余的不同KV存储设备330中(即在与k个KV存储设备330分离的r个KV存储设备330中，k个KV存储设备330具有从中挑选并擦除编码k个键对象350的队列)。因此，k个键对象350和r个奇偶校验对象460中的每一个可以被存储在N个KV存储设备330中的不同的相应一个中，并且与其相对应的数据均等地分布在奇偶校验组340的N个KV存储设备330中的每一个中。
尽管对于使用传统擦除编码的打包的可靠性机制，读取和写入相对简单，但是奇偶校验的恢复和重新计算可能不那么简单。对于奇偶校验的恢复和重新计算(例如，在更新的情况下)，为了使得能够知道哪些键对象350被一起分组在相同奇偶校验组340中从而使得能够计算奇偶校验(例如，哪些键对象350在擦除代码组340中)，关于键对象350的分组的信息、以及每个值对象450的实际值大小462(即没有虚拟零填充464的值大小462)可以作为元数据对象存储在KV存储设备330(例如，图1的KV存储设备130)中的每一个中。因此，在本实施例中，可以使用附加元数据来以键对象350的编码顺序来存储键对象350(例如，位于图1的可靠性组140中的键对象350)、与键对象350相对应的值对象450中的每一个的原始长度、以及KV存储设备130。
例如，元数据对象值可以具有指示可靠性组140的所有键对象350并且还指示值对象450的值大小462的字段，并且可以具有指示奇偶校验对象键(即值对象450包括虚拟零填充464的零)、奇偶校验对象460的值大小462、以及用于识别其中存储r个奇偶校验对象460的对应的r个KV存储设备330的设备ID的另一字段。
可以使用用户键存储数据。元数据可以被存储在使用用户键形成的内部键和表示“元数据”的MetaID指示符中。进一步，值大小462可以被存储在元数据中以使得当通过确定值对象450在哪里结束以及虚拟零填充464的零在哪里开始来重新创建值对象450时，能够知道虚拟零填充464的位置(即零在哪里被添加)用于精确重现(reproduction)。
如果KV存储设备330中的一个故障，因为数据和元数据两者可以被存储在相同的KV存储设备330中，数据和元数据两者可能潜在地丢失，从而使得不可能恢复。然而，为了避免这种情形，可以使用虚拟设备管理层120的“对象复制引擎”来复制元数据对象值，该“对象复制引擎”能够在元数据对象值上实施先前提到的对象复制的可靠性机制。
另外，因为元数据对象值对于可靠性组140中的所有对象是相同的，所以如果KV存储设备330支持对象链接，则相同的元数据对象值可以被链接到通常位于相同KV存储设备330中的多个键名。此外，如果支持批量写入，则可以将对象值一起批处理以获得更好的吞吐量。
为了总结根据本实施例的使用传统擦除编码的打包的可靠性机制，虚拟设备管理层120可以经由缓冲器从k个不同的KV存储设备330中挑选k个最近存储的键对象350。然后，虚拟设备管理层120可以利用虚拟零填充464来检索并填充与相应键对象350(除了奇偶校验组440的(多个)最大值对象470之外)相对应的值对象450，以使得值对象450具有相同大小(例如，(多个)最大值对象470的大小)。然后，虚拟设备管理层120可以使用MDS代码处理来从k个键对象350创建r个奇偶校验对象460。然后，虚拟设备管理层120可以将r个奇偶校验对象460写入除了k个KV存储设备330之外的、从N个KV存储设备330中选择键对象350的r个KV存储设备330，k+r等于N。虚拟设备管理层120然后可以创建表示以上信息的元数据对象。最后，虚拟设备管理层120可以将键对象350和奇偶校验对象460写入到N个KV存储设备330(例如，类似于复制引擎)并且与由用户键和元数据标识符形成的键一起。
图5是描绘根据本公开的实施例的一组KV存储设备的框图，该组KV存储设备被配置为根据使用传统擦除编码的单个对象(k，r)擦除编码(或“拆分”)的可靠性机制来存储键-值数据。
参考图5，对于具有大于适合于先前描述的使用传统擦除编码的对象复制和打包的可靠性机制的值的值大小的值大小的值，虚拟设备管理层120可以选择使用传统擦除编码的单个对象(k，r)擦除编码(或“拆分”)的可靠性机制。使用传统擦除编码的拆分的可靠性机制是每一对象/KV对可靠性机制，其可以适用于具有相对大的值大小的KV值/对象570，并且当KV值570被拆分为k个均等大小的拆分/组块/值/对象550时，其将具有良好的吞吐量。
在拆分KV值570之后，根据实施例，虚拟设备管理层120可以计算k个对象550中的每一个的校验和。此后，虚拟设备管理层120可以在k个对象550中的每一个之前插入元数据。
使用传统擦除编码的拆分可以包括将KV值570拆分为多个较小对象550，并且然后在k个连续存储设备530上分布KV值570的多个较小对象550。因此，k个均等大小的对象550的大小可以由底层KV存储设备530中的每一个来支持。
当使用拆分(其使用传统擦除编码)时，虚拟设备管理层120还可以添加使用系统MDS代码创建的r个奇偶校验值/对象560(例如，虚拟设备管理层120可以被配置有传统的(k，r)MDS擦除编码(诸如(4,2)Reed Solomon代码)作为默认代码)。然后，以类似于使用上述传统擦除编码打包的可靠性机制的方式，虚拟设备管理层120可以将k个对象550和r个奇偶校验对象560写入N个KV存储设备530(k+r＝N)。
因此，虚拟设备管理层120可以将相对大的KV值570拆分为到k个对象550，可以计算和添加r个奇偶校验对象560，并且可以将k个对象550和r个奇偶校验对象560存储在k+r个KV存储设备530中。
在使用拆分(其使用传统擦除编码)的可靠性机制中，在对与KV值570相对应的键580进行散列之后，虚拟设备管理层120可以确定主KV存储设备530a(例如，图5中示出的示例中的KV-SSD 2)以用于存储对应的对象(例如，图5所示示例中的k个对象550中的第一个(D1)可以被存储在散列标记零中)。然后，k+r个对象550、560可以在相同的用户键名下写入主KV存储设备530a和N-1个连续KV存储设备530中的相应的一个。也就是说，在图5中示出的示例中，k个对象550中的第一个可以被写入主KV存储设备530a“KV-SSD 2”中，并且k个对象550中的其余部分与r个奇偶校验对象560一起以循环方式被顺序地写入KV存储设备530“KV-SSD 3”到“KV-SSD N”和“KV-SSD 1”(例如，以类似于关于上述对象复制的可靠性机制所描述的方式)。
为了总结使用传统擦除编码的拆分的可靠性机制，虚拟设备管理层120可以将相对大的KV值570拆分为k个均等大小的对象550。然后，虚拟设备管理层120可以使用MDS代码过程来为k个对象550创建r个奇偶校验对象560。然后，虚拟设备管理层120可以对与KV值570相对应的键进行散列，以确定其中放置对象的主KV存储设备530a。虚拟设备管理层120然后可以以循环方式在相同的用户键名下写入k+r对象550、560，其可以包括由虚拟设备管理层120创建并与主KV存储设备530a和N-1个连续KV存储设备530相对应的适当MetaID字段。
返回参考图3和图4，根据另一实施例，虚拟设备管理层120可以选择使用再生擦除编码的K-对象(k，r，d)擦除编码或多个对象“打包”的可靠性机制(例如，根据图2的流程图200)。本可靠性机制类似于先前描述的使用传统擦除编码的打包的可靠性机制，其中虚拟设备管理层120将k-对象打包在k个KV存储设备中。然而，使用再生擦除编码的打包使用(k，r，d)再生代码，而不是使用传统的(k，r)擦除代码。因此，关于本实施例，通常可以参考图3和图4。
因此，当再生代码适合时但当拆分对象不适合时/当使对象保持完整更适合时，可以使用打包(其使用再生擦除编码)。使用再生擦除编码的打包可能适合于大于用于先前描述的对象复制的可靠性机制以及使用传统擦除编码的打包和拆分的值大小的值大小。当读取对象的多个子数据包不会导致比读取整个对象更低的性能时，使用再生擦除编码的打包可以被使用。当底层(underlying)KV存储设备(例如，图1的KV存储设备130或图3的KV存储设备330)是能够在修复/重建期间辅助的再生代码感知KV存储设备时，使用再生擦除编码的打包也是合适的。
图6是描述根据本公开的实施例的一组KV存储设备的框图，该组KV存储设备被配置为根据使用再生擦除编码的单个对象(k，r，d)擦除编码(或“拆分”)的可靠性机制来存储键-值数据。
参考图6，本可靠性机制允许虚拟设备管理层以类似于使用传统擦除编码的拆分的方式工作，如图4中所示，除了使用(k，r，d)再生代码而不是传统的(k，r)MDS擦除编码。与使用再生擦除编码的打包一样，当底层KV存储设备630是在修复/重建期间辅助的再生代码感知KV存储设备630时，本可靠性机制可以是合适的。
当对象670具有大于与先前描述的可靠性机制相对应的对象的值大小时，并且当读取对象670的k个拆分680的多个子数据包690不会导致比读取整个拆分680更低的性能时(例如，如利用使用传统擦除编码的拆分可靠性机制所做的那样)，使用再生擦除编码的拆分可以是合适的。
使用再生擦除编码的拆分的可靠性机制是每一对象(KV对)机制，其可以适用于具有非常大的值大小的对象/KV值670，即使当对象670被拆分为k个均等大小的对象/拆分650并且当拆分650被进一步虚拟拆分为许多子数据包690时(例如，在本示例中，每一拆分6504个子数据690)，以及当从对象670读取多个子数据包690比读取整个对象670具有更好的吞吐量时，其也将具有合适的吞吐量，其中值大小由所有底层KV存储设备630支持。
类似于使用传统擦除编码的拆分，如图4中所示，本可靠性机制的虚拟设备管理层120可以使用系统再生代码添加r个奇偶校验对象660，并且可以将k个拆分650和r个奇偶校验对象660写入N个KV存储设备630(k+r＝N)。然而，r个奇偶校验对象660中的每一个可以被拆分为许多奇偶校验子数据包692(例如，与每一拆分/k对象650的子数据包690的数量相对应的数量)。与使用传统擦除编码的拆分不同，本实施例中的默认代码可以是(4,2,5)之字形代码。
为了总结使用再生擦除编码的拆分的可靠性机制，虚拟设备管理层120可以将大的KV值670拆分为k个均等大小的对象650。然后，虚拟设备管理层120可以将k个对象650中的每一个拆分为m个均等大小的子数据包690，m是整数。然后，虚拟设备管理层120可以使用再生编码过程来为k个对象650创建r个奇偶校验对象660，并且可以将r个奇偶校验对象660中的每一个拆分为m个均等大小的奇偶校验子数据包692。然后，虚拟设备管理层120可以对与KV值670相对应的键进行散列，以确定其中放置对象的主KV存储设备630a。然后，虚拟设备管理层120可以以循环方式在相同的用户键名下为每一个写入包括m个子数据包690、692的k+r个对象650、660，其可以包括由虚拟设备管理层120创建的并且与主KV存储设备630a和N-1个连续KV存储设备630相对应的适当MetaID字段。
根据以上内容，虚拟设备管理层可以基于数据的一个或多个特性来从一组可靠性机制中选择合适的可靠性机制用于存储数据。因此，本文描述的实施例提供了对存储器存储领域的改进，因为描述的可靠性机制各自都能够进行单个键修复过程。当整个存储器设备故障时，本公开的实施例的虚拟设备管理层可以将故障存储器设备中存在的所有键修复并复制到新的存储器设备。虚拟设备管理层可以通过迭代可靠性组中与故障存储器设备相邻的存储设备中存在的所有键，并通过对可靠性机制确定已经在故障存储器设备上的键进行每一键修复，来完成修复和复制所有键。
本文描述的实施例进一步提供对存储器存储领域的改进，因为具有大于由底层可靠性机制支持(例如，根据底层存储设备大小限制)的值大小的值大小的非常大的KV对被可靠性管理器明确地拆分为多个KV对，并且因为可靠性机制将许多拆分和拆分数量信息以及存储在值中的元数据一起存储。
本文已经公开了实施例，并且虽然采用了特定术语，但是它们仅以一般性和描述性意义来使用和解释，而不是出于限制的目的。在一些情况下，如本领域普通技术人员在提交本申请时显而易见的，结合特定实施例描述的特征、特性和/或元件可以单独使用，或者与结合其他实施例描述的特征、特性和/或元件结合使用，除非另外指明。因此，本领域技术人员将理解的是，在不脱离以下权利要求中阐述的本公开的精神和范围的情况下，可以在形式和细节上进行各种改变，其功能等同物包括于其中。

Claims (20)

1.一种在键-值可靠性系统中存储数据的方法，所述键-值可靠性系统包括N个存储设备，所述N个存储设备被分组为可靠性组作为单个逻辑单元，并且由虚拟设备管理层管理，N是整数，所述方法包括：
确定所述数据是否满足与用于存储所述数据的可靠性机制相对应的阈值；
当满足所述阈值时，选择所述可靠性机制；和
根据所选择的可靠性机制存储所述数据。
2.如权利要求1所述的方法，其中所述阈值基于以下中的一个或多个：
所述数据的对象大小；
所述数据的吞吐量考虑；
所述数据的读取/写入温度；和
所述N个存储设备的基本擦除编码能力。
3.如权利要求1所述的方法，还包括使用一个或多个布隆过滤器或高速缓存用于测试用于可靠性机制的数据。
4.如权利要求1所述的方法，还包括插入元数据，所述元数据具有与用于记录所选择的可靠性机制的数据相对应的键，用于存储所述数据的N个存储设备中的每一个存储设备的一个或多个校验和，在存储所述数据的N个存储设备中的每一个存储设备中存储的数据的值的对象大小，以及用于指示所述N个存储设备中的哪些存储设备正在存储所述数据的N个存储设备的奇偶校验组成员的位置。
5.如权利要求1所述的方法，其中所选择的可靠性机制包括对象复制，并且其中存储所述数据包括：
选择KV值；
计算用于散列与所选择的KV值相对应的键的散列；
确定所述N个存储设备中的存储设备的子集，用于存储与所述KV值相对应的键对象的复制本；和
在相同的用户键名下，将与所述KV值相对应的更新值写入存储设备的所确定子集中的每一个。
6.如权利要求1所述的方法，其中所选择的可靠性机制包括打包，并且其中存储所述数据包括：
选择存储在所述可靠性组的N个存储设备中的k个存储设备中的k个键对象，k为整数；
检索与所述k个键对象相对应的k个值对象；
在k个值对象中不具有所述k个值对象的最大值大小的值对象的末端上填充虚拟零，以使所有所述k个值对象的虚拟值大小相同；
根据所述k个键对象创建r个奇偶校验对象，r是整数；
将所述k个键对象写入所述k个存储设备；和
将所述r个奇偶校验对象写入所述N个存储设备的r个存储设备，所述r个存储设备中的每一个存储设备与所述k个存储设备不同，
其中k+r＝N。
7.如权利要求6所述的方法，其中所选择的可靠性机制包括使用传统的擦除编码的打包，并且
其中所述N个存储设备被配置有传统的(k，r)最大距离可分(MDS)擦除编码。
8.如权利要求6所述的方法，其中所选择的可靠性机制包括使用再生擦除编码的打包，并且
其中所述N个存储设备被配置有(k，r，d)再生擦除编码。
9.如权利要求1所述的方法，其中所选择的可靠性机制包括拆分，并且其中存储所述数据包括：
选择KV值；
将所述KV值拆分为k个均等大小的对象，k是整数；
根据所述k个均等大小的对象创建r个奇偶校验对象，r是整数；
计算用于散列与所选择的KV值相对应的键的散列；
确定在其中基于所述散列放置所述KV值的N个存储设备的主设备；和
以连续顺序并从所述主设备开始将所述k个均等大小的对象和r个奇偶校验对象中的每一个对象写入所述N个存储设备中，
其中k+r＝N。
10.如权利要求9所述的方法，其中所选择的可靠性机制包括使用传统的擦除编码的拆分，并且
其中所述N个存储设备被配置有传统的(k，r)最大距离可分(MDS)擦除编码。
11.如权利要求9所述的方法，其中所选择的可靠性机制包括使用再生擦除编码的拆分，
其中所述N个存储设备被配置有(k，r，d)再生擦除编码，并且
其中存储所述数据还包括使用所述再生擦除编码将所述k个均等大小的对象中的每一个对象拆分为m个子数据包，m是整数，并且将所述r个奇偶校验对象中的每一个对象拆分为m个奇偶校验子数据包。
12.一种用于基于选择的可靠性机制存储数据的数据可靠性系统，所述数据可靠性系统包括：
N个存储设备，被配置为使用无状态数据保护的虚拟设备，N为整数；和
虚拟设备管理层，被配置为管理作为所述虚拟设备的所述N个存储设备，以根据选择的可靠性机制将数据存储在所述N个存储设备的选择的存储设备中，所述虚拟设备管理层被配置为：
确定所述数据是否满足与用于存储所述数据的可靠性机制相对应的阈值；
当满足所述阈值时，选择所述可靠性机制；和
根据所选择的可靠性机制来存储所述数据。
13.如权利要求12所述的数据可靠性系统，其中所选择的可靠性机制包括对象复制，并且其中所述虚拟设备管理层被配置为通过以下存储所述数据：
选择KV值；
计算用于散列与所选择的KV值相对应的键的散列；
确定所述N个存储设备中的存储设备的子集，用于存储与所述KV值相对应的键对象的复制本；和
在相同的用户键名下，将与所述KV值相对应的更新值写入存储设备的所确定的子集中的每一个。
14.如权利要求12所述的数据可靠性系统，其中所选择的可靠性机制包括打包，并且其中所述虚拟设备管理层被配置为通过以下存储所述数据：
选择存储在所述N个存储设备的k个存储设备中的k个键对象，k为整数；
检索与所述k个键对象相对应的k个值对象；
在k个值对象中不具有所述k个值对象的最大值大小的值对象的末端上填充虚拟零，以使所有所述k个值对象的虚拟值大小相同；
根据所述k个键对象创建r个奇偶校验对象，r是整数；
将所述k个键对象写入所述k个存储设备；和
将所述r个奇偶校验对象写入所述N个存储设备的r个存储设备，所述r个存储设备中的每一个存储设备与所述k个存储设备不同，
其中k+r＝N。
15.如权利要求12所述的数据可靠性系统，其中所选择的可靠性机制包括拆分，并且其中所述虚拟设备管理层被配置为通过以下存储所述数据：
选择KV值；
将所述KV值拆分为k个均等大小的对象，k是整数；
根据所述k个均等大小的对象创建r个奇偶校验对象，r是整数；
计算用于散列与所选择的KV值相对应的键的散列；
确定在其中基于所述散列放置所述KV值的N个存储设备的主设备；和
以连续顺序并从所述主设备开始将所述k个均等大小的对象和r个奇偶校验对象中的每一个写入所述N个存储设备中，
其中k+r＝N。
16.如权利要求15所述的数据可靠性系统，其中所选择的可靠性机制包括使用再生擦除编码的拆分，
其中所述N个存储设备被配置有(k，r，d)再生擦除编码，并且
其中所述虚拟设备管理层还被配置为通过使用所述再生擦除编码以将k个均等大小的对象中的每一个对象拆分为m个子数据包，m是整数，并且将r个奇偶校验对象中的每一个对象拆分为m个奇偶校验子数据包来存储所述数据。
17.一种具有计算机代码的非暂时性计算机可读介质，当在处理器上执行所述计算机代码时，实施在键-值可靠性系统中存储数据的方法，所述键-值可靠性系统包括N个存储设备，所述N个存储设备被分组为可靠性组作为单个逻辑单元并且由虚拟设备管理层管理，N是整数，所述方法包括：
确定所述数据是否满足与用于存储所述数据的可靠性机制相对应的阈值；
当满足所述阈值时，选择所述可靠性机制；和
根据所选择的可靠性机制存储所述数据。
18.如权利要求17所述的非暂时性计算机可读介质，其中所选择的可靠性机制包括对象复制，并且其中存储所述数据包括：
选择KV值；
计算用于散列与所选择的KV值相对应的键的散列；
确定所述N个存储设备中的存储设备的子集，用于存储与所述KV值相对应的键对象的复制本；和
在相同的用户键名下，将与所述KV值相对应的更新值写入存储设备的所确定的子集中的每一个。
19.如权利要求17所述的非暂时性计算机可读介质，其中所选择的可靠性机制包括打包，并且其中存储所述数据包括：
选择存储在所述可靠性组的N个存储设备的k个存储设备中的k个键对象，k为整数；
检索与所述k个键对象相对应的k个值对象；
在k个值对象中不具有所述k个值对象的最大值大小的值对象的末端上填充虚拟零，以使所有所述k个值对象的虚拟值大小相同；
根据所述k个键对象创建r个奇偶校验对象，r是整数；
将所述k个键对象写入所述k个存储设备；和
将所述r个奇偶校验对象写入所述N个存储设备的r个存储设备，所述r个存储设备中的每一个存储设备与所述k个存储设备不同，
其中k+r＝N。
20.如权利要求17所述的非暂时性计算机可读介质，其中所选择的可靠性机制包括拆分，并且其中存储所述数据包括：
选择KV值；
将所述KV值拆分为k个均等大小的对象，k是整数；
根据所述k个均等大小的对象创建r个奇偶校验对象，r是整数；
计算用于散列与所选择的KV值相对应的键的散列；
确定在其中基于所述散列放置所述KV值的N个存储设备的主设备；和
以连续顺序将所并从所述主设备开始述k个均等大小的对象和r个奇偶校验对象中的每一个对象写入所述N个存储设备，
其中k+r＝N。
CN201910007109.0A 2018-01-19 2019-01-04 用于对象存储设备的混合数据可靠性的系统和方法 Active CN110058806B (zh)

Applications Claiming Priority (10)

Application Number Priority Date Filing Date Title
US15/876,028 2018-01-19
US15/876,028 US10795760B2 (en) 2017-03-20 2018-01-19 Key value SSD
US201862635311P 2018-02-26 2018-02-26
US62/635,311 2018-02-26
US15/967,302 2018-04-30
US15/967,302 US10552062B2 (en) 2017-03-20 2018-04-30 System and method for storing very large key value objects
US201862713479P 2018-08-01 2018-08-01
US62/713,479 2018-08-01
US16/165,655 US11275762B2 (en) 2017-03-20 2018-10-19 System and method for hybrid data reliability for object storage devices
US16/165,655 2018-10-19

Publications (2)

Publication Number Publication Date
CN110058806A true CN110058806A (zh) 2019-07-26
CN110058806B CN110058806B (zh) 2024-10-18

Family

ID=67315591

Family Applications (1)

Application Number Title Priority Date Filing Date
CN201910007109.0A Active CN110058806B (zh) 2018-01-19 2019-01-04 用于对象存储设备的混合数据可靠性的系统和方法

Country Status (4)

Country Link
JP (1) JP7171452B2 (zh)
KR (1) KR102663422B1 (zh)
CN (1) CN110058806B (zh)
DE (1) DE102018131523A1 (zh)

Families Citing this family (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
KR102712808B1 (ko) * 2022-03-02 2024-10-02 인하대학교 산학협력단 비디오 스토리지 시스템에서 성능 저하 읽기를 위한 i/o 대역폭 최소화를 위한 중복 선택 방법 및 장치

Citations (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20080010580A1 (en) * 2005-06-27 2008-01-10 Seagate Technology Llc Redundancy for storage data structures
US8504535B1 (en) * 2010-12-20 2013-08-06 Amazon Technologies, Inc. Erasure coding and redundant replication
US8949180B1 (en) * 2012-06-28 2015-02-03 Emc International Company Replicating key-value pairs in a continuous data protection system
US8977804B1 (en) * 2011-11-21 2015-03-10 Western Digital Technologies, Inc. Varying data redundancy in storage systems
US20170177266A1 (en) * 2015-12-21 2017-06-22 Quantum Corporation Data aware deduplication object storage (dados)

Family Cites Families (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20020165942A1 (en) * 2001-01-29 2002-11-07 Ulrich Thomas R. Data path accelerator with variable parity, variable length, and variable extent parity groups
JP2013050836A (ja) * 2011-08-31 2013-03-14 Nec Corp ストレージシステムとデータ・インテグリティのチェック方法並びにプログラム
US8799746B2 (en) * 2012-06-13 2014-08-05 Caringo, Inc. Erasure coding and replication in storage clusters
CN102937967B (zh) * 2012-10-11 2018-02-27 南京中兴新软件有限责任公司 数据冗余实现方法及装置
US9135993B2 (en) * 2013-02-07 2015-09-15 Seagate Technology Llc Temperature based logic profile for variable resistance memory cells

Patent Citations (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20080010580A1 (en) * 2005-06-27 2008-01-10 Seagate Technology Llc Redundancy for storage data structures
US8504535B1 (en) * 2010-12-20 2013-08-06 Amazon Technologies, Inc. Erasure coding and redundant replication
US8977804B1 (en) * 2011-11-21 2015-03-10 Western Digital Technologies, Inc. Varying data redundancy in storage systems
US8949180B1 (en) * 2012-06-28 2015-02-03 Emc International Company Replicating key-value pairs in a continuous data protection system
US20170177266A1 (en) * 2015-12-21 2017-06-22 Quantum Corporation Data aware deduplication object storage (dados)

Also Published As

Publication number Publication date
KR20190088874A (ko) 2019-07-29
KR102663422B1 (ko) 2024-05-07
JP2019128959A (ja) 2019-08-01
JP7171452B2 (ja) 2022-11-15
CN110058806B (zh) 2024-10-18
DE102018131523A1 (de) 2019-08-14

Similar Documents

Publication Publication Date Title
US11275762B2 (en) System and method for hybrid data reliability for object storage devices
CN115114059B (zh) 使用区来管理归因于存储装置故障的容量减小
CN102937967B (zh) 数据冗余实现方法及装置
KR101758544B1 (ko) 비휘발성 메모리 시스템에서의 동기 미러링
US11288119B2 (en) Key value SSD
EP3230870B1 (en) Elastic metadata and multiple tray allocation
US9280457B2 (en) System and method for volume block number to disk block number mapping
US20240248651A1 (en) Data structure storage and data management
CN112889034A (zh) 对数据块的内容驱动的分布进行擦除编码
CN112889033A (zh) 提高具有变化的数据冗余方案的系统中的可用存储空间
KR102460568B1 (ko) 대형 키 밸류 객체들을 저장하는 시스템 및 방법
US9543988B2 (en) Adaptively strengthening ECC for solid state cache
US20160098322A1 (en) Background Initialization for Protection Information Enabled Storage Volumes
CN115114055A (zh) 管理归因于存储装置故障的容量减小和恢复
CN115114057A (zh) 管理在下移多层级存储器单元时的容量减小
CN115114054A (zh) 管理发生故障的多层级存储器单元的存储空间减小和再用
CN115114061A (zh) 管理归因于存储装置故障的容量减小
CN110058806B (zh) 用于对象存储设备的混合数据可靠性的系统和方法
US7685377B1 (en) Piecewise logical data management
CN109002266A (zh) 一种在传统raid组上提升元数据可靠性的方法
US10747610B2 (en) Leveraging distributed metadata to achieve file specific data scrubbing
WO2015161140A1 (en) System and method for fault-tolerant block data storage

Legal Events

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