# A simple write-once-read-many indexed based database

I started writing a cyrptocoin from scratch, and then got sidetracked writing the database portion which I eventually turned it into its own project.

Data is written to the database and then retrieved through an index, similar to a memory-mapped vector.

The data are stored in "segments" that can have a configurable size. Thus if the database exceeded a certain size the oldest segments would be deleted so that only the most recent data was available. The database does not support updates or deletes, however it does support "truncate" which allow you to delete all data after a given index.

I would love some feedback on the project which is located here: https://github.com/zethon/AshDB

The primary functionality of the database resides in ashdb.h which I provide here:

#pragma once

#include <iostream>
#include <sstream>
#include <atomic>
#include <optional>
#include <vector>

#include <boost/filesystem.hpp>

#include "options.h"
#include "primitives.h"
#include "status.h"

namespace ashdb
{

namespace bfs = boost::filesystem;

using SegmentIndices = std::vector<std::vector<std::size_t>>;

constexpr auto INDEX_EXTENSION = "idx";
constexpr auto VALIDCHARS = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvqxyz0123456789-_";

std::string BuildFilename(const std::string& folder,
const std::string& prefix,
const std::string& extension,
std::uint64_t fileindex);

std::vector<std::size_t> ReadIndexFile(const std::string& filename);

template<class ThingT>
class AshDB
{

public:
using Batch = std::vector<ThingT>;
using BatchIterator = typename std::vector<ThingT>::const_iterator;

// 0 - the segment index (i.e. _segmentIndicies[x]
// 1 - the index of the offset within the segment index (i.e. _segmentIndicies[x][y])
using IndexDetails = std::tuple<std::size_t, std::size_t>;

AshDB(const std::string& folder, const Options& options)
: _dbfolder{ folder },
_options{ options }
{
_startIndex.reset();
_lastIndex.reset();
}

[[maybe_unused]] OpenStatus open();
void close();

[[maybe_unused]]
WriteStatus write(const ThingT& thing);

[[maybe_unused]]
WriteStatus write(const Batch& batch);

[[maybe_unused]]

Batch read(std::size_t index, std::size_t count);

// deletes all records starting at, and includins, startIndex
// so that the last index in the database will be startIndex-1
void truncate(std::size_t startIndex);

// returns the accessor boundaries ot the database, for example
// if we use "db->at(i)", these functions tell us the range of "i"
std::optional<std::size_t> startIndex() const { return _startIndex; }
std::optional<std::size_t> lastIndex() const { return _lastIndex; }

// returns the size of all the "data-0001.dat" files on the disk
// but does NOT include the size of the corresponding index
// files (i.e. "data-0001.datidx")
std::uint64_t databaseSize() const;

// returns the number of records in the database
std::size_t size() const;

// data files have names like "data-0001.dat", the numbers returned
// by these methods represent the "0001" portion of the filename
std::uint16_t startSegmentNumber() const { return _startSegmentNumber; }
std::uint16_t activeSegmentNumber() const { return _activeSegmentNumber; }

// returns the full path of the file tobench which the next record will
// be written
std::string activeDataFile() const
{
return buildDataFilename(_activeSegmentNumber);
}

// returns the full path of the file to which the next index entry
// will be written
std::string activeIndexFile() const
{
return buildIndexFilename(_activeSegmentNumber);
}

// records the vector of vector that keeps track of all the records
// and their offsets
const SegmentIndices segmentIndices() const { return _segmentIndices; }

private:
// scans the database folder to establish the min and max records for
// the data files. For example, if we have the files data-00002.dat,
// data-00003.dat, data-00004.dat, then it will set the start and
// active record numbers to 2 and 4 respectively
void findFileBoundaries();

// find the boundaries of the accessor methods, i.e. we access
// the records in the database through at(i) and this will
// find the valid range of values of i. NOTE: This should
// be called AFTER _segmentIndices has been setup
void findIndexBoundaries();

// move the index forward by (1) incrementing the active record number,
// (2) deleting the oldest index and data files if necessary and (3)
// cleaning up _startIndex and _lastIndex as needed
void updateIndexing();

// writes the given offset to the current index file and will update
// "_segmentIndices" accordingly
void writeIndexEntry(std::size_t offset);

// writes records to the current data file until the begin == end or
// until the dat file exceeds the max file size
void writeBatchUntilFull(BatchIterator& begin, BatchIterator end);

std::string buildDataFilename(std::uint16_t x) const;
std::string buildIndexFilename(std::uint16_t x) const;

IndexDetails findIndexDetails(std::size_t index);

// reset the segment indices and all tracking info
void reset();

//////////////////////////////////////////////
// private variables
const std::string       _dbfolder;
const Options           _options;

SegmentIndices             _segmentIndices;

// the first and last accessors of the records using at() or operator[]
std::optional<std::size_t>  _startIndex = 0;
std::optional<std::size_t>  _lastIndex = 0;

// the current first and last file numbers
std::uint16_t           _startSegmentNumber = 0;
std::uint16_t           _activeSegmentNumber = 0;

std::atomic_bool        _open = false;
};

template<class ThingT>
OpenStatus AshDB<ThingT>::open()
{
if (_open)
{
}

if (_options.prefix.size() == 0
|| _options.prefix.find_first_not_of(VALIDCHARS) != std::string::npos)
{
return OpenStatus::INVALID_PREFIX;
}
else if (_options.extension.size() == 0
|| _options.extension == ashdb::INDEX_EXTENSION
|| _options.extension.find_first_not_of(VALIDCHARS) != std::string::npos)
{
return OpenStatus::INVALID_EXTENSION;
}

bfs::path dbpath{ _dbfolder };
if (!bfs::exists(dbpath))
{
if (_options.create_if_missing)
{
bfs::create_directories(dbpath);
}
else
{
return OpenStatus::NOT_FOUND;
}
}
else if (_options.error_if_exists)
{
return OpenStatus::EXISTS;
}

reset();

_open = true;
return OpenStatus::OK;
}

template<class ThingT>
void AshDB<ThingT>::close()
{
_startIndex.reset();
_lastIndex.reset();
_open = false;
}

template<class ThingT>
WriteStatus AshDB<ThingT>::write(const ThingT& thing)
{
if (!_open)
{
return WriteStatus::DATABASE_NOT_OPEN;
}

const auto datafile = this->activeDataFile();
auto destfilesize = bfs::exists(datafile)
? bfs::file_size(datafile.data()) : 0u;

// write the offset of the current filesize, since this marks the beginning
// of *this* record
writeIndexEntry(destfilesize);

std::ofstream datafs;
datafs.open(datafile.data(), std::ios::out | std::ios::binary | std::ios::app);
ashdb_write(datafs, thing);
datafs.close();

// now that we've written the data, check the filesize once again
destfilesize = bfs::file_size(datafile.data());
updateIndexing();
if (_options.filesize_max > 0 && destfilesize >= _options.filesize_max)
{
_activeSegmentNumber++;
}

return WriteStatus::OK;
}

template<class ThingT>
void AshDB<ThingT>::writeBatchUntilFull(BatchIterator& begin, BatchIterator end)
{
const auto datafile = this->activeDataFile();

// we have to manually keep track of the file offets by using the current
// filesize and the size of the data we're writing
const std::size_t startingOffset = bfs::exists(datafile) ?
bfs::file_size(datafile) : 0;
std::size_t currentOffset = startingOffset;

// we have two buffers: (1) for the data that we won't flush to disk until
// we've written as much as we can into this segment, and (2) for the index
// offsets which we also won't flush until the very end
std::stringstream indexBuffer;
std::stringstream buffer;

while (begin != end)
{
// If the currentOffset == 0 this means this is the first time we're writing to
// this segment. The first entry in an index file is not an offset, since it's
// unnecessary because we know the corresponding offset is also 0, but instead
// is the index number of the first entry in this segment
if (currentOffset == 0)
{
if (_segmentIndices.size() > 1)
{
const auto& secondToLast = _segmentIndices.end()[-2];

// under these conditions, currentOffset actually represents the
// index number of the first item in this segment's datafile
currentOffset = secondToLast.at(0) + secondToLast.size();
}
}

_segmentIndices.back().push_back(currentOffset);
indexBuffer.write(reinterpret_cast<char*>(&currentOffset), sizeof(currentOffset));

ashdb_write(buffer, *begin);
currentOffset = startingOffset + buffer.tellp();
++begin;

if (BOOST_LIKELY(_startIndex.has_value()))
{
(*_lastIndex)++;
}
else
{
// this condition should only happen when the database is brand new
assert(!_lastIndex.has_value());
_startIndex = 0;
_lastIndex = 0;
}

if (_options.filesize_max > 0 &&  currentOffset > _options.filesize_max)
{
break;
}
}

if (buffer.tellp() > 0)
{
assert(indexBuffer.tellp() > 0);

const std::string indexFile = activeIndexFile();
std::ofstream indexfs;
indexfs.open(indexFile.c_str(), std::ios::out | std::ios::binary | std::ios::app);
indexfs << indexBuffer.str();
// deepcode ignore MissingOpenCheckOnFile: indexfs has exceptions turned on
indexfs.close();

std::ofstream datsafs;
datsafs.open(datafile.data(), std::ios::out | std::ios::binary | std::ios::app);
// deepcode ignore MissingOpenCheckOnFile: datsafs has exceptions turned on
datsafs << buffer.str();
}
}

template<class ThingT>
WriteStatus AshDB<ThingT>::write(const AshDB<ThingT>::Batch& batch)
{
if (!_open)
{
return WriteStatus::DATABASE_NOT_OPEN;
}

BatchIterator begin = batch.begin();
BatchIterator end = batch.end();

while (begin != end)
{
// before we get started, first see if we have to add
// another segment index
const auto segmentCount = (_activeSegmentNumber - _startSegmentNumber) + 1;
if (_segmentIndices.size() == 0
|| _segmentIndices.size() < segmentCount)
{
assert(_segmentIndices.size() == segmentCount - 1);
_segmentIndices.push_back({});
}

// write as much as we can to the current segment
writeBatchUntilFull(begin, end);

// in case we stopped writing because the segment file got too big
// we need to increment the segment number
if ((begin != end) ||
(_options.filesize_max > 0 && (bfs::file_size(activeDataFile()) > _options.filesize_max)))
{
_activeSegmentNumber++;
}

// now see if the database is too big and we need to trim it down
if (_options.database_max > 0
&& databaseSize() > _options.database_max)
{
const auto fn = buildDataFilename(_startSegmentNumber);
const auto ifn = buildIndexFilename(_startSegmentNumber);
bfs::remove(fn);
bfs::remove(ifn);

_startSegmentNumber++;
_segmentIndices.erase(_segmentIndices.begin());
_startIndex = _segmentIndices.front().at(0);
}
}

return ashdb::WriteStatus::OK;
}

template<class ThingT>
{

auto [currentRecord, localIndex] = findIndexDetails(index);
auto readOffset = localIndex == 0 ? 0 : _segmentIndices[currentRecord][localIndex];

const auto dataFile = buildDataFilename(currentRecord);
std::ifstream datafs;
datafs.open(dataFile.data(), std::ios_base::binary);

ThingT thing;
datafs.close();

return thing;
}

template<class ThingT>
auto AshDB<ThingT>::read(std::size_t index, std::size_t count) -> AshDB<ThingT>::Batch
{

AshDB<ThingT>::Batch batch;
const auto endIndex = index + count;
auto [segment, offsetIndex] = findIndexDetails(index);

for (auto i = index; i < (index + count);)
{
auto localMax = _segmentIndices[segment].size();
if (endIndex <= (_segmentIndices[segment][0] + _segmentIndices[segment].size()))
{
localMax = endIndex - _segmentIndices[segment][0];
}

const auto datafile = this->buildDataFilename(segment);
std::ifstream datafs;
datafs.open(datafile.data(), std::ios_base::binary);

for (; offsetIndex < localMax; ++i, ++offsetIndex)
{
auto readOffset = offsetIndex == 0 ? 0 : _segmentIndices[segment][offsetIndex];

ThingT thing;
batch.push_back(std::move(thing));
}

datafs.close();
offsetIndex = 0;
segment++;
}

return batch;
}

template<class ThingT>
void AshDB<ThingT>::truncate(std::size_t startIndex)
{

auto [currentSegment, localIndex] = findIndexDetails(startIndex);

if (localIndex > 0)
{
// trim the data file
const auto offset = _segmentIndices[currentSegment][localIndex];
const auto datafile { buildDataFilename(currentSegment) };
boost::filesystem::resize_file(datafile.c_str(), offset);

// trim the index file
const auto indexfile { buildIndexFilename(currentSegment) };
boost::filesystem::resize_file(indexfile.c_str(), localIndex * sizeof(std::size_t));

// start deleting segment files at the next segment
currentSegment++;
}

// delete all excess segment and index files
while (currentSegment <= _activeSegmentNumber)
{
const auto datafile { buildDataFilename(currentSegment) };
boost::filesystem::remove(datafile.c_str());

const auto indexfile { buildIndexFilename(currentSegment) };
boost::filesystem::remove(indexfile.c_str());

currentSegment++;
}

reset();
}

template<class ThingT>
void AshDB<ThingT>::reset()
{
findFileBoundaries();

// load the record-index
_segmentIndices.clear();
for (auto i = _startSegmentNumber; i <= _activeSegmentNumber; ++i)
{
const auto indexFilename = buildIndexFilename(i);
if (bfs::exists(indexFilename))
{
_segmentIndices.push_back({});
}
}

findIndexBoundaries();
}

template<class ThingT>
void AshDB<ThingT>::findFileBoundaries()
{
bfs::path dbpath{_dbfolder};

// early fail if the folder is empty
if (bfs::is_empty(dbpath))
{
return;
}

// there is no portable glob method, so for now we're going to use this
// brute force and ugly method to get the boundaries
bool found = false;
std::uint16_t start = 0;
std::uint16_t end = 0;

for (std::uint16_t i = 0u; i < std::numeric_limits<std::uint16_t>::max(); ++i)
{
auto filename = ashdb::BuildFilename(_dbfolder, _options.prefix, _options.extension, i);
if (bfs::exists(filename))
{
if (!found)
{
start = i;
found = true;
}
}
else if (found)
{
assert(i > 0);
end = i - 1;
break;
}
}

_startSegmentNumber = start;
_activeSegmentNumber = std::max(_startSegmentNumber, end);

if (const auto datafile = activeDataFile();
_options.filesize_max != 0
&& bfs::exists(datafile.data())
&& bfs::file_size(datafile.data()) >= _options.filesize_max)
{
_activeSegmentNumber++;
}
}

template<class ThingT>
void AshDB<ThingT>::findIndexBoundaries()
{
_startIndex.reset();
_lastIndex.reset();

// load the accessor boundaries
if (_segmentIndices.size() > 0)
{
assert(_segmentIndices.front().size() > 0);
_startIndex = _segmentIndices.front().at(0);

assert(_segmentIndices.back().size() > 0);
_lastIndex = _segmentIndices.back().front() + (_segmentIndices.back().size() - 1);
}
}

template<class ThingT>
void AshDB<ThingT>::updateIndexing()
{
if (!_startIndex.has_value())
{
assert(!_lastIndex.has_value());
_startIndex = 0;
_lastIndex = 0;
}
else
{
(*_lastIndex)++;
}

// now see if the database is too big and we need to trim it down
if (_options.database_max > 0
&& databaseSize() > _options.database_max)
{
const auto fn = buildDataFilename(_startSegmentNumber);
const auto ifn = buildIndexFilename(_startSegmentNumber);
bfs::remove(fn);
bfs::remove(ifn);

_startSegmentNumber++;
_segmentIndices.erase(_segmentIndices.begin());
_startIndex = _segmentIndices.front().at(0);
}
}

template<class ThingT>
void AshDB<ThingT>::writeIndexEntry(std::size_t offset)
{
auto value = offset;

if (value == 0)
{
if (_segmentIndices.size() > 0)
{
value = _segmentIndices.back().at(0) + _segmentIndices.back().size();
}
}

std::string indexfile = activeIndexFile();
std::ofstream indexfs;
indexfs.open(indexfile.c_str(), std::ios::out | std::ios::binary | std::ios::app);
ashdb::ashdb_write(indexfs, value);
indexfs.close();

const auto segmentCount = (_activeSegmentNumber - _startSegmentNumber) + 1;
if (_segmentIndices.size() < segmentCount)
{
assert(_segmentIndices.size() == segmentCount - 1);
_segmentIndices.push_back({});
}

_segmentIndices.back().push_back(value);
}

template<class ThingT>
std::uint64_t AshDB<ThingT>::databaseSize() const
{
std::uint64_t retval = 0;
for (auto i = _startSegmentNumber; i <= _activeSegmentNumber; ++i)
{
const auto filename = ashdb::BuildFilename(
_dbfolder, _options.prefix, _options.extension, i);

bfs::path filepath{filename};

if (!bfs::exists(filepath))
{
assert(i == _activeSegmentNumber);
break;
}

retval += static_cast<std::uint64_t>(bfs::file_size(filepath));
}

return retval;
}

template<class ThingT>
std::size_t AshDB<ThingT>::size() const
{
if (!_open || !_startIndex.has_value())
{
assert(!_lastIndex.has_value());
return 0;
}

return (*_lastIndex - *_startIndex) + 1;
}

// TODO: this could be improved
template<class ThingT>
typename AshDB<ThingT>::IndexDetails AshDB<ThingT>::findIndexDetails(std::size_t index)
{
if (index < _startIndex || index > _lastIndex)
{
std::stringstream ss;
ss << "index " << index << " is out of bounds";
throw std::runtime_error(ss.str());
}

std::optional<std::size_t> localIndex = 0;
std::size_t currentSegment = _startSegmentNumber;
for (const auto& offsets : _segmentIndices)
{
if (index < (offsets.front() + offsets.size()))
{
localIndex = index - offsets.front();
break;
}
else
{
currentSegment++;
}
}

if (!localIndex.has_value())
{
std::stringstream ss;
ss << "index " << index << " could not be found";
throw std::runtime_error(ss.str());
}

return IndexDetails{currentSegment, *localIndex };
}

template<class ThingT>
std::string AshDB<ThingT>::buildDataFilename(std::uint16_t x) const
{
return ashdb::BuildFilename(_dbfolder, _options.prefix, _options.extension, x);
}

template<class ThingT>
std::string AshDB<ThingT>::buildIndexFilename(std::uint16_t x) const
{
const auto temp = _options.extension + INDEX_EXTENSION;
return ashdb::BuildFilename(_dbfolder, _options.prefix, temp, x);
}

}; // namespace ashdb


