Page Comparison

...

1. Select a new index host.
2. Case:
   • If there is a replica available, stream the data structure to the new index host.
   • If there is a replica flushed to disk available, stream the disk dump to the new index host.
   • Otherwise, use IndexRecovery Main Log recovery.

Optimization: use smaller k

The chances of having to fall back to IndexRecovery Main Log recovery are larger, but the overhead during normal operation is smaller.

...

1. Select a new index host.
2. Case:
   • If there is a shadow index available in memory or on disk:
     1. Case:
        • If there is a shadow index available in memory, stream the shadow index to the new index host.
        • If there is a shadow index available on disk, stream the disk dump to the new index host.
     2. Begin servicing requests
        • While servicing requests, if the new index host encounters a node in the tree or a hash bucket which is still in shadow form:
          1. Request the search key for each object ID stored in the shadow node/bucket from their masters.

             Bug: Assumes that each object ID will return only one search key. There are space/time trade-offs that solve this. -Diego

          2. Once the search keys have all returned, change the shadow node/bucket into a full node/bucket including the search keys.
        • Fetch nodes/buckets in the background until there are no more shadow nodes/buckets.
   • Otherwise, use IndexRecovery Main Log Recovery.

Optimization: array of new index hosts

• Similar to IndexRecovery Main log optimization.
• Stackable on top of shadow replicas
  • Partition on subtrees or bucket ranges

...