Behavioral monitoring of storage access patterns

A storage control system monitors storage operations directed to storage blocks in a storage device. The storage control system uses arrays of counters to track a number of the storage operations, sizes of the storage operations, types of transitions between the storage operations, and time durations between different types of successive storage operations. The storage blocks are classified into different behavioral groups based on the access pattern history of the individual blocks. The behavioral group classifications are then used by the storage control system to determine when to access the storage blocks from the storage device, when to load the storage blocks into a tiering media, or when to time out the storage blocks from the tiering media.

BACKGROUND

Current data center environments implement bulk storage as a block level service for use by software. The actual access behavior of the block accesses have many different variables that include the number of processes running on the computer, the priority of these messages, and the nature of interaction of user Input/Output (I/O) with the software.

Prefetching is a technique used for improving the performance of disk and memory systems. Nominal prefetching increases performance by keeping copies of accessed data, in the hope that the cached data will be accessed again. The information required for a successful prefetch algorithm includes:

What data to prefetch

The circumstances under which the prefetch occurs

The length of time to keep prefetched data cached (if no access occurs)

If the wrong data is prefetched, no accesses to the data will occur and no performance improvements will be realized. Likewise, if the right data is fetched at the wrong time, it may be replaced (by other caching data) before the access occurs. Incorrectly specifying the “keep time” will have a similar effect.

SUMMARY

A set of data structures track regional behavior of storage blocks. Parameters are obtained by observing and recording the different types of access to the storage blocks. Examples of the types of parameters derived from the storage block monitoring include elapsed time between accesses to particular storage blocks, type of access (read vs. write) to the storage blocks, and size of the accesses to the storage blocks. These parameters are then used in a causal Bayesian network as a reinforcement/punishment protocol to continuously tune the probabilities of the network. For example, the derived storage block parameters can be used to optimize accesses to a storage array.

DETAILED DESCRIPTION

Referring toFIG. 1, a storage control system15is located between a client10and a storage device18. In one example, the client10may be a server, personal computer, Personal Digital Assistant (PDA), or any other wired or wireless computing device that needs to access the data in storage device18. In one embodiment, the storage control system15is a stand-alone appliance, device, or blade, and the storage device18is a stand-alone disk storage array. In this embodiment, the client10, storage control system15, and storage device18are each coupled to each other via wired or wireless Internet connections12.

In another embodiment, the client10may be a processor in a personal computer that accesses one or more storage devices18over an internal or external data bus. The storage control system15in this embodiment could be located in the personal computer or server10, or could also be a stand-alone device coupled to the computer/client10via a computer bus or packet switched network connection.

The storage control system15operates a Behavioral Modeling Analyzer (BMA)16that identifies storage access patterns between the clients10and storage device18. The BMA16can operate in both a monitoring mode and an active mode. During the monitoring mode, read and write operations14from client10to storage device18are recorded. When sufficient information about the storage operations14has been gathered, BMA16switches from the monitoring mode to an active mode. The active mode performs prefetch, look-ahead, time-outs, and other tiering operations according to the heuristics obtained during the monitoring mode.

During the monitoring mode, the read and write storage operations14between the clients10and the storage device18are recorded by the BMA16without reference to the underlying data contained in the read and write operations14. That is, the type of read or write operation and block specification (address) are noted, but the data actually read or written during the storage operation14is ignored.

A last operation type register26A records the previous type of read or write operation14A to a particular storage block24and a last operation time register26B records when the previous storage operation14A happened. A current operation type register26C captures the current type of read or write operation14B to that same storage block24and a current operation time register26D records when the current storage operation identified in register26C happened.

An array of counters20record a number of different storage operation sequences. The operation sequences are read followed by read (RR), read followed by write (RW), write followed by read (WR), and write followed by write (WW). Each storage operation sequence maintains a plurality of counters each associated with a different time span range between a particular one of the storage operation sequences.

