• High availability: a user can tolerate failures of ⅓ full nodes and enjoy almost 100% high availability on read unless all nodes are down without worry about the single-point of failure of metadata servers (such as namenodes in HDFS) of traditional systems;

• High data integrity: a node could fully validate the integrity of any piece of the data written to the DFS. The validation can be very efficient: given the position of the data (filename, offset, len), the cost of validating the data has the same order of the cost of a client read operation.

• Highly trustworthy storage for clients: a writer can check the integrity of the written data and ensure immunity, and any reader could verify such integrity and immunity.

DFS Semantics Supported

Client Operation Semantics

• create(filename): create a file for write operation, return a file object upon success or throw if filename exists or other IO exception.

• open(filename, isReadonly): open a file for read or read/write, return a file object upon success or throw if filename is not found or other IO exception.

• read(file_object, buffer, offset, len): read the data of the file starting from offset and up to len bytes to buffer. Return the number of bytes read or -1 if the EOF is reached.

• append(file_object, buffer): append the data from buffer to the end file. Throw if a concurrent append is detected.

• flush(file_object): flush all cached append data to the network, and wait until the data are visible to all readers. Throw if concurrent append/flush is detected.

• close(file_object): flush if necessary and close the file.

Representation of the File System as a Blockchain Ledger

• a header

• a list of write transactions, where each transaction is

• (Chunks unchanged except the last one) chunk_idx > file_size’ // chunk_size (// is the integer division operator)

• (Last chunk write must be append) if chunk_idx == file_size’ // chunk_size + 1, then chunk_data_0 must contain last_chunk_data’, where last_chunk_data’ is the last chunk of the file before the write transaction.

Components of the BaaDFS Network

• Full node: A node that maintains a replica of the blockchain ledger. For better performance, the node may be implemented as a cluster — a group of servers that act as a single node in the network. The full nodes are connected via a network protocol (P2P or membership managed by a configuration service such as ZooKeeper). Upon observing a new valid block is produced, it will synchronize the block from its peers and append it to the ledger. The nodes may not necessarily trust each other in the network.

• Consensus: We will employ a fast-finality consensus, which may be Paxos/Raft for private/consortium usage or Tendermint for consortium/public usage.

• Finalized block: A finalized block is that a block that reaches finality and will be irreversible by the consensus. This means that if a block is finalized, all the write transactions of the block (and previous blocks) and the resulting file content, i.e., bytes in offset [0, filesize], will be immutable and be consistent among new readers. Furthermore, we denote the finalized block with the highest index and its index as LAST_FINALIZED_BLOCK and LAST_FINALIZED_BLOCK_INDEX, respectively.

• DFSClient: A DFSClient is a client run by a user that performs the interface of aforementioned file operations and translates the operations to blockchain operations. It will connect to one or multiple full nodes in the network.

Example Implementations of Supported Operations

• QUERY_FINALIZED_INFO: Query and return LAST_FINALIZED_BLOCK or LAST_FINALIZED_BLOCK_INDEX;

• QUERY_METADATA: Given a filename and a block index/hash, return the metadata of the filename of the block;

• QUERY_CHUNK_INFO: Given a chunk_info_trie_hash and chunk_index, return a chunk_info;

• QUERY_CHUNK_DATA: Given a chunk_info, return a chunk data;

• SUBMIT_TX_AND_WAIT: Given a transaction (tx), return success if the tx is included by a block before or equal to FINALZED_BLOCK, otherwise error.

• open(filename, isReadonly): The DFSClient will look up the metadata of file in the LAST_FINALIZED_BLOCK from the network, store the metadata in a file_object, and return the file_object.

• read(file_object, buf, offset, len): The DFSClient will look up the chunk_info’s associated with the chunk_info_trie_hash from the cached metadata and the read range of the file. For each chunk_info, DFSClient will read the corresponding chunk data, write the data to the user-provided buffer, and return to the user.

• write(file_object, buf): An optimized DFSClient will likely cache all contents from a write operation in the internal buffer and return immediately. After collecting several full chunks, the DFSClient will issue an actual write tx. This will reduce the number of writing tx on the last chunk with size < chunk_size, which requires read-modify-write and could be expensive.

