This pull request contains the changes from @AdamGleave's Hapi project for review. We should aim to upstream these changes in a reasonably timely manner in order not to uphold some of the upcoming changes to code structure.
Apart from a bunch of fixes and improvements, this pull request contains three major components:
A simulated Quincy cost model that allows us to simulate locality in a distributed file system with the Google trace simulator.
Changes to support the Hapi min-cost flow solvers in Firmament (adding approximate and incremental scheduling support).
Changes to the Google trace simulator to run experiments and measure a variety of metrics when running approximate and incremental flow solvers.
I will aim to go through the commits and tick them off individually, adding comments and deltas as required; I don't think there's an easy way to make this into multiple pull requests, unfortunately.
<img border=0 src='https://avatars.githubusercontent.com/u/192315?v=3' height=16 width=16'> What would the map be keyed by? The machine ID or the resource ID? If we use the machine, there is no benefit over using a vector, since the vector can be subscripted into at O(1) cost. If we use the resource ID, the placement code in GetMachines() will become more complex.
I think I agree that we should change it, but let's quickly discuss the design here.
<img border=0 src='https://avatars.githubusercontent.com/u/433340?v=3' height=16 width=16'> You're right, if we use an unordered_map then the GetMachines code will get quite tricky. We would have to keep two maps one mapping machine_index to resource_id and a reverse one. Overall, this may end up being slower than just using the vector. Definitely, GetMachines will be called more often than RemoveMachine.
Let's keep it as it it.
<img border=0 src='https://avatars.githubusercontent.com/u/433340?v=3' height=16 width=16'> I am a bit surprised that these methods are not implemented. I think we should use them in order to adjust the costs of the preference arcs. We should gather the number of tasks that are running on a machine. We don't want to place N tasks on the same machine if they are all hitting hard the disk.
<img border=0 src='https://avatars.githubusercontent.com/u/192315?v=3' height=16 width=16'> Adam didn't have time to add this functionality, I think. The original Quincy cost model (which we're implementing here) also has no such notion -- if a machine has a capacity for K tasks, it gets K tasks. (So this is faithful to the original model, though not necessarily a good idea.) Leave to later PR?
<img border=0 src='https://avatars.githubusercontent.com/u/192315?v=3' height=16 width=16'> It turns out that the simulated DFS class also uses this type. For now, we have two typedefs in different places for this, but that's clearly not ideal. We'll need to think about a shared header in the future. However the places that use this are in different modules ("sim" and "cost_models"), so there is no trivial solution.
<img border=0 src='https://avatars.githubusercontent.com/u/192315?v=3' height=16 width=16'> We discussed the reasoning behind this (a quick hack to allow direct mapping of tasks to racks, rather than via TECs). I'm not sure if we arrived at a conclusion what a better way of doing this would be? Needs more discussion
<img border=0 src='https://avatars.githubusercontent.com/u/192315?v=3' height=16 width=16'> I'm a little confused: why do we do this? There shouldn't usually be any others open, but there could be (e.g. if a perf file is written or logging is done concurrently). Is this in order to get rid of stale open FDs?
<img border=0 src='https://avatars.githubusercontent.com/u/192315?v=3' height=16 width=16'> In an ideal implementation, the simulated Quincy model would be a wrapper around the real Quincy model that feeds it with simulated data locality information. We should think about re-engineering it that way.
<img border=0 src='https://avatars.githubusercontent.com/u/433340?v=3' height=16 width=16'> Hmm..I think from this method we should just return the equiv_classes to which the resource node is going to be connected. Similarly, from the GetOutgoingEquivClassPrefArcs we should return the ResIDs to which the equiv_class will be connected (i.e., just the forward going arcs).
<img border=0 src='https://avatars.githubusercontent.com/u/433340?v=3' height=16 width=16'> Another way to do this is to have the fields (e.g. new_node, new_arc..) in the dimacs_change.cc. Then we can increment them from any subclass. Moreover, we won't have to do any instanceOf checks.
<img border=0 src='https://avatars.githubusercontent.com/u/192315?v=3' height=16 width=16'> The code uses Spooky::Hash32, which returns a uint32_t, so this is fine. However, looking at the Spooky source code, the uint32_t is obtained by casting a uint64_t, so we may as well move to Hash64 without drop in performance.
<img border=0 src='https://avatars.githubusercontent.com/u/192315?v=3' height=16 width=16'> Agree, though maybe we should make an issue for this and leave it as-is in this PR. Alternatively, re-engineer the code to make stats_file a FILE* everywhere. (Google style guide says that streams should only be used for logging.)
<img border=0 src='https://avatars.githubusercontent.com/u/192315?v=3' height=16 width=16'> I've added a comment, but it's not as you assume: by contrast, each task has its own, single-entity equivalence class. I think Adam did this as a short-cut hack in order to have information in the KB even though the SimulatedQuincyCostModel does not actually have a proper notion of TECs (it would record the stats on a per-rack basis!).
We almost certainly need to do some work here to improve statistics collection. Okay to merge anyway with my changes?
<img border=0 src='https://avatars.githubusercontent.com/u/192315?v=3' height=16 width=16'> This is a little suboptimal, as the ext directory isn't part of our standard include path (and not in the source tree either). Should we just add it to the include path in Makefile.config?
This pull request contains the changes from @AdamGleave's Hapi project for review. We should aim to upstream these changes in a reasonably timely manner in order not to uphold some of the upcoming changes to code structure.
Apart from a bunch of fixes and improvements, this pull request contains three major components:
I will aim to go through the commits and tick them off individually, adding comments and deltas as required; I don't think there's an easy way to make this into multiple pull requests, unfortunately.![](http://www.codereviewhub.com/site/github-bar.png)
misc/utils.cc
, since this is more general functionality that will be useful outside the simulator.ReplayTrace
and refactored it into smaller methods. It's now ~130 lines itself.