According to one embodiment, a storage device includes a storage and a controller. The storage stores a first table and a second table. The first table includes a set of a key and a value. The second table includes a set of the key and a member set that is a group of members requesting the value to be stored in the first table in association with the key. When receiving a delete command that requests the value associated with the key to be deleted in the first table, the controller deletes the member issuing the delete command in the member set stored in the second table, and deletes an entry corresponding to the key in the first table and an entry corresponding to the key in the second table when number of members in the member set becomes zero.