Software virtual machine for content delivery

• US 8,645,958 B2
• Filed: 06/15/2012
• Issued: 02/04/2014
• Est. Priority Date: 06/16/2011
• Status: Active Grant

• Current Assignee: Argyle Data, Inc. (Mavenir Group Holdings Ltd.)
• Original Assignee: uCIRRUS Corp.
• Inventors: Huetter, Raymond J., Yamarti, Alka
• Primary Examiner(s): KAWSAR, ABDULLAH AL
• Application Number:
  US13/524,959
• Publication Number:
  US 20120324448A1
• Time in Patent Office: 599 Days
• Field of Search: 707705-788, 718 1-107
• US Class Current: 718/101
• CPC Class Codes: G06F 2209/5017 Task decomposition
• CPC Class Codes: G06F 9/5066 Algorithms for mapping a plurality of inter-dependent sub-tasks onto a plurality of physical CPUs mappping at compile time, see G06F8/451

Abstract

In general, this disclosure is directed to a software virtual machine that provides high-performance transactional data acceleration optimized for multi-core computing platforms. The virtual machine utilizes an underlying parallelization engine that seeks to maximize the efficiencies of multi-core computing platforms to provide a highly scalable, high performance (lowest latency), virtual machine. In some embodiments, the virtual machine may be viewed as an in-memory virtual machine with an ability in its operational state to self organize and self seek, in real time, available memory work boundaries to automatically optimize maximum available throughput for data processing acceleration and content delivery of massive amounts of data.

Claims

1. A device comprising:

a multi-core hardware processor having a plurality of execution cores;

a plurality of memory partitions each associated with a different one of the execution cores;

an in-memory database comprising;

a database table having a field and one or more rows that each include a value for the field; and

an index having a set of index entries that each map a value for the field to a corresponding row of one or more rows of the database table,

wherein each of the plurality of memory partitions stores a different one of a plurality of portions of the index, wherein each of the different portions of the index includes a different subset of the set of index entries;

a content delivery engine that configures a plurality of private data channels to each deliver unique data to a corresponding one of a plurality of data consumers; and

a parallelization engine that receives, from the content delivery engine, a query request for rows of the one or more rows of the database table having a value for the field that matches a criteria of the query request,

wherein the parallelization engine, in response to the query request, applies an assignment algorithm to the criteria of the query request to identify one of the execution cores that is associated with one of the memory partitions that stores one of the portions of the index that includes one of the index entries that maps the value for the field that matches the criteria of the query request to a matching row of the one or more rows of the database table, and

wherein the parallelization engine spawns and deploys a task to the identified execution core to execute only on the identified execution core to obtain and return, to the content delivery engine and in response to the query request, at least one value of the matching row of the one or more rows of the database table.

2. The device of claim 1,

wherein the criteria of the query request comprises a first criterion and a second criterion, the device further comprising:

a plurality of virtual machines that each operate in accordance with a virtual instruction set, wherein each of the virtual machines executes on a different one of the execution cores; and

a statement execution task that executes on one of the virtual machines to decompose the query request into first and second sub-transactions, wherein the first sub-transaction is associated with the first criterion and the second sub-transaction is associated with the second criterion,

apply an assignment algorithm to the first sub-transaction to identify a first one of the execution cores associated with one of the memory partitions that stores one of the portions of the index that includes one of the index entries that maps the value for the field that matches the first criterion to a first matching row of the one or more rows of the database table, and

apply the assignment algorithm to the second sub-transaction to identify a second one of the execution cores associated with one of the memory partitions that stores one of the portions of the index that includes one of the index entries that maps the value for the field that matches the second criterion to a second matching row of the one or more rows of the database table,

wherein the statement execution task spawns and deploys, for each of the first and second sub-transactions, a sub-execution task to execute the sub-transaction only on the identified one of the execution cores for the sub-transaction.

3. The device of claim 2,

wherein each of the virtual machines comprises a scheduler for the corresponding execution core, and

