第二部分：构建系统与基础设施
2.1 CMake构建配置
企业级C++项目需要可靠的构建系统。CMake是C/C++项目的事实标准，支持跨平台构建。
# CMakeLists.txt - 顶层配置
cmake_minimum_required(VERSION 3.15)
project(KivaDB VERSION 1.0.0 LANGUAGES CXX)
# ========== C++标准配置 ==========
set(CMAKE_CXX_STANDARD 17)
set(CMAKE_CXX_STANDARD_REQUIRED ON)
set(CMAKE_CXX_EXTENSIONS OFF)
# ========== 编译选项 ==========
# 根据构建类型设置不同的编译选项
if(CMAKE_BUILD_TYPE STREQUAL "Debug")
# Debug模式：关闭优化，开启调试信息，开启地址消毒器
add_compile_options(-g -O0 -Wall -Wextra -Werror -Wno-unused-parameter)
add_compile_options(-fsanitize=address -fsanitize=undefined)
add_link_options(-fsanitize=address -fsanitize=undefined)
set(CMAKE_CXX_FLAGS_DEBUG "-DDEBUG")
else()
# Release模式：开启优化，开启LTO，生成调试符号便于线上排查
add_compile_options(-O3 -DNDEBUG -flto -march=native)
add_compile_options(-g -fno-omit-frame-pointer) # 保留帧指针，便于perf采样
add_link_options(-flto)
endif()
# ========== 平台检测 ==========
if(CMAKE_SYSTEM_NAME STREQUAL "Linux")
add_compile_definitions(__LINUX__)
set(PLATFORM_LIBS pthread dl rt)
# 检查epoll支持
include(CheckCXXSymbolExists)
check_cxx_symbol_exists(epoll_create sys/epoll.h HAVE_EPOLL)
if(NOT HAVE_EPOLL)
message(FATAL_ERROR "epoll is required on Linux")
endif()
elseif(CMAKE_SYSTEM_NAME STREQUAL "Darwin")
add_compile_definitions(__MACOS__)
set(PLATFORM_LIBS pthread)
# macOS使用kqueue
add_compile_definitions(HAVE_KQUEUE)
elseif(CMAKE_SYSTEM_NAME STREQUAL "Windows")
add_compile_definitions(__WINDOWS__)
set(PLATFORM_LIBS ws2_32)
# Windows使用IOCP
add_compile_definitions(HAVE_IOCP)
endif()
# ========== 第三方依赖 ==========
# 设置第三方库路径
set(THIRD_PARTY_DIR ${CMAKE_SOURCE_DIR}/third_party)
# jemalloc - 高性能内存分配器
option(USE_JEMALLOC "Use jemalloc as memory allocator" ON)
if(USE_JEMALLOC)
find_package(jemalloc)
if(jemalloc_FOUND)
add_compile_definitions(USE_JEMALLOC)
set(EXTRA_LIBS ${EXTRA_LIBS} jemalloc::jemalloc)
message(STATUS "Using jemalloc for memory allocation")
else()
message(STATUS "jemalloc not found, using system malloc")
endif()
endif()
# Google Test - 单元测试
option(BUILD_TESTS "Build unit tests" ON)
if(BUILD_TESTS)
include(FetchContent)
FetchContent_Declare(
googletest
GIT_REPOSITORY https://github.com/google/googletest.git
GIT_TAG release-1.12.1
)
FetchContent_MakeAvailable(googletest)
enable_testing()
endif()
# Google Benchmark - 性能测试
option(BUILD_BENCHMARKS "Build benchmarks" OFF)
if(BUILD_BENCHMARKS)
FetchContent_Declare(
benchmark
GIT_REPOSITORY https://github.com/google/benchmark.git
GIT_TAG v1.7.1
)
FetchContent_MakeAvailable(benchmark)
endif()
# ========== 源代码组织 ==========
# 核心模块
set(CORE_SOURCES
src/main.cpp
src/core/server.cpp
src/core/config.cpp
src/network/event_loop.cpp
src/network/channel.cpp
src/network/acceptor.cpp
src/network/connection.cpp
src/network/tcp_server.cpp
src/protocol/resp.cpp
src/protocol/command.cpp
src/datastore/dict.cpp
src/datastore/sds.cpp
src/datastore/object.cpp
src/datastore/expire.cpp
src/persistence/rdb.cpp
src/persistence/aof.cpp
src/replication/replication.cpp
src/replication/heartbeat.cpp
src/cluster/consistent_hash.cpp
src/cluster/cluster.cpp
src/thread/thread_pool.cpp
src/memory/allocator.cpp
src/memory/slab.cpp
src/utils/logger.cpp
src/utils/timer.cpp
src/utils/hash.cpp
src/utils/crc64.cpp
)
# 公共头文件目录
include_directories(
src/include
src
${CMAKE_SOURCE_DIR}
)
# 生成可执行文件
add_executable(kivadb ${CORE_SOURCES})
# 链接库
target_link_libraries(kivadb
${PLATFORM_LIBS}
${EXTRA_LIBS}
)
# ========== 编译优化选项 ==========
# 开启LTO（链接时优化）
set_target_properties(kivadb PROPERTIES INTERPROCEDURAL_OPTIMIZATION TRUE)
# 为特定目标开启高级优化
if(CMAKE_CXX_COMPILER_ID STREQUAL "GNU" OR CMAKE_CXX_COMPILER_ID STREQUAL "Clang")
target_compile_options(kivadb PRIVATE -fno-rtti -fno-exceptions)
endif()
# ========== 安装配置 ==========
install(TARGETS kivadb DESTINATION bin)
install(FILES config/kivadb.conf DESTINATION etc/kivadb)
install(DIRECTORY scripts/ DESTINATION bin)
# ========== 测试配置 ==========
if(BUILD_TESTS)
add_subdirectory(tests)
endif()
# ========== 打包配置 ==========
set(CPACK_GENERATOR "TGZ;ZIP")
set(CPACK_PACKAGE_NAME "kivadb")
set(CPACK_PACKAGE_VERSION ${PROJECT_VERSION})
set(CPACK_PACKAGE_DESCRIPTION_SUMMARY "High Performance Distributed KV Store")
include(CPack)
# 打印配置摘要
message(STATUS "================== KivaDB Configuration ==================")
message(STATUS "Version: ${PROJECT_VERSION}")
message(STATUS "Build Type: ${CMAKE_BUILD_TYPE}")
message(STATUS "C++ Standard: C++${CMAKE_CXX_STANDARD}")
message(STATUS "Platform: ${CMAKE_SYSTEM_NAME}")
message(STATUS "Use jemalloc: ${USE_JEMALLOC}")
message(STATUS "Build Tests: ${BUILD_TESTS}")
message(STATUS "Build Benchmarks: ${BUILD_BENCHMARKS}")
message(STATUS "===========================================================")
2.2 日志系统
日志是企业级系统的眼睛，对于问题排查、性能分析、安全审计至关重要。
// src/utils/logger.h
#ifndef KIVADB_LOGGER_H
#define KIVADB_LOGGER_H
#include <string>
#include <memory>
#include <cstdarg>
#include <mutex>
namespace kivadb {
// 日志级别
enum class LogLevel {
DEBUG = 0,
INFO = 1,
WARN = 2,
ERROR = 3,
FATAL = 4
};
// 日志系统 - 单例模式
class Logger {
public:
// 获取单例实例
static Logger& getInstance() {
static Logger instance;
return instance;
}
// 设置日志级别
void setLevel(LogLevel level) { level_ = level; }
// 设置日志文件路径
void setLogFile(const std::string& filename);
// 设置是否输出到控制台
void setConsoleOutput(bool enable) { console_output_ = enable; }
// 日志输出宏
void log(LogLevel level, const char* file, int line, const char* format, ...);
private:
Logger() = default;
~Logger();
Logger(const Logger&) = delete;
Logger& operator=(const Logger&) = delete;
std::string getLevelString(LogLevel level);
std::string getCurrentTime();
void writeToFile(const std::string& message);
LogLevel level_ = LogLevel::INFO;
std::string log_filename_;
FILE* log_file_ = nullptr;
bool console_output_ = true;
std::mutex mutex_;
};
// 日志宏定义
#define LOG_DEBUG(format, ...) \
kivadb::Logger::getInstance().log(kivadb::LogLevel::DEBUG, __FILE__, __LINE__, format, ##__VA_ARGS__)
#define LOG_INFO(format, ...) \
kivadb::Logger::getInstance().log(kivadb::LogLevel::INFO, __FILE__, __LINE__, format, ##__VA_ARGS__)
#define LOG_WARN(format, ...) \
kivadb::Logger::getInstance().log(kivadb::LogLevel::WARN, __FILE__, __LINE__, format, ##__VA_ARGS__)
#define LOG_ERROR(format, ...) \
kivadb::Logger::getInstance().log(kivadb::LogLevel::ERROR, __FILE__, __LINE__, format, ##__VA_ARGS__)
#define LOG_FATAL(format, ...) \
kivadb::Logger::getInstance().log(kivadb::LogLevel::FATAL, __FILE__, __LINE__, format, ##__VA_ARGS__)
} // namespace kivadb
#endif // KIVADB_LOGGER_H
// src/utils/logger.cpp
#include "logger.h"
#include <cstdio>
#include <ctime>
#include <cstdarg>
#include <sys/time.h>
namespace kivadb {
Logger::~Logger() {
if (log_file_) {
fclose(log_file_);
}
}
void Logger::setLogFile(const std::string& filename) {
std::lock_guard<std::mutex> lock(mutex_);
log_filename_ = filename;
if (log_file_) {
fclose(log_file_);
}
log_file_ = fopen(filename.c_str(), "a");
if (!log_file_) {
fprintf(stderr, "Failed to open log file: %s\n", filename.c_str());
}
}
std::string Logger::getLevelString(LogLevel level) {
switch (level) {
case LogLevel::DEBUG: return "DEBUG";
case LogLevel::INFO: return "INFO ";
case LogLevel::WARN: return "WARN ";
case LogLevel::ERROR: return "ERROR";
case LogLevel::FATAL: return "FATAL";
default: return "UNKNOWN";
}
}
std::string Logger::getCurrentTime() {
struct timeval tv;
gettimeofday(&tv, nullptr);
struct tm tm_info;
localtime_r(&tv.tv_sec, &tm_info);
char buffer[64];
strftime(buffer, sizeof(buffer), "%Y-%m-%d %H:%M:%S", &tm_info);
char result[64];
snprintf(result, sizeof(result), "%s.%03ld", buffer, tv.tv_usec / 1000);
return std::string(result);
}
void Logger::writeToFile(const std::string& message) {
if (log_file_) {
fprintf(log_file_, "%s\n", message.c_str());
fflush(log_file_);
}
}
void Logger::log(LogLevel level, const char* file, int line, const char* format, ...) {
if (level < level_) return;
// 格式化消息
char buffer[4096];
va_list args;
va_start(args, format);
vsnprintf(buffer, sizeof(buffer), format, args);
va_end(args);
// 构建日志行
std::string time_str = getCurrentTime();
const char* level_str = getLevelString(level);
// 提取文件名（去掉路径）
const char* filename = strrchr(file, '/');
if (filename) filename++; else filename = file;
char log_line[8192];
snprintf(log_line, sizeof(log_line), "[%s] [%s] [%s:%d] %s",
time_str.c_str(), level_str, filename, line, buffer);
// 输出到控制台
if (console_output_) {
fprintf(stderr, "%s\n", log_line);
fflush(stderr);
}
// 输出到文件
std::lock_guard<std::mutex> lock(mutex_);
writeToFile(log_line);
// FATAL级别直接终止程序
if (level == LogLevel::FATAL) {
abort();
}
}
} // namespace kivadb
2.3 不可拷贝基类
// src/utils/noncopyable.h
#ifndef KIVADB_NONCOPYABLE_H
#define KIVADB_NONCOPYABLE_H
namespace kivadb {
/**
* 不可拷贝基类
*
* 继承此类可以禁止拷贝构造和赋值操作。
* 适用于管理资源的类（如文件句柄、网络连接、互斥锁等）。
*
* 示例：
* class MyClass : public NonCopyable {
* // 此类不能进行拷贝
* };
*/
class NonCopyable {
protected:
NonCopyable() = default;
~NonCopyable() = default;
NonCopyable(const NonCopyable&) = delete;
NonCopyable& operator=(const NonCopyable&) = delete;
// 移动构造和移动赋值可以保留
NonCopyable(NonCopyable&&) = default;
NonCopyable& operator=(NonCopyable&&) = default;
};
} // namespace kivadb
#endif // KIVADB_NONCOPYABLE_H
第三部分：高性能数据结构
3.1 SDS（Simple Dynamic String）实现
C语言字符串的痛点：获取长度需要O(n)遍历、缓冲区溢出风险、二进制不安全。SDS是Redis采用的高性能字符串实现，我们将其作为KivaDB的基础组件。
// src/datastore/sds.h
#ifndef KIVADB_SDS_H
#define KIVADB_SDS_H
#include <stddef.h>
#include <stdint.h>
namespace kivadb {
/* SDS头部类型（根据字符串长度选择，节省内存）*/
#define SDS_TYPE_5 0 // 长度 < 32
#define SDS_TYPE_8 1 // 长度 < 256
#define SDS_TYPE_16 2 // 长度 < 64K
#define SDS_TYPE_32 3 // 长度 < 4GB
#define SDS_TYPE_64 4 // 长度 < 2^63
/* 内部使用的SDS头（内存布局紧凑，使用__attribute__((packed))避免内存对齐）*/
struct __attribute__((__packed__)) sdshdr8 {
uint8_t len; // 已使用长度
uint8_t alloc; // 分配的总长度（不含header和'\0'）
unsigned char flags; // 类型标识（低3位）
char buf[];
};
struct __attribute__((__packed__)) sdshdr16 {
uint16_t len;
uint16_t alloc;
unsigned char flags;
char buf[];
};
struct __attribute__((__packed__)) sdshdr32 {
uint32_t len;
uint32_t alloc;
unsigned char flags;
char buf[];
};
struct __attribute__((__packed__)) sdshdr64 {
uint64_t len;
uint64_t alloc;
unsigned char flags;
char buf[];
};
/* SDS类型定义 - 指向buf的指针 */
typedef char* sds;
/* ========== API声明 ========== */
// 创建与销毁
sds sdsnew(const char* init);
sds sdsnewlen(const void* init, size_t initlen);
sds sdsdup(const sds s);
void sdsfree(sds s);
// 信息获取
size_t sdslen(const sds s);
size_t sdsavail(const sds s);
size_t sdsAllocSize(const sds s);
// 修改操作
sds sdscatlen(sds s, const void* t, size_t len);
sds sdscat(sds s, const char* t);
sds sdscpylen(sds s, const char* t, size_t len);
sds sdscpy(sds s, const char* t);
sds sdsgrowzero(sds s, size_t len);
sds sdscatprintf(sds s, const char* fmt, ...);
void sdstrim(sds s, const char* cset);
void sdsrange(sds s, int start, int end);
// 比较
int sdscmp(const sds s1, const sds s2);
// 分割
sds* sdssplitlen(const char* s, int len, const char* sep, int seplen, int* count);
void sdsfreesplitres(sds* tokens, int count);
// 大小写转换
void sdstolower(sds s);
void sdstoupper(sds s);
// 数值转换
sds sdsfromlonglong(long long value);
} // namespace kivadb
#endif // KIVADB_SDS_H
// src/datastore/sds.cpp
#include "sds.h"
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cstdarg>
#include <algorithm>
namespace kivadb {
// 辅助函数：获取头大小
static inline size_t sdsHdrSize(char type) {
switch (type & SDS_TYPE_MASK) {
case SDS_TYPE_5: return sizeof(struct sdshdr5);
case SDS_TYPE_8: return sizeof(struct sdshdr8);
case SDS_TYPE_16: return sizeof(struct sdshdr16);
case SDS_TYPE_32: return sizeof(struct sdshdr32);
case SDS_TYPE_64: return sizeof(struct sdshdr64);
default: return 0;
}
}
// 辅助函数：根据长度确定类型
static inline char sdsReqType(size_t len) {
if (len < 32) return SDS_TYPE_5;
if (len < 256) return SDS_TYPE_8;
if (len < 65536) return SDS_TYPE_16;
#if (LONG_MAX == LLONG_MAX)
if (len < 4294967296LL) return SDS_TYPE_32;
return SDS_TYPE_64;
#else
return SDS_TYPE_32;
#endif
}
// 获取SDS头指针
static inline struct sdshdr8* sdsheader8(const sds s) {
return (struct sdshdr8*)(s - sizeof(struct sdshdr8));
}
static inline struct sdshdr16* sdsheader16(const sds s) {
return (struct sdshdr16*)(s - sizeof(struct sdshdr16));
}
static inline struct sdshdr32* sdsheader32(const sds s) {
return (struct sdshdr32*)(s - sizeof(struct sdshdr32));
}
static inline struct sdshdr64* sdsheader64(const sds s) {
return (struct sdshdr64*)(s - sizeof(struct sdshdr64));
}
// 获取SDS类型
static inline char sdsflags(const sds s) {
return s[-1];
}
// 获取SDS长度 - O(1)时间复杂度！
size_t sdslen(const sds s) {
if (!s) return 0;
unsigned char flags = sdsflags(s);
switch (flags & SDS_TYPE_MASK) {
case SDS_TYPE_5:
return (size_t)(((struct sdshdr5*)s)->buf[-1] >> 3);
case SDS_TYPE_8:
return sdsheader8(s)->len;
case SDS_TYPE_16:
return sdsheader16(s)->len;
case SDS_TYPE_32:
return sdsheader32(s)->len;
case SDS_TYPE_64:
return sdsheader64(s)->len;
default:
return 0;
}
}
// 获取可用空间
size_t sdsavail(const sds s) {
if (!s) return 0;
unsigned char flags = sdsflags(s);
switch (flags & SDS_TYPE_MASK) {
case SDS_TYPE_5: return 0;
case SDS_TYPE_8: return sdsheader8(s)->alloc - sdsheader8(s)->len;
case SDS_TYPE_16: return sdsheader16(s)->alloc - sdsheader16(s)->len;
case SDS_TYPE_32: return sdsheader32(s)->alloc - sdsheader32(s)->len;
case SDS_TYPE_64: return sdsheader64(s)->alloc - sdsheader64(s)->len;
default: return 0;
}
}
// 创建新SDS
sds sdsnewlen(const void* init, size_t initlen) {
char type = sdsReqType(initlen);
if (type == SDS_TYPE_5 && initlen == 0) type = SDS_TYPE_8;
size_t hdrlen = sdsHdrSize(type);
char* sh = (char*)malloc(hdrlen + initlen + 1);
if (!sh) return nullptr;
sds s = sh + hdrlen;
// 设置头部
switch (type) {
case SDS_TYPE_5: {
struct sdshdr5* h = (struct sdshdr5*)sh;
*((uint8_t*)h) = (uint8_t)((initlen << 3) | SDS_TYPE_5);
break;
}
case SDS_TYPE_8: {
struct sdshdr8* h = (struct sdshdr8*)sh;
h->len = initlen;
h->alloc = initlen;
h->flags = type;
break;
}
case SDS_TYPE_16: {
struct sdshdr16* h = (struct sdshdr16*)sh;
h->len = initlen;
h->alloc = initlen;
h->flags = type;
break;
}
case SDS_TYPE_32: {
struct sdshdr32* h = (struct sdshdr32*)sh;
h->len = initlen;
h->alloc = initlen;
h->flags = type;
break;
}
case SDS_TYPE_64: {
struct sdshdr64* h = (struct sdshdr64*)sh;
h->len = initlen;
h->alloc = initlen;
h->flags = type;
break;
}
}
if (initlen && init) {
memcpy(s, init, initlen);
}
s[initlen] = '\0';
return s;
}
sds sdsnew(const char* init) {
return sdsnewlen(init, init ? strlen(init) : 0);
}
// 空间预分配（Redis经典策略）
sds sdsMakeRoomFor(sds s, size_t addlen) {
size_t avail = sdsavail(s);
if (avail >= addlen) return s;
size_t len = sdslen(s);
size_t newlen = len + addlen;
char type = sdsReqType(newlen);
size_t hdrlen = sdsHdrSize(type);
char* sh;
if (type == SDS_TYPE_5) type = SDS_TYPE_8;
size_t old_hdrlen = sdsHdrSize(sdsflags(s));
// 核心策略：小于1MB时翻倍扩容，大于1MB时每次增加1MB
if (newlen < SDS_MAX_PREALLOC) {
newlen *= 2;
} else {
newlen += SDS_MAX_PREALLOC;
}
type = sdsReqType(newlen);
hdrlen = sdsHdrSize(type);
if (type == sdsflags(s)) {
sh = (char*)realloc(s - old_hdrlen, hdrlen + newlen + 1);
if (!sh) return nullptr;
s = sh + hdrlen;
} else {
sh = (char*)malloc(hdrlen + newlen + 1);
if (!sh) return nullptr;
memcpy(sh + hdrlen, s, len + 1);
free(s - old_hdrlen);
s = sh + hdrlen;
}
// 更新头部
switch (type) {
case SDS_TYPE_8: {
struct sdshdr8* h = (struct sdshdr8*)(s - hdrlen);
h->len = len;
h->alloc = newlen;
h->flags = type;
break;
}
case SDS_TYPE_16: {
struct sdshdr16* h = (struct sdshdr16*)(s - hdrlen);
h->len = len;
h->alloc = newlen;
h->flags = type;
break;
}
case SDS_TYPE_32: {
struct sdshdr32* h = (struct sdshdr32*)(s - hdrlen);
h->len = len;
h->alloc = newlen;
h->flags = type;
break;
}
case SDS_TYPE_64: {
struct sdshdr64* h = (struct sdshdr64*)(s - hdrlen);
h->len = len;
h->alloc = newlen;
h->flags = type;
break;
}
}
return s;
}
// 追加字符串
sds sdscatlen(sds s, const void* t, size_t len) {
size_t curlen = sdslen(s);
s = sdsMakeRoomFor(s, len);
if (!s) return nullptr;
memcpy(s + curlen, t, len);
s[curlen + len] = '\0';
// 更新长度
unsigned char flags = sdsflags(s);
switch (flags & SDS_TYPE_MASK) {
case SDS_TYPE_8:
sdsheader8(s)->len = curlen + len;
break;
case SDS_TYPE_16:
sdsheader16(s)->len = curlen + len;
break;
case SDS_TYPE_32:
sdsheader32(s)->len = curlen + len;
break;
case SDS_TYPE_64:
sdsheader64(s)->len = curlen + len;
break;
}
return s;
}
sds sdscat(sds s, const char* t) {
return sdscatlen(s, t, strlen(t));
}
} // namespace kivadb
3.2 高性能哈希表实现
https://hllft.cn/category/tech-trends.html
哈希表是KV存储系统的核心数据结构。KivaDB实现了渐进式哈希表，解决单次扩容导致的服务卡顿问题。
// src/datastore/dict.h
#ifndef KIVADB_DICT_H
#define KIVADB_DICT_H
#include <stdint.h>
#include <cstddef>
namespace kivadb {
/* 哈希函数类型 */
typedef uint64_t (*DictHashFunction)(const void* key, size_t len);
/* 键值对节点 */
struct DictEntry {
void* key;
union {
void* val;
uint64_t u64;
int64_t s64;
} v;
struct DictEntry* next; // 链地址法解决冲突
};
/* 字典类型（多态操作）*/
struct DictType {
uint64_t (*hashFunction)(const void* key, size_t len);
void* (*keyDup)(void* privdata, const void* key);
void* (*valDup)(void* privdata, const void* obj);
int (*keyCompare)(void* privdata, const void* key1, const void* key2);
void (*keyDestructor)(void* privdata, void* key);
void (*valDestructor)(void* privdata, void* obj);
};
/* 哈希表（一个字典有两个哈希表，用于渐进式rehash）*/
struct Dictht {
DictEntry** table; // 哈希桶数组
unsigned long size; // 哈希表大小
unsigned long sizemask; // 用于计算索引的掩码（size-1）
unsigned long used; // 已使用节点数
};
/* 字典主结构 */
struct Dict {
DictType* type; // 类型特定函数
void* privdata; // 私有数据
Dictht ht[2]; // 两个哈希表（ht[1]用于rehash）
int rehashidx; // rehash进度（-1表示未进行）
int iterators; // 当前运行的迭代器数量
};
/* 迭代器 */
struct DictIterator {
Dict* d;
int table; // 当前遍历的哈希表索引（0或1）
int index; // 当前桶索引
int safe; // 是否安全迭代器（允许修改）
DictEntry* entry; // 当前节点
DictEntry* nextEntry; // 下一个节点
};
/* API声明 */
Dict* dictCreate(DictType* type, void* privdata);
int dictExpand(Dict* d, unsigned long size);
int dictRehash(Dict* d, int n);
int dictAdd(Dict* d, void* key, void* val);
DictEntry* dictFind(Dict* d, const void* key);
void* dictFetchValue(Dict* d, const void* key);
int dictDelete(Dict* d, const void* key);
void dictRelease(Dict* d);
DictIterator* dictGetIterator(Dict* d);
DictEntry* dictNext(DictIterator* iter);
void dictReleaseIterator(DictIterator* iter);
} // namespace kivadb
#endif // KIVADB_DICT_H
// src/datastore/dict.cpp
#include "dict.h"
#include <cstdlib>
#include <cstring>
#include <cassert>
namespace kivadb {
#define DICT_HT_INITIAL_SIZE 4
#define DICT_HT_EXPAND_FACTOR 1
#define DICT_HT_SHRINK_FACTOR 10
/* 哈希函数（MurmurHash2的简化版本）*/
static uint64_t dictGenHashFunction(const void* key, size_t len) {
const uint64_t m = 0xc6a4a7935bd1e995ULL;
const int r = 47;
uint64_t h = 0x1234567890abcdefULL ^ (len * m);
const unsigned char* data = (const unsigned char*)key;
const unsigned char* end = data + (len & ~7);
while (data != end) {
uint64_t k = *(uint64_t*)data;
k *= m;
k ^= k >> r;
k *= m;
h ^= k;
h *= m;
data += 8;
}
switch (len & 7) {
case 7: h ^= (uint64_t)data[6] << 48;
case 6: h ^= (uint64_t)data[5] << 40;
case 5: h ^= (uint64_t)data[4] << 32;
case 4: h ^= (uint64_t)data[3] << 24;
case 3: h ^= (uint64_t)data[2] << 16;
case 2: h ^= (uint64_t)data[1] << 8;
case 1: h ^= (uint64_t)data[0];
h *= m;
}
h ^= h >> r;
h *= m;
h ^= h >> r;
return h;
}
/* 默认键值复制函数 */
static void* dictDupDefault(void* privdata, const void* key) {
return (void*)key;
}
/* 默认键比较函数 */
static int dictKeyCompareDefault(void* privdata, const void* key1, const void* key2) {
return key1 == key2;
}
/* 创建字典 */
Dict* dictCreate(DictType* type, void* privdata) {
Dict* d = (Dict*)malloc(sizeof(Dict));
if (!d) return nullptr;
d->type = type ? type : &defaultDictType;
d->privdata = privdata;
d->rehashidx = -1;
d->iterators = 0;
d->ht[0] = { nullptr, 0, 0, 0 };
d->ht[1] = { nullptr, 0, 0, 0 };
if (dictExpand(d, DICT_HT_INITIAL_SIZE) != 0) {
free(d);
return nullptr;
}
return d;
}
/* 扩容/缩容核心函数 */
int dictExpand(Dict* d, unsigned long size) {
// 如果正在rehash，不能再次扩容
if (d->rehashidx != -1) return -1;
// 确保size是2的幂
unsigned long realsize = DICT_HT_INITIAL_SIZE;
while (realsize < size) realsize <<= 1;
// 创建新哈希表
Dictht n;
n.size = realsize;
n.sizemask = realsize - 1;
n.used = 0;
n.table = (DictEntry**)calloc(realsize, sizeof(DictEntry*));
if (!n.table) return -1;
// 如果当前哈希表为空，直接使用新表
if (d->ht[0].table == nullptr) {
d->ht[0] = n;
return 0;
}
// 否则设置ht[1]为新表，启动渐进式rehash
d->ht[1] = n;
d->rehashidx = 0;
return 0;
}
/* 渐进式rehash（核心：分步迁移，避免单次卡顿）*/
int dictRehash(Dict* d, int n) {
// 空转保护
if (d->rehashidx == -1) return 0;
int empty_visits = n * 10; // 最多跳过10*n个空桶
while (n-- && d->ht[0].used != 0) {
// 跳过空桶（最多跳过empty_visits次）
while (d->ht[0].table[d->rehashidx] == nullptr) {
d->rehashidx++;
if (--empty_visits == 0) return 1;
}
// 迁移当前桶的所有节点
DictEntry* de = d->ht[0].table[d->rehashidx];
while (de) {
DictEntry* next = de->next;
// 计算在新表中的索引
unsigned long h = dictHashKey(d, de->key) & d->ht[1].sizemask;
de->next = d->ht[1].table[h];
d->ht[1].table[h] = de;
d->ht[0].used--;
d->ht[1].used++;
de = next;
}
d->ht[0].table[d->rehashidx] = nullptr;
d->rehashidx++;
}
// 检查rehash是否完成
if (d->ht[0].used == 0) {
free(d->ht[0].table);
d->ht[0] = d->ht[1];
d->ht[1] = { nullptr, 0, 0, 0 };
d->rehashidx = -1;
return 0;
}
return 1;
}
/* 添加键值对 */
int dictAdd(Dict* d, void* key, void* val) {
// 检查是否需要扩容
if (d->ht[0].used >= d->ht[0].size && d->rehashidx == -1) {
dictExpand(d, d->ht[0].used * 2);
}
// 如果正在rehash，推进
if (d->rehashidx != -1) dictRehash(d, 1);
// 计算哈希值
unsigned long h = dictHashKey(d, key);
int table = d->rehashidx != -1 ? 1 : 0;
unsigned long idx = h & d->ht[table].sizemask;
// 检查键是否已存在
DictEntry* de = d->ht[table].table[idx];
while (de) {
if (dictCompareKeys(d, key, de->key)) return -1;
de = de->next;
}
// 创建新节点
de = (DictEntry*)malloc(sizeof(DictEntry));
if (!de) return -1;
de->key = dictDupKey(d, key);
de->v.val = dictDupVal(d, val);
de->next = d->ht[table].table[idx];
d->ht[table].table[idx] = de;
d->ht[table].used++;
return 0;
}
/* 查找键 */
DictEntry* dictFind(Dict* d, const void* key) {
// 如果正在rehash，执行一步rehash（每次查找都推进）
if (d->rehashidx != -1) {
dictRehash(d, 1);
}
unsigned long h = dictHashKey(d, key);
// 先在ht[0]查找
DictEntry* de = d->ht[0].table[h & d->ht[0].sizemask];
while (de) {
if (dictCompareKeys(d, key, de->key)) return de;
de = de->next;
}
// 如果正在rehash，再到ht[1]查找
if (d->rehashidx != -1) {
de = d->ht[1].table[h & d->ht[1].sizemask];
while (de) {
if (dictCompareKeys(d, key, de->key)) return de;
de = de->next;
}
}
return nullptr;
}
} // namespace kivadb
