# US 10,311,023 B1 · Distributed data storage grouping

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 10,311,023 B1
- Document ID: US10311023B1
- Status: Granted
- Kind: B1
- Application number: 16/233,573
- Filed: 2018-12-27
- Published: 2019-06-27
- Granted: 2019-06-04
- Earliest claimed: 2015-07-27
- Assignees: SAS Institute Inc.
- Applicants: SAS Institute Inc.
- Inventors: Brian Payton Bowman; Jeff Ira Cleveland, III
- Web page: https://patentgrep.com/patent/US10311023B1

## CPC

- G06F 16/137: {Hash-based (content-based indexing of textual data G06F16/31)}
- G06F 3/0604: {Improving or facilitating administration, e.g. storage management}
- G06F 3/061: {Improving I/O performance}
- G06F 3/0614: {Improving the reliability of storage systems}
- G06F 3/0623: {in relation to content}
- G06F 3/064: {Management of blocks}
- G06F 3/0643: {Management of files}
- G06F 3/0644: {Management of space entities, e.g. partitions, extents, pools}
- G06F 3/067: {Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]}
- G06F 9/5072: {Grid computing}
- G06F 9/5077: {Logical partitioning of resources; Management or configuration of virtualized resources (specific details on emulation or internal functioning of virtual machines G06F9/455)}
- G06F 9/542: {Event management; Broadcasting; Multicasting; Notifications}
- G06F 12/0292: {using tables or multilevel address translation means (G06F12/023 takes precedence; address translation in virtual memory systems G06F12/10)}
- G06F 16/1827: {Management specifically adapted to NAS (management of storage area networks [SAN] G06F3/067)}
- G06F 16/22: Indexing; Data structures therefor; Storage structures
- G06F 16/278: {Data partitioning, e.g. horizontal or vertical partitioning}
- G06F 21/602: {Providing cryptographic facilities or services}
- G06F 2212/1016: Performance improvement
- G06F 2212/1056: Simplification
- G06F 2212/154: Networked environment
- G06F 2212/262: configured as RAID
- G06F 2212/263: Network storage, e.g. SAN or NAS
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

An apparatus of includes a processor component to: transmit node device identifiers to multiple node devices to define an ordering thereamong and among subsets of multiple blocks of data distributed thereamong; receive sizes of the subsets from the multiple node devices; derive block exchanges among the multiple node device based on the sizes and a minimum size imposed on data transmissions to storage device(s); and transmit a block exchange vector that describes the block exchanges to the multiple node devices, wherein: the subsets remain distributed among a reduced number of the multiple node devices following the block exchanges; at least all node devices of the reduced number but one stores an amount of the blocks of data exceeding the minimum size; and the block exchanges are all lower-order to higher-order node device transfers, or all higher-order to lower-order node device transfers.

## Claims

### Claim 1

An apparatus comprising a processor component and a storage to store instructions that, when executed by the processor component, cause the processor component to perform operations comprising:
transmit, from a control device, and to multiple node devices via a network, a set of node device identifiers to assign each node device of the multiple node devices a different node device identifier of the set of node device identifiers, wherein:
the set of node device identifiers defines an ascending or descending series of numerical values that define an ordering among the multiple node devices; and
the ordering among the node devices defines a corresponding ordering among subsets of multiple blocks of data of a data set that are distributed among the multiple node devices;
receive, from the multiple node devices via the network, an indication of a total size of the subset of the multiple blocks of data distributed to each node device of the multiple node devices;
derive, by the processor component, a set of block exchanges based on the total sizes of the subsets received from the multiple node devices and a minimum threshold size imposed on units of data of the data set to be transmitted to one or more storage devices, wherein:
at least one node device of the multiple node devices serves as a source device to transmit one of the subsets of the multiple blocks of data to another node device of the multiple node devices that serves as a target node device;
following a performance of the set of block exchanges, the data set remains distributed to a reduced number of the multiple node devices;
either each node device of the reduced number of node devices, or each node device but one of the reduced number of node devices, stores an amount of the data of the data set that is greater than the minimum threshold size; and
the set of block exchanges follows a block exchange rule that each transfer of one of the subsets of the multiple blocks of data in the set of block exchanges is to be from a lower-order source node device and to a higher-order target node device in the ordering among the multiple node devices, or that each transfer of one of the subsets of the multiple blocks of data is to be from a higher-order source node device and to a lower-order target node device in the ordering among the multiple node devices;
generate a block exchange vector that identifies each source node device and each target node device in the set of block exchanges based on the set of node device identifiers; and
transmit the block exchange vector to the multiple node devices as a block exchange instruction to cause a performance of the set of block exchanges among the multiple node devices.

