Granted Patent B2

US 12,675,393 · App. 18/760,105 · Granted Jul 7, 2026

Inventors: Ryan D. Menhusen (Fort Collins, CO); Clarete Riana Crasta (Bangalore, IN); Syed Ismail Faizan Barmawer (Bangalore, IN); Darel Neal Emmot (Wellington, CO); David R. Emberson (Santa Cruz, CA); Sharad Singhal (Belmont, CA); Sajeesh Kumar K V (Bangalore, IN); Ramesh Chandra Chaurasiya (Bangalore, IN); Adya Sharma (Bangalore, IN)

Assignee: Hewlett Packard Enterprise Development LP

G06F12/0223

Abstract

Claims (105)

1 . A method, comprising:

determining, by a processing entity, records and corresponding data items stored in a memory shared by other processing entities, a respective record comprising a key and a payload, and a respective corresponding data item comprising the key and a corresponding index indicating a physical location in the shared memory at which the respective record is stored;

obtaining, by the processing entity, a portion of the data items, the portion of a size based on an available processing capacity of the processing entity;

obtaining burst tree data by performing a burst sort on the obtained portion of the data items;

storing the burst tree data in a partition of a dynamic random access memory (DRAM);

moving data stored in the DRAM partition to a partition of the shared memory in response to a size of the stored data exceeding a predetermined threshold;

maintaining the shared memory partition and one or more shared memory partitions in an unsorted order;

obtaining sorted data items corresponding to the records by sorting the burst tree data stored in the one or more shared memory partitions;

writing the sorted data items to the shared memory; and

facilitating a sorted retrieval of the records in the shared memory while leaving the records in the respective physical location in the shared memory by accessing the sorted data items in the shared memory.

2 . The method of claim 1 :

the processing entities associated with computing nodes coupled to a network of switches; and

the shared memory comprising a memory resource attached to the network of switches.

3 . The method of claim 1 , further comprising:

performing, by the processing entities, load-balancing for sorting the records stored in the shared memory by:

obtaining, by a respective processing entity, the portion of the data items, wherein a size of the portion obtained by the respective processing entity is based on an available processing capability of the respective processing entity;

performing, by the respective processing entity, the burst sort on the obtained portion;

storing, by the respective processing entity, the burst tree data in a respective DRAM partition;

moving, by the respective processing entity, the data from the respective DRAM partition to a respective shared memory partition independently of other processing entities; and

eliminating communication and coordination between the processing entities while sorting the records stored in the shared memory.

4 . The method of claim 1 , further comprising:

in response to updating the records stored in the shared memory:

determining updated data items corresponding to the updated records;

performing the burst sort only on the updated data items until the burst tree data associated with the updated data items has been stored in a respective DRAM partition and moved to a respective shared memory partition;

refraining from performing the burst sort on data items corresponding to records previously stored in the shared memory; and

obtaining the sorted data items by sorting the burst tree data stored in the one or more shared memory partitions.

5 . The method of claim 1 , further comprising:

maintaining the burst tree data stored in the DRAM partition as a prefix tree in a sorted order; and

maintaining the shared memory partitions in an unsorted order prior to the processing entity sorting the burst tree data stored in the shared memory partitions, the shared memory partitions comprising partitions associated with a range of prefixes.

6 . The method of claim 1 , further comprising:

identifying the one or more shared memory partitions by:

generating tasks for a respective shared memory partition, wherein the respective shared memory partition is associated with keys sharing common prefixes, and wherein a respective task corresponds to sorting burst tree data stored in the respective shared memory partition;

inserting the generated tasks into a work queue; and

sorting, by the processing entity and the other processing entities, the respective shared memory partition in response to acquiring the respective task from the work queue.

7 . The method of claim 6 , further comprising:

determining whether a number of keys in a first generated task exceeds a predetermined number;

creating a new task for keys not included for processing in the first generated task in response to the number of keys in the first generated task exceeding the predetermined number; and

inserting the new task into the work queue.

8 . The method of claim 1 , wherein sorting the burst tree data stored in the one or more shared memory partitions is based on at least one of:

a comparison sort;

a quick sort; or

a count sort.

9 . The method of claim 1 , further comprising:

receiving a request for one or more of the records stored in the shared memory, wherein the request includes a plurality of the sorted indices; and

returning the requested one or more records in a sorted order from the shared memory based on indices of the sorted data items previously written to the shared memory.

10 . A computer system, comprising:

a processor; and

a storage device storing instructions to:

determine, by a processing entity, records and corresponding data items stored in a memory shared by other processing entities, wherein a respective record comprises a key and a payload, and wherein a respective corresponding data item comprises the key and a corresponding index indicating a physical location in the shared memory at which the respective record is stored;

obtain, by the processing entity, a portion of the data items, the portion of a size based on an available processing capacity of the processing entity;

obtain burst tree data by performing a burst sort on the obtained portion of the data items;

store the burst tree data in a partition of a dynamic random access memory (DRAM):

responsive to a size of the stored data exceeding a predetermined threshold, move data stored in the DRAM partition to a partition of the shared memory;

