Software virtual machine for acceleration of transactional data processing

• US 9,027,022 B2
• Filed: 06/15/2012
• Issued: 05/05/2015
• Est. Priority Date: 06/16/2011
• Status: Active Grant

• Current Assignee: Argyle Data, Inc. (Mavenir Group Holdings Ltd.)
• Original Assignee: Argyle Data, Inc. (Mavenir Group Holdings Ltd.)
• Inventors: Huetter, Raymond J., Yamarti, Alka
• Primary Examiner(s): Lee, Adam
• Assistant Examiner(s): Huaracha, Willy W
• Application Number:
  US13/524,881
• Publication Number:
  US 20120324447A1
• Time in Patent Office: 1,054 Days
• Field of Search: 718/1, 718/100, 718/101, 718/102, 718/104
• US Class Current: 718/1
• 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 virtual machines that each operate in accordance with a virtual instruction set, wherein each of the virtual machines executes on a corresponding one of the execution cores;

an in-memory database comprising different portions of data each stored within a different one of a plurality of memory partitions, wherein each of the memory partitions is associated with a different one of the execution cores; and

a plurality of tasks that execute on the virtual machines to decompose an incoming transaction for the in-memory database into sub-transactions that each modify respective portions of the data stored by the memory partitions, deploy the sub-transactions to the execution cores associated with the respective memory partitions that store the respective portions of the data to be modified by the sub-transactions, and concurrently execute the sub-transactions of the incoming transaction on the respective execution cores to which the sub-transactions are deployed,

wherein each virtual machine of the virtual machines includes, for the corresponding execution core, a scheduler that manages a separate run list data structure that stores references to tasks of the plurality of tasks that are scheduled for execution by the corresponding execution core and also manages a separate cross-queue data structure that stores references to tasks migrated to the virtual machine by tasks executing on other virtual machines of the virtual machines.

2. The device of claim 1, further comprising:

a statement execution task that executes on one of the virtual machines to apply an assignment algorithm to the sub-transactions to identify the respective execution cores associated with the memory partitions that store the respective portions of the data to be modified by the sub-transactions,

wherein the statement execution task spawns and deploys, for each of the sub-transactions, a sub-execution task to execute the sub-transaction on the identified one of the execution cores for the sub-transaction, wherein the sub-execution tasks for the corresponding sub-transactions concurrently execute on the virtual machines.

3. The device of claim 2,

wherein the statement execution task applies the assignment algorithm to a plurality of data referenced by the incoming transaction to identify the respective portions of the data for the sub-transactions,

wherein the assignment algorithm identifies a different one of the execution cores for each of the plurality of data referenced by the incoming transaction,

wherein each of the sub-transactions is a transaction for a corresponding one of the plurality of data referenced by the incoming transaction, and

wherein the statement execution task spawns a sub-execution task to the identified one of the execution cores for each of the plurality of data referenced by the incoming transaction to execute the corresponding sub-transaction.

4. The device of claim 2, further comprising:

a schema that describes database objects of the in-memory database;

a step library comprising one or more steps each specifying instructions executable by the plurality of cores; and

a transactional grammar that describes a language to which the incoming transaction conforms, wherein the transactional grammar comprises one or more substitution rules that reference steps of the step library,

wherein the statement execution task applies the transactional grammar and schema to the incoming transaction to generate sub-transactions that each comprise steps of the step library.

5. The device of claim 1,

wherein the virtual machines asynchronously execute the plurality of tasks, the device further comprising:

a heartbeat task that executes on each of the virtual machines according to a defined period to cause, upon execution of the heartbeat task, the corresponding virtual machine to wait to execute any additional tasks until the corresponding virtual machine receives a signal.

6. The device of claim 5,

wherein the heartbeat task comprises a task hook that specifies a hooked task,

wherein one of the virtual machines executes the hooked task, and

wherein the one of the virtual machines sends the signal to the other virtual machines after completing the hooked task.

7. The device of claim 6, wherein the hooked task comprises a checkpoint task that, when executed, generates and stores a checkpoint for the in-memory database.

8. The device of claim 1,

wherein a task executing on a first one of the virtual machines enqueues a reference to a first task to the cross-queue data structure of a second one of the virtual machines while the second virtual machine simultaneously executes a second task referenced in the run list managed by the scheduler of the second virtual machine, and

wherein the scheduler of the second virtual machine subsequently moves the first task to the run list managed by the scheduler of the second virtual machine.

9. The device of claim 1,

wherein each of the virtual machines defines a sleep list data structure that stores references to sleeping tasks ordered by remaining sleep time for the sleeping tasks,

wherein each of the plurality of execution cores comprises a timer,

wherein an alarm task executing on each of the virtual machines sets an expiration time for the timer for the corresponding executing core based at least on the smallest remaining sleep time for the sleeping tasks of the sleep list data structure of the virtual machine, and

wherein timer expiration causes the alarm task to awaken the next sleeping task of the sleep list.

10. The device of claim 1, wherein the incoming transaction is selected from the group consisting of inserting to, deleting from, and updating the in-memory database.

11. The device of claim 1, further comprising:

a plurality of cluster machines that each comprise a different, non-overlapping subset of the plurality of execution cores.

12. The device of claim 1, wherein the device comprises a database acceleration engine positioned between at least one data source and at least one data consumer.

13. The device of claim 1,

wherein the incoming transaction comprises a delete transaction to delete a row from the in-memory database, the device further comprising:

a plurality of garbage collector tasks that identify references to the row in a plurality of data structures of the in-memory database and concurrently execute to remove the references to the row in the plurality of data structures.

