Modeling file system operation streams

• US 7,603,372 B1
• Filed: 10/29/2004
• Issued: 10/13/2009
• Est. Priority Date: 10/29/2004
• Status: Active Grant

• Current Assignee: NetApp, Inc.
• Original Assignee: NetApp, Inc.
• Inventors: Sawyer, Darren, Honicky, Richard E. Jr., Ramany, Swaminathan
• Primary Examiner(s): Alam; Shahid A
• Assistant Examiner(s): NGUYEN, PHONG H
• Application Number:
  US10/976,659
• Time in Patent Office: 1,810 Days
• Field of Search: 703/13, 703/21, 703/22, 707/100, 707/1, 707/10, 707/101, 707/102, 707/104.1, 706/902
• US Class Current: 1/1
• CPC Class Codes: G06F 11/3414 Workload generation, e.g. scripts, playback
• CPC Class Codes: G06F 11/3447 Performance evaluation by modeling
• CPC Class Codes: G06F 11/3476 Data logging G06F11/14, G06F11/2205 take precedence
• CPC Class Codes: Y10S 706/902 Application using ai with detail of the ai system
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

A method and a system for modeling file system operation streams of a computing environment. File system operations of the file system operation streams are workloads produced by the devices of the computing environment. For example, a device of the computing environment produces the workloads, which are requests for information from a storage system of the computing environment. The requests are captured and form traces. The traces are then used as input to a model of the computing environment. The model is iteratively trained by using the traces to learn the dynamic behavior of the computing environment. Specifically, the model is trained to identify sequences of file system operations that are legal. Legal sequences can then be generated in realistic workloads that simulate the workloads produced by the devices of the computing environment to a high degree of probability.

Claims

1. A method in a computing system of modeling a file system operation stream, comprising:

by a processor of the computing system,

receiving file system operations directed to a storage system;

recording the received file system operations to produce a trace of the storage system, wherein the trace includes file system operations that are used as input to a model, the model including states defined by the file system operations, and wherein the model specifies valid state transitions between each state of the model;

training the model to produce a trained model, wherein the training includes inputting the trace into the model and determining probabilities associated with the states of the model; and

subsequent to training the model,

generating a resulting workload from the trained model that is used as input to simulate dynamic behavior of the storage system, wherein the resulting workload represents file system operations; and

simulating the file system operations of the generated workload to enable a performance analysis of the storage system.

2. The method of claim 1, wherein the file system operations are grouped according to an originating device, the originating device being capable of generating the file system operations.

3. The method of claim 1, wherein the model learns from the trace by using a mathematical algorithm that changes the probabilities associated with the states of the model.

4. The method of claim 3, wherein the probabilities associated with the states of the model are probability values that are included in a confusion matrix.

5. The method of claim 4, wherein the probability values cease changing when the change from one probability value to another probability value is a negligible amount.

6. The method of claim 5, wherein the model generates legal sequences of file system operations by using a state transition diagram.

7. A method in a computer system of modeling requests of a computing environment, comprising:

by a processor of the computer system,

receiving file system operations of a file system operation stream;

producing a trace from the file system operation stream, wherein the trace is produced by recording the received file system operations of the file system operation stream;

establishing a model capable of being trained to learn the dynamic behavior of the computing environment, wherein the model includes a plurality of states defined by file system operations, and wherein establishing the model includes defining valid state transitions between each state of the plurality of states;

training the model to learn the dynamic behavior of the computing environment; and

subsequent to establishing the model,

generating a workload from the trained model and randomly generated numbers, wherein the workload is a simulated sequence of file system operations of the trace and the randomly generated numbers are used to select states and state transitions in the model, wherein the states are defined by the file system operations, and wherein the simulated sequence of file system operations is used as input to simulate dynamic behavior of the computing environment; and

simulating the file system operations of the generated workload to analyze the performance of the computing environment.

8. The method of claim 7, wherein the file system operations are grouped according to an originating device, the originating device being capable of generating the file system operations.

9. The method of claim 7, wherein the model learns from the trace by using a mathematical algorithm that changes the probabilities associated with states of the model.

10. The method of claim 9, wherein the probabilities associated with the states of the model are probability values that are included in a confusion matrix.

11. The method of claim 10, wherein the probability values cease changing when the change from one probability value to another probability value is a negligible amount.

12. The method of claim 7, wherein the model generates legal sequences of file system operations by using a state transition diagram.

13. The method of claim 7, wherein establishing the model further comprises:

assigning probability values to initialize the model.

