Computer method and apparatus for asynchronous ordered operations

• US 5,666,532 A
• Filed: 05/02/1996
• Issued: 09/09/1997
• Est. Priority Date: 07/26/1994
• Status: Expired due to Term

• Current Assignee: EMC Corporation (Dell Technologies Inc.)
• Original Assignee: Novell Incorporated (Open Text Corporation)
• Inventors: Doshi, Kshitij Arun, Saks, Jonathan Haim
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Alam, Hosain T.
• Application Number:
  US08/648,304
• Time in Patent Office: 495 Days
• Field of Search: 395/616, 395/618, 395/621, 395/876, 395/878, 395/881, 395/856, 395/859
• US Class Current: 707/613
• CPC Class Codes: G06F 16/10 File systems; File servers
• CPC Class Codes: Y10S 707/959 Network
• CPC Class Codes: Y10S 707/99938 Concurrency, e.g. lock management in shared database
• CPC Class Codes: Y10S 707/99956 File allocation

Abstract

A computer system having data organized in files, having a secondary storage for storing files, having a primary storage, and having one or more types of file subsystems (file system implementations) for controlling transfer of files between primary storage and secondary storage. A subset of writes to secondary storage are performed using a Delayed Ordered Write (DOW) subsystem, which makes it possible for any file system to control the order in which modifications are propagated to disk. The DOW subsystem consists of two parts. The first part is a specification interface, which a file system implementation or any other kernel subsystem can use to indicate sequential ordering between a modification and some other modification of file system structural data. The second part of DOW subsystem is a mechanism that ensures that the disk write operations are indeed performed in accordance with the order store. DOW improves computer system performance by reducing disk traffic as well as the number of context switches that would be generated if synchronous writes were used for ordering.

Claims

1. An ordering subsystem for controlling the order of operations in a computer system, the computer system having a first unit and a second unit for files, having a file management subsystem for controlling operations for files, said file management subsystem specifying operations for files in response to new requests where a sequence of requests for said operations is represented by the requests R1, R2, . . . , Rr and where the requests for said operations in said sequence have order dependencies D1, D2, . . . , Dd where r and d are integers, said order dependencies constraining the order for carrying out said operations, said ordering subsystem including,

an ordering store for storing a plurality of entries, each of said entries containing an operation type identifying one of said operations for files, at least one of said entries at some time also containing a link which links said entry to another of said entries, said link specifying an order for carrying out said operations in said linked entries, said entries and said links defining a partially ordered acyclic graph,

add means for adding entries to the ordering store by processing said new requests to identify one or more common operations CO0, CO1, . . . , COco, each of said common operations identifying an operation requested by one or more of the requests R1, R2, . . . , Rr, where said common operations have common order dependencies CD0, CD1, . . . , CDcd that preserve the order dependencies D1, D2, . . . , Dd between the operations in the requests, and where co and cd are integers,

execution means for executing said one or more common operations CO0, CO1, . . . , COco responsive to the entries in the ordering store, and

delete means for deleting entries from the ordering store.

2. The ordering subsystem of claim 1 wherein said add means includes,

dow_-- create means for providing one or more of said entries as operation entries for identifying common operations, and

dow_-- order means for providing one or more of said entries as order entries for identifying said common order dependencies.

3. The ordering subsystem of claim 2 wherein said delete means includes operation delete means for deleting operation entries from said ordering store and includes order delete means for deleting order entries from said ordering store.

4. The ordering subsystem of claim 3 wherein said delete means includes dow_-- abort means for deleting entries from said ordering store.

5. The ordering subsystem of claim 4 wherein said dow_-- abort means operates asynchronously with respect to said execution means.

6. The ordering subsystem of claim 1 wherein said operations include writes from said first unit to said second unit.

7. The ordering subsystem of claim 1 wherein said operations include function calls.

