Method and system for storing data items to a storage device

• US 6,275,912 B1
• Filed: 06/30/1998
• Issued: 08/14/2001
• Est. Priority Date: 06/30/1998
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Haba, Erez
• Primary Examiner(s): Bragdon, Reginald G.
• Assistant Examiner(s): ANDERSON, MATTHEW D
• Application Number:
  US09/114,228
• Time in Patent Office: 1,141 Days
• Field of Search: 711/154, 711/158, 370/390, 370/393, 370/394, 370/905, 370/473, 370/412, 370/413, 370/428, 370/429, 709/213-216
• US Class Current: 711/154
• CPC Class Codes: G06F 3/0613 in relation to throughput
• CPC Class Codes: G06F 3/0656 Data buffering arrangements
• CPC Class Codes: G06F 3/0674 Disk device

Abstract

A system and method for efficiently storing data items to a storage device, such as hard disk, uses a data collector and a data writer running in different threads. A data source produces a stream of write requests to write data items to the storage device. The write requests are passed to the data collector, which accumulates, orders, and consolidates the write requests in a data structure. The data writer handles the operation of writing data to the storage device. The ordered and consolidated data items are then given to the data writer, which writes them to the storage device.

Claims

1. In a computer system, a method for storing data generated by a data source to a hardware device by a data writer operating in a separate thread than a data collector, the method comprising the steps of:

the data source generating a plurality of data items to be stored to the hardware device wherein at least a portion of the data items produced are to be stored contiguously on an area of the hardware device and are generated in an order other than one corresponding to the ordering for the contiguous area;

the data collector accumulating and producing an ordered set of data items according to their position to be stored on the hardware device and consolidating at least two data items that are to be written to contiguous portions of the hardware device into a larger data item within the set; and

the data writer acquiring the ordered set of data items from the data collector and storing the set of data items to the hardware device, and wherein the data source and the data collector are in the same execution thread.

2. The method of claim 1, wherein the data items are stored in a memory-mapped file.

3. The method of claim 1, wherein the data collector uses a heap data structure.

4. The method of claim 1, wherein the data items are stored in the same file.

5. The method of claim 1, wherein the data collector sorts the data items.

6. The method of claim 1, wherein the hardware device is a disk.

7. The method of claim 1, wherein an application program includes the data source, a device driver includes the data collector, and an operating system includes the data writer.

8. In a computer system, a method for storing data produced by a data source to a hardware device using a data writer operating in a separate thread than a data collector, the method comprising the steps of:

the data source producing a plurality of data items to be stored on the hardware device wherein at least a portion of the data items produced are to be stored contiguously on an area of the hardware device and are produced in an order other than one corresponding to the ordering for the contiguous area;

the data source producing an additional data item to be stored on the hardware device;

the data collector adding the additional data item to a collector data structure of items or consolidating the item with an another item in the data structure if the additional item and the another item are to be written to contiguous portions of storage space in the hardware device;

the data writer copying the data items from the collector data structure into a writer data structure when the data writer has no previously copied items remaining to be stored to the hardware device; and

the data writer storing the data items in the writer data structure to the hardware device, and wherein the data source and the data collector are in the same execution thread.

9. The method of claim 8, further comprising the step of the data writer causing the collector data structure to be reset after copying the collector data structure.

10. The method of claim 8, wherein the data items are stored in a memory-mapped file.

11. The method of claim 8, wherein the data structure is a heap.

12. The method of claim 8, wherein the data collector sorts the data items.

13. The method of claim 8, wherein an application program includes the data source, a device driver includes the data collector, and an operating system includes the data writer.

14. In a computer system, a method for storing data produced by a data source to a hardware device using a data writer operating in a separate thread than a data collector, the method comprising the steps of:

the data source producing a plurality of data items to be stored on the hardware device wherein at least a portion of the data items produced are to be stored contiguously on an area of the hardware device and are produced in an order other than one corresponding to the ordering for the contiguous area;

