Story of a File

From flud

This page provides a skeleton outline of the detailed steps taken to backup, verify, and retrieve a file. These skeletons provide a life sketch for the "story of a file" in the flud backup network.

Backing up a File

For each file to be backed up:

  1. Create an encryption key and a storage key for the file, f
    1. The encryption key is the SHA256 hash of the file, H(f) = eK
    2. The storage key is the SHA256 hash of the eK, H(eK) = H(H(f)) = sK
  2. Encrypt the file with eK
  3. Create local filesystem metadata
    1. filename, permissions, creation/modification/change times, ownership, extended attributes, etc.
    2. Encrypt file metadata with public key, Ku
  4. Encrypt file encryption key, eK, with public key, Ku, so that it, too, can be stored with metadata
  5. Erasure code the encrypted file
    1. split the file up into m blocks
    2. add k parity blocks
  6. Create a metadata key mK as the crc32 value of the plaintext filename
    1. (this allows us to align blocks of identical files but different names with their respective metadata blocks)
  7. Erasure code file metadata (same m & k as for file)
  8. Each storage block is composed of the one block of the file data and one block of the filesystem metadata
  9. See if the file has previously been stored (query DHT for sK)
    1. if previously stored, verify blocks.
      1. if all blocks verify correctly, done. Skip the remaining steps.
      2. if some blocks do not verify, replace them.
  10. Store the erasure-coded file
    1. each block is stored by its name, which is the CAS key for the block, H(b)
    2. each block can be stored on any node, choice is up to client (see Fairness)
  11. Create file metadata
    1. list of block names and the nodeIDs of where they are stored
  12. Store file metadata
    1. this is stored in the DHT layer, under sK
  13. Update local master metadata
    1. master metadata is simply a list of filenames to storage keys (sK), with timestamps

Retrieving a Backup File

For each file to retrieve:

  1. Query the DHT with sK (previously saved in master metadata), resulting in file metadata
  2. Retrive blocks described in metadata until reconstruction (erasure decode) is successful
  3. Decrypt file with eK (previously stored in file metadata)
  4. Copy the file to its proper location in the filesystem, restore filesystem metadata

Verifying a Backup File

  1. Create an encryption key and a storage key for the file, f
    1. The encryption key is the SHA256 hash of the file, H(f) = eK
    2. The storage key is the SHA256 hash of the eK, H(eK) = H(H(f)) = sK
  2. Create local file metadata
    1. filename, permissions, creation/modification/change times, ownership, extended attributes, etc.
    2. Encrypt file metadata with public key, Ku
  3. Encrypt the file with eK
  4. Erasure code the encrypted file
    1. split the file up into m blocks
    2. add k parity blocks
  5. Erasure code file metadata (same m & k as for file)
  6. See if the file has previously been stored (query DHT for sK)
    1. if previously stored, verify blocks.
      1. send challenge with random offset and length into each block (for both data and metadata)
        1. responses comes back as H(offset, length bytes) of stored block
  7. if all blocks verify correctly, success.
  8. report failures for blocks that do not verify correctly
  • note that steps 1-5 can be paritally optimized away by creating many challenges and storing them for later use (generate either during the initial store operation, or during a subsequent verify operation)
Personal tools