Say I have two Map instances in JavaScript (or HashMap in Java, or Dictionary in C#), A and B. I want to synchronize B to A, so that B is a copy of A. I can't copy the reference and I don't want to delete all keys and re-add; I want to keep B available and mostly accurate during processing. What's the most efficient algorithm to do that?

I'm looking for a general algorithm to do cache synchronization, while keeping the second cache available. This seems to be the same as dealing with maps.

  • Sharing your research helps everyone. Tell us what you've tried and why it didn't meet your needs. This demonstrates that you've taken the time to try to help yourself, it saves us from reiterating obvious answers, and most of all it helps you get a more specific and relevant answer. Also see How to Ask – gnat Oct 14 '19 at 15:07
  • 1
    @gnat I'm trying to avoid reinventing the wheel. If the XYZ Algorithm for this is well-known, I'll implement that. I have spent considerable time searching for that. I'm not asking people to write code for me; I'm asking for a known, efficient algorithm (whose name I don't know). – TrueWill Oct 14 '19 at 19:22
  • Why synchronize after the fact instead of implementing a redundant write strategy? – Thomas Junk Oct 15 '19 at 14:57
  • @ThomasJunk Good question. Our intent is to use events with subsequent writes to synchronize, but there is a concern that the caches may drift because reasons. So this is a "backup" strategy. – TrueWill Oct 15 '19 at 17:55

If you want to synchronize your maps, but avoid cloning every time the full content there are two general strategies:

  • Before: you replicate the "commands" that modify the map: for example:

    • one map updates the other for every operation ("do it now" approach),
    • or one map keeps track of the commands that modify it and that will be executed on the other map when useful by an object responsible for syncrhonization ("replay" strategy),
    • or even all the maps are updated through commands ("pilpelining" strategy). There are big chances that the command design pattern could be of use here.
  • After: you replicate the results of the transformation by using a similar approach than for caches, by marking as dirty the objects added or changed. A syncrhonizer would then iterate over the map and replicate all inserted or changed entries (and not everything). This strategy does however no work very well with deleting and renaming of keys. So for these you'd need your map to do some additional bookkeeping to keep trace of such changes.

In both strategies, your synchronized map needs to be well encapsulated in its own data structure and channel all the changes through its API. If the native map would leak, the replication strategies could be short circuited.

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.