Are there well-solved and simple storage patterns for Solidity?

Question

Simple and appropriate data organization can challenge Solidity newcomers. It wants us to organize everything in ways many of us aren’t accustomed to.

Are there well-solved general patterns for routine on-chain data organization?

Answer 1

Here are some simple and useful patterns in increasing order of utility.

Event logs are omitted for brevity. In practice, it's desirable to emit events for every important state change.

Simple List Using Array

Strengths

• Reliably chronological order
• Provides a count
• Random access by Row Number (not Id)

Weaknesses

• No random access by Id
• No assurance of uniqueness
• No check for duplicates
• Uncontrolled growth of the list

Example:

pragma solidity ^0.4.6;

contract simpleList {

  struct EntityStruct {
    address entityAddress;
    uint entityData;
    // more fields
  }

  EntityStruct[] public entityStructs;

  function newEntity(address entityAddress, uint entityData) public returns(uint rowNumber) {
    EntityStruct memory newEntity;
    newEntity.entityAddress = entityAddress;
    newEntity.entityData    = entityData;
    return entityStructs.push(newEntity)-1;
  }

  function getEntityCount() public constant returns(uint entityCount) {
    return entityStructs.length;
  }
}

Mapping with Struct

Strengths

• Random access by unique Id
• Assurance of Id Uniqueness
• Enclose arrays, mappings, structs within each "record"

Weaknesses

• Unable to enumerate the keys
• Unable to count the keys
• Needs a manual check to distinguish a default from an explicitly "all 0" record

Example:

contract mappingWithStruct {

  struct EntityStruct {
    uint entityData;
    bool isEntity;
  }

  mapping (address => EntityStruct) public entityStructs;

  function isEntity(address entityAddress) public constant returns(bool isIndeed) {
    return entityStructs[entityAddress].isEntity;
  }

  function newEntity(address entityAddress, uint entityData) public returns(bool success) {
    if(isEntity(entityAddress)) revert(); 
    entityStructs[entityAddress].entityData = entityData;
    entityStructs[entityAddress].isEntity = true;
    return true;
  }

  function deleteEntity(address entityAddress) public returns(bool success) {
    if(!isEntity(entityAddress)) revert();
    entityStructs[entityAddress].isEntity = false;
    return true;
  }

  function updateEntity(address entityAddress, uint entityData) public returns(bool success) {
    if(!isEntity(entityAddress)) revert();
    entityStructs[entityAddress].entityData = entityData;
    return true;
  }
}

Array of Structs with Unique Ids

Strengths

• Random access by Row number
• Assurance of Id uniqueness
• Enclose arrays, mappings and structs with each "record"

Weaknesses

• No random access by Id
• Uncontrolled growth of the list

Example:

contract arrayWithUniqueIds {

  struct EntityStruct {
    address entityAddress;
    uint entityData;
  }

  EntityStruct[] public entityStructs;
  mapping(address => bool) knownEntity;

  function isEntity(address entityAddress) public constant returns(bool isIndeed) {
    return knownEntity[entityAddress];
  }

  function getEntityCount() public constant returns(uint entityCount) {
    return entityStructs.length;
  }

  function newEntity(address entityAddress, uint entityData) public returns(uint rowNumber) {
    if(isEntity(entityAddress)) revert();
    EntityStruct memory newEntity;
    newEntity.entityAddress = entityAddress;
    newEntity.entityData = entityData;
    knownEntity[entityAddress] = true;
    return entityStructs.push(newEntity) - 1;
  }

  function updateEntity(uint rowNumber, address entityAddress, uint entityData) public returns(bool success) {
    if(!isEntity(entityAddress)) revert();
    if(entityStructs[rowNumber].entityAddress != entityAddress) revert();
    entityStructs[rowNumber].entityData    = entityData;
    return true;
  }
}

Mapped Structs with Index

Strengths

• Random access by unique Id or row number
• Assurance of Id uniqueness
• Enclose arrays, mappings and structs within each "record"
• List maintains order of declaration
• Count the records
• Enumerate the Ids
• "Soft" delete an item by setting a boolean

Weaknesses

• Uncontrolled growth of the list

Example:

