Source-linked AI summary
ForkBase: An Efficient Storage Engine for Blockchain and Forkable Applications
Sheng Wang, Tien Tuan Anh Dinh, Qian Lin, Zhongle Xie, Meihui Zhang, Qingchao Cai, Gang Chen, Wanzeng Fu, Beng Chin Ooi, Pingcheng Ruan
TL;DR
Modern applications need versioning, fork semantics, and tamper evidence that existing storage systems do not adequately support. ForkBase integrates these properties into a storage engine and demonstrates its use in three applications. The reported evaluations show improved performance in storage consumption, query efficiency, and coding complexity against state-of-the-art systems.
Problem
Existing storage systems do not adequately support modern applications' needs for data versioning, fork semantics, and tamper evidence.
Source: §1 · p. 1Method
ForkBase integrates versioning, general fork semantics, and tamper evidence into storage, using POS-Tree to organize large objects and identify duplicate chunks.
Source: §1 · p. 2Results
ForkBase improves storage consumption, query efficiency, and coding complexity against state-of-the-art implementations across three applications.
Source: §1 · p. 2, §7 · p. 14Takeaways & Limitations
The three implementations show that ForkBase makes application requirements easier to express and supports fast blockchain provenance tracking without scanning the whole chain.
Source: §7 · p. 13POS-Tree is not designed for objects containing sequences of repeated items; middle insertions can require node re-splitting.
Source: §4.3.3 · p. 7
Abstract
from arXiv · showhide
Existing data storage systems offer a wide range of functionalities to accommodate an equally diverse range of applications. However, new classes of applications have emerged, e.g., blockchain and collaborative analytics, featuring data versioning, fork semantics, tamper-evidence or any combination thereof. They present new opportunities for storage systems to efficiently support such applications by embedding the above requirements into the storage. In this paper, we present ForkBase, a storage engine specifically designed to provide efficient support for blockchain and forkable applications. By integrating the core application properties into the storage, ForkBase not only delivers high performance but also reduces development effort. Data in ForkBase is multi-versioned, and each version uniquely identifies the data content and its history. Two variants of fork semantics are supported in ForkBase to facilitate any collaboration workflows. A novel index structure is introduced to efficiently identify and eliminate duplicate content across data objects. Consequently, ForkBase is not only efficient in performance, but also in space requirement. We demonstrate the performance of ForkBase using three applications: a blockchain platform, a wiki engine and a collaborative analytics application. We conduct extensive experimental evaluation of these applications against respective state-of-the-art system. The results show that ForkBase achieves superior performance while significantly lowering the development cost.
1. INTRODUCTION
Modern applications need versioning, fork semantics, and tamper evidence that existing storage systems do not adequately support. ForkBase integrates these properties in storage and demonstrates benefits across three applications.
1. INTRODUCTION
- Modern applications need data versioning, fork semantics, and tamper evidence, while existing systems may offer only partial support or require application-specific implementations.Those approaches raise development costs and latency; key-value-backed blockchain systems may not scale well or support efficient analytics, while file-based version control does not scale to large datasets or support rich queries.Source: §1 · p. 1
- Integrating these properties into storage reduces application development effort and supports efficient historical queries and storage-layer performance optimizations.The paper also says the unified approach helps applications generalize better by providing features such as historical queries at no extra cost.Source: §1 · p. 1
- ForkBase versions uniquely identify data content and history, while POS-Tree chunks large objects to identify and remove duplicate chunks across objects.POS-Tree combines content-based slicing, Merkle trees, and B+-trees; copy-on-write limits unnecessary copies during forks, and two-layer partitioning distributes data evenly even under skewed workloads.Source: §1 · p. 2
- ForkBase provides general fork semantics and simple APIs, and differs from collaborative dataset systems by additionally supporting tamper evidence and general forks.The paper implements three representative applications and reports that only hundreds of lines of code are required to port major components.Source: §1 · p. 2
- ForkBase improves storage consumption, query efficiency, and coding complexity against state-of-the-art implementations across three applications.The applications are a blockchain platform, a wiki service, and collaborative analytics.Source: §1 · p. 2
2. BACKGROUND AND MOTIVATIONS
The section motivates unified storage support for versioning, fork semantics, and tamper evidence, then outlines how ForkBase combines chunking, version and branch organization, and APIs.
2.1 Data Versioning
- ForkBase applies content-based deduplication at the chunk level, splitting structured data at element boundaries to make updates and deduplication more efficient.Compared with delta-based deduplication, it can eliminate cross-dataset duplicates created by uncoordinated teams; its deduplication is less effective when deltas are much smaller than chunks.Source: §2.1 · pp. 2–3, §2.3 · p. 3
2.2 Fork Semantics
- Fork semantics creates independent branches and resolves conflicting updates; ForkBase natively supports both explicit and implicit forks and provides built-in conflict-resolution operations.On-demand forks suit isolated branches, while on-conflict forks arise from concurrent modifications.Source: §2.2 · p. 3
2.3 Tamper Evidence
- ForkBase targets blockchain analytics as well as tamper evidence, addressing that existing blockchain storage focuses on tamper evidence and does not efficiently support queries over state history.The background notes increasing demand for blockchain analytics and says current systems use key-value storage.Source: §2.3 · p. 3
- ForkBase lets applications verify whether an object's content and history have changed, providing tamper evidence against malicious storage providers.The paper identifies security-conscious applications, including blockchain platforms, as requiring protection against malicious modifications.Source: §2.3 · p. 3
2.4 Design Overview
- ForkBase's stack chunks and deduplicates data, organizes versions and branches for tamper evidence and history tracking, then exposes APIs with fork semantics and structured data types.The view layer can add access control and customized merge functions.Source: §2.4 · p. 3
3. DATA MODEL AND APIS
ForkBase extends a key-value model so each object can be retrieved at its latest value or through its evolution history. Its data model links version history to tamper evidence, supports two fork semantics and merges, and offers types suited to different workloads.
3.1 FObject
- Each key can retrieve its latest value or its history, represented as a DAG of FObjects whose links record derivation relationships.Each FObject has a unique uid.Source: §3.1 · pp. 3–4
3.2 Tamper-Evident Version
- Cryptographic hash links in the bases field connect versions to their predecessors, making the version history tamper-evident.Diff returns differences between FObjects of the same types; LCA returns the least common ancestor of two FObjects with the same key.Source: §3.2 · p. 4
3.3 Fork and Merge
- A branch is modifiable only at its head; historical versions can be changed by forking them into new branches, with no limit on branches per key.ForkBase supports fork on demand and fork on conflict.Source: §3.3 · p. 4
3.3.1 Fork on Demand
- Fork on demand explicitly creates a tagged branch from an existing branch or one of its non-head FObjects.The new branch can then receive updates independently.Source: §3.3.1 · p. 4
3.3.2 Fork on Conflict
- Fork on conflict implicitly creates untagged branches when concurrent Put operations make different changes to the same version.The application can inspect the conflicting heads and decide when and how to resolve them.Source: §3.3.2 · pp. 4–5
3.3.3 Merge
- Tagged branches can merge with another tagged branch or a specific version; untagged branches can be merged as a collection.ForkBase provides type-specific merge functions for built-in types, while applications resolve detected conflicts.Source: §3.3.3 · p. 5
3.4 Data Type
- Primitive types are optimized for fast access and are not deduplicated, while chunkable types use a deduplicated POS-Tree for large, incrementally updated data.Applications can select types such as String versus Blob or Tuple versus List according to expected workloads.Source: §3.4 · p. 5
3.5 Example
- At object and branch granularity, Put accepts either a whole new object or an updated base object, and batched updates retain only the final version.The section illustrates forking and editing a Blob object.Source: §3.5 · p. 5
4. DESIGN AND IMPLEMENTATION
ForkBase can run as embedded storage or as a distributed service. Its cluster architecture separates request routing, branch and object management, and chunk persistence.
4. DESIGN AND IMPLEMENTATION
- ForkBase can be used as embedded storage or run as a distributed service.The embedded configuration instantiates one servlet and one chunk storage.Source: §4 · p. 5, §4.1 · p. 5
4.1 Architecture
- A distributed cluster uses a master, dispatcher, servlets, and chunk storage; each servlet manages a disjoint key-space subset and is co-located with local storage.The master maintains runtime information, while the dispatcher forwards requests to the appropriate servlet.Source: §4.1 · p. 5
4.2 Physical Data Representation
ForkBase stores objects as chunks and uses content-derived identifiers to address them. Its FObject representation distinguishes embedded primitive data from chunkable data structures.
4.2 Physical Data Representation
- A chunk is ForkBase’s basic storage unit, and multiple chunk types correspond to chunkable data types.Source: §4.2.1 · p. 6
4.2.1 Chunk and cid
- A chunk’s cid is computed from its content with a cryptographic hash; ForkBase defaults to SHA-256 and permits faster alternatives such as BLAKE2.Chunks are stored and accessed via cids.Source: §4.2.1 · p. 6
4.2.2 FObject and Data Types
- A FObject’s uid aliases its meta chunk’s cid; primitive data is embedded in that chunk, while chunkable data points to an external POS-Tree.Updates to a chunkable object modify the cid value in the FObject structure.Source: §4.2.2 · p. 6
4.3 Pattern-Oriented-Split Tree
POS-Tree uses content-detected boundaries to support efficient access, version comparison and merging, deduplication, and tamper evidence. Its node-splitting design limits reconstruction work, with a stated caveat for repeated-content objects.
4.3 Pattern-Oriented-Split Tree
- Existing B+-tree variants make sharing and merging versioned trees difficult because insertion order changes their structure; fixed-size nodes instead risk boundary shifts.POS-Tree is designed to provide fast lookup and updates, fast difference-finding and merging, effective deduplication, and tamper evidence.Source: §4.3 · p. 6
4.3.1 Tree Structure
- POS-Tree resembles a B+-tree and Merkle tree: content patterns define chunk boundaries, and Figure 6 depicts its tree structure.Index nodes guide lookups using split keys or element counts; child cids hash node content, so identical objects have the same tree and trees can be compared recursively by cid.Source: §4.3.1 · p. 6, Figure 6 · p. 6, §4.3 · p. 6
4.3.2 Splitting a Leaf Node
- Leaf construction scans object content for rolling-hash patterns and creates chunks at detections, extending boundaries to keep each element in one chunk.The last leaf need not end at a pattern; the construction algorithm also chunks when a maximum length is exceeded.Source: §4.3.2 · p. 7
4.3.3 Splitting an Index Node
- Index nodes use a more efficient pattern function P′ on leaf-node cids, exploiting their randomness instead of the costlier leaf-node rolling hash.The paper reports the rolling hash accounts for 20% of POS-Tree construction cost; detected patterns build index nodes bottom-up to the root.Source: §4.3.3 · p. 7
- Updates reconstruct only affected nodes; preserving the last merged chunk’s boundary avoids involving later chunks, while P′ limits pattern changes within an index entry.Expected node size is configurable through q and r, with a force-chunking constraint when a chunk exceeds α times the average size.Source: §4.3.3 · p. 7
- Repeated-item or repeated-byte content is outside POS-Tree’s design: absent leaf patterns, nodes reach maximum size and middle insertions can trigger boundary-shift overhead.The leaf chunks can still be deduplicated when identical.Source: §4.3.3 · p. 7
4.4 Chunk Storage
Chunk storage persists and serves immutable, content-addressed chunks through a key-value interface, supporting integrity checks, reuse, and replication.
4.4 Chunk Storage
- Chunk storage maps each chunk’s cid to its raw bytes and can verify Get-Chunk and Put-Chunk requests on demand.If a Put-Chunk request contains an existing cid, storage can respond immediately by reusing the stored chunk.Source: §4.4 · p. 7
- Immutable chunks use a log-structured persistence layout, which also supports fast retrieval of consecutively generated POS-Tree chunks.The layout is described as facilitating retrieval of chunks generated consecutively in a POS-Tree.Source: §4.4 · p. 7
- Chunks can be replicated across nodes for durability and fault tolerance, with replicas also able to reduce access latency when placed near frequent users.Replication does not significantly affect deduplication; storage keeps only k copies of any chunk.Source: §4.4 · p. 7
4.5 Branch Management
ForkBase tracks branch heads in per-key branch tables, updating them as objects are created or branches change. Merges use a common ancestor and can return conflicts for application-level resolution.
4.5 Branch Management
- Each data key has a branch table of branch heads, with tagged branches in a name-to-cid map and untagged branches in a set of head cids.The untagged-branch table represents leaf nodes in the object derivation graph.Source: §4.5 · pp. 7–8
4.5.1 Branch Update
- Tagged-branch updates replace the old head, while forking adds an entry; guarded Put operations succeed only when the current head matches the supplied guard uid.Concurrent updates on a tagged branch are serialized by the servlet; untagged heads are updated as new FObjects are created and their base cids removed.Source: §4.5.1 · p. 8
4.5.2 Conflict Resolution
- Merging two branch heads uses a three-way merge with their most recent common ancestor; failures return conflicts for application resolution.Built-in functions handle simple conflicts, and applications may provide customized resolution strategies.Source: §4.5.2 · p. 8
4.6 Cluster Management
ForkBase partitions requests and chunks across cluster components using hashes, while keeping meta chunks local. POS-Tree construction can be redistributed when a servlet is overloaded.
4.6 Cluster Management
- A two-layer hash-based partitioning distributes workloads: request keys route dispatcher requests to servlets, and cids route chunks to chunk storage.Meta chunks remain in their servlet’s local chunk storage.Source: §4.6 · p. 8
- Cryptographic hashes distribute chunks evenly even under skewed workloads, while local meta chunks support primitive-object returns and historical-version tracking.Servlets may cache frequently accessed remote chunks; dispatchers route POS-Tree Get-Chunk requests directly to chunk storage.Source: §4.6 · p. 8
4.6.1 Re-balancing
- When a servlet is overloaded, POS-Tree construction can be assigned to another servlet while the first locks and later updates the target key’s branch table.The first servlet embeds the returned tree cid in the FObject and then unlocks the branch table.Source: §4.6.1 · p. 8
5. FAST DEVELOPMENT OF EFFICIENT APPLICATIONS
ForkBase is used to implement three applications whose requirements include versioning, fork semantics, tamper evidence, and analytics. The section describes how its storage model supports blockchain, wiki, and collaborative dataset workflows.
5. FAST DEVELOPMENT OF EFFICIENT APPLICATIONS
- ForkBase implements a blockchain platform, wiki service, and collaborative analytics application to demonstrate how its storage supports application requirements.The section presents these as examples of reducing development effort while supporting high performance.Source: §5 · p. 8
5.1 Blockchain
- Hyperledger stores ledger state and transactions in blocks linked by cryptographic hash pointers, while smart contracts maintain separate key-value state.Transactions that update states are stored in blocks; commits create new state structures and blocks.Source: §5.1 · p. 8, §5.1.1 · p. 9
5.1.2 Blockchain Analytics
- Blockchain state scans retrieve a state’s history, while block scans retrieve state values at a particular block; Hyperledger’s structures make both queries inefficient.The queries must traverse previous states and compute with state delta; the described alternative adds an in-memory index after parsing blocks.Source: §5.1.2 · p. 9
5.1.3 Hyperledger on ForkBase
- ForkBase represents Hyperledger state with two levels of Map objects, replacing Merkle trees and state delta with versioned objects.The first-level Map maps contract IDs to second-level Maps; those Maps map data keys to Blob versions.Source: §5.1.3 · p. 9
- Using ForkBase reduces Hyperledger history-and-integrity maintenance to 18 lines of code, eliminating 1,918 lines, and supports scans by following object versions.State scans follow Blob base versions; block scans retrieve the relevant Map and its Blob objects.Source: §5.1.3 · p. 9
5.2 Wiki Engine
- Wiki entries map naturally to multi-versioned ForkBase storage, with Blob values, metadata in context, and Get and Put operations on default branches.Cached chunks speed consecutive-version reads, POS-Tree supports efficient diffs, and two-level partitioning helps with hot-entry skew.Source: §5.2 · p. 9
5.3 Collaborative Analytics
- ForkBase supports row- and column-oriented relational dataset layouts, letting applications choose the organization best suited to their queries.Records are Tuples in Maps keyed by primary key; column values are Lists in Maps keyed by column name.Source: §5.3 · p. 10
- ForkBase fetches only relevant dataset chunks, supports efficient version diffs, and deduplicates across datasets to reduce storage overhead.The section contrasts this cross-dataset deduplication with systems that deduplicate within one dataset.Source: §5.3 · p. 10
6. EVALUATION
ForkBase is evaluated against application-specific systems across storage operations and three applications. Results show benefits in query performance, storage use, and selected write or scaling workloads, with trade-offs across operations and layouts.
6. EVALUATION
- ForkBase’s three applications improve performance against their respective state-of-the-art systems across storage consumption and query efficiency, while reducing coding complexity.The evaluation covers blockchain, wiki, and collaborative analytics workloads.Source: §6 · p. 10
6.1 Micro-Benchmark
- ForkBase’s chunkable-type operations incur rolling-hash computation in POS-Tree, the main contributor to Put latency relative to primitive types.The cost breakdown excludes network cost.Source: §6.1 · p. 10, Table 4 · p. 10
- ForkBase scales almost linearly for Put and Get as servlet count rises to 64.The authors attribute this behavior to the absence of communication between servlets.Source: §6.1 · p. 10, Figure 8 · p. 10
6.2.1 Blockchain Operations
- Blockchain reads and writes take under 0.1 ms, while commits take about two orders of magnitude longer; overall transaction throughput shows no difference among the compared systems.ForkBase is slower on reads but faster on writes than the alternatives; ForkBase and RocksDB have similar commit latency and both outperform ForkBase-KV.Source: §6.2.1 · p. 11, Figure 9 · p. 11, Figure 10 · p. 11
6.2.2 Merkle Trees
- ForkBase Map objects scale gracefully for commits, while bucket-tree latency rises with fewer buckets and trie latency exceeds ForkBase’s.The bucket tree’s write amplification increases as updates grow; a fixed bucket count is expected to stop scaling beyond some workload size.Source: §6.2.2 · p. 11, Figure 11 · p. 11
6.2.3 Analytical Queries
- State-scan performance favors ForkBase by up to four orders of magnitude for few keys, but the gap vanishes when all stored keys are scanned.For block scans, the performance difference starts at four orders of magnitude and remains at least two as the scanned block number rises.Source: §6.2.3 · p. 12, Figure 12 · p. 12
6.3.1 Edit and Read Pages
- ForkBase uses 50% less storage than Redis for wiki pages, and overtakes Redis when reading more versions, although Redis writes faster and reads the latest version faster.ForkBase’s cached chunks help reads across version history; two-level partitioning distributes chunks more evenly under skew than one-layer partitioning.Source: §6.3.1 · p. 12, §6.3.2 · p. 12, Figure 13 · p. 12
6.4 Collaborative Analytics
- ForkBase outperforms OrpheusDB by two orders of magnitude on dataset modification and uses less space for new sub-tables; its version-comparison cost is low for small differences but rises for large ones.For aggregation, column-oriented ForkBase is 10× faster than OrpheusDB, while row-oriented ForkBase performs similarly; OrpheusDB supports additional advanced analytics such as joins.Source: §6.4.1 · p. 13, §6.4.2 · p. 13, §6.4.3 · p. 13
7. CONCLUSIONS
ForkBase embeds versioning, fork semantics, and tamper evidence in a unified storage engine. Evaluations of three applications show improved performance, storage use, query efficiency, and coding complexity relative to state-of-the-art systems.
7. CONCLUSIONS
- ForkBase integrates data versioning, fork semantics, and tamper evidence that existing storage systems do not adequately address.The conclusion presents these as common requirements of blockchain and forkable applications.Source: §7 · p. 13
- Implementing three applications on ForkBase demonstrates simpler expression of application requirements and reduced development effort.The conclusion identifies blockchain and collaborative analytics as emerging applications the system may support.Source: §7 · pp. 13–14
- Experimental evaluation reports better performance than state-of-the-art systems in storage consumption, query efficiency, and coding complexity.The applications evaluated are a blockchain platform, wiki, and collaborative analytics application.Source: §7 · p. 14