A system and method for creating and managing a space-efficient, durable key-value map is disclosed. A key management engine initializes a key-value map by associating a plurality of keys with a first slot of the slots in the key-value map. A first key-value pair is then assigned to the first slot of the key-value map. The key management engine subsequently receives an indication that the first key is to be invalidated; and responsively reuses the first slot of the key-value map by assigning a second key-value pair to the first slot. The first key is then recycled in response to the first key becoming valid. The first and second key-value pairs include respective first and second values and respective first and second keys of the plurality of keys associated with the first slot. The first key becomes valid when it is no longer referenced by a data buffer.