# Generating Monotonically Increasing IDs with Redis During Failures

DevFeed: [Generating Monotonically Increasing IDs with Redis During Failures](<https://devfeed.tech/articles/the-binary-search-of-distributed-programming-20593.md>)

Original publisher: [Read original article](<http://antirez.com/news/102>)

Published: 2016-02-13T16:49:13Z

Content type: tutorial

Language: en

Sources: [Antirez](<https://devfeed.tech/sources/antirez.md>)

Topics: [distributed-systems](<https://devfeed.tech/topics/distributed-systems.md>), [Redis](<https://devfeed.tech/topics/redis.md>), [Programming](<https://devfeed.tech/topics/programming.md>), [Algorithms, Complexity](<https://devfeed.tech/topics/algorithms-complexity.md>), [Raft](<https://devfeed.tech/topics/raft.md>)

Tags: [distributed](<https://devfeed.tech/tags/distributed.md>), [distributed-systems](<https://devfeed.tech/tags/distributed-systems.md>), [programming](<https://devfeed.tech/tags/programming.md>), [raft](<https://devfeed.tech/tags/raft.md>), [redis](<https://devfeed.tech/tags/redis.md>), [systems](<https://devfeed.tech/tags/systems.md>)

## AI overview

This technical article explores an algorithm for generating monotonically increasing, non-duplicated IDs with Redis while preserving safety during network partitions and other failures. The proposed approach may become unavailable without a majority of reachable nodes and has a liveness issue under high request load; the author also modified it for client-side implementation and requests feedback on its correctness.

## Source excerpt

Yesterday night I was re-reading Redlock analysis Martin Kleppmann wrote (http://martin.kleppmann.com/2016/02/08/how-to-do-distributed-locking.html). At some point Martin wonders if there is some good way to generate monotonically increasing IDs with Redis. This apparently simple problem can be more complex than it looks at a first glance, considering that it must ensure that, in all the conditions, there is a safety property which is always guaranteed: the ID generated is always greater than all the past IDs generated, and the same ID cannot be generated multiple times. This must hold during network partitions and other failures. The system may just become unavailable if there are less than the majority of nodes that can be reached, but never provide the wrong answer (note: as we'll see this algorithm has another liveness issue that happens during high load of requests). So for the sake of playing a bit more with distributed systems algorithms, and learn a bit more in the process, I tried to find a solution. Actually I was aware of an algorithm that could solve the problem. It's an inefficient one, not suitable to generate tons of IDs per second. Many complex distributed algorithms, like Raft and Paxos, use it as a step in order to get monotonically increasing IDs, as a foundation to mount the full set of properties they need to provide. This algorithm is fascinating since it's extremely easy to understand and implement, and because it's very intuitive to understand *why* it works. I could say, it is the binary search of distributed algorithms, something easy enough but smart enough to let newcomers to distributed programming to have an ah!-moment. However I had to modify the algorithm in order to adapt it to be implemented in the client side. Hopefully it is still correct (feedbacks appreciated). While I'm not going to use this algorithm in order to improve Redlock (see my previous blog post), I think that trying to solve this kind of problems is both a good exerc