### Claim 2 (depends on 1)

The apparatus of claim 1, wherein:
the data of the data set comprises partitioned data wherein:
the data of the data set is divided into a set of partitions that are each required to be provided to a single node device;
each block of data is divided into one or more data sub-blocks that are each individually associated with a partition of the set of partitions; and
all data sub-blocks associated with a single partition of the set of partitions must be included within a single block of data;
each partition of the set of partitions is provided with a unique label of a set of labels;
the set of node device identifiers defines a 0-based ascending set of positive integers incremented by a value of 1; and
prior to using the set of node device identifiers to derive the set of block exchanges, the processor component is caused to use the set of node device identifiers to distribute the data set among the multiple node devices based on matches between the set of node device identifiers and a set of modulo values derived from the set of labels through dividing a hash value from a hash taken of each label by a quantity of the multiple node devices.

### Claim 3 (depends on 2)

The apparatus of claim 2, wherein, in response to receiving the block exchange instruction, a node device of the multiple node devices performs operations comprising:
analyze the block exchange vector in view of the node device identifier assigned to the node device to determine whether the node device is to serve as a source node device or a target node device;
in response to a determination that the node device is to serve as a source node device, employ the block exchange rule in parsing the block exchange vector to identify the corresponding target node device; or
in response to a determination that the node device is to serve as a target node device, employ the block exchange rule in parsing the block exchange vector to identify the corresponding source node device.

### Claim 4 (depends on 1)

The apparatus of claim 1, wherein, in response to receiving the block exchange instruction, and in response to the block exchange instruction comprising an indication that the node device is to serve as a target node to receive a subset of the multiple blocks of data from another node device that is to serve as a source node in the set of block exchanges, a node device of the multiple node devices performs operations comprising:
transmit a request, via the network and to the source node device, to transmit the subset to the node device; and
receive, from the source node device via the network, and along with the subset, an indication of a size of each block of data of the subset or of each sub-block of data within each block of data of the subset.

### Claim 5 (depends on 1)

The apparatus of claim 1, wherein, in response to receiving the block exchange instruction, and in response to the block exchange instruction comprising an indication that the node device is to serve as a source node to transmit a subset of the multiple blocks of data to another device that is to serve as a target node device in the set of block exchanges, a node device of the multiple node devices performs operations comprising:
receive, from the other device via the network, a request to transmit the subset to the other device; and
transmit, to the other device via the network, the subset and an indication of size of each block of data of the subset or each sub-block of data within each block of data of the subset.

### Claim 6 (depends on 1)

The apparatus of claim 1, wherein the processor component is caused to perform operations comprising:
as part of a registration of the multiple blocks of data by the reduced number of node devices following the performance of the set of block exchanges, receive from each node device of the reduced number of node devices, and for each block of data of the multiple blocks of data, an indication of a size of the block of data or indications of a size of each sub-block of the block of data; and
generate, based at least on the indications of size received during registration, map data indicative of an ordering among the multiple blocks of data by which the multiple blocks of data are to be stored within the one or more storage devices, and which stems from the ordering among the subsets of the multiple blocks of data.

### Claim 7 (depends on 6)

The apparatus of claim 6, wherein the processor component is caused to perform operations comprising:
determine a total size of a combination of at least the map data and of a metadata indicative of at least one of whether the data of the data set comprises partitioned data and whether the data set is to be stored within the one or more storage devices in encrypted form;
determine whether the total size of the combination meets the minimum threshold size; and
in response to a determination that the combination does not meet the minimum threshold size, perform operations comprising:
identify a lowest-order node device or a highest-order node device in the ordering among the multiple node devices that is among the reduced number of node devices; and
transmit, to the identified lowest-order node device or highest-order node device, and via the network, the combination of the map data and the metadata.