identify one or more shared memory partitions based on a work queue;

maintain the shared memory partition and the one or more shared memory partitions in an unsorted order;

obtain sorted keys and corresponding indices of the data items for the records by sorting the burst tree data stored in the one or more shared memory partitions; and

facilitate a sorted retrieval of the records in the shared memory while leaving the records in the respective physical location in the shared memory by writing the sorted keys and indices of the data items to the shared memory.

11 . The computer system of claim 10 ,

wherein the processing entities are associated with computing nodes coupled to a network of switches, and

wherein the shared memory comprises a memory resource attached to the network of switches.

12 . The computer system of claim 10 , the instructions further to:

perform, by the processing entities, load-balancing for sorting the records stored in the shared memory by:

obtaining, by a respective processing entity, the portion of the records stored in the shared memory, wherein a size of the portion obtained by the respective processing entity is based on an available processing capability of the respective processing entity;

performing, by the respective processing entity, the burst sort on the obtained portion;

storing, by the respective processing entity, the burst tree data in a respective DRAM partition;

moving, by the respective processing entity, the data from the respective DRAM partition to a respective shared memory partition independently of other processing entities; and

eliminating communication and coordination between the processing entities while sorting the records stored in the shared memory.

13 . The computer system of claim 10 , the instructions further to:

in response to updating the records stored in the shared memory:

perform the burst sort only on the updated records until the burst tree data associated with the updated records has been stored in a respective DRAM partition and moved to a respective shared memory partition;

refrain from performing the burst sort on the records previously stored in the shared memory; and

obtain the sorted indices for the updated records by sorting the burst tree data stored in the one or more shared memory partitions.

14 . The computer system of claim 10 , the instructions further to:

maintain the burst tree data stored in the DRAM partition as a prefix tree in a sorted order; and

maintain the shared memory partitions in an unsorted order prior to the processing entity sorting the burst tree data stored in the shared memory partitions, the shared memory partitions comprising partitions associated with a range of prefixes.

15 . The computer system of claim 10 , the instructions to identify the one or more shared memory partitions further to:

generate tasks for a respective shared memory partition, wherein the respective shared memory partition is associated with keys sharing common prefixes, and wherein a respective task corresponds to sorting burst tree data stored in the respective shared memory partition;

insert the generated tasks into a work queue; and

sort, by the processing entity and the other processing entities, the respective shared memory partition in response to acquiring the respective task from the work queue.

16 . The computer system of claim 10 , the instructions further to sort the burst tree data stored in the one or more shared memory partitions based on at least one of:

a comparison sort;

a quick sort; or

a count sort.

17 . The computer system of claim 10 , the instructions further to:

receiving a request for data stored in the shared memory, wherein the request includes a plurality of the sorted indices; and

returning data in a sorted order from the shared memory based on the sorted indices previously written to the shared memory.

18 . A non-transitory computer-readable medium storing instructions to:

determine, by a processing entity, records and corresponding data items stored in a memory shared by other processing entities, a respective record comprising a key and a payload, and a respective corresponding data item comprising the key and a corresponding index indicating a physical location in the shared memory at which the respective record is stored;

obtain, by the processing entity, a portion of the data items, the portion of a size based on an available processing capacity of the processing entity;

perform a burst sort on the obtained portion of the data items;

store, in a partition of a dynamic random access memory (DRAM), burst tree data obtained from the burst sort;

move data stored in the DRAM partition to a partition of the shared memory in response to a size of the stored data exceeding a predetermined threshold;

maintain the shared memory partition and one or more shared memory partitions in an unsorted order;

sort the burst tree data stored in the one or more shared memory partitions;

obtain sorted keys and corresponding indices of the data items for the records based on the sorted burst tree data; and

write the sorted keys and corresponding indices of the data items to the shared memory, wherein writing the sorted keys and corresponding indices of the data items to the shared memory facilitates a sorted retrieval of the records in the shared memory while leaving the records in the respective physical location in the shared memory.

19 . The non-transitory computer-readable medium of claim 18 , the instructions further to perform, by the processing entities, load-balancing for sorting the records stored in the shared memory, the instructions to perform the load-balancing further to:

obtain, by a respective processing entity, the portion of the records stored in the shared memory, wherein a size of the portion obtained by the respective processing entity is based on an available processing capability of the respective processing entity;

perform, by the respective processing entity, the burst sort on the obtained portion;

store, by the respective processing entity, the burst tree data in a respective DRAM partition;

move, by the respective processing entity, the data from the respective DRAM partition to a respective shared memory partition independently of other processing entities; and

eliminate communication and coordination between the processing entities while sorting the records stored in the shared memory.

20 . The non-transitory computer-readable medium of claim 18 , the instructions further to process a request for one or more of the records stored in the shared memory by:

receiving a request for the one or more records stored in the shared memory, wherein the request includes one or more of the sorted indices; and

in response to receiving the request, returning the requested one or more records in a sorted order from the shared memory based on the sorted indices previously written to the shared memory.

Assignments (1)

Priority Claims (1)

Continuity (1)

References Cited (40)