In one embodiment, a system of five counters is used for each read/write sequence. A first counter is incremented when a time difference between the first operation14A and the second subsequent operation14B to the same block24is less than a first time unit A. A second counter is incremented if the time difference between operations14A and14B is greater than time unit A but less than a time unit B. A third counter is incremented if the time difference between operations14A and14B directed to a particular block and for a particular storage sequence is greater than time unit B but less than a time unit C. A fourth counter is incremented if the time difference between operations14A and14B for a particular block and particular storage sequence is greater than value C but less than time unit D, and a fifth counter is incremented when the time difference is greater than the time unit D.

The values of time units A, B, C and D are chosen arbitrarily based on experimental knowledge and behavioral models of storage systems. For example, time units A, B, C and D could be in the same or different magnitudes of microseconds, milliseconds, seconds, minutes, hours, or even days.

Each storage block24may be accessed by the one or more clients10as part of an operation14that identifies multiple different contiguous block addresses. Each storage block24also has an associated set of counters22identifying the number of blocks accessed during the operations14. For example, the storage blocks24may each comprise 64 Kbytes. A single read operation14may comprise a read to blocks50through200. The BMA16increments the Rd counters22associated with each of the blocks50-200identified in the read operation. The size of each storage operation14is also recorded by incrementing the Rd counter22associated with 100<s<1000.

In one embodiment, the block range thresholds10,100and1000are chosen based on experimental knowledge. Of course, other gradations could also be used. The corresponding counters22record the four memory access ranges less than 10 blocks, greater than 10 blocks but less than 100 blocks, greater than 100 blocks but less than 1000 blocks and greater than 1000 blocks, respectively, for each read and write operation14.

Table 1.0 summarizes the different counters used by the BMA16.

TABLE 1.0Register NameDescriptionLAST OP. 26APrevious Read or Write OperationLAST OP. TIME 26BTime of Previous Read or Write OperationCURR. OP 26CCurrent Read or Write OperationCURR. OP. TIME 26DTime of Current Read or Write OperationR/R Counters 20 (1 . . . 5)One counter for each of five time bucketsincremented when a read operation to aparticular block is followed by another readR/W Counters 20 (1 . . . 5)One counter for each of five time bucketsincremented when a read operation to aparticular block is followed by a writeW/R Counters 20 (1 . . . 5)One counter for each of five time bucketsincremented when a write operation to aparticular block is followed by a readW/W Counters 20 (1 . . . 5)One counter for each of five time bucketsincremented when a write operation to aparticular block is followed by another writeRead Size Counter 22One counter for each of four block ranges(1 . . . 4)incremented when a particular read operationaccesses a number of blocks within aparticular rangeWrite Size Counter 22One counter for each of four block ranges(1 . . . 4)incremented when a particular writeoperation accesses a number of blocks withina particular range

The counters20and22are used for tracking sequences of storage block operations according to time and size and can be used for creating access profiles for each storage block24. As the number of accesses to the storage device18increase, the BMA16obtains more information regarding the traits of the storage operations14for different storage blocks24. The BMA16uses this information to optimize use of the tiering resources38shown inFIG. 2and, in turn, increase the performance of the overall storage control system15.

Referring toFIG. 2, a local memory38in storage control system15is alternatively referred to as a tiering resource or tiering media. The local memory38can include different types of Flash memory40and/or Dynamic Random Access Memory (DRAM)42, or even disk memory. However, in general all of local memory38has a relatively faster access time than the storage device18.

Based on the statistics recorded in counters20and22, the BMA16may access different storage blocks24from storage device18or temporarily store or time out the storage blocks in local memory38. These statistical based storage operations allow the storage control system15to more efficiently access particular storage blocks24on behalf of the clients10.

Behavioral Modeling Examples

A first example of a storage operation sequence received and recorded by the BMA16includes a first read to blocks1000-1099at time T=10 sec followed by a second read to blocks1000-1099at time T=15 sec.

