[꽥꽥 DuckDB Internals] 1. 스토리지 관리 (storage manager, block manager)

참고한 파일들:
src/storage/storage_manager.cpp
src/include/duckdb/storage/storage_manager.hpp
src/storage/single_file_block_manager.cpp
src/include/duckdb/storage/single_file_block_manager.hpp

 

1. Storage Manager (추상 클래스)

• DuckDB는 StorageManger를 base class로 하여 SingleFileStorageManger를 구현하였다. 현재까지는 single file만을 지원하기 때문에 자연스럽다.
• StorageManager에는 db, path, wal, read_only, load_complete 등의 멤버변수가 있다. 

//! StorageManager is responsible for managing the physical storage of the
//! database on disk
class StorageManager {
public:
	StorageManager(AttachedDatabase &db, string path, bool read_only);
	virtual ~StorageManager();

/* (중략) */

protected:
	virtual void LoadDatabase(const optional_idx block_alloc_size) = 0;

protected:
	//! The database this storage manager belongs to
	AttachedDatabase &db;
	//! The path of the database
	string path;
	//! The WriteAheadLog of the storage manager
	unique_ptr<WriteAheadLog> wal;
	//! Whether or not the database is opened in read-only mode
	bool read_only;
	//! When loading a database, we do not yet set the wal-field. Therefore, GetWriteAheadLog must
	//! return nullptr when loading a database
	bool load_complete = false;

/* (하략) */
};

 

2. SingleFileStorageManager (구상 클래스)

• 실제로 사용되는 SingleFileStorageManager가 주로 수행하는 기능들은 다음의 override 함수들에 구현되어 있다. 주로 보면 checkpoint와 관련된 기능들, 그리고 처음에 한번 데이터베이스를 불러오는 기능이다. (체크포인트에 대한 분석은 이후로 미룬다)

public:
	bool AutomaticCheckpoint(idx_t estimated_wal_bytes) override;
	unique_ptr<StorageCommitState> GenStorageCommitState(WriteAheadLog &wal) override;
	bool IsCheckpointClean(MetaBlockPointer checkpoint_id) override;
	void CreateCheckpoint(CheckpointOptions options) override;
	DatabaseSize GetDatabaseSize() override;
	vector<MetadataBlockInfo> GetMetadataInfo() override;
	shared_ptr<TableIOManager> GetTableIOManager(BoundCreateTableInfo *info) override;
	BlockManager &GetBlockManager() override;

protected:
	void LoadDatabase(const optional_idx block_alloc_size) override;

• LoadDatabase의 구현을 상세히 따라가보자. 먼저 in-memory인 경우엔 간단하게 InMemoryBlockManager를 만들고 끝나게 되지만, 우리는 disk-based 경로 위주로 살펴볼 것이므로 계속 진행하자.

