Simulator For Determining Data Loss In A Fault Tolerant System

• US 20100115335A1
• Filed: 10/30/2008
• Published: 05/06/2010
• Est. Priority Date: 06/23/2008
• Status: Active Grant

• Current Assignee: Valtrus Innovations Limited (f/k/a Dolya Holdco 9 Limited) (Key Patent Innovations Limited)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Greenan, Kevin M., Wylie, John Johnson
• Granted Patent: US 7,925,927 B2
• Time in Patent Office: Days
• US Class Current: 714/25
• 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

Abstract

A fault tolerant system is simulated to determine the occurrence of data loss in the fault tolerant system. A list of erasure patterns corresponding to an erasure code implemented across the devices in the system is provided and a device event is simulated. The list of erasure patterns is updated based on the device event, and the occurrence of data loss is determined based on the updated list.

Claims

1. A method of simulating a fault tolerant system to determine occurrence of a data loss, comprising:

providing a list of erasure patterns corresponding to an erasure code implemented across a plurality of devices in a fault tolerant system;

simulating a device event in the fault tolerant system;

updating the list of erasure patterns based on the device event; and

determining occurrence of a data loss in the fault tolerant system based on the updated list of erasure patterns.

2. The method as recited in claim 1, further comprising:

providing failure models corresponding to the devices in the fault tolerant system;

simulating device events based on the failure models; and

updating the list of erasure patterns when a number of device events resulting in a risk of data loss reaches or exceeds a predefined threshold.

3. The method as recited in claim 2, wherein the predefined threshold is a Hamming distance for the erasure code.

4. The method as recited in claim 1, wherein the erasure code comprises a plurality of symbols implemented across the plurality of devices, and the method further comprises:

identifying loss of at least one symbol resulting from the device event, wherein updating the list of erasure patterns comprises removing at least one symbol from the list of erasure patterns.

5. The method as recited in claim 4, wherein the list of erasure patterns is a list of minimal erasures, and wherein a data loss in the fault tolerant system is determined when all of the symbols have been removed from at least one of the minimal erasures.

6. The method as recited in claim 1, wherein the fault tolerant system comprises a storage system and the plurality of devices comprises a plurality of storage devices.

7. A method of simulating a storage system to determine occurrence of a data loss in the fault tolerant system, comprising:

providing a list of minimal erasures corresponding to an erasure code having a plurality of symbols implemented across a plurality of storage devices in a storage system;

providing failure models corresponding to the storage devices;

creating a bookkeeping minimal erasures list (MEL) based on the list of minimal erasures, the bookkeeping MEL comprising a plurality of entries corresponding to the minimal erasures;

simulating a plurality of device events based on the failure models that result in a risk of data loss;

updating the bookkeeping MEL based on the simulated device events; and

determining occurrence of a data loss from the storage system based on the updated bookkeeping MEL.

8. The method as recited in claim 7, wherein each device event comprises a failure event and a recovery event, the failure event resulting in loss of at least one symbol of the erasure code, and the recovery event resulting in recovery of at least one lost symbol of the erasure code, and wherein the bookkeeping MEL is updated when a number of non-recovered lost symbols reaches or exceeds a predefined threshold.

9. The method as recited in claim 8, wherein the predefined threshold is a Hamming distance of the erasure code.

10. The method as recited in claim 8, wherein updating the bookkeeping MEL comprises removing any non-recovered lost symbols from the bookkeeping MEL, and wherein a loss of data is determined when all symbols have been removed from at least one entry in the updated bookkeeping MEL.

11. The method as recited in claim 7, comprising continuing simulation of device events until a loss of data from the storage system is determined.

12. An article comprising a computer-accessible storage medium containing instructions that when executed by a processor-based system cause the processor-based system to:

generate a list of minimal erasures corresponding to an erasure code having a plurality of symbols;

simulate device events in a storage system comprising a plurality of storage devices, wherein the plurality of symbols is implemented across the storage devices;

track a number of symbols lost as a result of the device events;

update the list of minimal erasures when the number of lost symbols reaches or exceeds a predefined threshold; and

determine occurrence of a data loss from the storage system based on the updated list.

13. The article as recited in claim 12, wherein the predefined threshold is a Hamming distance of the erasure code.

14. The article as recited in claim 12, wherein the list of minimal erasures is updated by removing the lost symbols from the minimal erasures.

15. The article as recited in claim 12, wherein the occurrence of a data loss is determined when all symbols have been removed from at least one minimal erasure in the list of minimal erasures.