I think we should fetch the key from backing store, as you suggested as well. So treating a cache miss and cache fail the same.