Computer method and apparatus for asynchronous ordered operations

Claim 2

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.

Claim 3

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.

Claim 4

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.

Claim 5

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

Claim 6

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

Claim 7

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

Claim 8

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

Claim 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.

Claim 10

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.

Claim 11

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.

Claim 12

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.

Claim 13

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

Claim 14

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

Claim 15

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

Claim 16

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.

Claim 17

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.

Claim 18

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.

Claim 19

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.

Claim 20

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

Claim 21

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

Claim 22

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.

Claim 23

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.

Claim 24

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.

Claim 25

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

Claim 26

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.

Claim 27

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

Claim 28

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

Claim 29

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.

Claim 30

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

Claim 33

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.

Claim 34

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.

Claim 35

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

Claim 36

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

Claim 37

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

Claim 38

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

Claim 39

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.

Claim 40

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.

Claim 41

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.

Claim 42

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.

Claim 43

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

Claim 44

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

Claim 45

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

Claim 46

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.

Claim 47

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.

Claim 48

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.

Claim 49

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.

Claim 50

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

Claim 51

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

Claim 52

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.

Claim 53

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.

Claim 54

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.

Claim 55

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

Claim 56

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.