Diffing a JSON document

Question

Well, my question is a little complicated, but here goes:

I have a Python server that stores client (written in JavaScript) sessions, and has complete knowledge of what the client currently has stored in its state.

The server will constantly fetch data from the database and check for any changes against the client state. The data is JSON; consisting mostly of lists and dicts. I need a way to send a response to the client telling it to alter its data to match what the server has.

I have considered:

• Sending a JSON-serialised recursively diffed dict of changed elements and not ever using lists - not bad, but I can't use lists
• Send the entire server version of the client state to the client - costly and inefficient
• Find some convoluted way to diff lists - painful and messy
• Text-based diff of the two after dumping as JSON - plain silly

I'm pretty stumped on this, and I'd appreciate any help with this.

UPDATE

I'm considering sending nulls to the client to remove data it no longer requires and that the server has removed from its version of the client state.

Answer 1

Related question

• http://stackoverflow.com/questions/584338/how-to-push-diffs-of-data-possibly-json-to-a-server

See

• http://ajaxian.com/archives/json-diff-released
• http://michael.hinnerup.net/blog/2008/01/15/diffing_json_objects/

There are a couple of possible approaches:

1. Do an actual tree-parsing recursive diff;
2. Encapsulate your JSON updates such that they generate the diff at the same time;
3. Generate change-only JSON directly from your data.

What are your expected mean and max sizes for client-state JSON?

What are your expected mean and max sizes for diff updates?

How often will updates be requested?

How quickly does the base data change?

Why can't you use lists?

You could store just a last-known client state timestamp and query the database for items which have changed since then - effectively, let the database do the diff for you. This would require a last-changed timestamp and item-deleted flag on each table item; instead of directly deleting items, set the item-deleted flag, and have a cleanup query that deletes all records with item-deleted flag set more than two full update cycles ago.

It might be helpful to see some sample data - two sets of JSON client-state data and the diff between them.