Thoughts on SafeStore: A Durable and Practical Storage System

Authors: Ramakrishna Kotla, Lorenzo Alvisi, and Mike Dahlin (UT Austin)
Venue: Usenix 2007
Summary:
The author describe a system---SafeStore---that drastically increases the durability of data stored at storage service providers (SSPs). The system relies on the following points:

• Use hierarchical erasure coding within and across multiple SSPs
• SSPs should provide an interface that exposes the redundancy levels they support internally
• Use a heuristic to decide how/where to store data and with what redundancy levels
• Use auditing to ensure data is stored correctly and is available.

Auditing works as follows:

• When data owner stores data, it gets a signed receipt with object ID and hash.
  
• Data owner encodes and stores receipt across SSPs. **Does the receipt need a receipt?
• Routine audit:
  - Auditor sends salt for particular ID
  - SSP returns signed message with [obj ID, time, H(salt||data)]
  - If SSP honest, and finds that data is corrupted, returns error
  - If SSP dishonest, forced to return bogus H(salt||data) and now we have a crypto proof
  
• Spot Check:
  - Auditor verifies some percentage of the responses
  - It does this by retrieving data from owners' cache, SSP, or other SSPs (**Why retrieve whole data? Isn't hash sufficient? i.e. get SSP data, get receipt hash and compare. Several options...)
  - Proof of Misbehavior (POM) can be produced if hash fails.
• Cost:
  "our audit protocol improves durability of our system by two 9’s over a system with no audit at an additional audit cost of just 20%"
• All local state except encryption keys and list of SSPs used are soft-state.

Evaluation:

• Performance vs NFS: 13% worse
• Adding snapshots makes performance ~40% worse
• Over the WAN with large delays, moderate drop in performance: 5%
• SSFS versioning makes replication cheaper with less space overhead.