OneSwap系列七之基本数据结构

以太坊上的每一个智能合约，都可以读写一个专属的KVStore，Key和Val的长度都是256比特。当然也可以换一个角度来理解，把这个KVStore看成一个巨大的数组，其长度是2²⁵⁶，元素必须是长256比特的字节序列。这么大的一个KVStore/数组，其使用当然是有代价的。目前访问一次KVStore（使用SLOAD指令）需要花费800个Gas，初次写入（使用SSTORE指令）则需要花费20000个Gas。如果访问一个从未写入过的Key/索引，则返回0；如果写入0，则相当于删除该Key/索引处的值（如果此处有非0值的话）。为了鼓励智能合约删除无用KV对，节约存储空间，当删除KV对后，系统会返还15000个Gas（但某个交易总的Gas返还不能超过总Gas消耗的一半）。

当我们使用Solidity编写智能合约时，是不需要直接思考SLOAD和SSTORE指令的。Solidity合约可以定义状态变量，这些变量会按照一定的顺序和规则（由编译器搞定）存储在KVStore里。除了简单的值变量（比如地址、布尔、各种类型的int等），Solidity还支持数组和映射（Mapping）。在数组和映射的基础之上，我们还可以构造集合（Set）、链表（List）、栈（Stack）、队列（Queue）等数据结构。本文将讨论Solidity支持的各种存储变量及其实现细节，并结合OneSwap项目介绍各种数据结构的原理和应用。

状态变量的实现原理

我们先来讨论Solidity语言支持的各种状态变量，看看这些变量是如何在存储中占有自己的一席之地的。为此，我们将以一个简单的合约为例，分析其编译后的运行时字节码（关于运行时字节码的介绍，可以参考本系列的第2篇文章）。下面是这个示例合约的完整代码：

pragma solidity =0.6.12;

contract StateDemo {

    address                                         private v1;
    uint64                                          private v2;
    uint256                                         private v3;
    uint256[0x2000]                                 private a1;
    uint256[]                                       private a2;
    mapping(address => uint256)                     private m1;
    mapping(address => mapping(address => uint256)) private m2;

    function setV123() external {
        v1 = address(0xADD0);
        v2 = 0x1234;
        v3 = 0x5678;
    }

    function setA1() external returns (uint256) {
        a1[0x1001] = 0x1234;
        a1[0x1002] = 0x5678;
        return a1.length;
    }
    function setA2() external returns (uint256) {
        a2[0x1001] = 0xABAB;
        a2[0x1002] = 0xCDCD;
        return a2.length;
    }

    function setM1() external {
        m1[address(0xADD1)] = 0x1234;
        m1[address(0xADD2)] = 0x5678;
    }
    function setM2() external {
        m2[address(0xADD3)][address(0xADD4)] = 0x1234;
        m2[address(0xADD5)][address(0xADD6)] = 0x5678;
    }

}

简单变量

如果一个智能合约只使用了值类型的状态变量，且每个状态变量都要占用一个slot（256比特），那么这些状态变量会按定义的顺序存放在KVStore里。也就是说，第N个状态变量在第N个slot里（N从0开始）。如前所述，存储空间的读写是非常消耗Gas的，所以编译器有义务做一些优化，尽可能将多个长度较小的值变量塞进一个slot里。目前Solidity编译器的确会做这项优化，但是并不会为此重新排列这些状态变量。所以为了达到Gas最优化，程序员必须自己仔细排列合约的状态变量。

在上面的示例合约中，前三个状态变量是值类型，且前两个状态变量可以放进同一个slot里。所以这三个状态变量一共占用2个slot，索引是0和1。通过分析合约编译后的运行时字节码可以确定这一点。为了更清晰的观察字节码，我们可以使用 https://www.trustlook.com/services/smart.html 提供的在线反汇编工具（Disassembler）进行反汇编。下面是setV123()函数的反汇编结果：

function FUNC_4DEB3804() public return () {
    sstore(0x0, uint160(0xADD0));
    sstore(0x0, ((uint64(0x1234) * 0x10000000000000000000000000000000000000000) | (~0xFFFFFFFFFFFFFFFF0000000000000000000000000000000000000000 & sload(0x0))));
    sstore(0x1, 0x5678);
    return();
}

上面的逻辑可以使用伪代码表示为：

