Search code examples
algorithmlistdata-synchronization

Synchronize two lists of objects

Problem

I have two lists of objects. Each object contains the following:

  • GUID (allows to determine if objects are the same — from business point of view)
  • Timestamp (updates to current UTC each time the object changed)
  • Version (positive integer; increments each time the object changed)
  • Deleted (boolean flag; switches to "true" instead of actual object deleting)
  • Data (some useful payload)
  • Any other fields if need

Next, I need to sync two lists according to these rules:

  • If object with some GUID presented only in one list, it should be copied to another list
  • If object with some GUID presented in both lists, the instance with less Version should be replaced with one having greater Version (nothing to do if versions are equal)

Real-world requirements:

  • Each list has 50k+ objects, each object is about 1 Kb
  • Lists are placed on different machines connected via Internet (e.g., mobile app and remote server), thus, algorithm shouldn't waste the traffic or CPU much
  • Most of time (say, 96%) lists are already synced before sync process, hence, the algorithm should determine it with minimal effort
  • If there are any differences, most of time they are pretty small (3-5 objects changed/added)
  • Should proceed OK if one list is empty (and other still has 50k+ items)

Solution #1 (currently implemented)

  1. Client stores the time-of-last-sync-succeed (say T)
  2. Both lists are asked for all objects having Timestamp > T (i.e. recently modified; in the production it's ... > (T - day) for better robustness)
  3. These lists of recently modified objects are synced naively:
    • items presented only in first list are saved to second list
    • items presented only in second list are saved to first list
    • other items has their Version's compared and saved to appropriative list (if need)

Procs:

  • Works great with small changes
  • Almost fits the requirements

Cons:

  • Depends on T, which makes the algorithm fragile: it's easy to sync last updates, but hard to make sure lists are completely synced (using minimal T like 1970-01-01 just hangs the sync process)

My questions:

  1. Is there any common / best-practice / proved way to sync object lists?
  2. Is there any better [than #1] solutions for my case?

P.S. Already viewed, not duplicates:

Solution

  • Summary

    All answers has some worth points. To summarize, here is the compiled answer I was looking for, based on finally implemented working sync system:

    1. In general, use Merkle trees. They are dramatically efficient in comparing large amounts of data.

    2. If you can, rebuild your hash tree from scratch every time you need it. Check the time required to rebuild hash tree. Most likely it's pretty fast (e.g., in my case on Nexus 4 rebuilding tree for 20k items takes ~2 sec: 1.8 sec for fetching data from DB + 0.2 sec for building tree; the server performs ~20x faster), so you don't need to store the tree in the DB and maintain it when data changed (my first try was rebuilding only relevant branches — it's not too complicated to implement, but is very fragile).

    3. Nevertheless, it's ok to cache and reuse tree if no data modifications was done at all. Once modification happened, invalidate the whole cache.

    Technical details

    • GUID is 32 chars long without any hyphens/braces, lowercase;
    • I use 16-ary tree with the height of 4, where each branch is related to the GUID's char. It may be implemented as actual tree or map:
      • 0000 → (hash of items with GUID 0000*)
      • 0001 → (hash of items with GUID 0001*)
      • ...
      • ffff → (hash of items with GUID ffff*);
      • 000 → (hash of hashes 000_)
      • ...
      • 00 → (hash of hashes 00_)
      • ...
      • () → (root hash, i.e. hash of hashes _)

    Thus, the tree has 65536 leafs and requires 2 Mb of memory; each leaf covers ~N/65536 data items. Binary trees would be 2x more efficient in terms of memory, but it's a harder to implement.

    • I had to implement these methods:

      • getHash() — returns root hash; used for primary check (as mentioned, in 96% that's all we need to test);
      • getHashChildren(x) — returns list of hashes x_ (at most 16); used for effective, single-request discovering data difference;
      • findByIdPrefix(x) — returns items with GUID x*, x must contain exactly 4 chars; used for requesting leaf items;
      • count(x) — returns number of items with GUID x*; when reasonably small, we can dismiss checking tree branch-by-branch and transfer bunch of items with single request;

    • As far as syncing is done per-branch transmitting small amounts of data, it's very responsive (you can check the progress at any time) + very robust for unexpected terminating (e.g., due to network failure) and easily restarts from the last point if need.

    • IMPORTANT: sometimes you will stuck with conflicting state: {version_1 = version_2, but hash_1 != hash_2}: in this case you must make some decision (maybe with user's help or comparing timestamps as last resort) and rewrite some item with another to resolve the conflict, otherwise you'll end up with unsynced and unsyncable hash trees.

    Possible improvements

    • Implement transmitting (GUID, Version) pairs without payload for lightweighting requests.