the data collector acquiring a first data structure;

the data collector adding one of the data items to the first data structure or consolidating the item with another item in the first data structure if the item and the another item are to be written to contiguous portions of storage space in the hardware device;

the data writer acquiring the first data structure containing one or more items when there are no more data items in a second data structure remaining to be stored to the hardware device;

the data writer storing the one or more items in the first data structure to the hardware device;

the data collector acquiring the second data structure;

the data collector adding a second item to the second data structure or consolidating the second item with a second another item in the second data structure if the second item and the second another item are to be written to contiguous portions of storage space in the hardware device;

the data writer acquiring the second data structure containing one or more second items when the hardware device is available for writing and there are no more items in the first data structure remaining to be stored to the hardware device; and

the data writer storing the one or more second items in the second data structure to the hardware device, and wherein the data source and the data collector are in the same execution thread.

15. The method of claim 14, wherein the data collector and data writer use more than two data structures to communicate data to be stored on the hardware device.

16. The method of claim 14, wherein the file is a memory-mapped file.

17. The method of claim 14, wherein the first and second data structures are heaps.

18. The method of claim 14, wherein the data collector sorts the data items.

19. The method of claim 14, wherein an application program includes the data source, a device driver includes the data collector, and an operating system includes the data writer.

20. In a computer system, a method for storing a plurality of data items received from a data source on a hardware device at discrete locations using a data writer and a data collector operating in separate threads, the method comprising the steps of:

the data collector receiving and adding one of the plurality of data items to a data structure of items;

the data collector or the data writer consolidating one or more of the data items stored in the data structure of items into a new data item;

the data writer acquiring one or more items currently in the data structure when the data writer has no previously acquired items remaining to be stored to the hardware device; and

the data writer storing the one or more items to the hardware device and wherein the data source and the collector are in the same execution thread.

21. The method of claim 20, wherein the data writer acquires the one or more items by copying the data items from the data structure.

22. The method of claim 20, wherein the data writer acquires the one or more items by reading the items from the data structure while the data collector adds newly received items to a second data structure.

23. The method of claim 22, further comprising the step of the data writer acquiring one or more items currently in the second data structure and storing the one or more items to the hardware device when the hardware device is available for writing and the data writer has no previously acquired items remaining to be stored to the hardware device.

24. The method of claim 20, wherein the data items are stored in a memory-mapped file.

25. The method of claim 20, wherein the data structure is a heap, and the one or more items in the data structure are maintained in an order corresponding to the location for storing the items on the hardware device.

26. In a computer system, a method for efficiently flushing portions of a memory-mapped file to a hardware device, the memory-mapped file comprising a portion of memory within the computer system and a portion of a storage area of the hardware device, the method comprising the steps of:

a data collector receiving from a data source a plurality of write requests;

the data collector adding the plurality of write requests to a data structure and consolidating two or more data items in the data structure if the two or more data items are to be written to contiguous portions of storage space in the hardware device;

a data writer acquiring one or more write requests currently in the data structure when the data writer has no previously acquired items remaining to be stored to the hardware device; and

the data writer storing the one or more items to the hardware device, and wherein the data source and the data collector are in the same execution thread.

27. The method of claim 26, wherein the data writer acquires the one or more items by copying the data items from the data structure.

28. The method of claim 26, wherein the data writer acquires the one or more items by reading the items from the data structure while the data collector adds newly received items to a second data structure.

29. The method of claim 28, further comprising the step of the data writer acquiring one or more items currently in the second data structure and storing the one or more items to the hardware device when the hardware device is available for writing and the data writer has no previously acquired items remaining to be stored to the hardware device.

30. The method of claim 26, wherein the data structure is a heap, and the data collector maintains the one or more items in the data structure in an order corresponding to the location for storing the items on the hardware device.

31. The method of claim 26, wherein the data collector sorts the data items.

