How to create a monotonically increasing counter using Express.js and LMDB

The Challenge

It’s surprisingly challenging to code an auto-incrementing counter in a concurrent environment.

Specifically, the problem of “lost updates” quickly becomes quite real.

Lost Updates

Lost updates are updates that are unintentionally overwritten by other updates. An example would be when 2 concurrent calls to increment a counter only increment the counter by 1 because the second read-increment-and-write overrules the first. This article does a great job explaining the problem.

Whenever you have multiple readers/writers at the same time, you are at risk of lost updates. This can even occur in a single-threaded environment (such as Node.js) where a construct like the “event loop” might introduce “delays” and execute unrelated reads/writes in between reads/writes that were intended to be sequential and “uninterrupted”.

My Use Case

I was recently looking to implement a service that would provide a monotonically increasing counter. Specifically, to generate fencing tokens in order to provide certain guarantees of idempotence in an application I am building. This article by Martin Kleppman, author of Designing Data-Intensive Applications, explains how fencing tokens work.

I chose to use Node.js as the runtime, with Express.js as the web application framework.

In order to keep the counter monotonically increasing across crashes and restarts, I needed some kind of persistence.

Why LMDB?

I did some preliminary research on what options would be light and fast – since this would be a simple counter, I didn’t need much in the way of schema or query languages, and my use-case would need to be write-optimized instead of read-optimized.

LMDB presented itself as an option. There is also a Node.js binding named lmdb-js with typings (for Typescript).

Implementing a counter using lmdb-js

I found this GitHub issue where someone asked the maintainer of lmdb-js how best to increment a counter while preventing lost updates. What method will be most performant?

The author recommended using optimistic writes, where safety would be guaranteed by versioning each write so that any concurrent writes that were based on “stale” reads will be rejected.

However, the issue creator did some benchmarking and discovered that using LMDB transactions was actually more performant.

I did some of my own testing and learned that not only was the issue creator correct, but also discovered a way to further improve performance if you only have a single process of your counter service.

I want to share these methods and their benchmarks with you!

Alternative methods and benchmarks

Below are links to implementations of each method in GitHub, as well as their relative benchmarks from my testing.

Method 1: Using LMDB Versions

This is the slowest method. It should still be safe even if you have multiple processes reading and writing from the same LMDB database.

Link: https://github.com/umerx-github/fencing-token-generator/blob/safe-with-versions/src/index.ts

Benchmarks:

1. 176.593ms
2. 161.434ms
3. 178.941ms
4. 166.906ms
5. 130.849ms
6. 176.029ms

Method 2: Using LMDB Transactions

This method is middle-of-the-road in terms of performance. It should still be safe even if you have multiple processes reading and writing from the same LMDB database.

Link: https://github.com/umerx-github/fencing-token-generator/blob/safe-with-transactions/src/index.ts

Benchmarks:

1. 91.665ms
2. 75.542ms
3. 84.841ms
4. 80.877ms
5. 81.146ms
6. 85.428ms

Method 3: Incrementing an in-memory mutable data structure and persisting to LMDB

This method is not safe if you are running multiple instances (processes) of your counter service. Without some kind of additional memory replication, those processes will not be able to share the in-memory data structure and this will result in lost updates. Additionally, this method only works because even though it will handle requests concurrently (relying on the “event loop” in Node.js to switch between requests), the code incrementing the in-memory counter will only be handled by a single thread (the “main” thread in Node.js).

There is also no kind of “rollback” mechanism if the write to LMDB were to fail. The in-memory counter would still increment, and future or concurrent requests would all read, write, and respond with integers higher than this failed write – though the “failed” number was never served in any response.

If you are only running a single instance of your counter service, this is quite fast.

Link: https://github.com/umerx-github/fencing-token-generator/blob/safe-with-no-transactions-or-versions/src/index.ts

Benchmarks:

1. 101.112ms
2. 73.901ms
3. 83.868ms
4. 77.262ms
5. 66.239ms
6. 67.058ms