Data resiliency in a shared memory pool

• US 9,547,553 B1
• Filed: 03/08/2015
• Issued: 01/17/2017
• Est. Priority Date: 03/10/2014
• Status: Active Grant

• Current Assignee: DataRobot, Inc.
• Original Assignee: Parallel Machines Ltd.
• Inventors: Bar-Or, Ofer, Khermosh, Lior, Braverman, Avner, Shalvi, Ofir, Zuckerman, Gal
• Primary Examiner(s): Lottich, Joshua P
• Application Number:
  US14/641,401
• Time in Patent Office: 681 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 11/10 Adding special bits or symbols to the coded information, e.g. parity check, casting out 9's or 11's
• CPC Class Codes: G06F 11/1064 in cache or content addressable memories
• CPC Class Codes: G06F 12/0813 with a network or matrix configuration
• CPC Class Codes: G06F 12/0868 Data transfer between cache memory and other subsystems, e.g. storage devices or host systems
• CPC Class Codes: G06F 12/1458 by checking the subject access rights
• CPC Class Codes: G06F 2212/1024 Latency reduction
• CPC Class Codes: G06F 2212/1032 Reliability improvement, data loss prevention, degraded operation etc
• CPC Class Codes: G11C 29/52 Protection of memory contents; Detection of errors in memory contents
• CPC Class Codes: G11C 7/1072 for memories with random access ports synchronised on clock signal pulse trains, e.g. synchronous memories, self timed memories
• CPC Class Codes: H03M 13/373 with erasure correction and erasure determination, e.g. for packet loss recovery or setting of erasures for the decoding of Reed-Solomon codes

Abstract

Various systems to achieve data resiliency in a shared memory pool are presented. Multiple memory modules are associated with multiple data interfaces, one or multiple erasure-coding interfaces are communicatively connected with the multiple data interfaces, and multiple compute elements are communicatively connected with one or multiple erasure-coding interfaces. Data sets are erasure-coded, and the resulting fragments are stored in random access memory modules distributed throughout the system. Storage in RAM allows real-time fetching of fragments using random-access read cycles and streaming of fragments using random-access write cycles, in which read operations include reconstruction of data sets from fetched data fragments, and write operations allow conversion of data sets into fragments which are then streamed and distributively stored. Distributed memory creates data resiliency to reconstruct original data sets in cases such as data corruption, failure of a memory module, failure of a data interface, or failure of a compute element.

Claims

1. A system operative to achieve data resiliency in a shared memory pool, comprising:

a plurality of random access memory modules belonging to a shared memory pool and associated respectively with a plurality of data interfaces;

a first erasure-coding interface communicatively connected with said plurality of data interfaces using a switching network selected from a group consisting of;

(i) a non-blocking switching network, (ii) a fat tree packet switching network, and (iii) a cross-bar switching network; and

a first compute element communicatively connected with said first erasure-coding interface,

wherein;

said plurality of random access memory modules are configured to distributively store a plurality of data sets, such that each data set is distributively stored among at least two of the random access memory modules in a form of a plurality of data fragments coded using a first erasure-coding scheme, and each data fragment is stored on a different one of the at least two random access memory modules;

said first compute element is configured to send to the first erasure-coding interface a request for one of the data sets;

the first erasure-coding interface is configured to;

convert said request into a first plurality of secondary data requests;

send, via the switching network, said first plurality of secondary data requests respectively into at least a first sub-set of said plurality of data interfaces;

receive as responses, via the switching network, at least a sub-set of said plurality of data fragments associated with said one of the data sets;

reconstruct said one of the data sets, using said first erasure-coding scheme, from said data fragments received; and

send said reconstruction to the first compute element as a response to said request made; and

each of the plurality of data interfaces is configured to;

receive, from the first erasure-coding interface, one of said plurality of secondary data requests;

extract, from the respective random access memory module, using a random-access read cycle, one of the data fragments associated with said secondary data request; and

send the data fragment extracted to said first erasure-coding interface as part of said responses received by the first erasure-coding interface,

such that a combined result is that a first period beginning in said sending of the request and ending in said receiving of the response to said request is bounded by 5 (five) microseconds.

2. The system of claim 1, wherein:

one of the plurality of random access memory modules and the associated data interface are located in a first server; and

said first erasure-coding interface, said first compute element, others of the plurality of random access memory modules, and others of the associated data interfaces, are all located outside said first server;

such that the system is a distributed system that is configured to endure any failure in the first server, and such that said reconstruction is unaffected by said failure, due the use of said first erasure-coding interface and the use of said first erasure-coding scheme.

3. A system operative to achieve data resiliency in a shared memory pool, comprising:

a plurality of memory modules belonging to a shared memory pool and associated respectively with a plurality of data interfaces;

a first erasure-coding interface communicatively connected with said plurality of data interfaces; and

a first compute element communicatively connected with said first erasure-coding interface,

wherein;

said plurality of memory modules are configured to distributively store a plurality of data sets, such that each data set is distributively stored among at least two of the memory modules in a form of a plurality of data fragments coded using a first erasure-coding scheme, and each data fragment is stored on a different one of the at least two memory modules;

