Microsoft Technology Licensing, LLC

Parikshit Santhan Gopalan

Sergey M Yekhanin

John D Davis

Karin Strauss

Mark Steven Manasse

Cheng Huang

Huseyin Simitci

Jin Li

Bradley Gene Calder

Aaron William Ogus

Robert John Jenkins, Jr

Edmund Bernard Nightingale

Alexander Shamis

Dennis Craig Fetterly

In various embodiments, methods and systems for erasure coding with enhanced local protection groups are provided. An erasure coding scheme can be defined based on a Vertical Local Reconstruction Code (VLRC) that achieves high storage efficiency by combining the Local Reconstruction Code and conventional erasure coding, where the local reconstruction code (LRC) is carefully laid out across zones. Thus, when a zone is down, remaining fragments form an appropriate LRC. Further, an inter-zone erasure coding scheme&#x2014;Zone Local Reconstruction Code (ZZG-2 code)&#x2014;is provided having both local reconstruction within every zone and a-of-b recovery property across zones. An inter-zone adaptive erasure coding (uber code) scheme is provided, the uber code is configurable to produce near optimal performance in different environments characterized by intra and inter-zone bandwidth and machine failure rates. It is contemplated that embodiments described herein include functionality for recognizing correctable patterns and decoding techniques for coding schemes.

Flexible erasure coding with enhanced local protection group structures

The techniques and/or systems described herein implement erasure coding to generate various chunks for a data collection (e.g., data chunks and at least one encoding chunk). The chunks are then distributed and stored within an individual group (e.g., a pod) of storage units, where a pod of storage units is determined based on characteristics that affect an amount of time it takes to recover a data collection or to restore lost data.

Erasure coding of data within a group of storage units based on connection characteristics

A codeword is generated from a message. One or more anchor values are appended to the codeword at predetermined anchor positions. Before the codeword is stored in a memory block, the locations and values of stuck cells in the memory block are determined. Based on the values and positions of the stuck cells, the values of the codeword are remapped so that values of the codeword that are the same as the values of the stuck cells are placed at the positions of the stuck cells. The remapped codeword is stored in the memory block. When the message is later read, the original codeword can be recovered from the remapped codeword based on the locations of the anchor values in the remapped codeword.

Message storage in memory blocks using codewords

A memory region can durably self-identify as being faulty when read. Information that would have been assigned to the faulty memory region can be assigned to another of that sized region in memory using a replacement encoding technique. For phase change memory, at least two fault states can be provided for durably self-identifying a faulty memory region; one state at a highest resistance range and the other state at a lowest resistance range. Replacement cells can be used to shift or assign data when a self-identifying memory fault is present. A memory controller and memory module, alone or in combination may manage replacement cell use and facilitate driving a newly discovered faulty cell to a fault state if the faulty cell is not already at the fault state.

Self-identifying memory errors

In some examples, an erasure code can be implemented to provide for fault-tolerant storage of data. Maximally recoverable cloud codes, resilient cloud codes, and robust product codes are examples of different erasure codes that can be implemented to encode and store data. Implementing different erasure codes and different parameters within each erasure code can involve trade-offs between reliability, redundancy, and locality. In some examples, an erasure code can specify placement of the encoded data on machines that are organized into racks.

Local erasure codes for data storage

A memory controller can include an error correction module for extended lifetime memory that tracks at least one sized block of non-fault consecutive bits within the disabled page as spare blocks and reuses the spare blocks from the disabled pages as an error correction resource for active blocks. The active blocks can store data, data and metadata, or metadata only (e.g., error correction metadata). A method for extended lifetime memory can include, for an active block of metadata containing at least one fault, using at least one spare block to correct the data of the active block. For an active block of data containing at least one fault, the data can be initially corrected via XOR correction with a first spare block and then ultimately corrected via XOR correction with a second spare block.

Extended lifetime memory

In various embodiments, methods and systems for erasure coding data across multiple storage zones are provided. This may be accomplished by dividing a data chunk into a plurality of sub-fragments. Each of the plurality of sub-fragments is associated with a zone. Zones comprise buildings, data centers, and geographic regions providing a storage service. A plurality of reconstruction parities is computed. Each of the plurality of reconstruction parities computed using at least one sub-fragment from the plurality of sub-fragments. The plurality of reconstruction parities comprises at least one cross-zone parity. The at least one cross-zone parity is assigned to a parity zone. The cross-zone parity provides cross-zone reconstruction of a portion of the data chunk.

Erasure coding across multiple zones and sub-zones

Cloud data storage systems, methods, and techniques partition system data symbols into predefined-sized groups and then encode each group to form corresponding parity symbols, encode all data symbols into global redundant symbols, and store each symbol (data, parity, and redundant) in different failure domains in a manner that ensures independence of failures. In several implementations, the resultant cloud-encoded data features both data locality and ability to recover up to a predefined threshold tolerance of simultaneous erasures (unavailable data symbols) without any information loss. In addition, certain implementations also feature the placement of cloud-encoded data in domains (nodes or node groups) to provide similar locality and redundancy features simultaneous with the recovery of an entire domain of data that is unavailable due to software or hardware upgrades or failures.

Cloud data storage using redundant encoding

A generator matrix is provided to generate codewords from messages of write operations. Rather than generate a codeword using the entire generator matrix, some number of bits of the codeword are determined to be, or designated as, stuck bits. One or more submatrices of the generator matrix are determined based on the columns of the generator matrix that correspond to the stuck bits. The submatrices are used to generate the codeword from the message, and only the bits of the codeword that are not the stuck bits are written to a memory block. By designating one or more bits as stuck bits, the operating life of the bits is increased. Some of the submatrices of the generator matrix may be pre-computed for different stuck bit combinations. The pre-computed submatrices may be used to generate the codewords, thereby increasing the performance of write operations.

Growing community of inventors

Mountain View, CA, United States of America

Parikshit Santhan Gopalan