### Claim 8 (depends on 7)

The apparatus of claim 7, wherein the processor component is caused, in response to a determination that the combination does meet the minimum threshold size, to perform operations comprising:
form one or more segments for transmission to the one or more storage devices from the combination of the map data and the metadata that each fit within the minimum threshold size and a maximum threshold size imposed on units of data of the data set to be transmitted to one or more storage devices; and
transmit, to the one or more storage devices via the network, the one or more segments at least partially in parallel with multiple other segments formed from the multiple blocks of data by the reduced number of node devices.

### Claim 9 (depends on 1)

The apparatus of claim 1, wherein:
the data of the data set comprises partitioned data wherein:
the data of the data set is divided into a set of partitions that are each required to be provided to a single node device;
each block of data is divided into one or more data sub-blocks that are each individually associated with a partition of the set of partitions; and
all data sub-blocks associated with a single partition of the set of partitions must be included within a single block of data;
as part of the registration of the multiple blocks of data, the processor component is caused to receive, for each sub-block of each block of data, a hashed value indicative of a partition with which the sub-block is associated; and
the processor component is caused to generate, within the map data and for each block of data of the multiple blocks of data, a separate map entry that comprises the size and hashed value of each sub-block within the block of data.

### Claim 10 (depends on 1)

The apparatus of claim 1, wherein:
the data of the data set is to be stored within the one or more storage devices in encrypted form, wherein each block of data is to be separately encrypted by one of the node devices of the multiple node devices;
as part of the registration of multiple blocks of data, the processor component is caused to receive, for each block of data of the multiple blocks of data, data block encryption data by which the block of data is encrypted; and
the processor component is caused to generate, within the map data and for each block of data of the multiple blocks of data, a separate map entry that comprises the data block encryption data for the block of data.

### Claim 11

A computer-program product tangibly embodied in a non-transitory machine-readable storage medium, the computer-program product including instructions operable to cause a processor component to perform operations comprising:
transmit, from a control device, and to multiple node devices via a network, a set of node device identifiers to assign each node device of the multiple node devices a different node device identifier of the set of node device identifiers, wherein:
the set of node device identifiers defines an ascending or descending series of numerical values that define an ordering among the multiple node devices; and
the ordering among the node devices defines a corresponding ordering among subsets of multiple blocks of data of a data set that are distributed among the multiple node devices;
receive, from the multiple node devices via the network, an indication of a total size of the subset of the multiple blocks of data distributed to each node device of the multiple node devices;
derive, by the processor component, a set of block exchanges based on the total sizes of the subsets received from the multiple node devices and a minimum threshold size imposed on units of data of the data set to be transmitted to one or more storage devices, wherein:
at least one node device of the multiple node devices serves as a source device to transmit one of the subsets of the multiple blocks of data to another node device of the multiple node devices that serves as a target node device;
following a performance of the set of block exchanges, the data set remains distributed to a reduced number of the multiple node devices;
either each node device of the reduced number of node devices, or each node device but one of the reduced number of node devices, stores an amount of the data of the data set that is greater than the minimum threshold size; and
the set of block exchanges follows a block exchange rule that each transfer of one of the subsets of the multiple blocks of data in the set of block exchanges is to be from a lower-order source node device and to a higher-order target node device in the ordering among the multiple node devices, or that each transfer of one of the subsets of the multiple blocks of data is to be from a higher-order source node device and to a lower-order target node device in the ordering among the multiple node devices;
generate a block exchange vector that identifies each source node device and each target node device in the set of block exchanges based on the set of node device identifiers; and
transmit the block exchange vector to the multiple node devices as a block exchange instruction to cause a performance of the set of block exchanges among the multiple node devices.

### Claim 12 (depends on 11)

The computer-program product of claim 11, wherein:
the data of the data set comprises partitioned data wherein:
the data of the data set is divided into a set of partitions that are each required to be provided to a single node device;
each block of data is divided into one or more data sub-blocks that are each individually associated with a partition of the set of partitions; and
all data sub-blocks associated with a single partition of the set of partitions must be included within a single block of data;
each partition of the set of partitions is provided with a unique label of a set of labels;
the set of node device identifiers defines a 0-based ascending set of positive integers incremented by a value of 1; and
prior to using the set of node device identifiers to derive the set of block exchanges, the processor component is caused to use the set of node device identifiers to distribute the data set among the multiple node devices based on matches between the set of node device identifiers and a set of modulo values derived from the set of labels through dividing a hash value from a hash taken of each label by a quantity of the multiple node devices.

