I'm working on an I/O generator program for a distributed file system. The problem I need to solve can be worded as a set of requirements:

  1. Reproducible (i.e. given some initial condition, the algorithm must produce the exact same file system).
  2. Concurrent (or at least concurrency-friendly). Since file system itself is distributed, the I/O generator needs to work with it from multiple computers. Friendliness in this context means that I'd like to maximize the amount of work done independently by each connected computer, each connection from that computer to the file system and each thread operating on that connection.
  3. Parametrized (i.e. users of the I/O generator should be able to control parameters s.a. how many files are created per directory, how deeply the directories can be nested, similar for symbolic links etc.).
  4. Supervised error generation. When generating I/O for the testing purposes it is also important to generate legitimate errors, s.a. trying to rename a non-existing file, or renaming an existing file into another existing file and so on.
  5. Re-entrant (i.e. the state of the algorithm could be saved and the algorithm could be restarted from a given state).

Now, I am fully aware you aren't going to write a pseudocode answering to all the bullet points above... that'd be crazy if you could. What I'm hoping for is if you could point me to white papers / research / existing solutions. I'd be also thankful if you had partial answers, s.a. how to generate a random directed graph with fanout in a given range. Or, how to generate a tree concurrently. I'm more interested in the "algorithm" part of the question rather than in solving other more technical problems. I listed the technical problems in order to maybe give a general idea of what the algorithm needs to be used for.

  • $\begingroup$ What is an "I/O generator program"? Are you trying to come up with a simulated workload to use for performance testing? If so, the answer will depend on what you want to measure and what real workloads tend to look like. What research have you done? Have you looked at how other papers proposing distributed filesystem implementations have evaluated the performance of their system? Ultimately, this is not really an algorithms question; it's more a question of characterizing typical workloads (which is an empirical question). Many of the concerns you list are just simple programming. $\endgroup$ – D.W. Oct 21 '16 at 17:11
  • $\begingroup$ @D.W. Examples of I/O generator programs: FIO, FSTest, VDBench, SFS2008 and SFS2014 (they usually do more than just generating I/O, but they have to do that too). It is not intended for performance testing, it is intended for correctness testing, however, generating different amounts of traffic is part of correctness testing. There aren't that many papers that I could find... esp. not on distributed filesystem testing. They are usually on filesystem design (I tried reading GFS and Btrfs-related material). $\endgroup$ – wvxvw Oct 22 '16 at 12:18
  • $\begingroup$ (contd). The algorithmic part is in generating and maintaining a distributed presentation of a directed graph, however, sometimes you may ignore some aspects of this problem, like, you may not need it to be re-entrant, or may not need it to be reproducible. Eg. if you rely in your algorithm on reading off the contents of a directory w/o sorting it, you won't get a reproducible procedure. $\endgroup$ – wvxvw Oct 22 '16 at 12:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.