Some embodiments set forth probability based caching, whereby a probability value determines in part whether content identified by an incoming request should be cached or not. Some embodiments further set forth probability based eviction, whereby a probability value determines in part whether cached content should be evicted from the cache. Selection of the content for possible eviction can be based on recency and/or frequency of the content being requested. The probability values can be configured manually or automatically. Automatic configuration involves using a function to compute the probability values. In such scenarios, the probability values can be computed as a function of any of fairness, cost, content size, and content type as some examples.