From 7c03d771475421c1d5a2bbc135242536af1a371c Mon Sep 17 00:00:00 2001 From: Douglas Rumbaugh Date: Mon, 25 Sep 2023 10:49:36 -0400 Subject: Re-structuring Project + scheduling updates This is a big one--probably should have split it apart, but I'm feeling lazy this morning. * Organized the mess of header files in include/framework by splitting them out into their own subdirectories, and renaming a few files to remove redundancies introduced by the directory structure. * Introduced a new framework/ShardRequirements.h header file for simpler shard development. This header simply contains the necessary includes from framework/* for creating shard files. This should help to remove structural dependencies from the framework file structure and shards, as well as centralizing the necessary framework files to make shard development easier. * Created a (currently dummy) SchedulerInterface, and make the scheduler implementation a template parameter of the dynamic extension for easier testing of various scheduling policies. There's still more work to be done to fully integrate the scheduler (queries, multiple buffers), but some more of the necessary framework code for this has been added as well. * Adjusted the Task interface setup for the scheduler. The task structures have been removed from ExtensionStructure and placed in their own header file. Additionally, I started experimenting with using std::variant, as opposed to inheritence, to implement subtype polymorphism on the Merge and Query tasks. The scheduler now has a general task queue that contains both, and std::variant, std::visit, and std::get are used to manipulate them without virtual functions. * Removed Alex.h, as it can't build anyway. There's a branch out there containing the Alex implementation stripped of the C++20 stuff. So there's no need to keep it here. --- include/shard/PGM.h | 6 ++---- 1 file changed, 2 insertions(+), 4 deletions(-) (limited to 'include/shard/PGM.h') diff --git a/include/shard/PGM.h b/include/shard/PGM.h index 2cd153e..d960e70 100644 --- a/include/shard/PGM.h +++ b/include/shard/PGM.h @@ -15,15 +15,13 @@ #include #include +#include "framework/ShardRequirements.h" + #include "pgm/pgm_index.hpp" #include "psu-ds/PriorityQueue.h" #include "util/Cursor.h" #include "psu-ds/BloomFilter.h" #include "util/bf_config.h" -#include "framework/MutableBuffer.h" -#include "framework/RecordInterface.h" -#include "framework/ShardInterface.h" -#include "framework/QueryInterface.h" using psudb::CACHELINE_SIZE; using psudb::BloomFilter; -- cgit v1.2.3 From d2279e1b96d352a0af1d425dcaaf93e8a26a8d52 Mon Sep 17 00:00:00 2001 From: Douglas Rumbaugh Date: Mon, 30 Oct 2023 17:15:05 -0400 Subject: General Comment + Consistency updates --- include/shard/PGM.h | 4 ++++ 1 file changed, 4 insertions(+) (limited to 'include/shard/PGM.h') diff --git a/include/shard/PGM.h b/include/shard/PGM.h index d960e70..6d76376 100644 --- a/include/shard/PGM.h +++ b/include/shard/PGM.h @@ -235,6 +235,10 @@ public: return m_pgm.size_in_bytes() + m_alloc_size; } + size_t get_aux_memory_usage() { + return 0; + } + size_t get_lower_bound(const K& key) const { auto bound = m_pgm.search(key); size_t idx = bound.lo; -- cgit v1.2.3 From e02742b07540dd5a9bcbb44dae14856bf10955ed Mon Sep 17 00:00:00 2001 From: Douglas Rumbaugh Date: Mon, 6 Nov 2023 15:18:53 -0500 Subject: Refactoring progress --- include/shard/PGM.h | 267 ---------------------------------------------------- 1 file changed, 267 deletions(-) (limited to 'include/shard/PGM.h') diff --git a/include/shard/PGM.h b/include/shard/PGM.h index 6d76376..6b66b7d 100644 --- a/include/shard/PGM.h +++ b/include/shard/PGM.h @@ -31,34 +31,6 @@ using psudb::Alias; namespace de { -template -struct pgm_range_query_parms { - decltype(R::key) lower_bound; - decltype(R::key) upper_bound; -}; - -template -struct PGMPointLookupParms { - decltype(R::key) target_key; -}; - -template -class PGMRangeQuery; - -template -class PGMPointLookup; - -template -struct PGMState { - size_t start_idx; - size_t stop_idx; -}; - -template -struct PGMBufferState { - size_t cutoff; -}; - template class PGM { private: @@ -67,11 +39,6 @@ private: public: - - // FIXME: there has to be a better way to do this - friend class PGMRangeQuery; - friend class PGMPointLookup; - PGM(MutableBuffer* buffer) : m_reccnt(0), m_tombstone_cnt(0) { @@ -80,8 +47,6 @@ public: m_data = (Wrapped*)std::aligned_alloc(CACHELINE_SIZE, m_alloc_size); std::vector keys; - //m_bf = new BloomFilter(BF_FPR, buffer->get_tombstone_count(), BF_HASH_FUNCS); - size_t offset = 0; m_reccnt = 0; auto base = buffer->get_data(); @@ -110,13 +75,6 @@ public: base->header &= 3; m_data[m_reccnt++] = *base; keys.emplace_back(base->rec.key); - - /* - if (m_bf && base->is_tombstone()) { - m_tombstone_cnt++; - m_bf->insert(base->rec); - }*/ - base++; } @@ -148,8 +106,6 @@ public: } } - //m_bf = new BloomFilter(BF_FPR, tombstone_count, BF_HASH_FUNCS); - m_alloc_size = (attemp_reccnt * sizeof(Wrapped)) + (CACHELINE_SIZE - (attemp_reccnt * sizeof(Wrapped)) % CACHELINE_SIZE); assert(m_alloc_size % CACHELINE_SIZE == 0); m_data = (Wrapped*)std::aligned_alloc(CACHELINE_SIZE, m_alloc_size); @@ -172,10 +128,6 @@ public: if (!cursor.ptr->is_deleted()) { m_data[m_reccnt++] = *cursor.ptr; keys.emplace_back(cursor.ptr->rec.key); - /*if (m_bf && cursor.ptr->is_tombstone()) { - ++m_tombstone_cnt; - if (m_bf) m_bf->insert(cursor.ptr->rec); - }*/ } pq.pop(); @@ -190,15 +142,9 @@ public: ~PGM() { if (m_data) free(m_data); - //if (m_bf) delete m_bf; - } Wrapped *point_lookup(const R &rec, bool filter=false) { - //if (filter && !m_bf->lookup(rec)) { - // return nullptr; - //} - size_t idx = get_lower_bound(rec.key); if (idx >= m_reccnt) { return nullptr; @@ -284,219 +230,6 @@ private: K m_max_key; K m_min_key; pgm::PGMIndex m_pgm; - //BloomFilter *m_bf; -}; -template -class PGMPointLookup { -public: - constexpr static bool EARLY_ABORT=false; - constexpr static bool SKIP_DELETE_FILTER=false; - - static void *get_query_state(PGM *ts, void *parms) { - return nullptr; - } - - static void* get_buffer_query_state(MutableBuffer *buffer, void *parms) { - return nullptr; - } - - static void process_query_states(void *query_parms, std::vector &shard_states, void *buff_state) { - return; - } - - static std::vector> query(PGM *ts, void *q_state, void *parms) { - std::vector> records; - auto p = (PGMPointLookupParms *) parms; - auto s = (PGMState *) q_state; - - size_t idx = ts->get_lower_bound(p->target_key); - if (ts->get_record_at(idx)->rec.key == p->target_key) { - records.emplace_back(*ts->get_record_at(idx)); - } - - return records; - } - - static std::vector> buffer_query(MutableBuffer *buffer, void *state, void *parms) { - auto p = (PGMPointLookupParms *) parms; - auto s = (PGMBufferState *) state; - - std::vector> records; - for (size_t i=0; iget_record_count(); i++) { - auto rec = buffer->get_data() + i; - if (rec->rec.key == p->target_key) { - records.emplace_back(*rec); - return records; - } - } - - return records; - } - - static std::vector merge(std::vector>> &results, void *parms) { - std::vector output; - for (size_t i=0 ;i 0) { - output.emplace_back(results[i][0].rec); - return output; - } - } - - return output; - } - - static void delete_query_state(void *state) { - } - - static void delete_buffer_query_state(void *state) { - } }; - - -template -class PGMRangeQuery { -public: - constexpr static bool EARLY_ABORT=false; - constexpr static bool SKIP_DELETE_FILTER=false; - - static void *get_query_state(PGM *ts, void *parms) { - auto res = new PGMState(); - auto p = (pgm_range_query_parms *) parms; - - res->start_idx = ts->get_lower_bound(p->lower_bound); - res->stop_idx = ts->get_record_count(); - - return res; - } - - static void* get_buffer_query_state(MutableBuffer *buffer, void *parms) { - auto res = new PGMBufferState(); - res->cutoff = buffer->get_record_count(); - - return res; - } - - static void process_query_states(void *query_parms, std::vector &shard_states, void *buff_state) { - return; - } - - static std::vector> query(PGM *ts, void *q_state, void *parms) { - size_t tot = 0; - //std::vector> records; - auto p = (pgm_range_query_parms *) parms; - auto s = (PGMState *) q_state; - - // if the returned index is one past the end of the - // records for the PGM, then there are not records - // in the index falling into the specified range. - if (s->start_idx == ts->get_record_count()) { - return {}; - } - - auto ptr = ts->get_record_at(s->start_idx); - - // roll the pointer forward to the first record that is - // greater than or equal to the lower bound. - while(ptr->rec.key < p->lower_bound) { - ptr++; - } - - while (ptr->rec.key <= p->upper_bound && ptr < ts->m_data + s->stop_idx) { - if (ptr->is_tombstone()) --tot; - else if (!ptr->is_deleted()) ++tot; - //records.emplace_back(*ptr); - ptr++; - } - - return {Wrapped{0, {tot, 0}}}; - //return records; - } - - static std::vector> buffer_query(MutableBuffer *buffer, void *state, void *parms) { - size_t tot = 0; - auto p = (pgm_range_query_parms *) parms; - auto s = (PGMBufferState *) state; - - //std::vector> records; - for (size_t i=0; icutoff; i++) { - auto rec = buffer->get_data() + i; - if (rec->rec.key >= p->lower_bound && rec->rec.key <= p->upper_bound) { - if (rec->is_tombstone()) --tot; - else if (!rec->is_deleted()) ++tot; - //records.emplace_back(*rec); - } - } - - return {Wrapped{0, {tot, 0}}}; - //return records; - } - - static std::vector merge(std::vector>> &results, void *parms) { - /*std::vector>> cursors; - cursors.reserve(results.size()); - - PriorityQueue> pq(results.size()); - size_t total = 0; - size_t tmp_n = results.size(); - - - for (size_t i = 0; i < tmp_n; ++i) - if (results[i].size() > 0){ - auto base = results[i].data(); - cursors.emplace_back(Cursor{base, base + results[i].size(), 0, results[i].size()}); - assert(i == cursors.size() - 1); - total += results[i].size(); - pq.push(cursors[i].ptr, tmp_n - i - 1); - } else { - cursors.emplace_back(Cursor>{nullptr, nullptr, 0, 0}); - } - - if (total == 0) { - return std::vector(); - } - - std::vector output; - output.reserve(total); - - while (pq.size()) { - auto now = pq.peek(); - auto next = pq.size() > 1 ? pq.peek(1) : queue_record>{nullptr, 0}; - if (!now.data->is_tombstone() && next.data != nullptr && - now.data->rec == next.data->rec && next.data->is_tombstone()) { - - pq.pop(); pq.pop(); - auto& cursor1 = cursors[tmp_n - now.version - 1]; - auto& cursor2 = cursors[tmp_n - next.version - 1]; - if (advance_cursor>(cursor1)) pq.push(cursor1.ptr, now.version); - if (advance_cursor>(cursor2)) pq.push(cursor2.ptr, next.version); - } else { - auto& cursor = cursors[tmp_n - now.version - 1]; - if (!now.data->is_tombstone()) output.push_back(cursor.ptr->rec); - pq.pop(); - - if (advance_cursor>(cursor)) pq.push(cursor.ptr, now.version); - } - }*/ - - size_t tot = 0; - for (auto& result: results) - if (result.size() > 0) tot += result[0].rec.key; - - return {{tot, 0}}; - } - - static void delete_query_state(void *state) { - auto s = (PGMState *) state; - delete s; - } - - static void delete_buffer_query_state(void *state) { - auto s = (PGMBufferState *) state; - delete s; - } -}; - -; - } -- cgit v1.2.3 From 357cab549c2ed33970562b84ff6f83923742343d Mon Sep 17 00:00:00 2001 From: Douglas Rumbaugh Date: Tue, 7 Nov 2023 15:34:24 -0500 Subject: Comment and License updates --- include/shard/PGM.h | 6 +++++- 1 file changed, 5 insertions(+), 1 deletion(-) (limited to 'include/shard/PGM.h') diff --git a/include/shard/PGM.h b/include/shard/PGM.h index 6b66b7d..13db26a 100644 --- a/include/shard/PGM.h +++ b/include/shard/PGM.h @@ -2,8 +2,12 @@ * include/shard/PGM.h * * Copyright (C) 2023 Douglas B. Rumbaugh + * Dong Xie * - * All rights reserved. Published under the Modified BSD License. + * Distributed under the Modified BSD License. + * + * A shard shim around the static version of the PGM learned + * index. * */ #pragma once -- cgit v1.2.3 From bd74e27b28bd95267ce50d2e4b6f12b51d9b6aae Mon Sep 17 00:00:00 2001 From: Douglas Rumbaugh Date: Wed, 7 Feb 2024 17:23:23 -0500 Subject: Cleaned up shard files (except VPTree) Cleaned up shard implementations, fixed a few bugs, and set up some tests. There's still some work to be done in creating tests for the weighted sampling operations for the alias and aug btree shards. --- include/shard/PGM.h | 140 +++++++++++++++++----------------------------------- 1 file changed, 45 insertions(+), 95 deletions(-) (limited to 'include/shard/PGM.h') diff --git a/include/shard/PGM.h b/include/shard/PGM.h index 13db26a..8031870 100644 --- a/include/shard/PGM.h +++ b/include/shard/PGM.h @@ -14,24 +14,19 @@ #include -#include -#include -#include -#include #include "framework/ShardRequirements.h" #include "pgm/pgm_index.hpp" -#include "psu-ds/PriorityQueue.h" -#include "util/Cursor.h" #include "psu-ds/BloomFilter.h" +#include "util/SortedMerge.h" #include "util/bf_config.h" using psudb::CACHELINE_SIZE; using psudb::BloomFilter; using psudb::PriorityQueue; using psudb::queue_record; -using psudb::Alias; +using psudb::byte; namespace de { @@ -41,111 +36,65 @@ private: typedef decltype(R::key) K; typedef decltype(R::value) V; - public: - PGM(MutableBuffer* buffer) - : m_reccnt(0), m_tombstone_cnt(0) { - - m_alloc_size = (buffer->get_record_count() * sizeof(Wrapped)) + (CACHELINE_SIZE - (buffer->get_record_count() * sizeof(Wrapped)) % CACHELINE_SIZE); - assert(m_alloc_size % CACHELINE_SIZE == 0); - m_data = (Wrapped*)std::aligned_alloc(CACHELINE_SIZE, m_alloc_size); - std::vector keys; - - size_t offset = 0; - m_reccnt = 0; - auto base = buffer->get_data(); - auto stop = base + buffer->get_record_count(); + PGM(BufferView buffer) + : m_data(nullptr) + , m_bf(new BloomFilter(BF_FPR, buffer.get_tombstone_count(), BF_HASH_FUNCS)) + , m_reccnt(0) + , m_tombstone_cnt(0) + , m_alloc_size(0) { + + m_alloc_size = psudb::sf_aligned_alloc(CACHELINE_SIZE, + buffer.get_record_count() * + sizeof(Wrapped), + (byte**) &m_data); + auto res = sorted_array_from_bufferview(std::move(buffer), m_data, m_bf); + m_reccnt = res.record_count; + m_tombstone_cnt = res.tombstone_count; - std::sort(base, stop, std::less>()); - - K min_key = base->rec.key; - K max_key = (stop - 1)->rec.key; - - while (base < stop) { - if (!(base->is_tombstone()) && (base + 1) < stop) { - if (base->rec == (base + 1)->rec && (base + 1)->is_tombstone()) { - base += 2; - continue; - } - } else if (base->is_deleted()) { - base += 1; - continue; + if (m_reccnt > 0) { + std::vector keys; + for (size_t i=0; iheader &= 3; - m_data[m_reccnt++] = *base; - keys.emplace_back(base->rec.key); - base++; - } - - if (m_reccnt > 0) { m_pgm = pgm::PGMIndex(keys); } } - PGM(PGM** shards, size_t len) - : m_reccnt(0), m_tombstone_cnt(0) { - std::vector>> cursors; - cursors.reserve(len); - - PriorityQueue> pq(len); - + PGM(std::vector shards) + : m_data(nullptr) + , m_bf(nullptr) + , m_reccnt(0) + , m_tombstone_cnt(0) + , m_alloc_size(0) { + size_t attemp_reccnt = 0; size_t tombstone_count = 0; - - for (size_t i = 0; i < len; ++i) { - if (shards[i]) { - auto base = shards[i]->get_data(); - cursors.emplace_back(Cursor{base, base + shards[i]->get_record_count(), 0, shards[i]->get_record_count()}); - attemp_reccnt += shards[i]->get_record_count(); - tombstone_count += shards[i]->get_tombstone_count(); - pq.push(cursors[i].ptr, i); - - } else { - cursors.emplace_back(Cursor>{nullptr, nullptr, 0, 0}); - } - } + auto cursors = build_cursor_vec(shards, &attemp_reccnt, &tombstone_count); - m_alloc_size = (attemp_reccnt * sizeof(Wrapped)) + (CACHELINE_SIZE - (attemp_reccnt * sizeof(Wrapped)) % CACHELINE_SIZE); - assert(m_alloc_size % CACHELINE_SIZE == 0); - m_data = (Wrapped*)std::aligned_alloc(CACHELINE_SIZE, m_alloc_size); - - std::vector keys; - - while (pq.size()) { - auto now = pq.peek(); - auto next = pq.size() > 1 ? pq.peek(1) : queue_record>{nullptr, 0}; - if (!now.data->is_tombstone() && next.data != nullptr && - now.data->rec == next.data->rec && next.data->is_tombstone()) { - - pq.pop(); pq.pop(); - auto& cursor1 = cursors[now.version]; - auto& cursor2 = cursors[next.version]; - if (advance_cursor>(cursor1)) pq.push(cursor1.ptr, now.version); - if (advance_cursor>(cursor2)) pq.push(cursor2.ptr, next.version); - } else { - auto& cursor = cursors[now.version]; - if (!cursor.ptr->is_deleted()) { - m_data[m_reccnt++] = *cursor.ptr; - keys.emplace_back(cursor.ptr->rec.key); - } - pq.pop(); - - if (advance_cursor>(cursor)) pq.push(cursor.ptr, now.version); - } - } + m_bf = new BloomFilter(BF_FPR, tombstone_count, BF_HASH_FUNCS); + m_alloc_size = psudb::sf_aligned_alloc(CACHELINE_SIZE, + attemp_reccnt * sizeof(Wrapped), + (byte **) &m_data); + + auto res = sorted_array_merge(cursors, m_data, m_bf); + m_reccnt = res.record_count; + m_tombstone_cnt = res.tombstone_count; if (m_reccnt > 0) { + std::vector keys; + for (size_t i=0; i(keys); } } ~PGM() { - if (m_data) free(m_data); + free(m_data); + delete m_bf; } Wrapped *point_lookup(const R &rec, bool filter=false) { @@ -186,7 +135,7 @@ public: } size_t get_aux_memory_usage() { - return 0; + return (m_bf) ? m_bf->memory_usage() : 0; } size_t get_lower_bound(const K& key) const { @@ -228,6 +177,7 @@ public: private: Wrapped* m_data; + BloomFilter *m_bf; size_t m_reccnt; size_t m_tombstone_cnt; size_t m_alloc_size; -- cgit v1.2.3 From 402fc269c0aaa671d84a6d15918735ad4b90e6b2 Mon Sep 17 00:00:00 2001 From: Douglas Rumbaugh Date: Fri, 9 Feb 2024 12:30:21 -0500 Subject: Comment updates/fixes --- include/shard/PGM.h | 1 + 1 file changed, 1 insertion(+) (limited to 'include/shard/PGM.h') diff --git a/include/shard/PGM.h b/include/shard/PGM.h index 8031870..e2752ef 100644 --- a/include/shard/PGM.h +++ b/include/shard/PGM.h @@ -9,6 +9,7 @@ * A shard shim around the static version of the PGM learned * index. * + * TODO: The code in this file is very poorly commented. */ #pragma once -- cgit v1.2.3