• flush(file_object): This will forcibly issue write transactions and synchronously wait until the transaction is finalized (i.e., included by a finalized block).

• close(file_object): The operation will call flush(file_object) and destroy the file_object.

Advantages over HDFS/GFS

High availability

• The network can continuously perform writing even f full nodes have byzantine failures;

• For consistent read, as long as the DFSClient reads the metadata of the file in the LAST_FINALIZED_BLOCK from the network and read the content of the file from a full node with LAST_FINALIZED_BLOCK, the network will continue serving reading. Suppose a reader needs to read at least f + 1 full nodes to determine LAST_FINALIZED_BLOCK, read operation can tolerate 2f byzantine failures;

• If the consistency of read can be relaxed, the DFSClient may just read the metadata of the file in the last FINALIZED_BLOCK from any node and read the content of the file from the same full node, the network will continue serving reading until all full nodes are down.

High data integrity

1. Read the metadata of the file from the state_trie_hash of LAST_FINALIZED_BLOCK, and validate all cryptographic proofs that the metadata is indeed in the state_trie.
2. Read the chunk_info’s from the chunk_info_trie_hash in the metadata, and validate all cryptographic proofs that the chunk_info’s are included in the chunk_info_trie.
3. Read the data chunk for each chunk_info, and verify that each data chunk is included in the corresponding blocks.
4. Validate the blocks containing the data chunks are part of the history of the ledger (i.e., previous blocks of LAST_FINALIZED_BLOCK)

Highly trustworthy storage for clients

Scalability

Scalability on Storage

Scalability on Read

Scalability on Write

• (Transaction Submit Optimization). Instead of submitting the write transactions to the full node, a full node can instruct a DFSClient with a server in the cluster that receives the write transactions.

• (Transaction Broadcast Optimization). Conventional public blockchain network using Gossip protocol to broadcast transactions, which create extra traffic and is inefficiency. For a private/consortium blockchain, we could implement a pipeline protocol between the full nodes, where each full node assigns a server in its cluster to receive a write transaction and forwards the write transaction to another server in the next cluster in the pipeline similar to HDFS/GFS does.

• (Block Broadcast Optimization). When broadcasting a valid block, a block producer may assume most of the write transactions are already synchronized among full nodes, and thus it will only broadcast a compact version of the block where all transactions are replaced by their hashes in the compacted block. Upon receiving a compacted block, a node will check the existence of the transactions in the cluster, and if a transaction is missing, the node will instruct one of its servers to download the transaction from the peer. As a result, if multiple transactions are missing, downloading the missing transactions can be done in a parallel fashion.

• (Parallel Blockchains). Multi-chain/Sharding technology can be employed to increase the throughput and storage capacity (such as Boson Consensus). One extreme case is that each file is represented by a chain and a root chain only collects the hashes of the updated tips of the sub-chains for newly changed files.

Further Enhancements

• Mutual exclusion between writers upon open: When opening a file for write or create operation, the operation will be prohibited if the file has already been open for write by another writer.

• Deletion: Support delete(file_object). This operation prevents the file from opening, but the content of the file may still be accessible in the blockchain ledger.

• Access control: The network can define the access (read/write) rights of each file.

• Directory: Directory objects can be implemented in addition to file objects.

• Multiple writers: We may allow multiple writers that append to a file concurrently. If multiple appends are called by multiple writers, we only ensure that the append is atomic (i.e., the appended data will not be interleaved by other data) if the data size is smaller than a threshold (e.g., chunk size).

• Write-any semantics: Support write(file_object, buf, offset, len) operation. Note that any write operation with len greater than a threshold may not be atomic if multiple writers write the same part. Similarly, truncate(file_object) operation may also supported.

• Quota management: The system can limit the space used by a user and prevent spamming.

• Garbage collect (GC): Garbage data on blocks may be produced if a), A file is deleted; or b) A write transaction overwrites the last chunk of the previous write transaction, and thus the overwritten last chunk can be discarded. To discard the garbage and reclaim the storage, a GC can be implemented by creating a new block that reclaims the space of the first unGCed block. This will replay the transactions of the first unGCed block (starting from genesis block) by updating the chunk_info trie accordingly without performing actual write. This will also increase the index of the first unGCed, which can be written in a field in the block header.

Further Extensions