It seems like such a simple request at first, “I want data to be ordered by rank or priority, and I want users to be able to re-order the data based on which is most important”. This is an extremely common scenario in app development. You will find this problem everywhere from Todo Lists and task management systems, to complex and specific use-cases. The solution might seem simple at first, depending on your language/db solution, there might even be native support for a priority queue, or perhaps an array could function here. The solution becomes much more complex when it has to scale.
In this article, we are going to go over several unscalable ways of handling this problem as well a scalable way of handling it. For the purpose of this problem, we are going to assume that we have a Todo list with 10 million items all ranked by their priority (scroll down to the solution section to skip to the meat). Obviously this is an unrealistic example, but the purpose forces us to come up with a solution that scales.
There are a number of naive approaches. They might be appropriate solutions, but will generally not scale well. The commonality that all of these approaches share is that changing the priority/rank of a single Todo item affects all other todo items before it can be returned to the user.
(1) Priority Field:
This naive approach adds an integer to each Todo item. This is ordered from 1 — n, 1 being the lowest priority and n being the highest priority.
Pros: By ordering the priority in reverse, it makes adding Todo items very easily. Simply find the total number of Todos and add one. The new Todo item will now be set to the very top of the list without affecting any other todo items
Cons: Changing the rank of a todo is very expensive. In the list of 10 million todos, if I move my brand new todo (priority = 10000000) to priority = 1, I now have to update 10 million entries just to increment each priority by 1. Changing the priority cannot be an atomic interaction and will…