store[0x00] = (0x1234 << 160) | 0xADD0; // v1 = address(0xADD0); v2 = 0x1234;
store[0x01] = 0x5678;                   // v3 = 0x5678;

几乎所有的合约都会用到值类型的状态变量，所以此处就不一一举例了。另外，如果状态变量是简单结构体类型（字段都是值类型），其实现方式也是类似的：编译器会尽可能将多个连续字段塞进一个slot，并为整个结构体预留足够多个slot空间。本文就不展开介绍结构体类型的状态变量了，读者可以采用本文描述的方式自行分析。

定长数组

Solidity支持两种类型的数组：定长数据和变长数组。定长数组的长度在编译期已知，因此Solidity编译器将为数组预留足够多的slot空间。也就是说，如果定长数组的长度为L，那么编译器将预留L个slot。假设某定长数组之前已经使用了N个slot空间，那么定长数组的第M个元素将被放在第N+M个slot里（L、M、N都从0开始）。

在前面的示例合约中，a1为定长数组，长度为0x2000，前面已经使用了2个slot，因此编译器将后面的0x2000个slot预留给了a1。观察setA1()和setA2()函数的字节码可以确认这一点，下面是setA1()函数的反汇编结果：

function FUNC_6E7E996E() public return (var0) {
    assert((0x1001 < 0x2000));
    sstore(0x1003, 0x1234);
    assert((0x1002 < 0x2000));
    sstore(0x1004, 0x5678);
    return(0x2000);
}

可以看到，由于定长数组的长度在编译期就已经确定，所以编译器还顺便检查了索引的有效性。上面的逻辑可以使用伪代码表示为：

store[0x1003] = 0x1234; // a1[0x1001] = 0x1234;
store[0x1004] = 0x5678; // a1[0x1002] = 0x5678;
return 0x2000;

OneSwap在OneSwapPair合约中利用2个定长数组实现了订单薄，关键代码如下所示（后面讨论链表时还会再次介绍该合约）：

contract OneSwapPair is OneSwapPool, IOneSwapPair {
    // the orderbooks. Gas is saved when using array to store them instead of mapping
    uint[1<<22] private _sellOrders;
    uint[1<<22] private _buyOrders;
    ... // 其他代码省略
}

变长数组

和定长数组不同，变长数组的长度只有在运行时才能知道，且可以动态变化。由于长度是变化的，所以不能像定长数组那样，预留slot。Solidity采取的做法是在定长数组的位置预留1个slot，记录数组的实际长度。数组的起始slot，根据预留给数组的slot通过hash算法（keccak256）计算得到。假设某变长数组的前面已经使用了N个slot空间，则该数组的长度记录在第N个slot里；数组的第M个元素存储在第hash(N) + M个slot里（M、N都从0开始）。

在前面的示例合约中，a2为定长数组，前面已经使用了0x2002个slot，因此Solidity编译器将a2的长度记录在第0x2002个slot里，a2的起始索引为hash(0x2002)。观察setA2()函数的字节码可以确认这一点，下面是该函数的反汇编结果：

function FUNC_498E6857() public return (var0) {
    assert((0x1001 < sload(0x2002)));
    mstore(0x0, 0x2002);
    temp0 = keccak256(0x0, 0x20);
    sstore((temp0 + 0x1001), 0xABAB);
    assert((0x1002 < sload(0x2002)));
    mstore(0x0, 0x2002);
    temp1 = keccak256(0x0, 0x20);
    sstore((temp1 + 0x1002), 0xCDCD);
    return(sload(0x2002));
}

可以看到，编译器同样也检查了数组索引的有效性。上面的逻辑可以使用伪代码表示为：

store[hash(0x2002) + 0x1001] = 0xABAB; // a2[0x1001] = 0xABAB;
store[hash(0x2002) + 0x1002] = 0xCDCD; // a2[0x1001] = 0xCDCD;
return store[0x2002];

OneSwap在OneSwapFactory合约中使用变长数组（allPairs字段）记录了其创建的所有的交易对的地址，关键代码如下所示：

contract OneSwapFactory is IOneSwapFactory {
    struct TokensInPair {
        address stock;
        address money;
    }

    address public override feeTo;
    address public override feeToSetter;
    address public immutable gov;
    address public immutable ones;
    uint32 public override feeBPS = 50;
    address public override pairLogic;
    mapping(address => TokensInPair) private _pairWithToken;
    mapping(bytes32 => address) private _tokensToPair;
    address[] public allPairs;
    ... // 其他代码省略
}

