How to move an element in a sorted list and keep the CouchDb write "atomic"

Question

I have elements of a list in couchdb documents. Let's say these are 3 elements in 3 documents:

{ "id" : "783587346", "type" : "aList", "content" : "joey", "sort" : 100.0 }
{ "id" : "358734ff6", "type" : "aList", "content" : "jill", "sort" : 110.0 }
{ "id" : "abf587346", "type" : "aList", "content" : "jack", "sort" : 120.0 }

A view retrieves all "aList" documents and displays them sorted by "sort".

Now I want to move the elements, when I want to move "jack" to the middle, I could do this atomic in one write and change it's sort key to 105.0. The view now returns the documents in the new sort order.

After a lot of sorting I could end up with sort keys like 50.99999 and 50.99998 after some years and in extreme situations run out of digits?

What can you recommend, is there a better way to do this? I'd rather keep the elements in seperate documents. Different users might edit different list elements in parallel.

And users might also change the document order at the same time (which also can get tricky when 2 users want to move two different documents (like joey and jill) to the end with let's say "sort" = 130.0 at the same time).

Maybe there is a much better way?

Did I miss something on CouchDb transactions?

Answer 1

You are using the common pattern of a real number for user control of sorting. That is a fine technique, recommended by Damien Katz. To move between adjacent documents A and B, then you set your sort field to the average of A.sort and B.sort.

This question has several parts.

What about floating point precision?

Javascript Numbers are double-precision IEEE-754 floating point numbers. They have limited precision.

Doubles have a lot of precision. If this is human-initiated activity then it will be a very long time before dragging and dropping hits the limit. But you have two choices:

1. Re-normalize the sort values in the background

Remember rewriting your line numbers in BASIC? Same thing.

Have a cron job or some other task (NodeJS is getting popular) to check for unacceptably close sort values and space them out. This could use sophisticated heuristics such as:

• Wait until the site is under low activity to fix the sorts
• Wait until a specific user to be inactive for X time before fixing his sorts
• Only make modifications which space out sort values but which never change the view result. In other words, if you have 0.001, 0.002, and 0.003, move the 0.003 first to e.g. 0.100, then change 0.002 to 0.005. That may have a slight helpful effect in the UI but remember, replication may not copy these in the same order so the benefit is marginal, perhaps not worth the complexity.

2. Use a decimal data type with unlimited precision

Instead of sort storing a Javascript Number, it could store a string from but not including "0.0" through "1.0" (say, to 100 digits). Then a string sort is also a numeric sort. (You have "anchors" at 0.0 and 1.0 which are invalid for documents. To insert a document in the first position, set sort to the average of 0.0 and the current first document. For the last position, sort is the average of the last document and 1.0.)

Next, your client (whoever calculates the sort value) needs arbitrary-precision real number types. Java, Ruby, Python, pretty much all the languages have them. This post even inspired me to make a quick project, BigDecimal for Javascript which is the BigDecimal code from Google Web Toolkit (which itself came from Apache Harmony). But there are other implementations too.

I personally like BigDecimal. In your case however you would have to change your code to use a string for sort. However the benefit is, you never have to re-normalize the sorts to work around the precision.

What about collisions from concurrent activity?

CouchDB is Relaxed. What will happen is what users expect. CouchDB documents mimic the real world. As Chris Anderson says, "there are no transactions in real life."

For three elements in a UI:

• ItemA
• ItemB
• ItemC

What if I move A after C and you move B after C? Clearly, the list will either be C B A or C A B. Which should it be? That depends on your application?

Either, it doesn't matter: Great! CouchDB will order A and B arbitrarily and you will be fine. Users will infer (or see if your UI is good) that somebody else moved the other item.

Or,B must come before A because [some reason]: Well then, your sort value is wrong. It should include all relevant data to decide sub-sorts. For example, you can emit([120.000, doc.userLastName], doc). When users move docs to the same place, the sort becomes alphabetical.

If you say, A cannot be moved so soon after B moved then that is also application code that must be implemented regardless of the data store. In other words, it's not a transactional thing, it is software logic. For dragging and dropping UI elements, my feeling is, it's not worth it and the "it doesn't matter" solution is best.

Answer 2

Is the current system really atomic? After all, to move jack between joey and jill, we need to know the values of joey and jill which requires that they were queried first. It's perfectly feasible that in between the time 105.0 is calculated, the vales of joey and jill have also changed. In fact, I believe the only way this could work in SQL land would be to lock the relevant rows while reordering took place, resulting in a serializing of re-order requests.

Perhaps more details concerning the problem would be more useful.

Answer 3

What about adding 10 to anything >= 110, then updating the record 130 to 110 ? That allows you to keep clean intervals. Not ideal for records that are frequently updated by multiple users, nor for huge tables, but I am using that technique successfully on a small and rather static table.