Ordered Maps

Arcology Hash Maps

In Arcology, the map functions as a data structure with the properties of an ordered map. The ordered map permits iteration in a deterministic order. The maps also offer enhanced functionalities such as retrieval by index and explicit verification of key presence. Arcology's Hash Maps can be configured as in-memory, block-bound or in-storage, offering greater flexibility.

Issues with Mapping in Solidity

Solidity's mapping is similar to hash maps in other languages, but it has some major differences comparing to them:

  • Direct Iteration: Mappings do not support direct iteration. To iterate over keys or values, you need to maintain an auxiliary data structure, like an array, to store the keys separately.

  • Existence Check: There's no direct method to check if a key exists. You have to infer the existence based on the default value for the value type or maintain a separate boolean mapping.

  • Deletion of Keys: You can delete a key in a mapping using the delete keyword, but it only resets the value to its default state.

  • Storage-Based: Solidity mappings are primarily used for storing data on the blockchain. Each key-value pair is stored in the contract's storage, which is persistent and incurs storage costs.

Supported Data Types

Currently, the following data types are supported by the container:

  • Address / Boolean

  • Address / U256

  • Address / Cumulative U256

  • Hash / Cumulative U256

  • String / U256

  • U256 / U256

Custom Types: You can always derive maps of custom types from the Base contract. Developers can build their own HashMap of custom types using the base container provided by Arcology.

Address U256Cum Example

Address U256Cum is particularly useful because of it allows concurrent write to the same value without breaking the commutative property.

Original Implementation

Consider the following example from the Ethereum developers docs. The VendingMachine contract allows the owner to manage and sell cupcakes. It tracks the contract’s cupcake inventory and individual buyer balances. The owner can refill the inventory, and buyers can purchase cupcakes by sending 1 ETH per cupcake. 

pragma solidity 0.8.7;

contract VendingMachine {

    // Declare state variables of the contract
    address public owner;
    mapping (address => uint) public cupcakeBalances;

    // When 'VendingMachine' contract is deployed:
    // 1. set the deploying address as the owner of the contract
    // 2. set the deployed smart contract's cupcake balance to 100
    constructor() {
        owner = msg.sender;
        cupcakeBalances[address(this)] = 100;
    }

    // Allow the owner to increase the smart contract's cupcake balance
    function refill(uint amount) public {
        require(msg.sender == owner, "Only the owner can refill.");
        cupcakeBalances[address(this)] += amount;
    }

    // Allow anyone to purchase cupcakes
    function purchase(uint amount) public payable {
        require(msg.value >= amount * 1 ether, "You must pay at least 1 ETH per cupcake");
        require(cupcakeBalances[address(this)] >= amount, "Not enough cupcakes in stock to complete this purchase");
        cupcakeBalances[address(this)] -= amount;
        cupcakeBalances[msg.sender] += amount;
    }
}

The refill() function allows the contract owner to increase the cupcake inventory. It checks that the caller is the owner and then adds the specified amount to the contract’s cupcake balance.

The purchase() function allows anyone to buy cupcakes by sending ETH. It verifies that the buyer has sent enough ETH (1 ETH per cupcake) and that the contract has enough cupcakes in stock. If both conditions are met, it deducts the requested amount from the contract’s balance and adds the corresponding amount to the buyer’s balance.

Analysis

Below is a table highlighting potential conflicts when the same or different functions are called simultaneously. We can conclude that since these functions modify the same variable concurrently, transactions calling to refill() and/or purchase() cannot be processed in parallel.

Function Pair
Variable(s) Modified
Conflict Type

refill() / refill()

cupcakeBalances[address(this)]

Two concurrent refills modify the inventory simultaneously

refill() / purchase()

cupcakeBalances[address(this)]

Refill and purchase modify the sender's balance and the inventory.

purchase() / purchase()

cupcakeBalances[address(this)] cupcakeBalances[msg.sender]

Two concurrent purchases modify the sender's balance and the inventory.

How Conflicts Happen

Let's say there are two transactions calling refill(10) and purchase(5). The refill transaction will add 10 cupcakes to the contracts inventory by executing cupcakeBalances[address(this)] += 10, while the purchase transaction is trying to move 5 cakes from contract's inventory to user's account.

