Method and means for generation of realistic access patterns in storage subsystem benchmarking and other tests

Claim 5

The method according to claim 2, wherein each region includes 2 N tracks, and further wherein each track L in the region is binarily addressable in the relative address range 0≦L≦2 N -1, and still further wherein the implicit address tree forms a binary address tree.

Claim 6

The method according to claim 2, wherein the step (c) of assigning the next address as a random walk function includes the step of: (c1) traversing at least a first node subtended by the immediate predecessor address and performing a Bernoulli experiment having one of two possible outcomes, and (c1a) in the event of the first outcome, traversing yet another superior node and performing the Bernoulli experiment, said node-to-node traverse being repeatable until a second outcome occurs, a predetermined number of nodes have been traversed, or the root node encountered; and (c1b) in the event of the second outcome, randomly selecting an address from the address subset of leaf nodes subtending the node at which the Bernoulli experiment was performed.

Claim 7

The method according to claim 4, wherein the step (c1) of performing the Bernoulli experiment further includes the steps of: (c1a1) generating a random number lying within a predetermined range from a random number generator selected from the set consisting of a pseudo-random number generator and a quasi-random number generator; and (c1a2) comparing said generated number with that cf a threshold also lying with said predetermined range, said first outcome occurring in the event that comparison indicates that the generated number exceeds the threshold, said second outcome occurring in the event that comparison indicates that the generated number was equal to or less than the threshold.

Claim 8

The method according to claim 2, wherein the step (b) of assigning an arbitrary starting address includes the step of randomly selecting the starting address from among the track address in the region associated with the requesting process, and wherein the step (c) of assigning the next address as a random walk function includes the steps of assigning the next track address as a randomized function of the immediately preceding track address.

Claim 9

The method according to claim 2, wherein said steps further comprise writing at least one unit of data to each track in the assigned region and randomly selecting one unit of data from those stored on the track.

Claim 12

The method according to claim 8, wherein each region includes 2 N tracks and each track L in the region is binarily addressable in the relative address range 0≦L≦2 N -1.

Claim 13

The method according to claim 8, wherein the step (c1) of performing the Bernoulli experiment further includes the steps of: (c1a1) generating a random number lying within a predetermined range according to a protocol selected from the set consisting of pseudo-random number protocol and a quasi-random number protocol; and (c1a2) comparing said generated number with that of a threshold also lying within said predetermined range, said first outcome being that the generated number exceeds the threshold, said second outcome being that the generated number was equal to or less than the threshold.

Claim 14

A test generator for emulating realistic access requests used in static or dynamic performance testing of a disk-based storage subsystem, said access requests being expressed in the form of disk and track commands and addresses to units of data stored or to be written onto disk and track locations in the subsystem, said subsystem being shared among a plurality of concurrently executing processes, comprising: a source of pseudo-random number indicia; a processor for executing a plurality of tasks concurrently, each task generating one or more read or write requests for units of data; a first logic circuit coupling said processor for associating a region of disk storage of a predetermined number of contiguous addressable tracks to each executing process, each region implicitly defining an ordered set, each region further constituting an implicit address tree in which the leaves are the track addresses; an address register; a second logic circuit coupling said address register, said first logic circuit, and said processor and responsive to a first access request from each accessing process for assigning an arbitrary starting address among the track addresses in ihe region associated with accessing process and writing said starting address into the register; and a third logic circuit coupling said address register, the pseudo-random number source, the processor, and the first and second logic circuits and responsive to each access request from each process for assigning the next address to the access request from the process as a random walk function on the tree over a traverse from an immediate predecessor address or node to an intermediate or root node and as a random selection of an address from the address subset of leaf nodes subtending the intermediate or root node, said random walk function includes performing a Bernoulli experiment, the mutually exclusive outcomes of said experiment being either (a) traversal of the tree by a predetermined number of nodes and then repeating the Bernoulli experiment, or (b) randomly selecting an address from the set subtending the immediate node.

Claim 15

A test generator for emulating realistic access requests used in static or dynamic performance testing of a disk-based storage subsystem, said access requests being expressed in the form of disk and track commands and addresses to units of data stored or to be written onto disk and track locations in the subsystem, said subsystem being shared among a plurality of concurrently executing processes, comprising: a source of pseudo-random number indicia; a processor for executing a plurality of tasks concurrently, each task generating one or more read or write requests for units of data; a first logic circuit coupling said processor for associating a region of disk storage of a predetermined number of contiguous addressable tracks to each executing process, each region implicitly defining an ordered set, each region further constituting an implicit address tree in which the leaves are the track addresses; an address register; a second logic circuit coupling said address register, said first logic circuit, and said processor and responsive to a first access request from each accessing process for assigning an arbitrary starting address among the track addresses in ihe region associated with accessing process and writing said starting address into the register; and a third logic circuit coupling said address register, the pseudo-random number source, the processor, and the first and second logic circuits and responsive to each access request from each process for assigning the next address to the access request from the process as a random walk function on the tree over a traverse from an immediate predecessor address or node to an intermediate or root node and as a random selection of an address from the address subset of leaf nodes subtending the intermediate or root node, said random walk function includes performing a Bernoulli experiment, the mutually exclusive outcomes of said experiment being either (a) traversal of the tree by a predetermined number of nodes and then repeating the Bernoulli experiment, or (b) randomly selecting an address from the set subtending the immediate node.

Claim 16