32. The method of claim 26, wherein the hardware device is a disk.

33. The method of claim 26, wherein the computer system further comprises a network, and wherein the hardware device is connected via the network to the computer containing the portion of memory.

34. The method of claim 26, wherein the computer system further comprises a network, and wherein the memory-mapped file corresponds to at least one queue of a message queuing network.

35. The method of claim 26, wherein the computer system further comprises a network, and wherein each write request includes a memory location and an amount of data to store.

36. In a message queuing computer system, a method for maintaining a plurality of messages within a message queue comprising a memory-mapped file and using a data collector and a data writer operating in separate threads, the memory-mapped file including a portion of memory within the computer system and a portion of a storage area of a hardware device, the method comprising the steps of:

a message queuing server receiving a plurality of messages, storing the plurality of messages within the portion of memory, and generating a plurality of write requests to flush memory locations corresponding to the stored messages;

the data collector receiving the plurality of write requests, each write request including a memory location;

the data collector processing each one of the plurality of write requests and either adding the one write request to a data structure or consolidating the one write request with another write request in the data structure;

the data writer acquiring one or more write requests currently in the data structure when the data writer has no previously acquired write requests remaining to be stored to the hardware device; and

the data writer storing a data value corresponding to the one or more write requests to the hardware device wherein the message queuing server and the data collector are in the same execution thread.

37. The method of claim 36, wherein the plurality of write requests are received by the data collector in an order other than one corresponding to sequential order according to the memory locations of the write requests.

38. The method of claim 36, wherein the data structure is a heap, and the data collector maintains the one or more items in the data structure in an order corresponding to the location for storing the items on the hardware device.

39. The method of claim 36, wherein the data collector sorts the data items.

40. The method of claim 36, wherein the data writer cquires the one or more write requests by copying the data items from the data structure.

41. The method of claim 36, wherein the data writer acquires the one or more items by reading the items from the data structure while the data collector adds newly received items to a second data structure.

42. The method of claim 41, further comprising the step of the data writer acquiring one or more items currently in the second data structure and storing the one or more items to the hardware device when the data writer has no previously acquired items remaining to be stored to the hardware device.

43. The method of claim 36, wherein the data value corresponding to each write request is determined by a memory address and an amount of data to store contained within the write request.

44. The method of claim 36, where the data value corresponding to each write request is contained within the write request.

45. A computer-readable medium having computer-executable instructions for performing steps for storing a plurality of data items received from a data source on a hardware device at discrete locations using a data writer and a data collector operating in separate threads, the steps comprising:

the data collector receiving and adding one of the plurality of data items to a data structure of items;

the data collector or the data writer consolidating one or more of the data items stored in the data structure of items into a new data item;

the data writer acquiring one or more items currently in the data structure when the data writer has no previously acquired items remaining to be stored to the hardware device; and

the data writer storing the one or more items to the hardware device, wherein the data source and the data collector are in the same execution thread.

46. The computer-readable medium of claim 45, wherein the data writer acquires the one or more items by copying the data items from the data structure.

47. The computer-readable medium of claim 45, wherein the data writer acquires the one or more items by reading the items from the data structure while the data collector adds newly received items to a second data structure.

48. The computer-readable medium of claim 47, having further computer-executable instructions for performing the steps of the data writer acquiring one or more items currently in the second data structure and storing the one or more items to the hardware device when the hardware device is available for writing and the data writer has no previously acquired items remaining to be stored to the hardware device.

49. The computer-readable medium of claim 45, wherein the data items are stored in a memory-mapped file.

50. The computer-readable medium of claim 45, wherein the data structure is a heap, and the one or more items in the data structure are maintained in an order corresponding to the location for storing the items on the hardware device.

51. A computer-readable medium having computer-executable instructions for performing steps for efficiently flushing portions of a memory-mapped file to a hardware device, the memory-mapped file comprising a portion of memory within a computer system and a portion of a storage area of the hardware device, the steps comprising:

a data collector receiving from a data source a plurality of write requests;

the data collector adding the plurality of write requests to a data structure and consolidating two or more data items in the data structure if the two or more data items are to be written to contiguous portions of storage space in the hardware device;

a data writer acquiring one or more write requests currently in the data structure when the data writer has no previously acquired items remaining to be stored to the hardware device; and

the data writer storing the one or more items to the hardware device, wherein the data source and the data collector are in the same execution thread.

52. The computer-readable medium of claim 51, wherein the data writer acquires the one or more items by copying the data items from the data structure.

53. The computer-readable medium of claim 51, wherein the data writer acquires the one or more items by reading the items from the data structure while the data collector adds newly received items to a second data structure.

54. The computer-readable medium of claim 53, having further computer-executable instructions for performing the steps of the data writer acquiring one or more items currently in the second data structure and storing the one or more items to the hardware device when the hardware device is available for writing and the data writer has no previously acquired items remaining to be stored to the hardware device.

55. The computer-readable medium of claim 51, wherein the data structure is a heap, and the data collector maintains the one or more items in the data structure in an order corresponding to the location for storing the items on the hardware device.

56. The computer-readable medium of claim 51, wherein the data collector sorts the data items.

57. The computer-readable medium of claim 51, wherein the hardware device is a disk.

58. The computer-readable medium of claim 51, wherein the computer system further comprises a network, and wherein the hardware device is connected via the network to the computer containing the portion of memory.

59. The computer-readable medium of claim 51, wherein the computer system further comprises a network, and wherein the memory-mapped file corresponds to at least one queue of a message queuing network.

60. The computer-readable medium of claim 51, wherein the computer system further comprises a network, and wherein each write request includes a memory location and an amount of data to store.

61. A computer-readable medium having computer-executable instructions for performing steps for maintaining a plurality of messages within a message queuing computer system in a message queue comprising a memory-mapped file and using a data collector and a data writer operating in separate threads, the memory-mapped file including a portion of memory within the computer system and a portion of the storage area of a hardware device, the steps comprising:

a message queuing server receiving a plurality of messages, storing the plurality of messages within the portion of memory, and generating a plurality of write requests to flush memory locations corresponding to the stored messages;

the data collector receiving the plurality of write requests, each write request including a memory location;

the data collector processing each one of the plurality of write requests and either adding the one write request to a data structure or consolidating the one write request with another write request in the data structure;

the data writer acquiring one or more write requests currently in the data structure when the data writer has no previously acquired write requests remaining to be stored to the hardware device; and

the data writer storing a data value corresponding to the one or more write requests to the hardware device wherein the message queuing server and the data collector are in the same execution thread.

62. The computer-readable medium of claim 61, wherein the plurality of write requests are received by the data collector in an order other than one corresponding to sequential order according to the memory locations of the write requests.

63. The computer-readable medium of claim 61, wherein the data structure is a heap, and the data collector maintains the one or more items in the data structure in an order corresponding to the location for storing the items on the hardware device.

64. The computer-readable medium of claim 61, wherein the data collector sorts the data items.

65. The computer-readable medium of claim 61, wherein the data writer acquires the one or more write requests by copying the data items from the data structure.

66. The computer-readable medium of claim 61, wherein the data writer acquires the one or more items by reading the items from the data structure while the data collector adds newly received items to a second data structure.

67. The computer-readable medium of claim 66, having further computer-executable instructions for performing the steps of the data writer acquiring one or more items currently in the second data structure and storing the one or more items to the hardware device when the data writer has no previously acquired items remaining to be stored to the hardware device.

68. The computer-readable medium of claim 61, wherein the data value corresponding to each write request is determined by a memory address and an amount of data to store contained within the write request.

69. The computer-readable medium of claim 61, where the data value corresponding to each write request is contained within the write request.