void SingleFileStorageManager::LoadDatabase(StorageOptions storage_options) {
	if (InMemory()) {
		block_manager = make_uniq<InMemoryBlockManager>(BufferManager::GetBufferManager(db), DEFAULT_BLOCK_ALLOC_SIZE);
		table_io_manager = make_uniq<SingleFileTableIOManager>(*block_manager, DEFAULT_ROW_GROUP_SIZE);
		return;
	}

• StorageManager에 적용되는 여러 옵션들을 적용한다. 한 가지 눈에 띄는 것은 use_direct_io 옵션으로, config에 설정된 값을 그대로 가져온다. 
• 아래는 row_group_size에 대한 부분이다. row group이란 Parquet 포맷에서 말하는 것과 유사하게 데이터를 횡적으로 분할해 둔 것을 말한다. 기본값은 122,880개의 row이다.(이보다 작은 row group은 허용되지 않는다)
  • 여기서 등장하는 IsValid()나 GetIndex() 같은 것은 duckdb가 사용하는 자체적인 optional_idx 클래스의 메소드들이다. optional_idx는 본질적으로는 uint64_t지만 "no value"를 가질 수 있는 인덱스 비스무리한 것들에 사용하기 위해 정의되어 있다. invalid(= "no value")한 값을 나타내기 위해 -1을 사용한다.
• 벡터는 한 타입의 데이터를 담고 있는 배열이라고 생각하면 되는데, 기본 사이즈는 2048개다. 벡터는 vectorized execution을 위해 필수적이다.

	auto &fs = FileSystem::Get(db);
	auto &config = DBConfig::Get(db);

	StorageManagerOptions options;
	options.read_only = read_only;
	options.use_direct_io = config.options.use_direct_io;
	options.debug_initialize = config.options.debug_initialize;
	options.storage_version = storage_options.storage_version;

	idx_t row_group_size = DEFAULT_ROW_GROUP_SIZE;
	if (storage_options.row_group_size.IsValid()) {
		row_group_size = storage_options.row_group_size.GetIndex();
		if (row_group_size == 0) {
			throw NotImplementedException("Invalid row group size: %llu - row group size must be bigger than 0",
			                              row_group_size);
		}
		if (row_group_size % STANDARD_VECTOR_SIZE != 0) {
			throw NotImplementedException(
			    "Invalid row group size: %llu - row group size must be divisible by the vector size (%llu)",
			    row_group_size, STANDARD_VECTOR_SIZE);
		}
	}

• 이제 중요한 분기점이다. 1) read-only가 아니면서 2) file이 존재하지 않는 경우다.  이때는 새롭게 파일을 만들어야 한다. 파일을 담당하는 것은 SingleFileBlockManager다. 잠깐 뒤에서 살펴보기로 하고 일단 진행하자.

	// Check if the database file already exists.
	// Note: a file can also exist if there was a ROLLBACK on a previous transaction creating that file.
	if (!read_only && !fs.FileExists(path)) {
		// file does not exist and we are in read-write mode
		// create a new file

		// check if a WAL file already exists
		auto wal_path = GetWALPath();
		if (fs.FileExists(wal_path)) {
			// WAL file exists but database file does not
			// remove the WAL
			fs.RemoveFile(wal_path);
		}

		// Set the block allocation size for the new database file.
		if (storage_options.block_alloc_size.IsValid()) {
			// Use the option provided by the user.
			Storage::VerifyBlockAllocSize(storage_options.block_alloc_size.GetIndex());
			options.block_alloc_size = storage_options.block_alloc_size;
		} else {
			// No explicit option provided: use the default option.
			options.block_alloc_size = config.options.default_block_alloc_size;
		}
		if (!options.storage_version.IsValid()) {
			// when creating a new database we default to the serialization version specified in the config
			options.storage_version = config.options.serialization_compatibility.serialization_version;
		}

		// Initialize the block manager before creating a new database.
		auto sf_block_manager = make_uniq<SingleFileBlockManager>(db, path, options);
		sf_block_manager->CreateNewDatabase();
		block_manager = std::move(sf_block_manager);
		table_io_manager = make_uniq<SingleFileTableIOManager>(*block_manager, row_group_size);
		wal = make_uniq<WriteAheadLog>(db, wal_path);

• else이기 때문에, 1) read-only거나 2) 파일이 존재한다면 여기로 오게 된다. (그런데 read-only이면서 파일이 존재하지 않는 케이스에는 어떻게 될까? 파일의 path에 문제가 있을 것이기 때문에 어딘가에서 문제가 생길 수밖에 없다. 이는 LoadExistingDatabase() 함수 내에서 exception을 일으킨다)
• LoadExistingDatabase()로 문제 없이 block manager를 만들고 나면 std::move()를 사용해서 자신의 것으로 만들어준다. 
• 이후 체크포인트로부터 db 내용을 읽어오게 된다. 여기서 LoadDatabase()가 끝난다.

	} else {
		// Either the file exists, or we are in read-only mode, so we
		// try to read the existing file on disk.

		// Initialize the block manager while loading the database file.
		// We'll construct the SingleFileBlockManager with the default block allocation size,
		// and later adjust it when reading the file header.
		auto sf_block_manager = make_uniq<SingleFileBlockManager>(db, path, options);
		sf_block_manager->LoadExistingDatabase();
		block_manager = std::move(sf_block_manager);
		table_io_manager = make_uniq<SingleFileTableIOManager>(*block_manager, row_group_size);

		if (storage_options.block_alloc_size.IsValid()) {
			// user-provided block alloc size
			idx_t block_alloc_size = storage_options.block_alloc_size.GetIndex();
			if (block_alloc_size != block_manager->GetBlockAllocSize()) {
				throw InvalidInputException(
				    "block size parameter does not match the file's block size, got %llu, expected %llu",
				    storage_options.block_alloc_size.GetIndex(), block_manager->GetBlockAllocSize());
			}
		}

		// load the db from storage
		auto checkpoint_reader = SingleFileCheckpointReader(*this);
		checkpoint_reader.LoadFromStorage();

		auto wal_path = GetWALPath();
		wal = WriteAheadLog::Replay(fs, db, wal_path);
	}

 