wherein each of the schedulers maintains a separate run list data structure that stores references to tasks scheduled for execution by the corresponding one of the plurality of execution cores.

4. The device of claim 1,

wherein the content delivery engine presents an application programming interface (API) that allows data consumers to specify a continuous query that directs the content delivery engine to continuously apply the continuous query to data newly received by the device.

5. The device of claim 1,

wherein the content delivery engine receives a continuous query that directs the content delivery engine to continuously apply the continuous query to data newly received by the device.

6. The device of claim 5, wherein the continuous query specifies a future token.

7. The device of claim 6,

wherein the content delivery engine receives a first transaction that requests first data and a second transaction that requests second data, and

wherein the content delivery engine computes an aggregate transaction that requests the first data and the second data and outputs the aggregate transaction to another device.

8. The device of claim 6,

wherein the content delivery engine receives an aggregate transaction requesting first data and second data and directs the parallelization engine to execute an aggregate transaction to aggregate the first data and second data, and

wherein the content delivery engine outputs the first data and the second data aggregated by the parallelization engine in response to the aggregate transaction.

9. The device of claim 8,

wherein the plurality of tasks decomposes the aggregate transaction into a plurality of sub-transactions, concurrently execute the sub-transactions to retrieve the first data and the second data from the in-memory database, and return the first data and second data to the content delivery engine.

10. A method comprising:

associating each of a plurality of memory partitions with a different one of a plurality of execution cores of a multi-core hardware processor;

configuring, with a content delivery engine, a plurality of private data channels to each deliver unique data to a corresponding one of a plurality of data consumers;

configuring an in-memory database comprising;

a database table having a field and one or more rows that each include a value for the field; and

an index having a set of index entries that each map a value for the field to a corresponding row of one or more rows of the database table,

wherein each of the plurality of memory partitions stores a different one of a plurality of portions of the index, wherein each of the different portions of the index includes a different subset of the set of index entries;

receiving, with a parallelization engine executing on the multi-core hardware processor and from the content delivery engine, a query request for rows of the one or more rows of the database table having a value for the field that matches a criteria of the query request;

with the parallelization engine and in response to the query request, applying an assignment algorithm to the criteria of the query request to identify one of the execution cores that is associated with one of the memory partitions that stores one of the portions of the index that includes one of the index entries that maps the value for the field that matches the criteria of the query request to a matching row of the one or more rows of the database table; and

with the parallelization engine, spawning and deploying a task to the identified execution core to execute on the identified execution core to obtain and return, to the content delivery engine and in response to the query request, at least one value of the matching row of the one or more rows of the database table.

11. The method of claim 10, wherein the criteria of the query request comprises a first criterion and a second criterion, the method further comprising:

executing a plurality of virtual machines that each operate in accordance with a virtual instruction set, wherein each of the virtual machines executes on a different one of the execution cores of the multi-core hardware processor; and

decomposing, with a statement execution task executing on one of the virtual machines, the query request into first and second sub-transactions, wherein the first sub-transaction is associated with the first criterion and the second sub-transaction is associated with the second criterion;

applying, with the statement execution task, an assignment algorithm to the first sub-transaction to identify a first one of the execution cores associated with the one of the memory partitions that stores one of the portions of the index that includes one of the index entries that maps the value for the field that matches the first criterion to a first matching row of the one or more rows of the database table;

applying, with the statement execution task, the assignment algorithm to the second sub-transaction to identify a second one of the execution cores associated with the one of the memory partitions that stores one of the portions of the index that includes one of the index entries that maps the value for the field that matches the second criterion to a second matching row of the one or more rows of the database table; and

with the statement execution task and for each of the first and second sub-transactions, spawning and deploying a sub-execution task to execute the sub-transaction on the identified one of the execution cores for the sub-transaction.

12. The method of claim 11,

wherein each of the virtual machines comprises a scheduler for the corresponding execution core, and