14. The method of claim 13, wherein the probability values are assigned to an initialization vector, a transition matrix, and a confusion matrix.

15. An apparatus for modeling a file system operation stream, comprising:

a first device of a computing environment, the first device including a first processor and a first memory accessible to the first processor, the first device to generate a workload that includes file system operations, wherein the file system operations are captured to produce a trace that includes information specifying the file system operations; and

a second device including a second processor and a second memory accessible to the second processor, the second device coupled to the first device,

wherein the second device includes a model that includes a plurality of states corresponding to file system operations and wherein the model specifies valid state transitions between each state of the plurality of states,

wherein the second device receives the trace from the first device and uses the trace to train the model, the model being capable of learning sequences of the file system operations to enable the generation of a resulting workload that is used as input to simulate dynamic behavior of the computing environment for analyzing performance of the computing environment, and

wherein, subsequent to training the model, the second device generates a workload from the trained model and uses the generated workload to simulate the computing environment.

16. The apparatus of claim 15, wherein the second device includes a modeling engine capable of training the model.

17. The apparatus of claim 16, wherein the modeling engine further includes a serialization operation capable of identifying the first device that generated the workload.

18. The apparatus of claim 16, wherein the model further includes an initialization vector, a transition matrix, and a confusion matrix.

19. The apparatus of claim 15, wherein the sequences of the file system operations are derived from a stateless protocol or a stateful protocol.

20. The apparatus of claim 19, wherein the stateless protocol requires no order among the file system operations.

21. The apparatus of claim 19, wherein the stateful protocol requires an order among the file system operations.

22. A computing system operable in a computing environment, comprising:

a first device of the computing environment, the first device including a first processor and a first memory accessible to the first processor, the first device to generate a workload that includes file system operations, wherein the file system operations are captured to produce a trace that includes information specifying the file system operations;

a second device including a second processor and a second memory accessible to the second processor, the second device coupled to the first device to receive the trace and to use the trace to train a model that includes states defined by the file system operations, the model specifying valid state transitions between the states, the model being capable of learning sequences of the file system operations to enable the generation of a resulting workload that is used as input to simulate dynamic behavior of the computing environment; and

a computing environment management system capable of using the model after training to analyze the computing environment, wherein the computing environment management system analyzes the computing environment by;

generating a workload from the trained model, the generated workload representing file system operations that are used as input to the computing environment management system to simulate the computing environment; and

simulating the file system operations of the generated workload to analyze the performance of the computing environment.

23. A method in a computer system of modeling a file system operation stream, comprising:

by a processor of the computer system,

receiving file system operations directed to a storage system;

recording the received file system operations to produce a trace of the storage system, wherein the trace includes file system operations that are used as input to a model, the model including states defined by the file system operations, wherein the model specifies valid state transitions between each states, and wherein each state has a corresponding probability distribution representing a probability that a particular file system operation will be emitted into the trace in that state;

training the model to produce a trained model, wherein the training includes determining probabilities associated with the states of the model; and

subsequent to training the model,

generating a resulting workload from the trained model that is used as input to simulate dynamic behavior of the storage system, wherein the resulting workload represents file system operations of the file system operation stream; and

simulating the file system operations of the generated workload to enable a performance analysis of the storage system.

24. The method of claim 23, wherein the file system operations are grouped according to an originating device, the originating device being capable of generating the file system operations.

25. The method of claim 23, wherein the model learns from the trace by using a mathematical algorithm that changes the probabilities associated with the states of the model.

26. The method of claim 25, wherein the probabilities associated with the states of the model are probability values that are included in a confusion matrix.

27. The method of claim 26, wherein the probability values cease changing when the change from one probability value to another probability value is a negligible amount.

28. The method of claim 27, wherein the model generates legal sequences of file system operations by using a state transition diagram.

29. A method in a computing system of modeling a file system operation stream, the method comprising:

by a processor of the computing system,

receiving file system operations directed to a network storage server;

recording the received file system operations to produce a trace of the received file system operations;

establishing a model capable of being trained to learn dynamic behavior of the storage system, wherein the model includes a plurality of states defined by file system operations of the network storage server and wherein establishing the model includes specifying valid state transitions between each state of the plurality of states;

training the model to learn the dynamic behavior of the network storage server by inputting the trace of the received file system operations into the model and determining probabilities associated with each state of the model;

subsequent to training the model,

generating a workload from the trained model, wherein the generated workload represents file system operations that are used as input for simulation of the network storage server; and

simulating the file system operations of the generated workload on the network storage server to enable a performance analysis of the network storage server.