3. SingleFileBlockManager (구상 클래스) < BlockManager (추상 클래스)

• DBMS의 layered architecture에 대해 익숙한 사람이라면 당연히 여기서 block 이야기가 나와야 할 것을 기대하겠지만, 그렇지 않다면(나 포함) 당황할 수 있다. 그냥 storage manager가 storage device까지 다 관리하는 거 아닌가? 그렇지 않다. block manager는 말 그대로 DB 데이터 파일을 physical block 단위로 나누어 관리하면서 I/O를 책임지고(그 밑에는 또 DB의 file system이 존재한다), storage manager는 DuckDB에게 스토리지의 개념을 고수준에서 노출시킨다.
• 일단은 여기까지 해 두고 block manager를 살펴보자. 이 또한 storage manager와 마찬가지로 base - derived class 구조로 짜여져 있다. BlockManager 클래스의 메소드들은 전부 virtual로 오버라이드된다(아래 코드에서는 중략). unordered_map 컨테이너를 통해 각 block id에서 BlockHandle로의 포인터를 관리하고 있는 것이 보인다.

//! BlockManager is an abstract representation to manage blocks on DuckDB. When writing or reading blocks, the
//! BlockManager creates and accesses blocks. The concrete types implement specific block storage strategies.
class BlockManager {
public:
	BlockManager() = delete;
	BlockManager(BufferManager &buffer_manager, const optional_idx block_alloc_size_p);
	virtual ~BlockManager() = default;

	//! The buffer manager
	BufferManager &buffer_manager;

public:
	//! Creates a new block inside the block manager
	virtual unique_ptr<Block> ConvertBlock(block_id_t block_id, FileBuffer &source_buffer) = 0;
	virtual unique_ptr<Block> CreateBlock(block_id_t block_id, FileBuffer *source_buffer) = 0;

// (중략)

private:
	//! The lock for the set of blocks
	mutex blocks_lock;
	//! A mapping of block id -> BlockHandle
	unordered_map<block_id_t, weak_ptr<BlockHandle>> blocks;
	//! The metadata manager
	unique_ptr<MetadataManager> metadata_manager;
	//! The allocation size of blocks managed by this block manager. Defaults to DEFAULT_BLOCK_ALLOC_SIZE
	//! for in-memory block managers. Default to default_block_alloc_size for file-backed block managers.
	//! This is NOT the actual memory available on a block (block_size).
	optional_idx block_alloc_size;
};

• SingleFileBlockManager는 다음과 같은 private 변수들을 멤버로 갖는다. file 내의 블록들에 대해서도 free_list 등을 통해 관리가 이루어지고 있음을 알 수 있다.

	AttachedDatabase &db;
	//! The active DatabaseHeader, either 0 (h1) or 1 (h2)
	uint8_t active_header;
	//! The path where the file is stored
	string path;
	//! The file handle
	unique_ptr<FileHandle> handle;
	//! The buffer used to read/write to the headers
	FileBuffer header_buffer;
	//! The list of free blocks that can be written to currently
	set<block_id_t> free_list;
	//! The list of blocks that were freed since the last checkpoint.
	set<block_id_t> newly_freed_list;
	//! The list of multi-use blocks (i.e. blocks that have >1 reference in the file)
	//! When a multi-use block is marked as modified, the reference count is decreased by 1 instead of directly
	//! Appending the block to the modified_blocks list
	unordered_map<block_id_t, uint32_t> multi_use_blocks;
	//! The list of blocks that will be added to the free list
	unordered_set<block_id_t> modified_blocks;
	//! The current meta block id
	idx_t meta_block;
	//! The current maximum block id, this id will be given away first after the free_list runs out
	block_id_t max_block;
	//! The block id where the free list can be found
	idx_t free_list_id;
	//! The current header iteration count
	uint64_t iteration_count;
	//! The storage manager options
	StorageManagerOptions options;
	//! Lock for performing various operations in the single file block manager
	mutex block_lock;

