Querying the Mapping

A simple design is to store the entire logical-to-physical mapping in main memory. Reads are efficient and simple to implement: for each read operation, we simply use the logical address as an index to query a table to uncover the physical addresses. The price we pay is the cost of the map memory. A map entry in our system consumes four bytes per logical address per replica. The block size of our EW-Array implementation is 4 KB. With a $D_d \times D_m \times D_s$ EW-Array, the amount of map space is $D_m \cdot C / 1000$, where $C$ is the size of the logical disk which, in turn, is typically much smaller than the total amount of physical capacity in a TPC-C run. We have chosen this simple design due to the nature of the transaction processing workload that we are targeting. First, the large number of spindles that are necessary for achieving good performance make the cost of the map memory insignificant. Second, the poor locality of the workload implies that the relatively small amount of memory consumed by the map would have delivered little improvement to read performance had the memory been used as a data cache instead. For a workload that exhibits more locality, we are currently researching the alternative approach of keeping only the most frequently accessed portion of the map in memory and ``paging'' the rest to disk.