Storage Structure Organization

One of the first decisions in designing a server is what persistent storage structures to use. This section discusses how we organized storage structures for the grid example. There are numerous ways to organize storage. The primary decision is where to store the information about each item on the grid. We first discuss the implemented design and then present a couple of alternatives.

 

Implemented Design

We chose a relational database approach to organizing the data. Recall from the introduction that each item has a short string name and a coordinates on the grid. Each item is stored in a record. All item records are stored in a single file. Items can be retrieved using their record ID or by scanning the file.

To improve performance of lookups, we use two indices. To support name lookups, we use a B+-tree index mapping item names to record IDs. To support lookups on location, we use an R*-tree mapping an item's coordinates to its record ID.

All files and indices must be located on a volume. For the grid example, only one volume is used. This volume is located on a device whose name is specified with a configuration option. When the server starts, it must locate the file and indices for the grid, so we store the IDs of the file and indices in the root index of the volume.

This design has three desirable properties:

• Storage requirements are based on the number of items in the grid, not the size of the grid.
• Since each item is stored as a separate record we can take advantage of the fine-granularity (record-level) locking provided by the SSM.
• Adding new indices is easy.

 

Alternative Designs

One alternative design is to store items directly in a B+-tree index, with the item name as the key and coordinates as the data associated with it.

This design has some problems. First, unlike records, entries in a B+-tree index do not have IDs, so the the R*-tree index would then map to names, making spatial lookups awkward. Second, if items are enlarged to hold more data, they may no longer fit within the size limitation (1-page) of index entries. Third, indices do not support updating of individual entries, so changing the location of an item would require removing it from the index and reinserting it.

Another alternative design is to treat the grid as a 2-D array of items and store the entire grid in one large record. This representation would be efficient for densely populated grids, but is wasteful for sparse ones. It would also not support multiple items per location. Worse yet, the granularity of locking would be the entire grid.