简单映射

在Solidity中，映射的Key必须是内置的值类型，但是Val可以是值类型也可以是结构体、数组、映射等复杂类型。不过万变不离其宗，我们先来看看最简单的映射（Val是值类型）是如何工作的。假设某映射前面已经使用了N个slot空间，则编译器将为该映射预留第N个slot（但是并不实际存储数据）。而该映射的某个Key K对应的slot为K和N拼接之后的hash值，也就是hash(K, N)。

在前面的示例合约中，m1为简单映射，其Key为地址类型，Val为uint256整型。m1前面已经使用了0x2003个slot空间，因此对于m1来说，Key K对应的slot为hash(K, 0x2003)。观察setM1()函数的字节码可以确认这一点，下面是该函数的反汇编结果（由作者手工生成）：

function FUNC_D216F61F() public return () {
    mstore(0x00, 0xadd1 & 0xffffffffffffffffffffffffffffffffffffffff);
    mstore(0x20, 0x2003);
    sstore(keccak256(0x00, 0x40), 0x1234);

    mstore(0x00, 0xadd2 & 0xffffffffffffffffffffffffffffffffffffffff);
    mstore(0x20, 0x2003);
    sstore(keccak256(0x00, 0x40), 0x5678);
    return();
}

上面的逻辑可以使用伪代码表示为：

store[hash(0xadd1, 0x2003)] = 0x1234; // m1[address(0xADD1)] = 0x1234;
store[hash(0xadd2, 0x2003)] = 0x5678; // m1[address(0xADD2)] = 0x5678;

OneSwap中多个合约都用到了映射表，例如前面给出的OneSwapFactory合约就定义了两个映射（_tokensToPair和_pairWithToken）。值得说明的是，如果单独使用映射，我们是无法遍历其中的KV对的。为了获得遍历能力，映射表往往需要和数组搭配使用，例如OneSwapFactory合约中的allPairs数组记录了所有的交易对地址，使得遍历该工厂所创建的全部交易对成为可能。

复杂映射

如前所述，映射的Val也可以是复杂类型，比如结构体、数组、映射等。我们这里只分析最为常用的一种情况，也就是Val为映射的情况，其他的情况读者可以采用本文描述的方式自行分析。在前面的示例合约中，m2定义了一个“映射的映射”，setM2()函数对该映射进行了操作。这次我们反过来，先来看一下setM2()函数的反编译结果（由作者手工生成）：

function FUNC_3ACBD4FB() public return () {
    mstore(0x00, 0xadd3 & 0xffffffffffffffffffffffffffffffffffffffff);
    mstore(0x20, 0x2004);
    hash1 = keccak256(0x00, 0x40);
    mstore(0x00, 0xadd4 & 0xffffffffffffffffffffffffffffffffffffffff);
    mstore(0x20, hash1);
    hash2 = keccak256(0x00, 0x40);
    sstore(hash2, 0x1234);

    mstore(0x00, 0xadd5 & 0xffffffffffffffffffffffffffffffffffffffff);
    mstore(0x20, 0x2004);
    hash1 = keccak256(0x00, 0x40);
    mstore(0x00, 0xadd6 & 0xffffffffffffffffffffffffffffffffffffffff);
    mstore(0x20, hash1);
    hash2 = keccak256(0x00, 0x40);
    sstore(hash2, 0x5678);
    return();
}

通过上面的代码不难看出，编译器同样为m1预留了一个slot。根据该slot索引以及实际的Key做两次hash即可得到Val的最终slot索引。假设映射占据的slot为N，那么编译器将保留第N个slot。假设两个Key分别为K1和K2，那么Val占据的slot为hash(K2, hash(K1, N))。上面这个函数的逻辑可以使用伪代码表示为：

store[hash(0xADD4, hash(0xADD3, 0x2004))] = 0x1234; // m2[address(0xADD3)][address(0xADD4)] = 0x1234;
store[hash(0xADD6, hash(0xADD5, 0x2004))] = 0x1234; // m2[address(0xADD5)][address(0xADD6)] = 0x5678;

在OneSwap中，OneSwapToken合约利用“映射的映射”实现了ERC20的“授权转账”功能，下面给出该合约的关键状态：

