New creates a new Storage.

WithDatabase wraps s such that any calls made with a nil *Txn will be wrapped in a call to db.Txn.

Spans is the format of the message encoded in the spans column of a the system.protectedts_records table.