said first compute element is configured to send to the first erasure-coding interface a request for one of the data sets;

the first erasure-coding interface is configured to;

convert said request into a first plurality of secondary data requests;

send said first plurality of secondary data requests respectively into at least a first sub-set of said plurality of data interfaces;

receive as responses at least a sub-set of said plurality of data fragments associated with said one of the data sets;

reconstruct said one of the data sets, using said first erasure-coding scheme, from said data fragments received; and

send said reconstruction to the first compute element as a response to said request made; and

each of the plurality of data interfaces is configured to;

receive, from the first erasure-coding interface, one of said plurality of secondary data requests;

extract, from the respective memory module, using a random-access read cycle, one of the data fragments associated with said secondary data request and send the data fragment extracted to said first erasure-coding interface as part of said responses received by the first erasure-coding interface,

in which the system further comprising;

additional erasure-coding interfaces, each configured to perform all tasks associated with said first erasure-coding interface, such that any failure of the first erasure-coding interface still allows the system to perform said reconstruction using at least one of the additional erasure-coding interfaces instead of the first erasure-coding interface.

4. The system of claim 3, wherein:

said first erasure-coding interface is located in a second server; and

said additional erasure-coding interfaces, said first compute element, and said others of the plurality of memory modules and the associated data interfaces, are all located outside said second server,

such that the system is a distributed system, and is configured to endure any failure in the second server, and such that said reconstruction is still possible even after a failure in the second server.

5. A system operative to achieve data resiliency in a shared memory pool, comprising:

a plurality of memory modules belonging to a shared memory pool and associated respectively with a plurality of data interfaces;

a first erasure-coding interface communicatively connected with said plurality of data interfaces; and

a first compute element communicatively connected with said first erasure-coding interface,

wherein;

said plurality of memory modules are configured to distributively store a plurality of data sets, such that each data set is distributively stored among at least two of the memory modules in a form of a plurality of data fragments coded using a first erasure-coding scheme, and each data fragment is stored on a different one of the at least two memory modules;

said first compute element is configured to send to the first erasure-coding interface a request for one of the data sets;

the first erasure-coding interface is configured to;

convert said request into a first plurality of secondary data requests;

send said first plurality of secondary data requests respectively into at least a first sub-set of said plurality of data interfaces;

receive as responses at least a sub-set of said plurality of data fragments associated with said one of the data sets;

reconstruct said one of the data sets, using said first erasure-coding scheme, from said data fragments received; and

send said reconstruction to the first compute element as a response to said request made; and

each of the plurality of data interfaces is configured to;

receive, from the first erasure-coding interface, one of said plurality of secondary data requests;

extract, from the respective memory module, using a random-access read cycle, one of the data fragments associated with said secondary data request; and

send the data fragment extracted to said first erasure-coding interface as part of said responses received by the first erasure-coding interface,

in which the system further comprising;

additional erasure-coding interfaces, each configured to perform all tasks associated with said first erasure-coding interface; and

additional compute elements, each configured to associate with at least one of the erasure-coding interfaces in conjunction with erasure-coding transactions associated with the plurality of memory modules and the plurality of data fragments,

such that each of the plurality of compute elements, including the first compute element, is configured to receive said one of the data sets reconstructed using at least one of said additional erasure-coding interfaces,

and such that said shared memory pool is configured to serve said plurality of data sets to said plurality of compute elements regardless of any failure in one of the memory modules.

6. The system of claim 5, wherein:

said plurality of memory modules are based on dynamic-random-access-memory (DRAM);

at least 64 (sixty four) memory modules are included in said plurality of memory modules; and

said first erasure-coding interface together with the additional erasure-coding interfaces are communicatively connected with said plurality of data interfaces using a switching network selected from a group consisting of;

(i) a non-blocking switching network, (ii) a fat tree packet switching network, and (iii) a cross-bar switching network,

such that a combined result is that a rate at which said data sets are being reconstructed is at least 400 Giga-bits-per second.

7. A system operative to achieve data resiliency in a shared memory pool, comprising:

a plurality of random access memory modules belonging to a shared memory pool and associated respectively with a plurality of data interfaces;

a first erasure-coding interface communicatively connected with said plurality of data interfaces using a switching network selected from a group consisting of;

(i) a non-blocking switching network, (ii) a fat tree packet switching network, and (iii) a cross-bar switching network; and

a first compute element communicatively connected with said first erasure-coding interface,

wherein;

said plurality of random access memory modules are configured to distributively store a plurality of data sets, such that each data set is distributively stored among at least two of the random access memory modules in a form of a plurality of data fragments coded using a first erasure-coding scheme, and each data fragment is stored on a different one of the at least two random access memory modules;

said first compute element is configured to send to the first erasure-coding interface a request for one of the data sets;

the first erasure-coding interface is configured to;

convert said request into a first plurality of secondary data requests;

send, via the switching network, said first plurality of secondary data requests respectively into at least a first sub-set of said plurality of data interfaces;

receive as responses, via the switching network, at least a sub-set of said plurality of data fragments associated with said one of the data sets;