8. The ordering subsystem of claim 1 wherein said first unit is primary storage and said second unit is secondary storage and wherein said requests are update requests and said operations include writes from said primary storage to said secondary storage.

9. The ordering subsystem of claim 1 wherein said first unit is primary storage and said second unit is secondary storage and wherein said requests are update requests and said operations include writes from said primary storage to said secondary storage and may include function calls.

10. The ordering subsystem of claim 9 wherein a write for one or more of said update requests is delayed so as to be part of one of said common writes.

11. The ordering subsystem of claim 9 wherein said update requests R1, R2, . . . , Rr are presented in time order with R1 before R2, R2 before R3, . . . , R(r-1) before Rr and wherein a write for one or more of said update requests is delayed so as to be part of one of said common writes whereby writes for one or more of said update request are not necessarily in the time order of the update requests R1, R2, . . . , Rr.

12. The ordering subsystem of claim 9 wherein said add means operates asynchronously with respect to said execution means.

13. The ordering subsystem of claim 9 wherein said delete means operates asynchronously with respect to said execution means.

14. The ordering subsystem of claim 1 wherein said system includes a local unit and a remote unit connected by a network.

15. The ordering subsystem of claim 14 wherein said first unit is primary storage in said local unit and said second unit is secondary storage in said local unit, wherein said requests are update requests and said operations include writes from said primary storage to said secondary storage and may include function calls, and wherein said remote unit initiates said requests for writes from said primary storage to said secondary storage over said network.

16. An ordered write subsystem for controlling the order of operations in connection with writes from primary storage to secondary storage in a computer system, the computer system having data organized in files, having primary storage for storing files, having a secondary storage for storing files, having a file management subsystem for controlling transfers of files between primary storage and secondary storage, said file management subsystem specifying operations in connection with writes from primary storage to secondary storage in response to new update requests for said operations, where a sequence of update requests is represented by the update requests R1, R2, . . . , R(r-1), Rr, where the update requests in said sequence have order dependencies D1, D2, . . . , Dd and where r and d are integers, said order dependencies constraining the order for carrying out said operations, said ordered write subsystem including,

an ordering store for storing a plurality of entries, each of said entries containing an operation type identifying one of said operations, at least one of said entries at some time also containing a link which links said entry to another of said entries, said link specifying an order for carrying out said operations in said linked entries, said entries and said links defining a partially ordered acyclic graph,

add means for adding entries to said ordering store by processing said new update requests to identify common operations, said common operations including,

one or more common writes CW1, CW2, . . . , CWcw for a combined operation requested by one or more of the update requests R1, R2, . . . , Rr where cw is an integer less than r, and one or more function calls FC1, FC2, . . . , FCfc where fc is an integer, and wherein said common writes and said function calls have common order dependencies CD1, CD2, . . . , CDcd that preserve the update order dependencies D1, D2, . . . , Dd between the operations, where cd is an integer,

execution means for executing common operations including,

write means responsive to the entries in the ordering store for writing from primary storage to secondary storage with said common writes CW1, CW2, . . . , CWcw constrained by the common-write order dependencies CD1, CD2, . . . , CDcd,

function means for executing said function calls, and

delete means for deleting entries from the ordering store.

17. The ordering subsystem of claim 16 wherein said add means includes,

dow_-- create means for providing one or more of said entries as operation entries for identifying said common operations, and dow_-- order means for providing one or more of said entries as order entries for identifying said common order dependencies.

18. The ordering subsystem of claim 17 wherein said dow_-- create means provides said operation as common-write entries for identifying common writes.

19. The ordering subsystem of claim 17 wherein said dow_-- create means provides said operation entries as function-call entries for identifying function calls.

20. The ordering subsystem of claim 16 wherein said ordering store includes ordered locations with higher-order locations and lower-order locations and for each common-write entry, zero or more higher-order locations for an order entry pointing to zero or more high-order common writes and zero or more lower-order locations for an order entry pointing to zero or more lower-order common writes.