Any feedback would be appreciated!

Looks good! I see you are familiar with "modern" C++ techniques and habits. 😀

Hmm, the use of const data members means that the class cannot be moved, as well as not assigned to.

Where's the destructor of AshDB? It contains file handles and things which need cleaning up; you rely on the user explicitly calling close?!!?

Likewise, declare the copy constructor as =deleted since the automatically provided one will simply not work right.

I don't know what OpenStatus is, but I would suggest using standard error code types.

Why are you using Boost filesystem instead of the standard library? I see your post is tagged as [C++17] so you should have that available.

• A const member will prevent generation of the copy assignment operator, not the constructor. Being able to move might be useful, which is why I lamented the lack of being able to move it. Jun 9, 2021 at 19:38
• @JDługosz Thank you for the review! I wonder if a destructor is really necessary? None of the file handles live longer than the methods where they're used, so I didn't feel there was any cleanup to do.
Jun 9, 2021 at 20:35
• @JDługosz: Oh, quite right. Muddled thinking on my part. Jun 10, 2021 at 3:16
• @Addy declare ~AshDB() =default; to make it clear that you don't need to add anything to what's generated, and did not simply forget about it. Jun 10, 2021 at 13:35

# Use of the filesystem library

You are using <boost/filesystem.hpp>, but this has become standardized as std::filesystem in C++17. Consider moving over to that one. Just change the using directive:

using bfs = std::filesystem;


And it should work just fine. But perhaps it is better to change bfs to fs then.

I would also recommend you make more use of it, in particular use fs::path for all variables and function parameters that should hold paths, filenames, and even filename extensions.

# Use uintmax_t for file sizes

You are using uint64_t to represent file sizes, and while it is better than std::size_t, since the latter might not be big enough on a 32-bit system to represent file sizes, the C++17 filesystem library uses uintmax_t as the return type for std::filesystem::file_size(). Consider matching this.

# Don't use [[maybe_unused]] for member functions

It's not necessary to annotate class member functions as [[maybe_unused]], the compiler is not going to warn about them anyway. Also note that it applies to the function, not to the return type.

# Are 16 bits going to be enough for segment numbers?

I see you use std::uint16_t for segment numbers. Are you sure that is going to always be big enough? At the very least, I would create a type alias for segment numbers, so that if you do need to change the type, it's just one line that has to be changed.

# Globbing

Indeed, there is no glob function in C++. However, you can easily iterate over the contents of a directory, and C++ does have regular expressions. So findFileBoundaries() could be written as:

template<class ThingT>
void AshDB<ThingT>::findFileBoundaries()
{
const std::regex pattern(_options.prefix + "-\$$[0-9]\\{4\\}\$$\\." + _options.extension);

for(auto &entry: fs::directory_iterator(_dbfolder)) {
if (std::smatch match; std::regex_match(entry.path(), match, pattern)) {
std::uint16_t segment = std::stoi(match[1].str());
...
}
}

...
}


