Persistent data storage techniques

• US 8,489,567 B2
• Filed: 02/24/2010
• Issued: 07/16/2013
• Est. Priority Date: 10/13/2000
• Status: Active Grant

• Current Assignee: MIOsoft Corporation
• Original Assignee: Microsoft Corporation
• Inventors: Barabas, Albert B., Siepman, Ernst M., van Gulik, Mark D. A.
• Primary Examiner(s): To, Baoquoc N
• Application Number:
  US12/711,402
• Publication Number:
  US 20100191705A1
• Time in Patent Office: 1,238 Days
• Field of Search: 707/704
• US Class Current: 707/704
• CPC Class Codes: G06F 16/23 Updating
• CPC Class Codes: G06F 16/2343 Locking methods, e.g. distributed locking or locking implementation details
• CPC Class Codes: G06F 16/2379 Updates performed during online database operations; commit processing
• CPC Class Codes: G06F 16/289 Object oriented databases
• CPC Class Codes: G06F 9/46 Multiprogramming arrangements
• CPC Class Codes: Y10S 707/99938 Concurrency, e.g. lock management in shared database

Abstract

A database is maintained that stores data persistently. Tasks are accepted from task sources. At least some of the tasks have competing requirements for use of regions of the database. Each of the regions includes data that is all either locked or not locked for writing at a given time. Each of the regions is associated with an available processor. For each of the tasks, jobs are defined each of which requires write access to regions that are to be accessed by no more than one of the processors. Jobs are distributed for concurrent execution by the associated processors.

Claims

1. A method comprising

maintaining a database that stores data persistently,

accepting tasks from task sources, the tasks being associated with priority information that identifies each of them as having one of at least two different levels of priority for execution,

defining, for each of the tasks, jobs to be executed to complete the task,

distributing the jobs for concurrent execution by processors, the jobs being assigned to the processors based on characteristics of items of the data to be accessed during execution, and

selecting jobs for execution in an order that is based on the priorities of the tasks with which they are associated.

2. The method of claim 1 in which the items of the data comprise objects in an object database.

3. The method of claim 1 in which the items of the data are provided as objects to an object-oriented application.

4. The method of claim 3 in which an object relational broker provides persistent storage of objects for an object-oriented application.

5. The method of claim 3 in which the data is stored in a relational database with object-oriented extensions.

6. The method of claim 1, 2, or 3 in which at least some of the tasks have competing requirements for use of regions of the database, each of the regions including data that is all either locked or not locked for writing at a given time, and each of the regions is associated with one of the processors.

7. The method of claim 6 comprising

causing at least some of the processors to execute at least some of the jobs in an order based on the regions of the database to be accessed by the jobs.

8. The method of claim 6 comprising

causing at least some of the processors to execute at least some of the jobs other than in an order in which the jobs are accepted for execution, the jobs being assigned to the processors based on respective regions of the database to which the data to be accessed belongs.

9. The method of claim 1, 2, or 3 in which the jobs are executed in an order that assures no more than a predetermined average short delay between creation of a task and the execution of the jobs defined for the task.

10. The method of claim 1, 2, or 3 in which jobs of one priority are guaranteed to be executed in a manner that does not delay jobs of a second priority by more than a predetermined average delay time.

11. The method of claim 1, 2, or 3 in which the tasks include higher priority tasks generated by users for execution in real-time and lower priority tasks generated by software processes.

12. The method of claim 11 in which the lower priority tasks comprise batch-type update tasks.

13. The method of claim 1, 2, or 3 in which jobs are selected into an execution set of a predetermined size by each of the processors from a staged set of jobs that has been distributed to that processor and is awaiting execution.

14. The method of claim 13 in which only jobs of higher priority are selected from the staged set until the execution set is filled, and, if the execution set cannot be filled by the jobs of higher priority, then jobs of lower priority are selected from the staged set for inclusion in the execution set.

15. The method of claim 1 comprising causing the processors to execute at least some of the jobs synchronously.

16. The method of claim 1, wherein the priority information of the tasks comprises deadlines for executing the tasks, and at least some of the jobs are selected for execution in the order that is based on the deadlines associated with the tasks.

17. The method of claim 1 comprising causing each of the processors to execute at least some of the jobs in an order determined by actions to be performed by the jobs with respect to the data.

18. The method of claim 1 in which the at least some of the jobs to be executed by one of the processors are replaced by a single aggregated job.

19. The method of claim 18 in which the jobs that are replaced have been pre-identified as requiring execution as a synchronization group to ensure correctness of results, all of the jobs of the synchronization group being associated with information that identifies them as members of the group and defines their respective fractions of a quorum.

20. The method of claim 1 in which each of the processors determines an order in which to process at least some of the jobs based on physical locations on disk of the data that must be accessed by the jobs.

21. The method of claim 20 in which the processing order is determined based on a page structure of data on the disk.

22. The method of claim 20 in which the jobs are clustered for processing so that accesses to a given physical portion of the disk are clustered.

23. The method of claim 1 in which at least some of the jobs to be executed by a processor are redundant, and the processor does not execute the redundant jobs.

24. The method of claim 23 in which the redundant jobs are identical, and fewer than all of the identical jobs are executed.

25. The method of claim 23 in which some of the redundant jobs supersede others of the redundant jobs and only the superseding jobs are executed.

26. The method of claim 25 in which the redundant jobs have associated time stamps and the superseding jobs have later time stamps than the superseded jobs.