1

System tries to run the transactions in full parallel.

2

Transactions read and write the same memory slot; the conflict detector will detect a write-write conflict after execution. One transaction is rolled back.

3

Only the surviving one proceeds.

4

Scheduler will learn the conflict pattern and avoiding putting transactions calling these conflict functions in the same generation in the future.

Parallelized Version

Upon examining the cupcakeBalances mapping, we can immediately see that these variables are never directly modified. Instead, they apply a difference—a delta value—to the original balance, either by adding or subtracting an amount. There is no read involved, meaning the final state isn't needed immediately. This makes it a perfect use case for cumulative variables. In the parallelized version:

  • We replaced the original uint used in cupcakeBalances mapping with a cumulative u256 provided by Arcology's concurrent library.

  • We removed the line cupcakeBalances[address(this)] >= amount. It is unnecessary because U256Cum enforces bounds internally at commit time after each generation. If a sub(amount) causes the value to fall below its lower limit, the transaction will be automatically reverted after execution.

https://github.com/arcology-network/examples/blob/main/eth-examples/contracts/ParallelizedVendingMachine.sol
// SPDX-License-Identifier: GPL-3.0
pragma solidity >=0.7.0;

import "@arcologynetwork/concurrentlib/lib/map/AddressU256Cum.sol";
import "@arcologynetwork/concurrentlib/lib/commutative/U256Cum.sol";

// This example is a parallelized version of the vending machine example from
// https://ethereum.org/developers/docs/smart-contracts/#a-digital-vending-machine
// This version allows multiple purchases and refills to be processed concurrently
// using the Arcology Network's concurrent libraries.
contract VendingMachine {

    // Declare state variables of the contract
    address public owner;
    // mapping (address => U256Cum) public cupcakeBalances;
    // We use an AddressU256CumMap to store cupcake balances instead of a mapping
    // The data structure has the advantage of being able to efficiently handle
    // concurrent updates to the same entry.
    AddressU256CumMap cupcakeBalances = new AddressU256CumMap();

    // U256Cumulative cupcakeStock;

    event BalanceQuery(uint256 value);

    // When 'VendingMachine' contract is deployed:
    // 1. set the deploying address as the owner of the contract
    // 2. set the deployed smart contract's cupcake balance to 100
    constructor() {
        owner = msg.sender;

        // Set the smart contract's cupcake balance to 100, the lower bounds
        // is 0 and the upper bounds is type(uint256).max
        cupcakeBalances.set(address(this), 0, 0, type(uint256).max);
        // cupcakeStock = new U256Cumulative(0, 5000000);
    }

    // Allow the owner to increase the smart contract's cupcake balance
    function refill(uint256 amount) public {
        require(msg.sender == owner, "Only the owner can refill.");
        cupcakeBalances.set(address(this), int256(amount)); 
    }

    // Allow anyone to purchase cupcakes
    function purchase(uint256 amount) public payable {
        require(msg.value >= amount * 1 ether, "You must pay at least 1 ETH per cupcake");
        cupcakeBalances.set(address(this),-int256(amount), 0, type(uint256).max);
        cupcakeBalances.set(msg.sender,int256(amount), 0, type(uint256).max);
    }

    function getCupcakeStock() public returns(uint256){
        emit BalanceQuery(cupcakeBalances.get(address(this)));
        return cupcakeBalances.get(address(this));
    }

    function getCupcakeBalances(address addr) public returns(uint256){
        emit BalanceQuery(cupcakeBalances.get(addr));
        return cupcakeBalances.get(addr);
    }
}

Contention Free Execution

Let's rerun two transactions calling refill(10) and purchase(5). The refill transaction will add 10 cupcakes to the contracts inventory by executing cupcakeBalances[address(this)].add(10), while the purchase transaction is try to move 5 cakes from contract's inventory to user's account.

1

System tries to run the transactions in full parallel.

2

Transactions read and write the same concurrent variable that is commutative and associate. There is no conflict. Both transactions will through.

3

Alice successfully fill the inventory and Bob gets his cakes.

PreviousArraysNextBehind the Scenes

Last updated