Optimizing Disk Accesses Through Speculative Execution

Speculative execution Speculative execution Landon Cox Landon Cox April 13, 2016 April 13, 2016

Making disk accesses tolerable Basic idea Basic idea Remove disk accesses from critical path Transform disk latencies into memory latencies Requires predicting the future Caching Caching Assume future accesses will look like past accesses Process Operating system Get D1 Get D1 D 1 D 1 D 1 D 2 How long does the initial access take? How long does the initial access take? ~10ms ~10ms

Making disk accesses tolerable Basic idea Basic idea Remove disk accesses from critical path Transform disk latencies into memory latencies Requires predicting the future Caching Caching Assume future accesses will look like past accesses Process Operating system Get D1 D 1 D 1 D 1 D 2 How long does the subsequent access take? How long does the subsequent access take? ~10ns (~million ~10ns (~million x x faster) faster)

Making disk accesses tolerable Basic idea Basic idea Remove disk accesses from critical path Transform disk latencies into memory latencies Requires predicting the future Pre Pre- -fetching fetching Guess future accesses based on past accesses Process Operating system Get D1, D2 Get D1 D 1 D 1 D 2 D 1 D 2

Making disk accesses tolerable Basic idea Basic idea Remove disk accesses from critical path Transform disk latencies into memory latencies Requires predicting the future Pre Pre- -fetching fetching Guess future accesses based on past accesses Process Operating system Get D2 D 1 D 2 D 1 D 2 D 1 D 2

Hiding disk latency Caching works when Caching works when The recent past looks like the near future Amortize initial retrieval penalty over many other accesses Pre Pre- -fetching makes sense when it is fetching makes sense when it is Accurate: anticipate accesses before they occur Cheap: pre-fetching must not hinder other activities Metrics for better pre Metrics for better pre- -fetching fetching More accurate accurate predictions Reasonable cost cost to obtain and act on those predictions

Approaches to pre-fetching Usually rely on heuristics Usually rely on heuristics Doesn t require apps to be modified Sequential read-ahead or history-based However, heuristics However, heuristics Can be very bad for many classes of apps E.g., databases and small files May require extra resources to maintain history Or let the programmer issue hints. Positives and negatives? Or let the programmer issue hints. Positives and negatives? Programmer knows best (better accuracy) Must rewrite app, which could involve significant restructuring Source code may not be available

Speculative execution Dynamic self Dynamic self- -analysis Allow app to run into the future on fake data Speculative execution reveals future requests Why is this approach appealing? Why is this approach appealing? Doesn t require apps to be modified Hints not limited to specific access heuristics However However Speculation has to be correct despite fake data Speculation has to be lightweight analysis

Spec. execution approach

Speculative execution Assign each process a speculative thread Assign each process a speculative thread Run speculative thread when original stalls Speculative thread generates I/O hints Hints used by storage system to pre-fetch data In what address space should thread run? In what address space should thread run? Needs access to process state But what shouldn t spec. thread be able to do? But what shouldn t spec. thread be able to do? Modify process state Should have no direct side-effects on original s state

Speculative execution Ways that the spec. thread could cause side Ways that the spec. thread could cause side- -effects Could modify data in address space Could modify data outside address space (e.g., files) Could generate signals (e.g., seg fault) How do would you prevent this? How do would you prevent this? Use software-enforced copy-on-write Instrument loads/stores and point to copy versions But won t instrumentation degrade performance? But won t instrumentation degrade performance? Make a copy of the program text Only instrument copy Original program can run un-instrumented effects

Speculative execution When speculation goes off track When speculation goes off track Speculative thread operates on fake data Fake data could affect program control flow Could cause speculative thread to execute differently than orig. Is there any way to prevent this? Is there any way to prevent this? Not really If we knew content of real data would return it Have to detect off track speculation instead How should we detect off How should we detect off- -track speculation? track speculation? Maintain a log of hints Original thread checks if hints are correct If they differ, then speculation has gone off track

Speculative execution When speculative execution is effective When speculative execution is effective Speculative thread can overlap with slow operation Speculative thread is much faster than slow operation Speculation rarely goes off track i.e., fake data must not meaningfully affect control flow i.e., result of slow operation is often known in advance Other slow operations besides disk reads? Other slow operations besides disk reads? Distributed consistency protocols (two-phase commit) Synchronous meta-data writes Lots of interesting uses for speculative execution

Speculative execution Why are multi Why are multi- -threaded apps hard? threaded apps hard? Have to ensure that thread interleavings are same On a uni-processor possible most of the time On a multi-core machine much harder Area of active research

Does it work? Hints are really Hints are really useful useful Generating hints is Generating hints is cheap cheap Runtime with spec + hints Runtime with spec + hints Runtime with spec + no hints Runtime with spec + no hints