A method for writing data to persistent storage. The method include receiving a first write request including a key and a value, hashing the key to obtain a hashed key, obtaining a hash table depth (d), obtaining d bits from the hashed key, and making a first determination that a hash frag associated with the d bits from the hashed key exists. In response to the first determination, obtaining the hash frag, making a second determination that there is available space to store a hash frag entry in the hash frag, storing the hash frag entry in the hash frag to obtain an updated hash frag, where the hash frag entry includes the hashed key and value information for the value, and storing the updated hash frag in the persistent storage.