lbug 0.16.0

An in-process property graph database management system built for query speed and scalability
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183

#pragma once

#include "density_state.h"
#include "gds_object_manager.h"
#include "graph/graph.h"

namespace lbug {
namespace storage {
class MemoryManager;
}
namespace processor {
struct ExecutionContext;
}
namespace function {

// TODO(Xiyang): optimize if edgeID is not needed.
class ParentList {
public:
    void setNbrInfo(common::nodeID_t nodeID_, common::relID_t edgeID_, bool isFwd_) {
        nodeID = nodeID_;
        edgeID = edgeID_;
        isFwd = isFwd_;
    }
    common::nodeID_t getNodeID() const { return nodeID; }
    common::relID_t getEdgeID() const { return edgeID; }
    bool isFwdEdge() const { return isFwd; }

    void setNextPtr(ParentList* ptr) { next.store(ptr, std::memory_order_relaxed); }
    ParentList* getNextPtr() { return next.load(std::memory_order_relaxed); }

    void setIter(uint16_t iter_) { iter = iter_; }
    uint16_t getIter() const { return iter; }

    void setCost(double cost_) { cost = cost_; }
    double getCost() const { return cost; }

private:
    common::nodeID_t nodeID;
    common::relID_t edgeID;
    bool isFwd = true;

    uint16_t iter = UINT16_MAX;
    double cost = std::numeric_limits<double>::max();
    // Next pointer
    std::atomic<ParentList*> next;
};

class BaseBFSGraph {
    friend class BFSGraphManager;

public:
    explicit BaseBFSGraph(storage::MemoryManager* mm) : mm{mm} {}
    virtual ~BaseBFSGraph() = default;

    // This function should be called by a worker thread Ti to grab a block of memory that
    // Ti owns and writes to.
    ObjectBlock<ParentList>* addNewBlock();

    virtual void pinTableID(common::table_id_t tableID) = 0;

    // Used to track path for all shortest path & variable length path.
    virtual void addParent(uint16_t iter, common::nodeID_t boundNodeID, common::relID_t edgeID,
        common::nodeID_t nbrNodeID, bool fwdEdge, ObjectBlock<ParentList>* block) = 0;
    // Used to track path for single shortest path. Assume each offset has at most one parent.
    virtual void addSingleParent(uint16_t iter, common::nodeID_t boundNodeID,
        common::relID_t edgeID, common::nodeID_t nbrNodeID, bool fwdEdge,
        ObjectBlock<ParentList>* block) = 0;
    // Used to track path for all weighted shortest path.
    virtual bool tryAddParentWithWeight(common::nodeID_t boundNodeID, common::relID_t edgeID,
        common::nodeID_t nbrNodeID, bool fwdEdge, double weight,
        ObjectBlock<ParentList>* block) = 0;
    // Used to track path for single weighted shortest path. Assume each offset has at most one
    // parent.
    virtual bool tryAddSingleParentWithWeight(common::nodeID_t boundNodeID, common::relID_t edgeID,
        common::nodeID_t nbrNodeID, bool fwdEdge, double weight,
        ObjectBlock<ParentList>* block) = 0;

    virtual ParentList* getParentListHead(common::offset_t offset) = 0;
    virtual ParentList* getParentListHead(common::nodeID_t nodeID) = 0;

    virtual void setParentList(common::offset_t offset, ParentList* parentList) = 0;

    template<class TARGET>
    TARGET& cast() {
        return common::dynamic_cast_checked<TARGET&>(*this);
    }

protected:
    std::mutex mtx;
    storage::MemoryManager* mm;
    std::vector<std::unique_ptr<ObjectBlock<ParentList>>> blocks;
};

class DenseBFSGraph : public BaseBFSGraph {
    friend class BFSGraphManager;
    friend class BFSGraphInitVertexCompute;

public:
    DenseBFSGraph(storage::MemoryManager* mm, common::table_id_map_t<common::offset_t> maxOffsetMap)
        : BaseBFSGraph{mm}, maxOffsetMap{std::move(maxOffsetMap)} {}