Example Transaction (Times Relative to Start of Tracking)

The type of transaction is identified as a Read followed by Read=R/R.

A previous state of the counters20associated with a particular storage block26after the first transaction1may be as follows.

CountersBelowAbove202 sec2-4 sec4-6 sec6-8 Sec8 secR/R——20——R/W—————W/R—————W/W—————
A previous state of the counters22for that same particular block26after the first transaction1may be as follows.

After the second transaction2, the BMA16increments the counters20associated with a 5 second time interval between the two sequential read operations for each of blocks1000-1099as follows.

CountersBelowAbove202 sec2-4 sec4-6 sec6-9 Sec8 secR/R——21——R/W—————W/R—————W/W—————
The BMA16also increments the counters22associated with the second 100 block read operation during transaction2for each of blocks1000-1099.

FIG. 3shows behavioral modeling states associated with each of the storage blocks24in storage device18. As described above, in one embodiment, the storage device18is a disk array that has one or more disks partitioned into multiple storage blocks24. The storage operations14initiated by the clients10inFIG. 1may include a starting block address A for a particular block and an ending block address A+i for a particular read or write operation. In this example, all the blocks between block A and block A+i are read.

The BMA16identifies each of the blocks24between block A and block A+i associated with the storage operation14and identifies an operation length52of the storage operation14. For example, if block A is the 100thblock in storage device18and block A+i is the 999thblock in the storage device18, the operation length52for storage operation14is 900.

As also explained above, separate behavioral modeling state information50is kept for each storage block24based on a tracked history of the storage operations14. In the examples provided above, the behavioral modeling state information50includes the last and current operation type counters26A and26C, respectively, and the last and current time counters26B and26D, respectively. The behavioral modeling state information50also includes the information tracked in transition time counters20and the information in the block size counters22.

FIGS. 4A and 4Bshow another example of how the BMA16tracks the behavioral modeling states50for the different blocks24. The transition time counters20and block size counters22inFIG. 4Amay all initially be zeroed out. The transition time counters20and block size counters22inFIG. 4Aare associated with one particular block that is accessed by each of the operations described inFIG. 4B. For example, each block read or write operation inFIG. 4Baccesses the storage block associated with the time counters20and block size counter22inFIG. 4A.

A first operation inFIG. 4Breads 50 blocks at time10. Again one of the 50 blocks read at time10is associated with the transition time counters20and block size counters22inFIG. 4A. Since this is the first operation, there is no change to the transition time counters20. The Rd counter22for Rd 10<s<100 in incremented to 1.

The second operation reads 150 blocks at time40. Again one of the 150 blocks read at time40is associated with the transition time counters20and block size counters22inFIG. 4A. The R/R time counter2010<t<50 is incremented since 30 time units have expired since the last read to this particular block in operation1. The block size Rd counter22for 100<s<1000 is incremented since 150 blocks were read in operation2.

Operation3writes 20 blocks at time200. Again one of the 20 blocks written to at time200is associated with the particular block associated with the time counters20and block size counters22inFIG. 4A. The R/W time counter20for 50<t<200 is incremented since 160 time units have expired since the last read operation to this particular block. The block size Wr counter22for 10<s<100 is incremented since 20 blocks were written in operation3.

Operation4writes 60 blocks at time215. The W/W time counter20for 10<t<50 is incremented since 15 time units have expired since the previous write operation to this particular block in operation3. The block size Wr counter22for 10<s<100 is incremented since 215 blocks were written in operation4.

Operation5reads 300 blocks at time300. The W/R time counter20for 50<t<200 is incremented since 85 time units have expired since the last write to this particular block in operation4. The block size Rd counter22for 100<s<1000 is incremented since 300 blocks were read in operation5.

Operation6reads 5 blocks at time1000. The R/R time counter20for 500<t is incremented since 700 time units have expired since the last read to this particular block in operation5. The block size Rd counter22for s<10 is incremented since 5 blocks were read operation6.

