Microsoft Technology Licensing, LLC

Microsoft Corporation

Cheng Huang

Jin Li

Aaron William Ogus

Huseyin Simitci

Bradley Gene Calder

Sergey M Yekhanin

Philip Andrew Chou

Parikshit Santhan Gopalan

Keith W Ross

Ju Wang

Shane Kumar Mainali

Andrew James Edwards

Yikang Xu

Minghua Chen

Ioan Oltean

Yu Lin Chen

Douglas Wayne Phillips

Jinyang Li

Nicholas Leonard Holt

Shuai Mu

Anders Edgar Klemets

Dan Teodosiu

Jacob Rubin Lorch

Alexandra K Heron

Eyal Schwartz

John T Spivey

Chao Zhang

Jonathan Roshan Tuliani

Jieqing Wang

Robert John Jenkins, Jr

Sridhar Srinivasan

Albert Gordon Greenberg

Sanjeev Mehrotra

Ming Zhang

Sudipta Sengupta

Edmund Bernard Nightingale

David A Maltz

Yunnan Wu

Hao Chen

Garret Buban

Aleksandar Kuzmanovic

David C Steere

Alexander Shamis

Dennis Craig Fetterly

Jay Thaler

Manish Jain

Felix Livni

Peng Huang

Jianfeng Zhu

Ye Yi Wang

Jonathan J Bruso

Amit Kumar Mondal

Daniel Chen

Marat Marsovich Galeev

Henning Klein

Ivan Ivanov Batanov

Viveck Cadambe

Richard R Yang

Jiajun Wang

Tom Kleinpeter

Parikshit Santhana Gopalan

Tejas Shah

Zhenshan Yu

Terry Chen

Yilong Zhao

Mauricio David Zaragoza Ibarra

Yiheng Tao

Various embodiments, methods, and systems for erasure coding with overlapped local reconstruction codes, are provided. An erasure coding scheme can be defined based on Overlapped Local Reconstruction Codes (OLRC) that achieve high storage efficiency by providing fault tolerance properties that optimize reconstruction for common cases of failures while maintaining the reconstruction costs for uncommon case of failures. In operation, a data chunk is divided into data fragments. The data fragments correspond to zones. A plurality of parity fragments is computed using the data fragments. A parity fragment is computed using a subset of the data fragments. The plurality of parity fragments are assigned to the zones comprising the data fragments, where the data fragments and the plurality of parity fragments define overlapped local construction codes having a plurality of local groups. An unavailable data fragment is recoverable from at least two local groups from the plurality of local groups.

Erasure coding with overlapped local reconstruction codes

In various embodiments, methods and systems for implementing a distributed metadata management system in distributed storage systems are provided. A distributed storage system operates based on data storage resources (e.g., extents and streams). The distributed metadata management system is implemented for extent and stream metadata to facilitate the scalability of metadata processing. The distributed storage system implements extent managers and stream managers that independently manage extent and stream metadata, respectively. The extent managers are associated with an extent table that stores extent metadata. The stream managers are associated with streams that store associations with extents. The distributed metadata management system can also utilize a bootstrap layer that leverages components of a legacy distributed storage system to facilitate distributed management of extent and stream metadata. The bootstrap layer is used to store the extent table as a system table and to persist the state of the stream manager as system streams.

Distributed metadata management in a distributed storage system

In various embodiments, methods and systems for implementing distributed data object management are provided. The distributed data object management system includes a distributed storage system having a local metadata-consensus information store in and one or more remote metadata-consensus information stores. A metadata-consensus information store is configured to store metadata-consensus information. The metadata-consensus information corresponds to erasure coded fragments of a data object and instruct on how to manage the erasure coded fragments. The distributed storage system further includes a local data store and one or more remote data stores for the erasure coded fragments. The distributed data object management system includes a distributed data object manager for operations including, interface operations, configuration operations, write operations, read operations, delete operations, garbage collection operations and failure recovery operations. The distributed data object management system is operates based on metadata paths and data paths, operating in parallel, for write operations and read operations.

Distributed data object management system

In various embodiments, methods and systems for implementing distributed data object management are provided. The distributed data object management system includes a local metadata-consensus information store and one or more remote metadata-consensus information stores for metadata-consensus information and a local data store and one or more remote data stores for erasure coded fragments. For a write operation, corresponding metadata writes and data writes are performed in parallel using a metadata write path and a data write path, respectively, when writing to the local metadata-consensus information store and the one or more remote metadata-consensus information stores and the local data store and the one or more remote data stores. And, for a read operation, corresponding metadata reads and data reads are performed in parallel using a metadata read path and a data read path, respectively, when reading from the metadata-consensus information stores and the data stores.

Distributed data object management system operations