21. The ordering subsystem of claim 16 wherein a write for one or more of said update requests is delayed so as to be part of one of said common writes.

22. The ordering subsystem of claim 16 wherein said update requests R1, R2, . . . , Rr are presented in time order with R1 and before R2, R2 before R3, . . . , R(r-1) before Rr and wherein a write for one or more of said update requests is delayed so as to be part of one of said common writes whereby writes for one or more of said update requests are not in the time order of the update requests R1, R2, . . . , R(r-1), Rr.

23. The ordering subsystem of claim 16 wherein said add means operates asynchronously with respect to said execution means.

24. The ordering subsystem of claim 16 wherein said delete means includes operation delete means for deleting operation entries from said ordering store and includes order delete means for deleting order entries from said ordering store.

25. The ordering subsystem of claim 24 wherein said operation delete means includes dow_-- abort means for deleting entries from said ordering store.

26. The ordering subsystem of claim 25 wherein said dow_-- abort means operates asynchronously with respect to said execution means.

27. The ordering subsystem of claim 16 wherein said primary storage includes a cache and wherein said ordered write subsystem causes said file management subsystem to initiate writes from said cache.

28. The ordering subsystem of claim 26 further including device drivers connected to write from said cache to said secondary storage.

29. A method in a computer system having a first unit and second unit for files, having a file management subsystem for controlling operations for files, said file management subsystem specifying operations for files in response to new requests where a sequence of requests for the operations is represented by the requests R1, R2, . . . , Rr and where the requests for the operations in said sequence have order dependencies D1, D2, . . . , Dd where r and d are integers, said order dependencies constraining the order for carrying out the operations, said computer system including an ordering subsystem for controlling the order of operations including, said method comprising:

storing a plurality of entries in an ordering store, each of said entries containing an operation type identifying one of said operations for files, at least one of said entries at some time also containing a link which links said entry to another of said entries, said link specifying an order for carrying out said operations in said linked entries, said entries and said links defining a partially ordered acyclic graph,

adding entries to the ordering store by processing said new requests to identify one or more common operations CO1, CO2, . . . , COco, each of the common operations identifying an operation requested by one or more of the requests R1, R2, . . . , Rr, where said common operations have common order dependencies CD1, CD2, . . . , CDcd that preserve the order dependencies D1, D2, . . . , Dd between the operations in the requests, and where co and cd are integers, and

executing said one or more common operations CO1, CO2, . . . , COco responsive to the entries in the ordering store.

30. The computer method of claim 29 wherein said adding step includes,

dow_-- create step for providing one or more of said entries as operation entries for identifying common operations, and

dow_-- order step for providing one or more of said entries as order entries for identifying said common order dependencies.

31. The computer method of claim 30 further comprising a delete step which includes an operation delete step for deleting operation entries from said ordering store and includes an order delete step for deleting order entries from said ordering store.

32. The computer method of claim 31 wherein said delete step includes a dow_-- abort step for deleting entries from said ordering store.

33. The computer method of claim 32 wherein said dow_-- abort step operates asynchronously with respect to said execution step.

34. The computer method of claim 29 wherein said operations include writes from said first unit to said second unit.

35. The computer method of claim 29 wherein said operations include function calls.

36. The computer method of claim 29 wherein said first unit is primary storage and said second unit is secondary storage and wherein said requests are update requests and said operations include writes from said primary storage to said secondary storage.

37. The computer method of claim 29 wherein said first unit is primary storage and said second unit is secondary storage and wherein said requests are update requests and said operations include writes from said primary storage to said secondary storage and may include function calls.

38. The computer method of claim 37 wherein a write for one or more of said update requests is delayed so as to be part of one of said common writes.

39. The computer method of claim 37 wherein said update requests R1, R2, . . . , Rr are presented in time order with R1 before R2, R2 before R3, . . . , R(r-1) before Rr and wherein a write for one or more of said update requests is delayed so as to be part of one of said common writes whereby writes for one or more of said update requests are not necessarily in the time order of the update requests R1, R2, . . . , Rr.