Operation7writes 250 blocks at time1005. The R/W time counter20for t<10 is incremented since 5 time units have expired since the last read operation to this particular block in previous operation6. The block size Wr counter22for 100<s<1000 is incremented since 250 blocks were written in operation7.

Operation8reads 120 blocks at time1010. The W/R time counter20for t<10 is incremented since 5 time units have expired since the last write operation to this particular block in previous operation7. The block size Rd counter22for 100<s<1000 is incremented since 120 blocks were read in operation8.

At the end of the 8 storage operations, the counters20contain the behavioral state of the transition times between sequential accesses to this particular block and counters22contain the behavioral state for the range of block accesses that included this particular storage block.

FIG. 5Bshows one example of how the behavioral state for a particular block identified by counters20and22inFIG. 5Ais used by the BMA16to perform a fast timeout operation. In the current behavioral state for this particular block, the transition time counters20indicate a W/R count of 100 for t<10 and a R/W count of 100 for 200<t<500. The block size counters22indicate a Rd count of 100 for the block range 10<s<100 and a Wr count of 100 for the block range 10<s<100.

In operation100the BMA16starts a process for determining if any blocks in the storage device18should be labeled as members of a fast timeout group. A fast timeout group identifies blocks that can be removed relatively quickly after being loaded into the tiering media38inFIG. 2.

Operation102first determines if a particular block has a majority of W/R transition counters20for t<10. In this example, all of the W/R transitions are less than 10 time units. Therefore the condition in operation102is true. The BMA16in operation104then determines if the particular block has a majority of R/W time counters20in a substantially larger transition time period. In this example, all of the R/W transitions are above 200 time units. Therefore the condition in operation104is also true.

The quick transitions identified for the W/R time counters22in operation102indicate that this particular block after being written to is then quickly read. The long time periods between the R/W transitions in operation104also indicates that this particular block after being read is not accessed again for a relatively long period of time until there is another write to that same block (W/R transition).

There are no sequential R/R transitions for this block. This indicates that after the block is read, it will likely not be read again until a next write operation. There are also no sequential W/W transitions for this block. This indicates that after the block is written, it will likely not be written to again until after a next read operation.

Thus, the block associated with the counters inFIG. 5Ais labeled by the BMA16for fast timeout in operation106. Whenever this block is written to, it may be determined to be a good candidate for temporary storage in the local tiering media38. Alternatively, the block could be placed in a low priority status after residing in the tiering media38for more than 10 time units. The tiering media38is more efficiently utilized since the fast timeout blocks are not stored in the local tiering media38any longer than necessary. This increases availability of the tiering media38for other storage operations.

FIGS. 6B and 6Cshow how a favored read ahead operation can be performed based on the state information contained in counters20and22. A favored read ahead operation determines if other subsequent blocks should be read based on a read to a first particular block.

FIG. 6Ais a diagram showing read operations120performed by one or more of the clients10inFIG. 1. In this example, a succession of back to back read operations (R/R) are performed in less than 10 time units (t<10). The read operations120are for a particular range of blocks R. After a series of 50 read operations to the block range R, there is a relatively long time lapse124(200<t<500) until another series of 50 relatively fast successive back to back read operations122(t<10) are performed for the same block range R.

FIG. 6Bshow the transition time counters20and block size counters22reflecting the state for a particular one of the blocks involved in the read operations shown in6A. The counters20and22are incremented by the BMA16according to the read operations shown inFIG. 6A.FIGS. 4A and 4Bpreviously provided one example of how the BMA16populates the values in the counters20and22.

In this example, the BMA16recorded 98 R/R transitions for t<10 and 1 R/R transition for 200<t<500 in transition time counters20. In addition, the BMA16recorded 100 Rd operations each having a block range of 10<s<100 in block counters22. Note that for 100 read operations there will only be 99 R/R transitions recorded in transition time counters20since there is no read/read transition for the first read operation.

