Efficiently accessing an encoded data slice in a memory container utilizing a memory bin

• US 9,141,307 B2
• Filed: 02/18/2014
• Issued: 09/22/2015
• Est. Priority Date: 10/06/2010
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: Cleversafe Incorporated (International Business Machines Corporation)
• Inventors: Resch, Jason K., Ma, Siyuan
• Primary Examiner(s): Chery, Mardochee
• Application Number:
  US14/182,755
• Publication Number:
  US 20140164699A1
• Time in Patent Office: 581 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 11/08 Error detection or correction by redundancy in data representation, e.g. by using checking codes
• CPC Class Codes: G06F 11/1004 to protect a block of data words, e.g. CRC or checksum G06F11/1076 takes precedence; security arrangements for protecting computers or computer systems against unauthorized activity G06F21/00
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 11/3485 for I/O devices
• CPC Class Codes: G06F 12/023 Free address space management
• CPC Class Codes: G06F 16/13 File access structures, e.g. distributed indices arrangements of input from, or output to, record carriers G06F3/06
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: H04L 67/1097 for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS]

Abstract

A method begins by receiving encoded data slices for storage. At least some of the encoded data slices have different data sizes. The method continues by accessing memory container information of the storage unit that includes a listing of virtual memory containers of the storage unit and, for each virtual memory container, bin identifier information. Each virtual memory contain is divided into bins, where the bins of a virtual memory container are of a substantially similar storage size. At least some of the virtual memory containers have different bin storage sizes. The method continues by mapping encoded data slices to virtual memory containers of the plurality based on data size of the encoded data slices and bin storage sizes of the virtual memory containers. The method continues by storing the encoded data slices in the virtual memory containers based on the mapping.

Claims

1. A method for execution by a processing module of a storage unit of a dispersed storage network (DSN), the method comprises:

receiving a plurality of encoded data slices for storage, wherein at least some of the encoded data slices of the plurality of encoded data slices have different data sizes;

accessing memory container information of the storage unit, wherein the memory container information includes a listing of a plurality of virtual memory containers of the storage unit and, for each virtual memory container, bin identifier information, wherein physical memory of the storage unit is virtually divided into the virtual memory containers and each virtual memory contain is divided into a plurality of bins, wherein the plurality of bins of a virtual memory container of the plurality of virtual memory containers are of a substantially similar storage size, and wherein at least some of the plurality of virtual memory containers have different bin storage sizes; and

mapping encoded data slices of the plurality of encoded data slices to virtual memory containers of the plurality of virtual memory containers based on data size of the encoded data slices and bin storage sizes of the virtual memory containers; and

storing the encoded data slices in the virtual memory containers based on the mapping.

2. The method of claim 1, wherein the memory container information comprises:

a slice location table that includes a slice name field, a virtual memory container identifier field, and a bin location identifier field, wherein the slice location table tracks storage of the plurality of encoded data slices in the physical memory of the storage unit; and

an open location table that includes a virtual memory container identifier field and an open bin location identifier field, wherein the open location table tracks availability of bins of each of the plurality of virtual memory containers.

3. The method of claim 1, wherein the memory container information comprises:

a first virtual memory container table that includes a bin location field and a data block identifier field, wherein the first virtual memory container table tracks which bins of first virtual memory container of the plurality of virtual memory containers are open and data blocks that are stored in particular bins of the first virtual memory container; and

a second virtual memory container table that includes a second bin location field and a second data block identifier field, wherein the second virtual memory container table tracks which bins of second virtual memory container of the plurality of virtual memory containers are open and data blocks that are stored in particular bins of the second virtual memory container.

4. The method of claim 1 further comprises:

determining the data sizes of the plurality of encoded data slices by at least one of;

extracting the data size from a store encoded data slice request;

sending a query to a requesting entity and receiving the data size in response to the query; and

counting a number of bytes of the encoded data slice to produce the data size.

5. The method of claim 1, wherein the mapping comprises:

determining data size for an encoded data slice of the plurality of encoded data;

comparing the data size with the bin storage size of the plurality of virtual memory containers;

determining a best match of the data size to the bin storage size of one of the plurality of virtual memory containers; and

allocating an open bin of the plurality of bins of the one of the plurality of virtual memory containers to the encoded data slice.

6. The method of claim 1, wherein the storing the encoded data slices in the virtual memory containers comprises:

updating a slice location table with the storage of the encoded data slices in the virtual memory containers; and

updating an open location table by removing bins of the virtual memory containers in which the encoded data slices are stored.

7. A storage unit of a dispersed storage network, wherein the storage unit comprises:

an interface;

a memory; and

a processing module operable to;

receive, via the interface, a plurality of encoded data slices for storage, wherein at least some of the encoded data slices of the plurality of encoded data slices have different data sizes;

access memory container information of the storage unit, wherein the memory container information includes a listing of a plurality of virtual memory containers of the storage unit and, for each virtual memory container, bin identifier information, wherein physical memory of the storage unit is virtually divided into the virtual memory containers and each virtual memory contain is divided into a plurality of bins, wherein the plurality of bins of a virtual memory container of the plurality of virtual memory containers are of a substantially similar storage size, and wherein at least some of the plurality of virtual memory containers have different bin storage sizes; and

map encoded data slices of the plurality of encoded data slices to virtual memory containers of the plurality of virtual memory containers based on data size of the encoded data slices and bin storage sizes of the virtual memory containers; and

store the encoded data slices in the virtual memory containers based on the mapping.

8. The storage unit of claim 7, wherein the memory container information comprises:

a slice location table that includes a slice name field, a virtual memory container identifier field, and a bin location identifier field, wherein the slice location table tracks storage of the plurality of encoded data slices in the physical memory of the storage unit; and

an open location table that includes a virtual memory container identifier field and an open bin location identifier field, wherein the open location table tracks availability of bins of each of the plurality of virtual memory containers.

9. The storage unit of claim 7, wherein the memory container information comprises:

a first virtual memory container table that includes a bin location field and a data block identifier field, wherein the first virtual memory container table tracks which bins of first virtual memory container of the plurality of virtual memory containers are open and data blocks that are stored in particular bins of the first virtual memory container; and

a second virtual memory container table that includes a second bin location field and a second data block identifier field, wherein the second virtual memory container table tracks which bins of second virtual memory container of the plurality of virtual memory containers are open and data blocks that are stored in particular bins of the second virtual memory container.

10. The storage unit of claim 7, wherein the processing module is further operable to:

determine the data sizes of the plurality of encoded data slices by at least one of;

extracting the data size from a store encoded data slice request;

sending a query to a requesting entity and receiving the data size in response to the query; and

counting a number of bytes of the encoded data slice to produce the data size.

11. The storage unit of claim 7, wherein the processing module is further operable to perform the mapping by:

determining data size for an encoded data slice of the plurality of encoded data;

comparing the data size with the bin storage size of the plurality of virtual memory containers;

determining a best match of the data size to the bin storage size of one of the plurality of virtual memory containers; and

allocating an open bin of the plurality of bins of the one of the plurality of virtual memory containers to the encoded data slice.

12. The storage unit of claim 7, wherein the processing module is further operable to store the encoded data slices in the virtual memory containers by:

updating a slice location table with the storage of the encoded data slices in the virtual memory containers; and

updating an open location table by removing bins of the virtual memory containers in which the encoded data slices are stored.