• SingleFileBlockManager 내에서 먼저 CreateNewDatabase()와 LoadExistingDatabase()를 살펴보자. 이 함수들은 위의 storage manager단에서 불렸던 적이 있는 함수들이다.
• CreateNewDatabase()는 실질적으로 main header 1개와 2개의 database header를 적어넣는 것과 동일하다. main header는 MainHeader 구조체로 구현되어 있으며 "DUCK"이라는 magic bytes와 데이터베이스의 version number 등을 포함한다. 실질적으로 데이터베이스에 대한 정보를 보관하는 곳은 database header이다. DatabaseHeader 구조체로 구현되어 있는데, 체크포인트가 이루어질 때마다 1씩 증가하는 Iteration count를 갖고 있다. 이것은 어느 헤더를 active 헤더로 사용할지 판정하는 데에 사용된다(후술할 LoadExistingDatabase() 참고). 
• 두 개의 database header를 사용하는 이유가 명시적으로 기술되어 있지는 않으나, crash가 발생했을 때에도 하나의 헤더가 온전하기 때문에 crash safety를 위해 사용하며, 더 높은 iteration count를 가진 헤더를 active header로 사용하여 최신의 데이터를 읽는다.

	// header 1
	h1.iteration = 0;
	h1.meta_block = idx_t(INVALID_BLOCK);
	h1.free_list = idx_t(INVALID_BLOCK);
	h1.block_count = 0;
	// We create the SingleFileBlockManager with the desired block allocation size before calling CreateNewDatabase.
	h1.block_alloc_size = GetBlockAllocSize();
	h1.vector_size = STANDARD_VECTOR_SIZE;
	h1.serialization_compatibility = options.storage_version.GetIndex();
	SerializeHeaderStructure<DatabaseHeader>(h1, header_buffer.buffer);
	ChecksumAndWrite(header_buffer, Storage::FILE_HEADER_SIZE);

	// check the header with the highest iteration count
	if (h1.iteration > h2.iteration) {
		// h1 is active header
		active_header = 0;
		Initialize(h1, GetOptionalBlockAllocSize());
	} else {
		// h2 is active header
		active_header = 1;
		Initialize(h2, GetOptionalBlockAllocSize());
	}

• 다만 LoadExistingDatabase()의 마지막 부분에서 LoadFreeList()를 호출하는데, 이는 free list가 들어있는 블록으로부터 내용을 읽어와서 메모리상에 free block list를 재구축한다.

 

• BlockManager의 중요한 역할 중 하나는 버퍼에 사용되는 block handle을 위해 블록을 만들고, 읽어들이는 것이다. 

unique_ptr<Block> SingleFileBlockManager::CreateBlock(block_id_t block_id, FileBuffer *source_buffer) {
	unique_ptr<Block> result;
	if (source_buffer) {
		result = ConvertBlock(block_id, *source_buffer);
	} else {
		result = make_uniq<Block>(Allocator::Get(db), block_id, GetBlockSize());
	}
	result->Initialize(options.debug_initialize);
	return result;
}

void SingleFileBlockManager::Read(Block &block) {
	D_ASSERT(block.id >= 0);
	D_ASSERT(std::find(free_list.begin(), free_list.end(), block.id) == free_list.end());
	ReadAndChecksum(block, GetBlockLocation(block.id));
}

• 정작 블록에 대해서 설명하지 않았는데, 블록에 대해서 설명하기 위해서는 파일에 대해 설명해야 하기 때문에 다음 글로 미룬다.