A server and/or a client stores a metadata hash map that includes one or more entries associated with keys for data records stored in a cache on a server. Each of the entries stores metadata for a corresponding data record, wherein the metadata comprises a server-side remote pointer that references the corresponding data record stored in the cache, as well as a version identifier for the key. A selected data record is accessed using a provided key by: (1) identifying potentially matching entries in the metadata hash map using the provided key; (2) accessing data records stored in the cache using the server-side remote pointers from the potentially matching entries; and (3) determining whether the accessed data records match the selected data record using the provided key and the version identifiers from the potentially matching entries.