DEV Community

Cover image for MongoDB stable sort with _id
Sibelius Seraphini for Woovi

Posted on

MongoDB stable sort with _id

MongoDB ObjectIds

ObjectIds are small, likely unique, fast to generate, and ordered. ObjectId values are 12 bytes in length, consisting of:

A 4-byte timestamp, representing the ObjectId's creation, measured in seconds since the Unix epoch.

A 5-byte random value is generated once per process. This random value is unique to the machine and process.

A 3-byte incrementing counter is initialized to a random value.

MongoDB Stable sort

Imagine you are creating a Ledger implementation in which you need to link a new transaction to the last transaction, like a hash chain. How would you get the latest item from the collection using MongoDB?

HashChain

You can sort by _id, or you can sort by createdAt



const latestItem = await Transaction.findOne().sort({ _id: -1 }).limit(1);


Enter fullscreen mode Exit fullscreen mode


const latestItem = await Transaction.findOne().sort({ createdAt: -1 }).limit(1);


Enter fullscreen mode Exit fullscreen mode

Using createdAt for sorting like this has some drawbacks.
createdAt is not unique, so you can't guarantee a stable sort. createdAt is not automatically indexed, so you can have slow queries.

Happened-before

_id is usually generated by the MongoDB client instead of the MongoDB database server.

MongoDB clients

In a distributed system, with many servers, MongoDB client 1 can generate an _id before MongoDB client 2, but MongoDB client 2 can commit the changes to the database first.
In the scenario above, the sort based on createdAt and _id are different:

createdAt: mongodbClient2, mongodbClient1 (mongodbClient2 saved first in the database)
_id: mongodbClient1, mongodbClient2 (mongodbClient1 created _id first)

Using a different sorting strategy or changing the sorting strategy can lead to some hard bugs to debug.

In Summary

It is interesting to understand how different databases solve some classic distributed system problems. Everybody knows that incremental IDs do not scale. Distributed IDs provide a scalable architecture with a few guarantees.

References

MongoDB ObjectId
Time, Clocks, and the Ordering of Events in a Distributed System
Snowflake


Woovi
Woovi is a Startup that enables shoppers to pay as they like. To make this possible, Woovi provides instant payment solutions for merchants to accept orders.

If you want to work with us, we are hiring!


Image by storyset on Freepik

Top comments (0)