Current data centers require storage capacities of hundreds of terabytes to petabytes. Time-critical applications such as on-line transaction processing depend on getting adequate performance from the storage subsystem; otherwise, they fail. It is difficult to provide predictable quality of service at this level of complexity, because I/O workloads are extremely variable and device behavior is poorly understood. Ensuring that unrelated but competing workloads do not affect each other?s performance is still more difficult, and equally necessary. We present SLEDS, a distributed controller that provides statistical performance guarantees on a storage system built from commodity components. SLEDS can adaptively handle unpredictableworkload variations so that each client continues to get the performance it needs even in the presence of misbehaving, competing peers. After evaluating SLEDS on a heterogeneous mid-range storage system, we found that it is vastly superior to the raw system in its ability to provide performance guarantees, while only introducing a negligible overhead.