Data Structures

The algorithm requires very simple data structures: a sorted queue for storing write groups, a hash-based lookup for checking whether a write group is presented in the sorted queue (that is for hit/miss determination), and a destage pointer for determining the next candidate write group for destage. The fact that insertion in a sorted queue is an $O(\log(n))$ operation does not present a practical problem due to the limited sizes of NVS and the availability of cheap computational power.