wherein each of the schedulers maintains a separate run list data structure that stores references to tasks scheduled for execution by the corresponding one of the plurality of execution cores.

13. The method of claim 10,

wherein the content delivery engine presents an application programming interface (API) that allows data consumers to specify a continuous query that directs the content delivery engine to continuously apply the continuous query to newly received data.

14. The method of claim 10, further comprising:

receiving, with the content delivery engine, a continuous query that directs the content delivery engine to continuously apply the continuous query to data newly received by the device.

15. The method of claim 14, wherein the continuous query specifies a future token.

16. The method of claim 15, further comprising:

receiving, with the content delivery engine, a first transaction that requests first data and a second transaction that requests second data;

computing, with the content delivery engine, an aggregate transaction that requests the first data and the second data; and

outputting the aggregate transaction to another device.

17. The method of claim 15,

receiving, with the content delivery engine, an aggregate transaction requesting first data and second data;

directing the parallelization engine to execute an aggregate transaction to aggregate the first data and second data; and

outputting, with the content delivery engine, the first data and the second data aggregated by the parallelization engine in response to the aggregate transaction.

18. The method of claim 17,

wherein the plurality of tasks decomposes the aggregate transaction into a plurality of sub-transactions, concurrently execute the sub-transactions to retrieve the first data and the second data from the in-memory database, and return the first data and second data to the content delivery engine.

19. A non-transitory computer-readable storage device comprising instructions that, when executed, cause a multi-core hardware processor having a plurality of execution cores to:

associate each of a plurality of memory partitions with a different one of a plurality of execution cores of a multi-core hardware processor;

configure, with a content delivery engine, a plurality of private data channels to each deliver unique data to a corresponding one of a plurality of data consumers;

configure an in-memory database comprising;

a database table having a field and one or more rows that each include a value for the field; and

an index having a set of index entries that each map a value for the field to a corresponding row of the one or more rows of the database table,

wherein each of the plurality of memory partitions stores a different one of a plurality of portions of the index, wherein each of the different portions of the index includes a different subset of the set of index entries;

receive, with a parallelization engine executing on the multi-core hardware processor and from the content delivery engine, a query request for rows of the one or more rows of the database table having a value for the field that matches a criteria of the query request;

with the parallelization engine and in response to the query request, apply an assignment algorithm to the criteria of the query request to identify one of the execution cores that is associated with one of the memory partitions that stores one of the portions of the index that includes one of the index entries that maps the value for the field that matches the criteria of the query request to a matching row of the one or more rows of the database table; and

with the parallelization engine, spawn and deploy a task to the identified execution core to execute on the identified execution core to obtain and return, to the content delivery engine and in response to the query request, at least one value of the matching row of the one or more rows of the database table.

20. The non-transitory computer-readable storage device of claim 19, wherein the criteria of the query request comprises a first criterion and a second criterion, and wherein the instructions, when executed, further cause the multi-core hardware processor to:

execute a plurality of virtual machines that each operate in accordance with a virtual instruction set, wherein each of the virtual machines executes on a different one of the plurality of execution cores;

execute a statement execution task on one of the virtual machines to decompose the query request into first and second sub-transactions, wherein the first sub-transaction is associated with the first criterion and the second sub-transaction is associated with the second criterion;

applying, with the statement execution task, an assignment algorithm to the first sub-transaction to identify a first one of the execution cores associated with the one of the memory partitions that stores one of the portions of the index that includes one of the index entries that maps the value for the field that matches the first criterion to a first matching row of the one or more rows of the database table;

applying, with the statement execution task, the assignment algorithm to the second sub-transaction to identify a second one of the execution cores associated with the one of the memory partitions that stores one of the portions of the index that includes one of the index entries that maps the value for the field that matches the second criterion to a second matching row of the one or more rows of the database table; and

with the statement execution task and for each of the sub-transactions, spawn and deploy a sub-execution task to execute the sub-transaction on the identified one of the execution cores for the sub-transaction.