contract MappedStructsWithIndex {

  struct EntityStruct {
    uint entityData;
    bool isEntity;
  }

  mapping(address => EntityStruct) public entityStructs;
  address[] public entityList;

  function isEntity(address entityAddress) public constant returns(bool isIndeed) {
      return entityStructs[entityAddress].isEntity;
  }
  
  function getEntityCount() public constant returns(uint entityCount) {
    return entityList.length;
  }

  function newEntity(address entityAddress, uint entityData) public returns(uint rowNumber) {
    if(isEntity(entityAddress)) revert();
    entityStructs[entityAddress].entityData = entityData;
    entityStructs[entityAddress].isEntity = true;
    return entityList.push(entityAddress) - 1;
  }

  function updateEntity(address entityAddress, uint entityData) public returns(bool success) {
    if(!isEntity(entityAddress)) revert();
    entityStructs[entityAddress].entityData    = entityData;
    return true;
  }
}

Mapped Structs with Delete-enabled Index

Strengths

• Random access by unique Id or row number
• Assurance of Id uniqueness
• Enclose arrays, mapping and structs within each "record"
• Count the records
• Enumerate the ids
• Logically control the size of the active list with delete function

Weaknesses

• Marginally increased code complexity
• Marginally higher storage costs
• Key list is inherently unordered

UPDATE, 2019

This pattern is available as a library for Solidity 0.5.1: https://medium.com/@robhitchens/solidity-crud-epilogue-e563e794fde, https://github.com/rob-Hitchens/UnorderedKeySet

Example:

contract mappedWithUnorderedIndexAndDelete {

  struct EntityStruct {
    uint entityData;
    uint listPointer;
  }

  mapping(address => EntityStruct) public entityStructs;
  address[] public entityList;

  function isEntity(address entityAddress) public constant returns(bool isIndeed) {
    if(entityList.length == 0) return false;
    return (entityList[entityStructs[entityAddress].listPointer] == entityAddress);
  }

  function getEntityCount() public constant returns(uint entityCount) {
    return entityList.length;
  }

  function newEntity(address entityAddress, uint entityData) public returns(bool success) {
    if(isEntity(entityAddress)) revert();
    entityStructs[entityAddress].entityData = entityData;
    entityStructs[entityAddress].listPointer = entityList.push(entityAddress) - 1;
    return true;
  }

  function updateEntity(address entityAddress, uint entityData) public returns(bool success) {
    if(!isEntity(entityAddress)) revert();
    entityStructs[entityAddress].entityData = entityData;
    return true;
  }

  function deleteEntity(address entityAddress) public returns(bool success) {
    if(!isEntity(entityAddress)) revert();
    uint rowToDelete = entityStructs[entityAddress].listPointer;
    address keyToMove   = entityList[entityList.length-1];
    entityList[rowToDelete] = keyToMove;
    entityStructs[keyToMove].listPointer = rowToDelete;
    entityList.length--;
    return true;
  }

}

This last one has an explainer here: https://medium.com/@robhitchens/solidity-crud-part-2-ed8d8b4f74ec#.ekc22r5lf

and here: https://bitbucket.org/rhitchens2/soliditycrud/src/83703dcaf4d0c4b0d6adc0377455c4f257aa29a7/docs/?at=master

Folder Tree Example: How can we organize storage of a folder or object tree in Solidity?

Linked List example shows a way to maintain an ordered list using a library. https://github.com/ethereum/dapp-bin/blob/master/library/linkedList.sol 0

Answer 2

Adding to Rob's answer, please use revert() as an alternative of throw.From version 0.4.13 the throw keyword is deprecated and will be phased out in the future. Read here for more information: require, assert and revert in solidity.

So, as an example you should change

if(isEntity(entityAddress)) throw;

to

if(isEntity(entityAddress)) revert();

in above code provided by Rob.

Answer 3

Great answer by Rob Hitchens. Would like to point out to a minor breaking change in the code mentioned. In the newEntity function of the simpleList contract, the author has used return entityStructs.push(newEntity)-1;

Ever since Solidity version 0.6.0, the array.push() function does not return anything. Please refer to the answer here: https://ethereum.stackexchange.com/a/87791/73743. So, the return entityStructs.push(newEntity)-1; part of the code breaks the smart contract.

Answer 4

Thanks Rob for inspiration!

Here is extended version of Mapped Structs with Delete-enabled Index that also support nested mappings, "unstructured" data and ownership

Hope it will help someone