Check out the new USENIX Web site. next up previous
Next: Experimental Set-up Up: WOW : Some design Previous: Variable I/O sizes

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.

Binny Gill 2005-10-17