InFIG. 6C, the BMA16begins a process in operation140for identifying different blocks that are members of a favored read ahead group. In operation142the BMA16identifies any blocks having a majority of R/R transitions in the lowest time range t<10. In this example, the counters20for this particular block have 98 R/R transitions where t<10 and only one R/R transition where 200<t<500. Therefore, the read ahead state in operation142is true. Accordingly, the block associated with counters20and22inFIG. 6Bis marked as a read ahead block in operation144.

The BMA16also lists the adjacent blocks that are part of the same read ahead group. For example, the block size 10<s<100 range in counters22may be used to determine the range of the adjacent block read ahead. The lower end range 10, upper end range 100, or half of the upper end range 100 could be used as the range of adjacent blocks that are grouped together as part of the read ahead operation.

In operation146, the BMA identifies a read to one of the blocks labeled for read ahead. The BMA16then triggers a read ahead for a range R of blocks adjacent to the identified block for reading from the storage device18at the same time.

Any variety of timeout schemes, such as the timeout scheme described above, could then be used for determining how long the read ahead blocks are temporarily stored in the tiering media16. In another example, the total number of read operations indicated by registers20(100) could be divided by the number of relatively long R/R transitions in 200<t<500 plus one. The resulting number could then be multiplied by the threshold time period (10) associated with counter t<10. Thus, 100÷(1+1)=50×10=500 time units.

FIGS. 7A-7Cshow how storage blocks can be associated with a same prefetch group.FIG. 7Ashows a table144containing an example set of operations performed by one or more of the clients10inFIG. 1. A first column146in the table144identifies blocks accessed by the clients10and a second column148identifies the last storage operation and the time of the last storage operation directed to the block identified in column146. The information in table144is obtained by the BMA16from the registers26associated with the different blocks as shown above inFIG. 1.

Referring toFIG. 7B, the BMA16in operation150determines if any of the blocks in table144should be members of a same prefetch group. In operation152, the BMA16identifies the last operation time t=10 for block A. Since there are no other blocks B-H that have a last operation time within +/−one time unit of t=10 block A is not marked as part of a prefetch group in operation154.

The BMA16in operation156ofFIG. 7Ccontinues through the table144to determine if any of the other blocks B-H should be listed as part of a same prefetch group. In operation158, the BMA16determines the last read operation for block B happened at t=500. The BMA16determines in operation158that blocks D, F, and H in table144also had storage operations within one time unit of t=500. Of course some time range other from a single time unit could also be used to determine if blocks should be combined in a same prefetch group. The time range could also be dynamically varied according to current operating conditions of the storage control system15.

The BMA16in operation160marks each of the blocks B, D, F, and H as part of the same prefetch group. The next time any of the blocks B, D, F, or H is accessed by one of the clients10, the BMA16will then prefetch all of the blocks from the prefetch group from the storage control system15and load the blocks into the local tiering media38. Other timeout parameters as described above inFIGS. 5 and 6could then be used to determine when the storage blocks in the prefetch group should time out in the local tiering media38.

FIGS. 5-7show examples of how the behavioral modeling states50inFIG. 3are tracked for each of the different blocks24in storage device18and then used to dynamically control what blocks are accessed from storage device18, what blocks are temporarily stored in the local tiering media38, and what blocks are quickly timed out in the tiering media38. Other storage operations can also be based on the behavioral modeling state information50described above and are not limited to the examples provided above.

The system described above can use dedicated processor systems, micro controllers, programmable logic devices, or microprocessors that perform some or all of the operations. Some of the operations described above may be implemented in software and other operations may be implemented in hardware.

Having described and illustrated the principles of the invention in a preferred embodiment thereof, it should be apparent that the invention may be modified in arrangement and detail without departing from such principles. We/I claim all modifications and variation coming within the spirit and scope of the following claims.