Notes on Google Keep's list item ordering approach

I'm working on a personal grocery list application. I want it to be collaborative and that means I need to work out how to support list reordering in a way that is robust to concurrent edits. I'm already familiar with a number of techniques in the abstract, but I thought it would be worthwhile to work out how a real application handles it. Luckily Google's Keep application runs in the browser so I can easily inspect its behavior via browser developer tools.

Raw Observations

# initial
a: 
  sortValue: 0
b: 
  sortValue: -1048576
c: 
  sortValue: -2097152
d: 
  sortValue: -3145728

# reorder d
a:
  sortValue: 0
b:
  sortValue: -1048576
d:
  sortValue: -1572864
c: 
  sortValue: -2097152

# nest c under b
a: 
  sortValue: 0
b: 
  sortValue: -1048576
c: # now under b
  sortValue: -1179648
  superListItemId: b.id
d: 
  sortValue: -1572864

# add e
a: 
  sortValue: 0
b: 
  sortValue: -1048576
c: # now under b
  sortValue: -1179648
  superListItemId: b.id
d: 
  sortValue: -1572864
e:
  sortValue: -2621440

Some conclusions

Sort values use negative numbers. New items are added to the bottom of the list. New values are assigned via max(sortValue) - 1048576

1048576 - 0       = 1048576
2097152 - 1048576 = 1048576
3145728 - 2097152 = 1048576
2621440 - 1572864 = 1048576

When an item is moved -- either by reordering or nesting -- the item's new sortValue is assigned as the number half-way between the items on either side of its new position, i.e. above.sortValue + (absdiff(below.sortValue, above.sortValue) / 2).

See this example from above where d is reordered to be above c:

-1048576  - ((2097152 - 1048576) / 2)

If we assume these are integers this has the downside that these midpoints will eventually converge. If we assume these are arbitrary precision floats then, in theory, there will always be another midpoint.

If we assume these are integers the initial interval size is 2^20 so there should be room for 20 insertions. Let's see! (drag and drop controls kinda suck for this!!!!)

We'll start with the following:

a: 0
b: -1048576
c: -2097152

---

a: 0
c: -524288
b: -2097152

---
a: 0
b: -262144
c: -524288

---
a: 0
c: -131072
b: -262144

---
# ... at swap no. 19
a: 0
b: -4
c: -8

---
a: 0
c: -2
b: -4

---
a: 0
b: -1
c: -2

---
# this is the swap that could either reveal these are arbitrary precision floats
# or cause c to either go to 0 or -1 (thus messing up the sort)
a: 2097152
c: 1572864
b: 1048576

!!! Instead of converging or going into decimals, it readjusts a, b and c all at once and buys another ~20 swaps. Keep's API makes this straightforward to implement. It POSTs a set of new data to a /changes endpoint which responds with an arbitrary set of changes for the client to apply to its state. It doesn't exchange a total representation of the list or of the list's items; it exchanges changes.

This example was kinda trivial since we only had the three items and they were all at the top of the list already. I wonder what would happen if we had items above and below the cluster.

side note: If you clear out all the items in a list the sortValue resets to 0.

So far it appears that it updates the sortValues of all items in the list when an insert would cause a collision. An unexpected observation: rather than mirror the initial state of the list and assign sortValues in decreasing order starting from 0 for the first item in the list, it appears to assign sortValues in increasing order with 0 assigned to the last item in the list. I noticed that part of the API payloads is this configuration:

{
  "nodeSettings": {
    "newListItemPlacement": "BOTTOM"
  }
}

To me this indicates that the use of negative numbers initially is probably driven primarily by the "add to bottom" behavior. This produces mildly surprising behavior when the list reorders to avoid a collision: it prefers to start from 0 and increment sortValues.

clarkenciel/google-keep-sort-notes.md

Notes on Google Keep's list item ordering approach

Raw Observations

Some conclusions