### Claim 13 (depends on 12)

The computer-program product of claim 12, wherein, in response to receiving the block exchange instruction, a node device of the multiple node devices performs operations comprising:
analyze the block exchange vector in view of the node device identifier assigned to the node device to determine whether the node device is to serve as a source node device or a target node device;
in response to a determination that the node device is to serve as a source node device, employ the block exchange rule in parsing the block exchange vector to identify the corresponding target node device; or
in response to a determination that the node device is to serve as a target node device, employ the block exchange rule in parsing the block exchange vector to identify the corresponding source node device.

### Claim 14 (depends on 11)

The computer-program product of claim 11, wherein, in response to receiving the block exchange instruction, and in response to the block exchange instruction comprising an indication that the node device is to serve as a target node to receive a subset of the multiple blocks of data from another node device that is to serve as a source node in the set of block exchanges, a node device of the multiple node devices performs operations comprising:
transmit a request, via the network and to the source node device, to transmit the subset to the node device; and
receive, from the source node device via the network, and along with the subset, an indication of a size of each block of data of the subset or of each sub-block of data within each block of data of the subset.

### Claim 15 (depends on 11)

The computer-program product of claim 11, wherein, in response to receiving the block exchange instruction, and in response to the block exchange instruction comprising an indication that the node device is to serve as a source node to transmit a subset of the multiple blocks of data to another device that is to serve as a target node device in the set of block exchanges, a node device of the multiple node devices performs operations comprising:
receive, from the other device via the network, a request to transmit the subset to the other device; and
transmit, to the other device via the network, the subset and an indication of size of each block of data of the subset or each sub-block of data within each block of data of the subset.

### Claim 16 (depends on 11)

The computer-program product of claim 11, wherein the processor component is caused to perform operations comprising:
as part of a registration of the multiple blocks of data by the reduced number of node devices following the performance of the set of block exchanges, receive from each node device of the reduced number of node devices, and for each block of data of the multiple blocks of data, an indication of a size of the block of data or indications of a size of each sub-block of the block of data; and
generate, based at least on the indications of size received during registration, map data indicative of an ordering among the multiple blocks of data by which the multiple blocks of data are to be stored within the one or more storage devices, and which stems from the ordering among the subsets of the multiple blocks of data.

### Claim 17 (depends on 16)

The computer-program product of claim 16, wherein the processor component is caused to perform operations comprising:
determine a total size of a combination of at least the map data and of a metadata indicative of at least one of whether the data of the data set comprises partitioned data and whether the data set is to be stored within the one or more storage devices in encrypted form;
determine whether the total size of the combination meets the minimum threshold size; and
in response to a determination that the combination does not meet the minimum threshold size, perform operations comprising:
identify a lowest-order node device or a highest-order node device in the ordering among the multiple node devices that is among the reduced number of node devices; and
transmit, to the identified lowest-order node device or highest-order node device, and via the network, the combination of the map data and the metadata.

### Claim 18 (depends on 17)

The computer-program product of claim 17, wherein the processor component is caused, in response to a determination that the combination does meet the minimum threshold size, to perform operations comprising:
form one or more segments for transmission to the one or more storage devices from the combination of the map data and the metadata that each fit within the minimum threshold size and a maximum threshold size imposed on units of data of the data set to be transmitted to one or more storage devices; and
transmit, to the one or more storage devices via the network, the one or more segments at least partially in parallel with multiple other segments formed from the multiple blocks of data by the reduced number of node devices.

### Claim 19 (depends on 11)