Various methods, computer storage media, and systems for implementing hierarchical data integrity verification, in distributed computing systems, are provided. A data manager operates to perform hierarchical data integrity verification operations on message-digests that are associated based on a linear property of a non-cryptographic function, such that a data integrity of source data is verifiable based on the message-digests combined based on an exclusive-or (XOR) operator. The data manager accesses data fragments that are erasure coded fragments and a parity fragment generated from the data fragments, which correspond to source data. The data manager generates and stores the data-fragment message-digests, data-parity message-digests, and parity-fragment message-digests in corresponding data fragment zones and parity fragment zones. The data manager executes two different types of hierarchical data integrity verification operations, to verify the data integrity of the source data, the operations include: local data integrity verification operations, and global data integrity verification operations.

Hierarchical data integrity verification of erasure coded data in a distributed computing system

Various embodiments, methods and systems for implementing distributed data synchronization in a distributed computing system, are provided. In operation, a data record of a first data set is accessed. The data record is encoded to generate, for a first distributed invertible bloom filter ('DIBF') data structure, a first DIBF record. The first DIBF record comprises a data field and a quantifier field that includes a quantifier value, which represents a reference count for the first DIBF record. The first and second DIBF data structures are accessed and decoded based at least in part on computing a difference between a quantifier value in the first DIBF data structure and a quantifier value in the second DIBF data structure. A determination whether a match exists between the first DIBF data structure and second DIBF data structure is made based on computing the difference between the first and second DIBF data structures.

Distributed data synchronization in a distributed computing system

In various embodiments, methods and systems for implementing garbage collection in distributed storage systems are provided. The distributed storage system operates based on independent management of metadata of extent and stream data storage resources. A hybrid garbage collection system based on reference counting garbage collection operations and mark-and-sweep garbage collection operations is implemented. An extent lifetime table that tracks reference weights and mark sequences for extents is initialized and updated based on indications from extent managers and stream managers, respectively. Upon determining that an extent is to be handed-off from weighted reference counting garbage collection operations to mark-and-sweep garbage collection operations, a reference weight field for the extent is voided and a mark sequence field of the extent is updated. The mark sequence field is updated with a latest global sequence number. The mark-and-sweep garbage collection operations are utilized to reclaim the extent when the extent is no longer referenced.

Hybrid garbage collection in a distributed storage system

A system includes determination of a plurality of meta-copysets of a plurality of storage devices, each of the meta-copysets including a first number of storage devices, determination of a first copyset of a second number of storage devices from a first one of the meta-copysets, where the second number is less than the first number, storage of first data in a fault-tolerant format using the first copyset, determination to migrate the first data from a first storage device of the first copyset, and, in response to the determination to migrate the first data, determine a second copyset of the second number of storage devices including a storage device from the first meta-copyset which is not in the first copyset, and the storage devices of the first copyset except for the first storage device of the first copyset and storage of the first data in a fault-tolerant format using the second copyset.

Meta-copysets for fault-tolerant data storage

A first set of replicated state machines includes a first state machine that compares a clock value included in a state update message incremented by a first amount, a clock value for the first state machine incremented by a second amount, and a current local wall clock value for the first state machine to determine a maximum value and assigns the maximum value as the clock value for the first state machine. Additionally, in response to a passage of an amount of time, the first state machine advances the clock value for the first state machine to its current local wall clock value and propagates this clock value to the other state machines in the first set of replicated state machines. The advancement of the clock value for all state machines even in the absence of state updates improves their ability to respond to distributed read requests.

Performing scalable, causally consistent reads using a logical wall clock

A 'Media Sharer' operates within peer-to-peer (P2P) networks to provide a dynamic peer-driven system for streaming high quality multimedia content, such as a video-on-demand (VoD) service, to participating peers while minimizing server bandwidth requirements. In general, the Media Sharer provides a peer-assisted framework wherein participating peers assist the server in delivering on-demand media content to other peers. Participating peers cooperate to provide at least the same quality media delivery service as a pure server-client media distribution. However, given this peer cooperation, many more peers can be served with relatively little increase in server bandwidth requirements. Further, each peer limits its assistance to redistributing only portions of the media content that it also receiving. Peer upload bandwidth for redistribution is determined as a function of surplus peer upload capacity and content need of neighboring peers, with earlier arriving peers uploading content to later arriving peers.

Smart pre-fetching for peer assisted on-demand media

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

Techniques are provided for the caching of content prior to the content being requested. A request for desired content may be received from a client application at a caching server. The request may also indicate additional content related to the desired content that may be subsequently requested by the client application. The indicated additional content (and the desired content, if not already cached) is retrieved from an origin server. The desired content is transmitted to the client application at the user device, and the additional content is cached at the caching server. Subsequently, a second request may be received from the client application that includes a request for the additional content. The additional content, which is now cached at the caching server, is served to the client application by the caching server in response to the second request (rather than being retrieved from the origin server).

Application-driven CDN pre-caching

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

Growing community of inventors

Redmond, WA, United States of America

Cheng Huang