IMPLEMENTING ADVANCED CACHING

摘要

Embodiments are disclosed for implementing a priority queue in a storage device, e.g., a solid state drive. At least some of the embodiments can use an in-memory set of blocks to store items until the block is full, and commit the full block to the storage device. Upon storing a full block, a block having a lowest priority can be deleted. An index storing correspondences between items and blocks can be used to update priorities and indicated deleted items. By using the in-memory blocks and index, operations transmitted to the storage device can be reduced.

主权项

1. A method for implementing a priority queue in a storage device, comprising:
dividing the storage device into multiple blocks; identifying, as active blocks, a subset of the multiple blocks, each active block associated with a priority; creating multiple in-memory blocks, each created in-memory block corresponding to one of the active blocks and having the priority of the corresponding active block; receiving an item to be stored in the storage device and a priority for the received item; adding, to an index, an entry corresponding to the received item, the entry including the priority for the received item and an identification of a block at which the received item is to be stored; storing the received item in an in-memory block having a priority closest to the received item; and in an event the in-memory block is full, writing contents of the full in-memory block to the storage device.