Persistent data storage techniques

• US 7,689,560 B2
• Filed: 04/09/2004
• Issued: 03/30/2010
• Est. Priority Date: 10/13/2000
• Status: Active Grant

• Current Assignee: MIOsoft Corporation
• Original Assignee: MIOsoft Corporation
• Inventors: Barabas, Albert B., van Gulik, Mark D. A., Siepman, Ernst M.
• Primary Examiner(s): To; Baoquoc N
• Application Number:
  US10/821,586
• Publication Number:
  US 20040267807A1
• Time in Patent Office: 2,181 Days
• Field of Search: 707/8, 707/10, 709/210
• US Class Current: 1/1
• 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 persistently on a physical storage medium,

partitioning the database into regions based on characteristics of items of data in the database,

receiving tasks that are in contention to write data to the respective regions,

reducing the contention among the received tasks by creating jobs that are based on each of the tasks, each of the jobs needing to write data in no more than one of the regions,

for each of the regions, queuing only those jobs that need to write data in the region and executing the queued jobs for each region, one job after another and without contention, and

executing jobs that are queued for different regions simultaneously, in parallel, and without contention.

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

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

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

5. The method of claim 1 in which the database comprises a relational database with object-oriented extensions.

6. The method of claim 1 in which the database comprises files that persistently store the items of data.

7. The method of claim 1, 2 or 3 in which the number of tasks received is arbitrarily large.

8. The method of claim 1, 2, or 3 in which the tasks are received from task sources, and the number of task sources is arbitrarily large.

9. The method of claim 1, 2, or 3 also including assigning each of the regions to a respective available processor, each of the regions being assignable to any of the processors.

10. The method of claim 9 in which the number of the regions is no fewer than the number of available processors.

11. The method of claim 9 in which the number of the regions is equal to the number of available processors.

12. The method of claim 9 also including organizing the regions to maximize the throughput of the available processors in executing the jobs.

13. The method of claim 9 in which the regions are assigned dynamically to the available processors to maximize the throughput of the available processors.

14. The method of claim 9 in which the processors do not use shared memory.

15. The method of claim 9 in which more than one of the regions is associated with one of the available processors.

16. The method of claim 15 in which each of the processors comprises a physical processor running at least one process.

17. The method of claim 9 in which each of the regions is associated with at least two available processors, one of which executes jobs and the other of which performs administrative functions with respect to the associated region.

18. The method of claim 9 in which each region comprises millions of sub-regions.

19. The method of claim 9 in which additional jobs are created in connection with the execution of the jobs, and a process running on one of the processors executes the jobs and creates the additional jobs, and in which at least some of the additional jobs are queued for regions served by other processors.

20. The method of claim 9 in which each of the jobs is assigned an index associated with the corresponding region.

21. The method of claim 20 in which the indexes are used to load balance the jobs among the processors.

22. The method of claim 9 in which (1) queuing the jobs includes maintaining a queuing system that has a capacity to receive jobs for execution at any arbitrarily large rate, (2) the queuing system includes conceptual rows each of which can receive the jobs, and (3) the queuing system includes conceptual columns associated with respective contention spaces, the queuing system comprising a conceptual matrix of cells at the intersections of the rows and columns, in which each of the cells is read from or written to without conflicting with reads and writes to other cells.

23. The method of claim 22 in which the rows are associated with sources of jobs and the number of rows is sufficient to permit all of the sources of jobs to load jobs into the queue concurrently.

24. The method of claim 22 in which the number of rows is sufficient to permit jobs to be fetched for execution from all of the columns concurrently.

25. The method of claim 1, 2, or 3 in which the tasks are received asynchronously.

26. The method of claim 1, 2, or 3 in which the tasks are received concurrently.

27. The method of claim 1, 2, or 3 in which creating the jobs comprises creating a hierarchy of subtasks in which the lowest level of the hierarchy contains the jobs.

28. The method of claim 1, 2, or 3 in which at least one of the tasks comprises a single job.

29. The method of claim 1, 2, or 3 in which one of the jobs generates a task to be performed.

30. The method of claim 1, 2, or 3 in which each of the tasks is completed with a certainty that is at least as high as the certainty that items of data updated in a requested database transaction are not lost once the transaction is committed.

31. The method of claim 1, 2, or 3 in which at least one of the regions comprises a single data item.

32. The method of claim 1, 2, or 3 in which at least one of the regions comprises at least a million data items.

33. The method of claim 1, 2, or 3 in which each of the tasks is generated by a user request.

34. The method of claim 1, 2, or 3 in which queuing the jobs includes maintaining a queuing system that has a capacity to receive jobs for execution at an arbitrarily large rate by adding processors proportionately to the number of jobs expected to require execution.

35. The method of claim 34 in which the queuing system includes conceptual rows each of which can receive the jobs.

36. The method of claim 35 in which each of the rows is locked when jobs are being received in the row.

37. The method of claim 36 in which a job can be accepted by the corresponding processor for execution from any of the rows that is not locked.

38. The method of claim 37 in which a row is locked only for reading when a processor is accepting jobs from that row.

39. The method of claim 1, 2, or 3 in which additional jobs are created in connection with the execution of the jobs.

40. The method of claim 39 in which further jobs are created by the additional jobs.

41. The method of claim 39 in which the creation of the additional jobs is dependent on data read from the database in executing the jobs.

42. The method of claim 1, 2, or 3 in which the tasks relate to commercial transactions.

43. The method of claim 1, 2, or 3 in which the database includes database units that are distributed among different physical locations.

44. The method of claim 1, 2, or 3 in which each of the jobs comprises steps.

45. The method of claim 44 in which execution of a job includes executing a portion of the steps, committing a database transaction representing those steps, and repeating until the job is completed.

46. The method of claim 45 also including, upon a failure to complete any portion of the steps, restarting the execution at the first step of the failed portion with at least the same level of certainty that the job will be completed as the certainty that data written in a requested transaction is not lost once the transaction is committed.

47. The method of claim 1, 2, or 3 also including synchronizing the executions of synchronization groups of the jobs to ensure correctness of results.

48. The method of claim 47 in which the synchronizing includes assigning to each of the jobs of a synchronization group a tag that identifies them as members of the group.

49. The method of claim 47 in which the synchronizing includes assigning to each of the jobs of a synchronization group a quorum fraction representing the job'"'"'s proportion of participation in the group.

50. The method of claim 49 in which the jobs are not executed until all of the jobs in the synchronization group are ready for execution by a processor.

51. Apparatus comprising

a physical storage medium on which a database is persistently maintained, the database being partitioned into regions, and

a job processing mechanism that (1) receives tasks that in contention to write data to the respective regions of the database, (2) creates jobs that are based on each of the tasks, each of the jobs needing to write data in no more than one of the regions, (3) for each of the regions, queues only those jobs that need to write data in the region, one job after another and without contention, and (4) executes jobs that are queued for different regions simultaneously, in parallel, and without contention.

52. The apparatus of claim 51 in which the data items of the database comprise objects in an object database.

53. The apparatus of claim 51 in which the data items are provided as objects to an object-oriented application.

54. The apparatus of claim 51 in which an object relational broker provides persistent storage of objects for an object-oriented application.

55. The apparatus of claim 51 in which the data is stored in a relational database with object-oriented extensions.