I guess a funny randomized algorithm is just "if snapshots.size() > capacity delete random snapshot" (depending on complexity of random deletions.) If they're i

I guess a funny randomized algorithm is just "if snapshots.size() > capacity delete random snapshot" (depending on complexity of random deletions.) If they're in a B-tree not bad. Snapshots have a half life so they fall off exponentially. Maybe not hard to get a deterministically good distribution (haven't properly read TFA) but I guess you'd be sad if you didn't do better than the most obvious thing. I guess also an algorithm like "delete the (i mod n)th oldest element once you hit the capacity" also deletes every second element every n iterations, though maybe a bit uneven as it prefers to thin things out in quite local ways.