lbug 0.22.0

An in-process property graph database management system built for query speed and scalability
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

#pragma once

#include <cmath>
#include <cstdint>
#include <cstring>

#include "common/constants.h"
#include "common/system_config.h"
#include "common/types/string_t.h"
#include "common/types/types.h"
#include "function/hash/hash_functions.h"
#include "storage/index/hash_index_header.h"

namespace lbug {
namespace storage {

static constexpr uint64_t NUM_HASH_INDEXES = common::HashIndexConstants::NUM_HASH_INDEXES;
static constexpr uint64_t NUM_HASH_INDEXES_LOG2 = common::HashIndexConstants::NUM_HASH_INDEXES_LOG2;

static constexpr common::page_idx_t INDEX_HEADER_PAGES = 2;
static constexpr uint64_t INDEX_HEADERS_PER_PAGE =
    common::LBUG_PAGE_SIZE / sizeof(HashIndexHeaderOnDisk);

static constexpr common::page_idx_t P_SLOTS_HEADER_PAGE_IDX = 0;
static constexpr common::page_idx_t O_SLOTS_HEADER_PAGE_IDX = 1;
static constexpr common::page_idx_t NUM_HEADER_PAGES = 2;
static constexpr uint64_t INDEX_HEADER_IDX_IN_ARRAY = 0;

// so that all 256 hash indexes can be stored in two pages, the HashIndexHeaderOnDisk must be
// smaller than 32 bytes
static_assert(NUM_HASH_INDEXES * sizeof(HashIndexHeaderOnDisk) <=
              common::LBUG_PAGE_SIZE * INDEX_HEADER_PAGES);

enum class SlotType : uint8_t { PRIMARY = 0, OVF = 1 };

struct SlotInfo {
    slot_id_t slotId{UINT64_MAX};
    SlotType slotType{SlotType::PRIMARY};

    bool operator==(const SlotInfo&) const = default;
};

class HashIndexUtils {

public:
    static constexpr auto INVALID_OVF_INFO =
        SlotInfo{SlotHeader::INVALID_OVERFLOW_SLOT_ID, SlotType::OVF};

    static bool areStringPrefixAndLenEqual(std::string_view keyToLookup,
        const common::string_t& keyInEntry) {
        auto prefixLen =
            std::min(static_cast<uint64_t>(keyInEntry.len), common::string_t::PREFIX_LENGTH);
        return keyToLookup.length() == keyInEntry.len &&
               memcmp(keyToLookup.data(), keyInEntry.prefix, prefixLen) == 0;
    }

    template<typename T>
    static common::hash_t hash(const T& key) {
        common::hash_t hash = 0;
        function::Hash::operation(key, hash);
        return hash;
    }

    // Pre-0.21 string hash, solely for detecting stale persisted indexes (issue #1092).
    // Before the char-signedness portability fix (issue #882, v0.21.0), the trailing size%8
    // bytes were accumulated through plain (possibly signed) char, sign-extending bytes >=
    // 0x80 on signed-char platforms (x86-64, macOS arm64, wasm32). String-key hash indexes
    // persisted by <= 0.20.x on those platforms therefore placed non-ASCII keys in slots the
    // current hash function never probes. This replicates those legacy values exactly (the
    // 8-byte blocks use memcpy instead of the original misaligned uint64_t load, which is
    // value-identical and avoids reintroducing issue #879). Do NOT use for any new hashing.
    static common::hash_t hashStringPre021(std::string_view key) {
        common::hash_t hashValue = 0;
        for (size_t i = 0u; i < key.size() / 8; i++) {
            uint64_t block = 0;
            memcpy(&block, key.data() + i * sizeof(block), sizeof(block));
            hashValue = function::combineHashScalar(hashValue, function::murmurhash64(block));
        }
        uint64_t last = 0;
        for (size_t i = 0u; i < key.size() % 8; i++) {
            last |= static_cast<uint64_t>(key[key.size() / 8 * 8 + i]) << i * 8;
        }
        return function::combineHashScalar(hashValue, function::murmurhash64(last));
    }

    static uint8_t getFingerprintForHash(common::hash_t hash) {
        // Last 8 bits before the bits used to calculate the hash index position is the fingerprint
        return (hash >> (64 - NUM_HASH_INDEXES_LOG2 - 8)) & 255;
    }

    static slot_id_t getPrimarySlotIdForHash(const HashIndexHeader& indexHeader,
        common::hash_t hash) {
        auto slotId = hash & indexHeader.levelHashMask;
        if (slotId < indexHeader.nextSplitSlotId) {
            slotId = hash & indexHeader.higherLevelHashMask;
        }
        return slotId;
    }

    static uint64_t getHashIndexPositionForHash(common::hash_t hash) {
        return (hash >> (64 - NUM_HASH_INDEXES_LOG2)) & (NUM_HASH_INDEXES - 1);
    }

    static uint64_t getHashIndexPosition(common::IndexHashable auto key) {
        return getHashIndexPositionForHash(HashIndexUtils::hash(key));
    }

    // Sub-index chosen by the pre-0.21 string hash (issue #1172). Keys persisted by <= 0.20.x
    // on signed-char platforms sit in this sub-index, which usually differs from the current
    // sub-index when the key is non-ASCII. Used solely to probe the legacy location so a
    // stale entry fails loudly instead of silently missing.
    static uint64_t getLegacyHashIndexPosition(std::string_view key) {
        return getHashIndexPositionForHash(hashStringPre021(key));
    }

    static uint64_t getNumRequiredEntries(uint64_t numEntries) {
        return ceil(static_cast<double>(numEntries) * common::DEFAULT_HT_LOAD_FACTOR);
    }
};
} // namespace storage
} // namespace lbug