MongoDB stable sort with _id
Tags: mongodb, sort
Published: 2024-01-17 20:53:16

## 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](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/e6m1xdt3akcliqpr6pg6.png)

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

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

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

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](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/xngntk6da00n415hftxd.png)

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](https://www.mongodb.com/docs/manual/reference/bson-types/#std-label-objectid)
[Time, Clocks, and the Ordering of Events in a Distributed System](https://www.microsoft.com/en-us/research/publication/time-clocks-ordering-events-distributed-system/?from=https://research.microsoft.com/en-us/um/people/lamport/pubs/time-clocks.pdf&type=exact)
[Snowflake](https://github.com/twitter-archive/snowflake/tree/b3f6a3c6ca8e1b6847baa6ff42bf72201e2c2231)

---
Woovi
[Woovi](https://www.woovi.com) 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](https://woovi.com/jobs/)!

---
<a href="https://www.freepik.com/free-vector/sorting-thoughts-concept-illustration_12780668.htm#query=sorting&position=2&from_view=search&track=sph&uuid=139dc95a-1639-4869-900d-609a7bde8756">Image by storyset</a> on Freepik