    void init(processor::ExecutionContext* context, graph::Graph* graph);

    void pinTableID(common::table_id_t tableID) override;

    void addParent(uint16_t iter, common::nodeID_t boundNodeID, common::relID_t edgeID,
        common::nodeID_t nbrNodeID, bool fwdEdge, ObjectBlock<ParentList>* block) override;
    void addSingleParent(uint16_t iter, common::nodeID_t boundNodeID, common::relID_t edgeID,
        common::nodeID_t nbrNodeID, bool fwdEdge, ObjectBlock<ParentList>* block) override;
    bool tryAddParentWithWeight(common::nodeID_t boundNodeID, common::relID_t edgeID,
        common::nodeID_t nbrNodeID, bool fwdEdge, double weight,
        ObjectBlock<ParentList>* block) override;
    bool tryAddSingleParentWithWeight(common::nodeID_t boundNodeID, common::relID_t edgeID,
        common::nodeID_t nbrNodeID, bool fwdEdge, double weight,
        ObjectBlock<ParentList>* block) override;

    ParentList* getParentListHead(common::offset_t offset) override;
    ParentList* getParentListHead(common::nodeID_t nodeID) override;

    void setParentList(common::offset_t offset, ParentList* parentList) override;

private:
    common::table_id_map_t<common::offset_t> maxOffsetMap;
    GDSDenseObjectManager<std::atomic<ParentList*>> denseObjects;
    std::atomic<ParentList*>* curData = nullptr;
};

class SparseBFSGraph : public BaseBFSGraph {
    friend class BFSGraphManager;

public:
    explicit SparseBFSGraph(storage::MemoryManager* mm,
        common::table_id_map_t<common::offset_t> maxOffsetMap)
        : BaseBFSGraph{mm}, sparseObjects{maxOffsetMap} {}

    void pinTableID(common::table_id_t tableID) override;

    void addParent(uint16_t iter, common::nodeID_t boundNodeID, common::relID_t edgeID,
        common::nodeID_t nbrNodeID, bool fwdEdge, ObjectBlock<ParentList>* block) override;
    void addSingleParent(uint16_t iter, common::nodeID_t boundNodeID, common::relID_t edgeID,
        common::nodeID_t nbrNodeID, bool fwdEdge, ObjectBlock<ParentList>* block) override;
    bool tryAddParentWithWeight(common::nodeID_t boundNodeID, common::relID_t edgeID,
        common::nodeID_t nbrNodeID, bool fwdEdge, double weight,
        ObjectBlock<ParentList>* block) override;
    bool tryAddSingleParentWithWeight(common::nodeID_t boundNodeID, common::relID_t edgeID,
        common::nodeID_t nbrNodeID, bool fwdEdge, double weight,
        ObjectBlock<ParentList>* block) override;

    ParentList* getParentListHead(common::offset_t offset) override;
    ParentList* getParentListHead(common::nodeID_t nodeID) override;

    void setParentList(common::offset_t offset, ParentList* parentList) override;

    const std::unordered_map<common::offset_t, ParentList*>& getCurrentData() const {
        return *curData;
    }

private:
    GDSSpareObjectManager<ParentList*> sparseObjects;
    std::unordered_map<common::offset_t, ParentList*>* curData = nullptr;
};

class BFSGraphManager {
public:
    BFSGraphManager(common::table_id_map_t<common::offset_t> maxOffsetMap,
        storage::MemoryManager* mm);

    BaseBFSGraph* getCurrentGraph() const {
        DASSERT(curGraph);
        return curGraph;
    }

    void switchToDense(processor::ExecutionContext* context, graph::Graph* graph);

private:
    GDSDensityState state = GDSDensityState::SPARSE;
    std::unique_ptr<DenseBFSGraph> denseBFSGraph;
    std::unique_ptr<SparseBFSGraph> sparseBFSGraph;
    BaseBFSGraph* curGraph = nullptr;
};

} // namespace function
} // namespace lbug