A test generator for emulating realistic access requests used in static or dynamic performance testing of a disk-based storage subsystem, said access requests being expressed in the form of disk and track commands and addresses to units of data stored or to be written onto disk and track locations in the subsystem, said subsystem being shared among a plurality of concurrently executing processes, comprising: a source of pseudo-random number indicia; a processor for executing a plurality of tasks concurrently, each task generating one or more read or write requests for units of data; a first logic circuit coupling said processor for associating a nonexclusive region of disk storage of a predetermined number of contiguous addressable tracks to each executing process, each region implicitly defining an ordered set, each region further constituting an implicit address tree in which the leaves are the track addresses; an address register; a second logic circuit coupling said address register, said first logic circuit, and said processor and responsive to a first access request from each accessing process for assigning an arbitrary starting address L among the track addresses in the region associated with accessing process and writing said starting address into the register; and a third logic circuit coupling said address register, the pseudo-random number source, the processor, and the first and second logic circuits and responsive to each access request from each process for assigning the next address to the access request from the process as a random walk function starting from an immediate predecessor address, said third logic circuit including: a first arrangement for traversing a predetermined number of nodes to a target node in the tree in a leaf-to-root node direction; and a second arrangement responsive to the number source for randomly selecting an address from the address subset subtending the target node and for writing said selected address in the register.

Claim 17

A test generator for emulating realistic access requests used in static or dynamic performance testing of a disk-based storage subsystem, said access requests being expressed in the form of disk and track commands and addresses to units of data stored or to be written onto disk and track locations in the subsystem, said subsystem being shared among a plurality of concurrently executing processes, comprising: a source of pseudo-random number indicia; a processor for executing a plurality of tasks concurrently, each task generating one or more read or write requests for units of data; a first logic circuit coupling said processor for associating a nonexclusive region of disk storage of a predetermined number of contiguous addressable tracks to each executing process, each region implicitly defining an ordered set, each region further constituting an implicit address tree in which the leaves are the track addresses; an address register; a second logic circuit coupling said address register, said first logic circuit, and said processor and responsive to a first access request from each accessing process for assigning an arbitrary starting address L among the track addresses in the region associated with accessing process and writing said starting address into the register; and a third logic circuit coupling said address register, the pseudo-random number source, the processor, and the first and second logic circuits and responsive to each access request from each process for assigning the next address to the access request from the process as a random walk function starting from an immediate predecessor address, said third logic circuit including: a first arrangement for traversing a predetermined number of nodes to a target node in the tree in a leaf-to-root node direction; and a second arrangement responsive to the number source for randomly selecting an address from the address subset subtending the target node and for writing said selected address in the register.

Claim 18

The test generator according to claim 12, wherein each region includes 2 N tracks, and further wherein each track L in the region is binarily addressable in the relative address range 0≦L≦2 N -1, and still further wherein the implicit address tree forms a binary address tree.

Claim 19

An article of manufacture comprising a machine-readable memory having stored therein a plurality of processor-executable control program steps for emulating realistic access requests used in static or dynamic performance testing of a disk-based storage subsystem, said access requests being expressed in the form of disk and track commands and addresses to units of data stored or to be written onto disk and track locations in the subsystem, said subsystem being shared among a plurality of concurrently executing processes, said control program steps include: (a) a control program step for associating a region of disk storage of a predetermined number of contiguous binarily addressable tracks to each executing process, each region implicitly defining an ordered set, each region further constituting an implicit binary address tree in which the leaves are the binary track addresses; (b) a control program step for assigning a starting address among the track addresses in the region associated with and responsive to a first access request from each accessing process; and (c) a control program step responsive to each access request from each process completing control program steps (a) and (b), for assigning the next address to the access request from the process as a random walk function on the tree over a traverse from an immediate predecessor address or node to an intermediate or root node and as a random selection of an address from the address subset of leaf nodes subtending the intermediate or root node, said random walk function includes performing a Bernoulli experiment the mutually exclusive outcomes of said experiment being either (a) traversal of the tree by a predetermined number of nodes and then repeating the Bernoulli experiment, or (b) randomly selecting an address from the set subtending the immediate node.

Claim 20

An article of manufacture comprising a machine-readable memory having stored therein a plurality of processor-executable control program steps for emulating realistic access requests used in static or dynamic performance testing of a disk-based storage subsystem, said access requests being expressed in the form of disk and track commands and addresses to units of data stored or to be written onto disk and track locations in the subsystem, said subsystem being shared among a plurality of concurrently executing processes, said control program steps include: (a) a control program step for associating a region of disk storage of a predetermined number of contiguous binarily addressable tracks to each executing process, each region implicitly defining an ordered set, each region further constituting an implicit binary address tree in which the leaves are the binary track addresses; (b) a control program step for assigning a starting address among the track addresses in the region associated with and responsive to a first access request from each accessing process; and (c) a control program step responsive to each access request from each process completing control program steps (a) and (b), for assigning the next address to the access request from the process as a random walk function on the tree over a traverse from an immediate predecessor address or node to an intermediate or root node and as a random selection of an address from the address subset of leaf nodes subtending the intermediate or root node, said random walk function includes performing a Bernoulli experiment the mutually exclusive outcomes of said experiment being either (a) traversal of the tree by a predetermined number of nodes and then repeating the Bernoulli experiment, or (b) randomly selecting an address from the set subtending the immediate node.