FastAD: An authenticated directory for billions of objects

We develop techniques that make authenticated directories efficient and scalable toward the goal of managing tens of billions of objects in a single directory. Internet storage services have already realized this scale: Amazon's S3 contained more than 52 billion objects as of April 2009 [1]. Our contributions include defining on-disk, block-oriented data structures and algorithms for authenticated directories that exceed memory capacity and optimizations that reduce the I/O required to insert and access entries in the directory.