Behind the Scenes
Foundation of All Concurrency Data Structures
Under the hood, all Arcology concurrent containers are derived from a primitive container — essentially an ordered map providing the foundation for concurrency.
Committed & Pending Write Sets
The container allows multiple transactions to add or remove elements in parallel without immediate coordination. During execution, each transaction operates in isolation and records its intended changes—new elements are marked as pending appends, and deletions are marked as pending removals.
The updates are not immediately reflected in the shared container. Instead, they remain in their own state until all transactions in the generation complete. At that point, the system performs conflict detection and resolves any overlapping operations.
After Commit
In the "After Commit" phase, pending appends are deterministically ordered and merged into the container, while valid removals are finalized. At this point, both the pending appended and removal sets are empty. This design ensures that parallel modifications are commutative, conflict-resilient, and merged without rollback, enabling scalable and deterministic state transitions.
Length & Indices
In Arcology’s concurrent execution model, committedLength() is thread-safe because it reflects the number of finalized elements from previous batches. This value is consistent across all parallel transactions, making it safe to use for deterministic, index-based reads.
In contrast, speculative length functions like fullLength() and nonNilCount() depend on the global state aggregated from all transactions. But because the parallel transactions are unning in complete isolation—something each transaction has no visibility into until the generation concludes. While reading the speculative length itself may not cause a conflict (assuming no transaction adds or removes entries), using that length for index-based access isn't thread-safe. Even if every job successfully commits, the relative ordering of newly inserted elements is not determined until the generation is finalized. As a result, index-based access into speculative space assumes a structure that does not yet exist, violating commutativity.
Unless you are certain that you are the only one accessing the container during the current generation, index-based reads using speculative lengths are unsafe and should be avoided. Doing so risks introducing subtle, non-deterministic behavior that can lead to conflicts, rollbacks during parallel execution.
Implementation
In Arcology, all concurrent containers are inherited from an ordered map implementation in the Base contract, where each element is stored as a key-value pair. This structure enables parallel-safe updates, fine-grained conflict detection, and sparse indexing.
Last updated