reconstruct said one of the data sets, using said first erasure-coding scheme, from said data fragments received; and

send said reconstruction to the first compute element as a response to said request made; and

each of the plurality of data interfaces is configured to;

receive, from the first erasure-coding interface, one of said plurality of secondary data requests;

extract, from the respective random access memory module, using a random-access read cycle, one of the data fragments associated with said secondary data request; and

send the data fragment extracted to said first erasure-coding interface as part of said responses received by the first erasure-coding interface,

such that a combined result is that a rate at which said data sets are being reconstructed is at least 100 Giga-bits-per second.

8. A system operative to achieve data resiliency in a shared memory pool, comprising:

a plurality of memory modules belonging to a shared memory pool and associated respectively with a plurality of data interfaces;

a first erasure-coding interface communicatively connected with said plurality of data interfaces; and

a first compute element communicatively connected with said first erasure-coding interface,

wherein;

said plurality of memory modules are configured to distributively store a plurality of data sets, such that each data set is distributively stored among at least two of the memory modules in a form of a plurality of data fragments coded using a first erasure-coding scheme, and each data fragment is stored on a different one of the at least two memory modules;

said first compute element is configured to send to the first erasure-coding interface a request for one of the data sets;

the first erasure-coding interface is configured to;

convert said request into a first plurality of secondary data requests;

send said first plurality of secondary data requests respectively into at least a first sub-set of said plurality of data interfaces;

receive as responses at least a sub-set of said plurality of data fragments associated with said one of the data sets;

reconstruct said one of the data sets, using said first erasure-coding scheme, from said data fragments received; and

send said reconstruction to the first compute element as a response to said request made; and

each of the plurality of data interfaces is configured to;

receive, from the first erasure-coding interface, one of said plurality of secondary data requests;

extract, from the respective memory module, using a random-access read cycle, one of the data fragments associated with said secondary data request; and

send the data fragment extracted to said first erasure-coding interface as part of said responses received by the first erasure-coding interface,

in which;

said one of the data sets is a first value associated with a first key;

said first value is stored as one of the pluralities of data fragments in said plurality of memory modules;

said request for one of the data sets is a request for the first value, in which the request conveys said first key;

said first plurality of secondary data requests are requests for said one of the pluralities of data fragments, in which each of said requests for said one of the pluralities of data fragments conveys said first key or a derivative of the first key to the respective data interface; and

the respective data interface is configured to use said first key or a derivative of the first key to determine an address from which to perform said random access read cycles.

9. A system operative to stream data resiliently into a shared memory pool, comprising:

a plurality of random access memory modules belonging to a shared memory pool and associated respectively with a plurality of data interfaces;

a first erasure-coding interface communicatively connected with said plurality of data interfaces using a switching network selected from a group consisting of;

(i) a non-blocking switching network, (ii) a fat tree packet switching network, and (iii) a cross-bar switching network; and

a first compute element communicatively connected with said first erasure-coding interface,

wherein;

the first compute element is configured to stream a plurality of data sets into said first erasure-coding interface;

the first erasure-coding interface is configured to;

receive said stream;

convert in real-time each of said plurality of data sets in the stream into a plurality of data fragments using a first erasure-coding scheme; and

stream each of said pluralities of data fragments respectively into said plurality of data interfaces via the switching network, such that a plurality of sub-streams of data fragments are created in conjunction with said plurality of data interfaces; and

each of the data interfaces is configured to;

receive one of said sub-streams of data fragments; and

write in real-time each of the data fragments in the sub-stream into the respective random access memory module using a random-access write cycle,

thereby resulting in a real-time erasure-coding of said stream of data sets into said shared memory pool as facilitated by said first erasure-coding interface and said random-access write cycles, such that any one of said data sets is written in said plurality of memory modules no later than 5 (five) microseconds from being put in said stream.

10. A system operative to stream data resiliently into a shared memory pool, comprising:

a plurality of random access memory modules belonging to a shared memory pool and associated respectively with a plurality of data interfaces;

a first erasure-coding interface communicatively connected with said plurality of data interfaces using a switching network selected from a group consisting of;

(i) a non-blocking switching network, (ii) a fat tree packet switching network, and (iii) a cross-bar switching network; and

a first compute element communicatively connected with said first erasure-coding interface,

wherein;

the first compute element is configured to stream a plurality of data sets into said first erasure-coding interface;

the first erasure-coding interface is configured to;

receive said stream;

convert in real-time each of said plurality of data sets in the stream into a plurality of data fragments using a first erasure-coding scheme; and

stream each of said pluralities of data fragments respectively into said plurality of data interfaces via the switching network, such that a plurality of sub-streams of data fragments are created in conjunction with said plurality of data interfaces; and

each of the data interfaces is configured to;

receive one of said sub-streams of data fragments; and

write in real-time each of the data fragments in the sub-stream into the respective random access memory module using a random-access write cycle,

thereby resulting in a real-time erasure-coding of said stream of data sets into said shared memory pool as facilitated by said first erasure-coding interface and said random-access write cycles,

such that a combined result is that a rate at which said data sets are being written is at least 100 Giga-bits-per second.