The computer-program product of claim 11, wherein:
the data of the data set comprises partitioned data wherein:
the data of the data set is divided into a set of partitions that are each required to be provided to a single node device;
each block of data is divided into one or more data sub-blocks that are each individually associated with a partition of the set of partitions; and
all data sub-blocks associated with a single partition of the set of partitions must be included within a single block of data;
as part of the registration of the multiple blocks of data, the processor component is caused to receive, for each sub-block of each block of data, a hashed value indicative of a partition with which the sub-block is associated; and
the processor component is caused to generate, within the map data and for each block of data of the multiple blocks of data, a separate map entry that comprises the size and hashed value of each sub-block within the block of data.

### Claim 20 (depends on 11)

The computer-program product of claim 11, wherein:
the data of the data set is to be stored within the one or more storage devices in encrypted form, wherein each block of data is to be separately encrypted by one of the node devices of the multiple node devices;
as part of the registration of multiple blocks of data, the processor component is caused to receive, for each block of data of the multiple blocks of data, data block encryption data by which the block of data is encrypted; and
the processor component is caused to generate, within the map data and for each block of data of the multiple blocks of data, a separate map entry that comprises the data block encryption data for the block of data.

### Claim 21

A computer-implemented method comprising:
transmitting, by a processor component from a control device, and to multiple node devices via a network, a set of node device identifiers to assign each node device of the multiple node devices a different node device identifier of the set of node device identifiers, wherein:
the set of node device identifiers defines an ascending or descending series of numerical values that define an ordering among the multiple node devices; and
the ordering among the node devices defines a corresponding ordering among subsets of multiple blocks of data of a data set that are distributed among the multiple node devices;
receiving, by the processor component from the multiple node devices via the network, an indication of a total size of the subset of the multiple blocks of data distributed to each node device of the multiple node devices;
deriving, by the processor component, a set of block exchanges based on the total sizes of the subsets received from the multiple node devices and a minimum threshold size imposed on units of data of the data set to be transmitted to one or more storage devices, wherein:
at least one node device of the multiple node devices serves as a source device to transmit one of the subsets of the multiple blocks of data to another node device of the multiple node devices that serves as a target node device;
following a performance of the set of block exchanges, the data set remains distributed to a reduced number of the multiple node devices;
either each node device of the reduced number of node devices, or each node device but one of the reduced number of node devices, stores an amount of the data of the data set that is greater than the minimum threshold size; and
the set of block exchanges follows a block exchange rule that each transfer of one of the subsets of the multiple blocks of data in the set of block exchanges is to be from a lower-order source node device and to a higher-order target node device in the ordering among the multiple node devices, or that each transfer of one of the subsets of the multiple blocks of data is to be from a higher-order source node device and to a lower-order target node device in the ordering among the multiple node devices;
generating, by the processor component, a block exchange vector that identifies each source node device and each target node device in the set of block exchanges based on the set of node device identifiers; and
transmitting, by the processor component, the block exchange vector to the multiple node devices as a block exchange instruction to cause a performance of the set of block exchanges among the multiple node devices.

### Claim 22 (depends on 21)

The computer-implemented method of claim 21, wherein:
the data of the data set comprises partitioned data wherein:
the data of the data set is divided into a set of partitions that are each required to be provided to a single node device;
each block of data is divided into one or more data sub-blocks that are each individually associated with a partition of the set of partitions; and
all data sub-blocks associated with a single partition of the set of partitions must be included within a single block of data;
each partition of the set of partitions is provided with a unique label of a set of labels;
the set of node device identifiers defines a 0-based ascending set of positive integers incremented by a value of 1; and
the method comprises, prior to using the set of node device identifiers to derive the set of block exchanges, using the set of node device identifiers to distribute the data set among the multiple node devices based on matches between the set of node device identifiers and a set of modulo values derived from the set of labels through dividing a hash value from a hash taken of each label by a quantity of the multiple node devices.

### Claim 23 (depends on 22)

The computer-implemented method of claim 22, wherein, in response to receiving the block exchange instruction, a node device of the multiple node devices performs operations comprising:
analyze the block exchange vector in view of the node device identifier assigned to the node device to determine whether the node device is to serve as a source node device or a target node device;
in response to a determination that the node device is to serve as a source node device, employ the block exchange rule in parsing the block exchange vector to identify the corresponding target node device; or
in response to a determination that the node device is to serve as a target node device, employ the block exchange rule in parsing the block exchange vector to identify the corresponding source node device.

### Claim 24 (depends on 21)

