Processes and systems described herein are directed to determining efficient sampling rates for metrics generated by various different metric sources of a distributed computing system. In one aspect, processes and systems retrieve the metrics from metric data storage and determine non-constant metrics of the metrics generated by the various metric sources. Processes and systems separately determine an efficient sampling rate for each non-constant metric by constructing a plurality of corresponding reduced metrics, each reduced metric comprising a different subsequence of the corresponding metric. Information loss is computed for each reduced metric. An efficient sampling rate is determined for each metric based on the information losses created by constructing the reduced metrics. The efficient sampling rates are applied to corresponding streams of run-time metric values and may also be used to resample the corresponding metric already stored in metric data storage, reducing storage space for the metrics.