contract OneSwapToken is IOneSwapToken, OneSwapBlackList {

    using SafeMath256 for uint256;

    mapping (address => uint256) private _balances;
    mapping (address => mapping (address => uint256)) private _allowances;
    uint256 private _totalSupply;
    string private _name;
    string private _symbol;
    uint8 private immutable _decimals;
    ... // 其他代码省略

}

注意，虽然EVM提供的KVStorage非常巨大、keccak256哈希算法也有很好的抗碰撞性，但理论上仍然是存在发生碰撞的可能性的，只是可能性非常之小，通常都不需要考虑。然而动态数组的使用却会增加碰撞的可能性，可能会带来安全隐患，需要谨慎处理。关于以太坊存储hash碰撞的更多讨论可以参考这篇文章。

数据结构

数组和映射是Solidity语言提供的基本数据结构，在此基础之上，很容易构造集合、链表、栈和队列等数据结构。接下来我们简单介绍一下这些数据结构的实现方式以及它们在OneSwap中的应用。

集合

集合的实现非常简单，只要定义一个Val为布尔类型的映射即可。例如OneSwapBlackList抽象合约使用集合记录了黑名单用户，关键代码如下所示：

abstract contract OneSwapBlackList is IOneSwapBlackList {

    address private _owner;
    address private _newOwner;
    mapping(address => bool) private _isBlackListed;
    ... // 其他代码省略
}

和映射一样，集合本身也是不可遍历的。如果要实现可遍历集合，就需要数组的帮助。例如OneSwapBuyback合约使用映射和数组实现了可遍历的主流币种列表，关键代码如下所示：

contract OneSwapBuyback is IOneSwapBuyback {

    mapping(address => bool) private _mainTokens;
    address[] private _mainTokenArr;
    ... // 其他代码省略
}

链表

单链表可以使用映射+结构体，或者数组+结构体的方式实现。如果是单链表，那么结构体中仅需要记录前一个（或者后一个）节点即可；如果是双链表那么前后节点都需要记录。例如OneSwapPair合约使用定长数组+结构体的方式构造了订单薄单链表，关键代码如下所示：

struct Order { // total 256 bits
    address sender; // 160 bits, sender creates this order
    uint32 price;   // 32-bit decimal floating point number
    uint64 amount;  // 42 bits are used, the stock amount to be sold or bought
    uint32 nextID;  // 22 bits are used
}

contract OneSwapPair is OneSwapPool, IOneSwapPair {
    // the orderbooks. Gas is saved when using array to store them instead of mapping
    uint[1<<22] private _sellOrders;
    uint[1<<22] private _buyOrders;
    ... // 其他代码省略
}

由于订单薄链表可能会很长，所以OneSwap使用了“链外查询，链上确认”的技巧。例如在下限价单时，可以预先查询订单在链上的位置，然后在交易执行时直接确认位置并插入订单即可。由于这些优化技巧以及其他各种优化手段的使用，OneSwap在提供了限价单服务的同时，仍然将各种操作的Gas消耗保持在了和UniSwap同样低的水平。

栈和队列

Solidity变长数组提供了push()和pop()函数，因此直接就可以当作栈来使用。队列既可以用动态数组实现，也可以用映射来实现。OneSwap没有直接使用栈和队列，这里就不展开介绍了，读者可以参考这篇文章进一步了解这两种数据结构的实现方式。

总结

以太坊为每一个部署在上面的智能合约都提供了一个巨大的KVStore，合约的状态即存储在该KVStore里。底层的EVM提供了SSTORE和SLOAD指令来读写这个KVStore，且这两条指令相对而言比较消耗Gas。在Solidity合约中，我们可以定义各种类型的状态变量，包括值类型、结构体类型、定长或变长数组、映射等。无论是何种类型的状态变量，都必须存储在同一个KVStore里。为了合理、高效的利用这个存储空间，Solidity编译器做了大量的优化。然而，合约的编写者也必须仔细排列各种状态变量。

本文介绍了Solidity语言各种状态变量的实现原理，如何基于数组和映射构造结合和链表等数据结构，以及这些数据结构在OneSwap项目中的应用。关于OneSwap的更多信息请关注我们的后续文章。

参考资料

原文：《OneSwap Series 7 — Basic Data Structures》
链接：https://oneswap.medium.com/oneswap-series-7-basic-data-structures-57bdf4b9e8b

翻译：OneSwap中文社区