40. The computer method of claim 37 wherein said add step operates asynchronously with respect to said execution step.

41. The computer method of claim 37 further comprising a delete step which operates asynchronously with respect to said execution step.

42. The computer method of claim 29 wherein said system includes a local unit and a remote unit connected by a network.

43. The computer method of claim 42 wherein said first unit is primary storage in said local unit and said second unit is secondary storage in said local unit, wherein said requests are update requests and said operations include writes from said primary storage to said secondary storage and may include function calls, wherein said remote unit communicates over said network with said local unit to move data between said first unit and said second unit.

44. A computer method in a computer system having data organized in files, having primary storage for storing files, having a secondary storage for storing files, having a file management subsystem for controlling transfers of files between primary storage and secondary storage, said file management subsystem specifying operations in connection with writes from primary storage to secondary storage in response to new update requests where a sequence of update requests for the operations is represented by the update requests R1, R2, . . . , R(r-1), Rr, where the update requests in said sequence have order dependencies. D1, D2, . . . , Dd and where r and d are integers, the order dependencies constraining the order for carrying out the operations, said computer method including an ordered write subsystem for controlling the order of operations in connection with writes from primary storage to secondary storage, said method including,

storing a plurality of entries in an ordering store, each of said entries containing an operation type identifying one of said operations for files, at least one of said entries at some time also containing a link which links said entry to another of said entries, said link specifying an order for carrying out said operations in said linked entries, said entries and said links defining a partially ordered acyclic graph,

add steps for adding entries to said ordering store by processing said new update requests to identify common operations, said common operations including,

one or more common writes CW1, CW2, . . . , CWcw for a combined operation identifying an operation requested by one or more of the update requests R1, R2, . . . , Rr where cw is an integer less than r, and one or more function calls FC1, FC2, . . . , FCfc where fc is an integer, and where said common writes and said function calls have common order dependencies CD1, CD2, . . . , CDcd that preserve the update order dependencies D1, D2, . . . , Dd between the operations in the requests, where cd is an integer,

executing common operations including,

write steps responsive to the entries in the ordering store for writing from primary storage to secondary storage with said common writes CW1, CW2, . . . , CWcw constrained by the common-write order dependencies CD1, CD2, . . . , CDcd,

function steps for executing said function calls, and

deleting entries from the ordering store.

45. The computer method of claim 44 wherein said add steps include,

dow_-- create steps for providing one or more of said entries as operation entries for identifying said common operations, and

dow_-- order steps for providing one or more of said entries as order entries for identifying said common order dependencies.

46. The computer method of claim 44 wherein said dow_-- create steps provide said operation entries as common-write entries for identifying common writes.

47. The computer method of claim 44 wherein said dow_-- create steps provide said operation entries as function-call entries for identifying function calls.

48. The computer method of claim 44 wherein said ordering store includes ordered locations with higher-order locations and lower-order locations and wherein said ordering store includes for each common-write entry, zero or more higher-order locations for an order entry pointing to zero or more higher-order common writes and zero or more lower-order locations for an order entry pointing to zero or more lower-order common writes.

49. The computer method of claim 44 wherein a write for one or more of said update requests is delayed so as to be part of one of said common writes.

50. The computer method of claim 44 wherein said update requests R1, R2, . . . , Rr are presented in time order with R1, R2 before R3, . . . , R(r-1) before Rr and wherein a write for one or more of said update requests is delayed so as to be part of one of said common writes whereby writes for one or more of said update requests are not in the time order of the update requests R1, R2, . . . , R(r-1), Rr.

51. The computer method of claim 44 wherein said add steps operate asynchronously with respect to said execution steps.

52. The computer method of claim 44 wherein said deleting step includes an operation delete step for deleting operation entries from said ordering store and includes an order delete step for deleting order entries from said ordering store.