System and method for inline erasure coding for a distributed log structured storage system

• US 10,642,689 B2
• Filed: 07/09/2018
• Issued: 05/05/2020
• Est. Priority Date: 07/09/2018
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Shaikh, Faraz Ahmed, Pimpale, Swapnil, Ramanan, Jyothir, Pednekar, Ashwin, Vartak, Mayuresh, Mahalingam, Mallikarjunan, Yadappanavar, Krishna
• Primary Examiner(s): Vallecillo, Kyle
• Application Number:
  US16/030,069
• Publication Number:
  US 20200012564A1
• Time in Patent Office: 666 Days
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 3/0604 Improving or facilitating administration, e.g. storage management
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/0658 Controller construction arrangements
• CPC Class Codes: G06F 3/0659 Command handling arrangements, e.g. command buffers, queues, command scheduling
• CPC Class Codes: G06F 3/0689 Disk arrays, e.g. RAID, JBOD
• CPC Class Codes: H03M 13/154 Error and erasure correction, e.g. by using the error and erasure locator or Forney polynomial
• 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

Presented herein are methodologies for implementing erasure coding in a distributed log structured storage system. A method includes receiving a write request for first data from a file system, selecting a physical sector on a selected storage device in an array of storage devices on which to store the first data, assigning a key to the physical sector, storing the key and an indication of the physical sector in a key-to-physical medium map, erasure coding the data, including generating parity data associated with the first data, writing the first data and the parity data as a data stripe to each storage device in the array of storage devices and, in response to receiving the write request, sending the key to the file system. Read, update, and delete procedures in the context of a log structured framework are also described.

Claims

1. A method comprising:

receiving a write request for first data from a file system;

selecting a physical sector on a selected storage device in an array of storage devices on which to store the first data;

assigning a key to the physical sector;

storing the key and an indication of the physical sector in a key-to-physical medium map;

erasure coding the first data, including generating parity data associated with the first data;

writing the first data and the parity data as a data stripe to each storage device in the array of storage devices;

in response to receiving the write request, sending the key to the file system;

designating one of the storage devices in the array of storage devices as a first write leader;

routing subsequent write requests from the file system only to the first write leader;

executing a write leader election algorithm to designate another of the storage devices in the array of storage devices as a second write leader, different from the first write leader; and

after designating the second write leader, routing further subsequent write requests from the file system only to the second write leader.

2. The method of claim 1, further comprising storing in the key-to-physical medium map, along with the indication of the physical sector, an indication of the selected storage device.

3. The method of claim 1, further comprising storing the key-to-physical medium map on each storage device in the array of storage devices.

4. The method of claim 1, further comprising after writing the first data and the parity data as a data stripe to each storage device in the array of storage devices, but before sending the key to the file system, receiving an acknowledgement from each storage device in the array of storage devices that respective writes to each storage device in the array of storage devices was successfully persisted.

5. The method of claim 1, wherein writing the first data and the parity data as a data stripe to each storage device in the array of storage devices comprises sending a packet to each storage device in the array of storage devices comprising the first data, the parity data, and the key.

6. The method of claim 1, further comprising:

receiving a read request from the file system, the read request including the key;

looking up the key in the key-to-physical medium map and obtaining a physical sector on the selected storage device from which to read the first data;

reading the first data from the physical sector; and

in response to the read request, returning the first data to the file system.

7. The method of claim 6, wherein the read request is received at one of the storage devices in the array of storage devices that is not the selected storage device.

8. The method of claim 7, further comprising obtaining the first data via an erasure coding recovery mechanism using data, other than the first data, stored the data stripe.

9. The method of claim 1, wherein each storage device in the array of storage devices is disposed in a single enclosure.

10. The method of claim 1, wherein each storage device in the array of storage devices is disposed in respective enclosures.

11. A device comprising:

an interface unit configured to enable network communications;

a memory;

and one or more processors coupled to the interface unit and the memory, and configured to;

receive a write request for first data from a file system;

select a physical sector on a selected storage device in an array of storage devices on which to store the first data;

assign a key to the physical sector;

store the key and an indication of the physical sector in a key-to-physical medium map;

erasure code the first data, including generating parity data associated with the first data;

write the first data and the parity data as a data stripe to each storage device in the array of storage devices;

in response to receipt of the write request, send the key to the file system;

designate one of the storage devices in the array of storage devices as a first write leader;

route subsequent write requests from the file system only to the first write leader;

execute a write leader election algorithm to designate another of the storage devices in the array of storage devices as a second write leader, different from the first write leader; and

after the second write leader is designated, route further subsequent write requests from the file system only to the second write leader.

12. The device of claim 11, wherein the one or more processors are further configured to store in the key-to-physical medium map, along with the indication of the physical sector, an indication of the selected storage device.

13. The device of claim 11, wherein the one or more processors are further configured to store the key-to-physical medium map on each storage device in the array of storage devices.

14. The device of claim 11, wherein the one or more processors are further configured to

receive a read request from the file system, the read request including the key;

look up the key in the key-to-physical medium map and obtain a physical sector on the selected storage device from which to read the first data;

read the first data from the physical sector; and

in response to the read request, return the first data to the file system.

15. A non-transitory computer readable storage media encoded with instructions that, when executed by a processor, cause the processor to:

receive a write request for first data from a file system;

select a physical sector on a selected storage device in an array of storage devices on which to store the first data;

assign a key to the physical sector;

store the key and an indication of the physical sector in a key-to-physical medium map;

erasure code the first data, including generating parity data associated with the first data;

write the first data and the parity data as a data stripe to each storage device in the array of storage devices;

in response to receiving the write request, send the key to the file system;

designate one of the storage devices in the array of storage devices as a first write leader;

route subsequent write requests from the file system only to the first write leader;

execute a write leader election algorithm to designate another of the storage devices in the array of storage devices as a second write leader, different from the first write leader; and

after the second write leader is designated, route further subsequent write requests from the file system only to the second write leader.

16. The non-transitory computer readable storage media of claim 15, further including instructions that, when executed by a processor, cause the processor to store in the key-to-physical medium map, along with the indication of the physical sector, an indication of the selected storage device.

17. The non-transitory computer readable storage media of claim 15, further including instructions that, when executed by a processor, cause the processor to store the key-to-physical medium map on each storage device in the array of storage devices.