Although it's not safe to do this (nor using a hypothetical glob function!) if you don't know exactly what is in _options.prefix or _options.extension, as any character in those strings could potentially have a special meaning in a regular or glob expression. It's perhaps better to use std::starts_with() and std::ends_with() (or equivalent functionality if you can't use C++20) to check if the filename matches the expected format.

There might even be options to avoid the whole globbing thing, perhaps you could maintain a symlink to the first valid segment?

# Use of std::stringstream

A std::stringstream is not the most efficient data structure ever. Apart from it potentially having to resize its internal buffer many times as you add to it, getting the string out using str() will result in a copy being made (unless you can use the overload from C++20 that supports move semantics).

It might be better to write directly to the index and data files instead of first accumulating everything in std::stringstreams, if that is possible.

# ACID properties

When writing a database, think carefully whether you need it to have ACID properties (atomicity, consistency, isolation and durability), or perhaps a subset of those properties. If you do need it, make sure your implementation matches the requirements. In particular, be aware that a computer could crash at any moment, and if that happens while data was still being written to disk, the resulting files or the directory structure itself might not be in a valid state for your database anymore, even if the filesystem itself is fine.

The filesystem libraries do not provide any way to do atomic writes. At best std::filesystem::rename()` is atomic if the actual filesystem supports atomic renames, but it is not guaranteed by the C++ standard. You might have to resort to operating-specific functions to ensure file and directory contents are synced to disk at the right times (see this LWN article discussing the issue).

A trick that is used by some databases is to have some append-only structure, where a checksum is written after a block of data is added to a file. A valid checksum means the whole block was written correctly, so that is a way to provide some form of atomicity.

• Thank you for the excellent feedback! The 16-bit limit on segment numbers was a conscious decision to limit them, mostly because I didn't want the segment number to exceed 5 characters as a decimal string. I will take your advise though and use a type alias.