14. A method 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 corresponding one of a plurality of execution cores of a multi-core hardware processor of a computing device;

associating a different one of the execution cores with each of a plurality of memory partitions, wherein each of the memory partitions stores a different portion of data for an in-memory database; and

executing a plurality of tasks with the virtual machines, wherein the plurality of tasks decompose an incoming transaction for the in-memory database into sub-transactions that each modify respective portions of the data stored by the memory partitions, deploy the sub-transactions to the execution cores associated with the respective memory partitions that store the respective portions of the data to be modified by the sub-transactions, and concurrently execute the sub-transactions of the incoming transaction on the respective execution cores to which the sub-transactions are deployed,

wherein each virtual machine of the virtual machines includes, for the corresponding execution core, a scheduler that manages a separate run list data structure that stores references to tasks of the plurality of tasks that are scheduled for execution by the corresponding execution core and also manages a separate cross-queue data structure that stores references to tasks migrated to the virtual machine by tasks executing on other virtual machines of the virtual machines.

15. The method of claim 14, further comprising:

applying, with a statement execution task on one of the virtual machines, an assignment algorithm to the sub-transactions to identify the respective execution cores associated with the memory partitions that store the respective portions of the data to be modified by the sub-transactions,

wherein the statement execution task spawns and deploys, for each of the sub-transactions, a sub-execution task to execute the sub-transaction on the identified one of the execution cores for the sub-transaction, wherein the sub-execution tasks for the corresponding sub-transactions concurrently execute on the virtual machines.

16. The method of claim 15,

wherein the statement execution task applies the assignment algorithm to a plurality of data referenced by the incoming transaction to identify the respective portions of the data for the sub-transactions,

wherein the assignment algorithm identifies a different one of the execution cores for each of the plurality of data referenced by the incoming transaction,

wherein each of the sub-transactions comprises a transaction for a corresponding one of the plurality of data referenced by the incoming transaction, and

wherein the statement execution task spawns a sub-execution task to the identified one of the execution cores for each of the plurality of data to execute the corresponding sub-transaction.

17. The method of claim 15,

wherein the statement execution task applies a transactional grammar and a schema to the incoming transaction to generate sub-transactions that each comprise steps of a step library,

wherein the schema that describes database objects of the in-memory database,

wherein the step library comprises one or more steps each specifying instructions executable by the plurality of cores, and

wherein the transactional grammar describes a language to which the incoming transaction conforms and comprises one or more substitution rules that reference steps of the step library.

18. The method of claim 14, wherein the virtual machines asynchronously execute the plurality of tasks, the method further comprising:

executing a heartbeat task on each of the virtual machines according to a defined period to cause, upon execution of the heartbeat task, the corresponding virtual machine to wait to execute any additional tasks until the corresponding virtual machine receives a signal.

19. The method of claim 18,

wherein the heartbeat task comprises a task hook that specifies a hooked task,

wherein one of the virtual machines executes the hooked task, and

wherein the one of the virtual machines sends the signal to the other virtual machines after completing the hooked task.

20. The method of claim 19, wherein the hooked task comprises a checkpoint task that, when executed, generates and stores a checkpoint for the in-memory database.

21. The method of claim 14,

wherein a task executing on a first one of the virtual machines enqueues a reference to a first task to the cross-queue data structure of a second one of the virtual machines while the second virtual machine simultaneously executes a second task referenced in the run list managed by the scheduler of the second virtual machine, and

wherein the scheduler of the second virtual machine subsequently moves the first task to the run list managed by the scheduler of the second virtual machine.

22. The method of claim 14,

wherein each of the virtual machines defines a sleep list data structure that stores references to sleeping tasks ordered by remaining sleep time for the sleeping tasks, and

wherein each of the plurality of execution cores comprises a timer, the method further comprising:

executing an alarm task on each of the virtual machines to set an expiration time for the timer for the corresponding executing core based at least on the smallest remaining sleep time for the sleeping task of the sleep list data structure of the virtual machine,

wherein timer expiration causes the alarm task to awaken the next sleeping task of the sleep list.

23. The method of claim 14, wherein the incoming transaction comprises one of inserting to, deleting from, and updating, the in-memory database.

24. The method of claim 14, wherein a database acceleration engine of the computing device is positioned between at least one data source and at least one data consumer.

25. The method of claim 14,

wherein the incoming transaction comprises a delete transaction to delete a row from the in-memory database, the method further comprising:

executing a plurality of garbage collector tasks to identify references to the row in a plurality of data structures of the in-memory database and concurrently remove the references to the row in the plurality of data structures.

26. A computer-readable storage device comprising instructions that, when executed, cause a multi-core hardware processor having a plurality of execution cores 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 corresponding one of the plurality of execution cores;

associate a different one of the execution cores with each of a plurality of memory partitions, wherein each of the memory partitions stores a different portion of data for an in-memory database; and

execute a plurality of tasks with the virtual machines, wherein the plurality of tasks decompose an incoming transaction for the in-memory database into sub-transactions that each modify respective portions of the data stored by respective memory partitions, deploy the sub-transactions to the execution cores associated with the respective memory partitions that store the respective portions of the data to be modified by the sub-transactions, and concurrently execute the sub-transactions of the incoming transaction on the respective execution cores to which the sub-transactions are deployed,

wherein each virtual machine of the virtual machines includes, for the corresponding execution core, a scheduler that manages a separate run list data structure that stores references to tasks of the plurality of tasks that are scheduled for execution by the corresponding execution core and also manages a separate cross-queue data structure that stores references to tasks migrated to the virtual machine by tasks executing on other virtual machines of the virtual machines.