0

In a client-server architecture, what technique is used to efficiently update ordered list of items without actually sending the entire list?

Note that multiple clients will be updating the order of the list simultaneously and the server will decide the correct order.

EDIT: For more clarity.

Say example I have a real-time Kanban board web application and all participants can change the order of tasks in the columns by, say, drag and drop. I want to update the order of the tasks for all clients when the order changes.

I was thinking that I can give each task a property e.g. rank (float type) and then when the position changes, I can update its rank as such:

thisTask.rank = (beforeTask.rank + afterTask.rank) / 2.0f

And then just send thisTask to all clients.

But I would like to know whether there are more efficient way to do it since this method is limited by the sizeof(float) and may introduce issues with conflict resolution at the server level.

  • Please provide an example with data and code. Unclear what you mean by "entire list" and "server will decide the correct order." – Dan Wilson Jul 31 '18 at 10:21
  • @Jake did you find the solution? It could be good for the question to get a valid answer and that could be your current solution. So far I see, the core of any solution goes through concurrency control. Pessimistic or optimistic will depend on the business and the user experience. – Laiv Nov 29 '18 at 12:04
  • @Laiv unfortunately no definitive answer I can find on the internet. Yes, I would like a mathematical approach rather than a concurrency control solution. – Jake Dec 7 '18 at 2:35
  • @jake have you realised that you are basically implementing something similiar to a Google Spreadsheet? Have you "debuged" a Google Spreadsheet to get some ideas? I have some ideas about how to do it, but they all are the same: micro-synchronization + redolog (concurrency control) – Laiv Dec 7 '18 at 5:51
  • Regarding mathematical approaches, the keyword is "rank aggregation": algorithms for identifying the ranking that is the closest approximation to a set of differing rankings. These problems arise in voting theory. – Marco Dec 29 '18 at 14:53
0

You can either send the entire list (you don't want to ok!) or... .. create a protocol between client and server.

Server to client
send_full_list ( if new client connects or on client request)

send_deleted_item (pass reference to the index in the list)

send_modified_item (pass reference to the index in the list + changes)

send_added_item (pass reference to the index in the list where to insert)

Client to Server

please_send_full_list

Both client and server will need code to make this work. You need strong acknowledgements to avoid things getting out of sync.

One way for clients to be sure their list is not out of sync is that Server sends a hash or CRC of the full list along with every change. Then the Client can regenerate the CRC on its updated list and test for a match with what the server sent. If NOT the same Client would need to request a new full list - otherwise it is confident its updated list is true.

However, simplest and safest to send the full list, unless it VERY large.

  • 1
    I think the problem with this approach is when you change one item, say move it to the top of the list. do you also change all the other items, moving them down by one. If so, you are bound to run into conflicts with other users moving items – Ewan Jul 31 '18 at 10:48
  • His scenario is unclear, but I took it to mean complying with Observer Pattern, where the server alone "decides" changes of state ( ie in the list) and propagates changes to clients. If clients are not making changes, and server is in control, then there is no conflict. Otherwise you are quite right! Let Jake clarify as needed I would say. – bcperth Jul 31 '18 at 10:58
  • ahh, makes sense – Ewan Jul 31 '18 at 11:00
  • In my question, all clients can change (request to change) the order of the items. It will send to the server, and the server will resolve the final order of items. – Jake Dec 7 '18 at 2:32
0

The answer to this depends enourmously on how you are structuring your web service application.

But if you are using REST, and JSON, an excellent choice would be to use JSON Patch or enter link description here

e.g.

 curl -X PATCH -d '{ "op": "remove", "path": "/biscuits/0" }' URL'
 curl -X PATCH -d '{ "op": "add", "path": "/biscuits/1", "value": { "name": "Nut" } }'

To deal with 'multiple clients will be update the order of the list simultaneously' - with JSON Patch (and REST) you can GET the ETAG associated with the current version of your 'array', and do those updates with a CONDITIONAL prefix. e.g.

PATCH /my/data HTTP/1.1
Host: example.org
Content-Length: 326
Content-Type: application/json-patch+json
If-Match: "abc123"

[
     { "op": "test", "path": "/a/b/c", "value": "foo" },
     { "op": "remove", "path": "/a/b/c" },
     { "op": "add", "path": "/a/b/c", "value": [ "foo", "bar" ] },
     { "op": "replace", "path": "/a/b/c", "value": 42 },
     { "op": "move", "from": "/a/b/c", "path": "/a/b/d" },
     { "op": "copy", "from": "/a/b/d", "path": "/a/b/e" }
]

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.