CommunityNews

CommunityNews

Rethinking Sanakirja, a Rust database engine with fast clones

My last post about Sanakirja sparked a few really constructive discussions, and made me realise that people still cared about the problem of on-disk key-value stores, as unfancy as that problem may sound. This post looks back on some design mistakes I’ve made when I wrote it, and includes benchmarks showing it’s now faster than the fastest equivalent C library.

Why?

A long time ago, Pijul was using LMDB as its backend, with a number of fundamental limitations, including:

  • Being restricted to two datatypes: an array of B+ trees where keys are byte strings and values are either (1) byte strings or (2) B+ trees where keys are bytestrings and values are zero-sized. In Rust terminology, this is equivalent to roughly 500 tables, where a table is either BTreeMap<&[u8], &[u8]> or BTreeMap<&[u8], BTreeMap<&[u8], ()>>.
  • Being written in C, meaning that it is potentially fast, but hard to extend in any nontrivial way. About the “fast” part, my benchmarks show that indeed, it is quite fast — just not as fast as a carefully-designed Rust version.
  • More importantly, I needed to fork tables efficiently, without copying anything. This was especially important back then, when Pijul tables for small repositories often weighed dozens of megabytes. It may be slightly less relevant now, but now that it’s there, there is no reason not to use it.This is implemented with an extra table storing reference counts of each page that is referenced at least twice (in order to avoid infinite recursions, the table itself isn’t clonable, and therefore all its pages are referenced once).

This thread was posted by one of our members via one of our news source trackers.

Where Next?

Popular Backend topics Top

First poster: bot
Rust vs Go — Bitfield Consulting. Which is better, Rust or Go? Which language should you choose for your next project, and why? How do t...
New
First poster: bot
When I need to configure something in a complicated way, I find myself reviewing the embedded language that provided the server to create...
New
First poster: Exadra37
Summary: I describe a simple interview problem (counting frequencies of unique words), solve it in various languages, and compare perform...
New
First poster: bot
Ruby on Rails is a web framework that contains many libraries you’d need to create and deploy a successful web application. We often take...
New
First poster: bot
Once a year, I look back at the recent developments in the PHP world, and also look forward to what’s to come. And just like in 2020 and ...
New
First poster: bot
This post is a spiritual successor to Loris Cro’s Go cross-compilation. The encounter During a recent stage 2 meeting Jakub Konka wanted...
New
CommunityNews
Have you ever wanted to write a structurally typed function in Rust? Do you spend a lot of time and effort getting your Rust struct s jus...
New
brainlid
In episode 78 of Thinking Elixir, we talk with Chase Granberry about Logflare. We learn why Chase started the company, what Logflare does...
New
mtmattei
For the past few years, Safari has been putting in a lot of effort to enhance its WebAssembly support and 2024 was no exception… I believ...
New
brainlid
Episode 244 of Thinking Elixir. News includes the release of Elixir 1.18.2 with various enhancements and bug fixes, a new experimental SQ...
New

Other popular topics Top

AstonJ
A thread that every forum needs! Simply post a link to a track on YouTube (or SoundCloud or Vimeo amongst others!) on a separate line an...
New
PragmaticBookshelf
Brace yourself for a fun challenge: build a photorealistic 3D renderer from scratch! In just a couple of weeks, build a ray tracer that r...
New
DevotionGeo
I know that -t flag is used along with -i flag for getting an interactive shell. But I cannot digest what the man page for docker run com...
New
New
PragmaticBookshelf
Learn different ways of writing concurrent code in Elixir and increase your application's performance, without sacrificing scalability or...
New
DevotionGeo
The V Programming Language Simple language for building maintainable programs V is already mentioned couple of times in the forum, but I...
New
PragmaticBookshelf
Use WebRTC to build web applications that stream media and data in real time directly from one user to another, all in the browser. ...
New
PragmaticBookshelf
Author Spotlight: VM Brasseur @vmbrasseur We have a treat for you today! We turn the spotlight onto Open Source as we sit down with V...
New
DevotionGeo
I have always used antique keyboards like Cherry MX 1800 or Cherry MX 8100 and almost always have modified the switches in some way, like...
New
hilfordjames
There appears to have been an update that has changed the terminology for what has previously been known as the Taskbar Overflow - this h...
New