src/lsm/level.cpp - master - smychkov/SStorage

src/lsm/level.cpp
178 строк7 KB
Андрей Смычков
docs: перевод оставшихся комментариев на русский + актуализация AGENTS
25 апр 2026, 10:08
25 апр 2026, 10:08f2b9fd9
#include "level.hpp"

#include <algorithm>

namespace sstorage {

//============================================================================
// Извлечение seqNo из пути SSTable
//============================================================================
// Имя файла: sst_L{level}_{seqNo}.sst
// Если парсинг не удался — возвращаем 0.
//============================================================================
namespace {

uint64_t extractSeqNoFromPath(const std::string& path) {
    size_t slash = path.find_last_of('/');
    std::string name = (slash == std::string::npos) ? path : path.substr(slash + 1);

    // Ожидаем формат: sst_L<N>_<seqNo>.sst
    size_t underscore = name.find('_', 4);  // пропускаем "sst_"
    if (underscore == std::string::npos) return 0;
    size_t dot = name.rfind(".sst");
    if (dot == std::string::npos || dot <= underscore + 1) return 0;

    std::string seqStr = name.substr(underscore + 1, dot - underscore - 1);
    try {
        return std::stoull(seqStr);
    } catch (...) {
        return 0;
    }
}

}

//============================================================================
// addTable
//============================================================================
void Level::addTable(SSTablePtr table) {
    if (num_ == 0) {
        // L0: новые файлы в начало (они свежее)
        tables_.insert(tables_.begin(), std::move(table));
    } else {
        // L1+: вставка в отсортированное место
        auto it = std::lower_bound(tables_.begin(), tables_.end(), table,
            [](const SSTablePtr& a, const SSTablePtr& b) {
                return a->minKey() < b->minKey();
            });
        tables_.insert(it, std::move(table));
    }
}

//============================================================================
// Удаление таблицы из уровня по пути файла
//============================================================================
bool Level::removeTable(const std::string& path) {
    auto it = std::find_if(tables_.begin(), tables_.end(),
        [&](const SSTablePtr& t) { return t->path() == path; });
    if (it == tables_.end()) return false;
    tables_.erase(it);
    return true;
}

//============================================================================
// replaceTables — атомарный swap для compaction
//============================================================================
void Level::replaceTables(const std::vector<std::string>& removePaths,
                          const std::vector<SSTablePtr>& addTables) {
    for (const auto& p : removePaths) {
        removeTable(p);
    }
    for (const auto& t : addTables) {
        addTable(t);
    }
}

//============================================================================
// overlapping — все таблицы, пересекающие [from, to]
//============================================================================
std::vector<SSTablePtr> Level::overlapping(const std::string& from,
                                           const std::string& to) const {
    std::vector<SSTablePtr> result;
    for (const auto& t : tables_) {
        if (t->overlaps(from, to)) {
            result.push_back(t);
        }
    }
    return result;
}

//============================================================================
// findTable — только для L1+
//============================================================================
SSTablePtr Level::findTable(const std::string& key) const {
    if (num_ == 0) return nullptr;   // для L0 не поддерживаем (могут перекрываться)

    // Бинпоиск: ищем таблицу с minKey <= key <= maxKey.
    // Так как L1+ не перекрываются, такая таблица максимум одна.
    auto it = std::upper_bound(tables_.begin(), tables_.end(), key,
        [](const std::string& k, const SSTablePtr& t) {
            return k < t->minKey();
        });
    if (it == tables_.begin()) return nullptr;
    --it;
    if (key >= (*it)->minKey() && key <= (*it)->maxKey()) {
        return *it;
    }
    return nullptr;
}

//============================================================================
// Суммарное количество записей на уровне (по всем SSTable)
//============================================================================
uint64_t Level::totalRecords() const {
    uint64_t total = 0;
    for (const auto& t : tables_) total += t->numRecords();
    return total;
}

//============================================================================
// sortTables — используется при recovery
//============================================================================
void Level::sortTables() {
    if (num_ == 0) {
        // L0: seqNo DESC (новые первые)
        std::sort(tables_.begin(), tables_.end(),
            [](const SSTablePtr& a, const SSTablePtr& b) {
                return extractSeqNoFromPath(a->path()) >
                       extractSeqNoFromPath(b->path());
            });
    } else {
        // L1+: minKey ASC
        std::sort(tables_.begin(), tables_.end(),
            [](const SSTablePtr& a, const SSTablePtr& b) {
                return a->minKey() < b->minKey();
            });
    }
}

//============================================================================
// resolveOverlaps — для L1+ после recovery без manifest
//============================================================================
// Если compaction упал между созданием новых и удалением старых файлов,
// на диске окажутся перекрывающиеся файлы. Оставляем файл с большим seqNo
// (это новый, полученный в compaction), остальные — в toDelete.
//============================================================================
void Level::resolveOverlaps(std::vector<std::string>& toDelete) {
    if (num_ == 0) return;  // L0 могут перекрываться — это нормально
    if (tables_.size() < 2) return;

    sortTables();   // по minKey ASC

    std::vector<SSTablePtr> keep;
    for (auto& t : tables_) {
        if (keep.empty()) {
            keep.push_back(t);
            continue;
        }

        auto& prev = keep.back();
        // Перекрытие: prev.maxKey >= t.minKey
        if (prev->maxKey() >= t->minKey()) {
            // Оставляем того, у кого seqNo больше
            uint64_t seqPrev = extractSeqNoFromPath(prev->path());
            uint64_t seqCur = extractSeqNoFromPath(t->path());
            if (seqCur > seqPrev) {
                toDelete.push_back(prev->path());
                keep.back() = t;
            } else {
                toDelete.push_back(t->path());
            }
        } else {
            keep.push_back(t);
        }
    }
    tables_ = std::move(keep);
}

}