The computer-implemented method of claim 21, wherein, in response to receiving the block exchange instruction, and in response to the block exchange instruction comprising an indication that the node device is to serve as a target node to receive a subset of the multiple blocks of data from another node device that is to serve as a source node in the set of block exchanges, a node device of the multiple node devices performs operations comprising:
transmit a request, via the network and to the source node device, to transmit the subset to the node device; and
receive, from the source node device via the network, and along with the subset, an indication of a size of each block of data of the subset or of each sub-block of data within each block of data of the subset.

### Claim 25 (depends on 21)

The computer-implemented method of claim 21, wherein, in response to receiving the block exchange instruction, and in response to the block exchange instruction comprising an indication that the node device is to serve as a source node to transmit a subset of the multiple blocks of data to another device that is to serve as a target node device in the set of block exchanges, a node device of the multiple node devices performs operations comprising:
receive, from the other device via the network, a request to transmit the subset to the other device; and
transmit, to the other device via the network, the subset and an indication of size of each block of data of the subset or each sub-block of data within each block of data of the subset.

### Claim 26 (depends on 21)

The computer-implemented method of claim 21, comprising:
as part of a registration of the multiple blocks of data by the reduced number of node devices following the performance of the set of block exchanges, receiving by the processor component from each node device of the reduced number of node devices, and for each block of data of the multiple blocks of data, an indication of a size of the block of data or indications of a size of each sub-block of the block of data; and
generating, by the processor component, based at least on the indications of size received during registration, map data indicative of an ordering among the multiple blocks of data by which the multiple blocks of data are to be stored within the one or more storage devices, and which stems from the ordering among the subsets of the multiple blocks of data.

### Claim 27 (depends on 26)

The computer-implemented method of claim 26, comprising:
determining, by the processor component, a total size of a combination of at least the map data and of a metadata indicative of at least one of whether the data of the data set comprises partitioned data and whether the data set is to be stored within the one or more storage devices in encrypted form;
determining, by the processor component, whether the total size of the combination meets the minimum threshold size; and
in response to a determination that the combination does not meet the minimum threshold size, performing operations comprising:
identifying, by the processor component, a lowest-order node device or a highest-order node device in the ordering among the multiple node devices that is among the reduced number of node devices; and
transmitting, by the processor component, to the identified lowest-order node device or highest-order node device, and via the network, the combination of the map data and the metadata.

### Claim 28 (depends on 27)

The computer-implemented method of claim 27, comprising, in response to a determination that the combination does meet the minimum threshold size, performing operations comprising:
forming, by the processor component, one or more segments for transmission to the one or more storage devices from the combination of the map data and the metadata that each fit within the minimum threshold size and a maximum threshold size imposed on units of data of the data set to be transmitted to one or more storage devices; and
transmitting, by the processor component, to the one or more storage devices via the network, the one or more segments at least partially in parallel with multiple other segments formed from the multiple blocks of data by the reduced number of node devices.

### Claim 29 (depends on 21)

The computer-implemented method of claim 21, wherein:
the data of the data set comprises partitioned data wherein:
the data of the data set is divided into a set of partitions that are each required to be provided to a single node device;
each block of data is divided into one or more data sub-blocks that are each individually associated with a partition of the set of partitions; and
all data sub-blocks associated with a single partition of the set of partitions must be included within a single block of data; and
the method comprises:
as part of the registration of the multiple blocks of data, receiving, by the processor component, for each sub-block of each block of data, a hashed value indicative of a partition with which the sub-block is associated; and
generating, by the processor component, within the map data and for each block of data of the multiple blocks of data, a separate map entry that comprises the size and hashed value of each sub-block within the block of data.

### Claim 30 (depends on 21)

The computer-implemented method of claim 21, wherein:
the data of the data set is to be stored within the one or more storage devices in encrypted form, wherein each block of data is to be separately encrypted by one of the node devices of the multiple node devices; and
the method comprises:
as part of the registration of multiple blocks of data, receiving, by the processor component, for each block of data of the multiple blocks of data, data block encryption data by which the block of data is encrypted; and
generating, by the processor component, within the map data and for each block of data of the multiple blocks of data, a separate map entry that comprises the data block encryption data for the block of data.