Replace sometime evicts the replaced entry

[EtienneDx]

When replacing an entry, it sometimes get evicted if the new value makes it go over the size limit. I'd expect other entries to be evicted first.