Rippled Audit

The Node/SHAMap Store

In rippled SHAMap is the base data structure that is persisted to the underlying database backend and used to store ledgers with transactions and accounts. This system is referred to as the NodeStore in the code, but is also known as the SHAMapStore.

At the core SHAMap (implemented under src/ripple/shamap) is defined as "both a radix tree with a fan-out of 16 and a Merkle tree". This means:

  • Nodes in trees are identified by a cryptographic hash of their contents, the actual contained object in the case of leaf nodes and the children in the case of internal nodes (in rippled the half-sha512 is used)
  • Nodes are identified by their position in the tree, where the descendants of any given node share the prefix associated with that node
  • Only child nodes are merged with their parents and thus edges can be labeled with sequences of elements as well as single elements
  • This saves spaces and increases performance as redundant data is optimized out

The core leaf definition SHAMapItem is associated with the generic Blob structure, which in return is aliased to a generic Vector of unsigned chars.

The nodestore defines the core database which is used to persistently store ledger data. This is accomplished through the instantiation of the Database class containing references to abstract Backend instances, implmented via concrete Adapters under src/ripple/nodestore/backend (instantiated via a named factory pattern). Backends exist for NuDB and rocksdb.

Core DataBase API (abridged) - src/ripple/nodestore/Database.h

53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
    class Database : public Stoppable
    {
    public:
        Database(std::string name, Stoppable& parent, Scheduler& scheduler,
            int readThreads, Section const& config, beast::Journal j);

        virtual
        std::string
        getName() const = 0;

        virtual
        void
        import(Database& source) = 0;

        virtual
        void
        store(NodeObjectType type, Blob&& data,
            uint256 const& hash, std::uint32_t seq) = 0;

        virtual
        std::shared_ptr<NodeObject>
        fetch(uint256 const& hash, std::uint32_t seq) = 0;

        virtual
        bool
        asyncFetch(uint256 const& hash, std::uint32_t seq,
            std::shared_ptr<NodeObject>& object) = 0;

        virtual
        bool
        copyLedger(std::shared_ptr<Ledger const> const& ledger) = 0;
    }

Abstract Backend Class (abridged) - src/ripple/nodestore/Backend.h

37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
    class Backend
    {
    public:
        virtual std::string getName() = 0;

        virtual void open(bool createIfMissing = true) = 0;

        virtual void close() = 0;

        virtual Status fetch (void const* key, std::shared_ptr<NodeObject>* pObject) = 0;

        virtual
        bool
        canFetchBatch() = 0;

        virtual
        std::vector<std::shared_ptr<NodeObject>>
        fetchBatch (std::size_t n, void const* const* keys) = 0;

        virtual void store (std::shared_ptr<NodeObject> const& object) = 0;

        virtual void storeBatch (Batch const& batch) = 0;

        virtual void for_each (std::function <void (std::shared_ptr<NodeObject>)> f) = 0;
    }

We can see the instantiation of the database and backend via the factory pattern in the Manager class. This takes a Stoppable instance which to assign as a parent to the database, facilititating its inclusion in the core Application lifecycle. We can see in the Application Class the Job Queue is specified as the DataBase parent. Various database read operations are run asynchronously via this system.

Database and Backend creation - src/ripple/nodestore/impl/ManagerImp.cpp

42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
    std::unique_ptr <Backend>
    ManagerImp::make_Backend (
        Section const& parameters,
        Scheduler& scheduler,
        beast::Journal journal)
    {
        std::string const type {get<std::string>(parameters, "type")};
        if (type.empty())
            missing_backend();

        auto factory {find(type)};
        if(!factory)
            missing_backend();

        return factory->createInstance(
            NodeObject::keyBytes, parameters, scheduler, journal);
    }

    std::unique_ptr <Database>
    ManagerImp::make_Database (
        std::string const& name,
        Scheduler& scheduler,
        int readThreads,
        Stoppable& parent,
        Section const& config,
        beast::Journal journal)
    {
        auto backend {make_Backend(config, scheduler, journal)};
        backend->open();
        return std::make_unique <DatabaseNodeImp>(
            name,
            scheduler,
            readThreads,
            parent,
            std::move(backend),
            config,
            journal);
    }

All in all the entire NodeStore instantiation workflow can be seen below:

The various specific DB adapters can be found in the src/ripple/nodestore/backend directory, specifically for the two official supported backeds: NuDB and RocksDB. In both cases we can see the DB connection is kept alive until closed on object destruction (NuDB and RocksDB).

Use of the NodeStore can be seen in various ledger-handling modules.

Using the NodeStore (saving a ledger)- src/ripple/app/ledger/Ledger.cpp

787
788
789
790
791
792
    static bool saveValidatedLedger (
    Application& app,
    std::shared_ptr<Ledger const> const& ledger,
    bool current)
    {
      // ...
832
833
834
835
836
837
838
839
      // ...
    {
        Serializer s (128);
        s.add32 (HashPrefix::ledgerMaster);
        addRaw(ledger->info(), s);
        app.getNodeStore().store(hotLEDGER,
            std::move(s.modData()), ledger->info().hash, seq);
    }

The final component of the NodeStore subsystem is the NodeStore::Schedule interface and the NodeStoreScheduler (a Stoppable child of Appliction) facilitating an optional BatchWrite mechanism as well as the collection of DB fetch benchmarks. Currently only the RocksDBBackend supports BatchWrite.

<<Back Home >>Next