6

I'm working on a file-synchronization client that currently produces a stream of changes to the underlying filesystem. That is a stream of create/update/move/delete events is produced for each synchronization "target".

Each event includes a sequence-ID, which provides information about the ordering of events, and then information such as:

  • source path (& destination path for move events)
  • md5 (for files)
  • mtime timestamp
  • event type : {create, move, update, delete}

This works reasonably well, but there are often redundancies. For example, a move from path X to path Y and then back to path X will be reported as two events:

  1. X -> Y
  2. Y -> X

This is clearly redundant, and can be removed altogether from the stream.

Are there any well-documented techniques for detecting and removing such redundancies?

Similarly, is there a well-understood and efficient way to detect redundancies stemming from deletions? For example:

  1. Update A
  2. A -> B
  3. B -> C
  4. Delete C

Here, changes 1 - 4 could be reduced to Delete A.

Informal approaches, along with academic papers would be most welcome, bearing in mind that it's not uncommon to encounter streams of tens of thousands of events in this case.

Many thanks!

EDIT

Does this problem have a name? The reason I'm here is because google has failed me, and I'm guessing this is because I'm missing some vocabulary!

  • 1
    The closest existing thing I can think of is the optimization stage of a compiler. For instance, peephole optimization often removes redundant moves in exactly the same way (e.g. from AX to BX and back to AX again). – Kilian Foth Jan 23 '18 at 12:45
  • @KilianFoth I have the same intuition as you, despite having only the most superficial understanding of how compilers work. Could you please recommend some reading materials? – blz Jan 23 '18 at 12:54
  • This is also similar to the way React handles a stream of events that update a web page's DOM. Their solution was to make the changes to a "Shadow DOM" and then periodically diff the Shadow DOM against the real DOM and apply the patch to update the real DOM with only the differences. Not sure if that's too heavy handed an approach for your problem though. – combinatorics Jan 23 '18 at 13:44
  • Does this problem have a name?, not sure about exact term, but tools such as git do something similar. – S.D. Jan 23 '18 at 13:47
  • It is an optimization problem, but the solution depends on how time plays a factor into this. For example Update A, A->B, wait a day, B->C, wait a day, Delete C might not be correct to simply reduce to Delete A. Waiting a day is a bit over the top, but you get the idea. Do you optimize your work queue as work items are queued in? How quickly are items pulled off the stack? – Berin Loritsch Jan 23 '18 at 13:52
2

What you're describing is very similar in code generation & optimization.

A difference is that in code generation copies are not destructive, whereas in your situation, the moves are destructive of the originals. However, I believe many of the same approaches could be adapted to your situation. So, I'll point some of them out. Optimization operates on a sequence or stream of instructions.

The code stream being optimized contains instructions like

Copy X -> Y
...
Copy Y -> X

We want to eliminate unnecessary copies in the final optimized code stream. So one approach is copy propagation. The optimization equates X & Y together upon seeing the first copy and substitutes Y for X later to eliminate presence of Y. Thus the code becomes:

//Copy X -> Y  eliminated by copy elimination, by equating X & Y
...             // here verify that X is not changed so X still == Y 
Copy X -> X     // later eliminated as redundant

Another optimization is called dead code elimination. This works backward through the stream. First some late element in the stream generates an instruction whose target isn't subsequently used,

add P + Q -> X
add X + Y -> Z

(here Z is not used) so that instruction is eliminated. That affects the preceding instructions that generate targets (X, Y) that were sourced by the eliminated instruction as their targets may no longer be used. So some preceding instructions can also be eliminated, and this can work backward through the stream.

These analyses involves detecting uses (sources) and definitions (targets), in an algorithm or field called data flow analysis. It is probably more complex in code generation b/c of the control flow within the instruction stream that needs to be factored into the algorithm. Control flow in cg is usually broken down into units called basic blocks that are sequences of sequential flow from start to end; the basic blocks are then interconnected by control flow operations (fork,join,loop). Your stream probably doesn't have control flow to deal with so it would be like doing the first part of data flow analysis, which happens on a single basic block and skipping the iteration that computes a larger procedure or program from those basic blocks. See also def-use chain.

  • I'm upvoting this because while @Useless' answer is quite good (and very much deserving up an upvote), I have already tried something similar and found it tedious and error-prone. This, on the other hand, is more along the lines of what I had in mind. Any recommended reading beyond the links provided would be most appreciated! Thanks! – blz Jan 23 '18 at 18:01
  • While my answer focused on the simple pathname-based collapsing you asked about, a better structure is probably required if you have to deal with links, and particularly hard links, instead. – Useless Jan 24 '18 at 10:52
4

All you have to do is buffer your structured events such that you can look them up by affected path (source and destination, probably).

The actual mechanism for combining any given pair of events will depend on what those events are, so you just need to manually code the optimisations you want.

It's much simpler to do this pairwise than to somehow recognise chains of 4 events. For example:

  1. copy and delete of source -> move

    • get delete event, look up other events indexed by deleted path
    • find one, a copy
    • matching path is the source of the copy
    • so replace it by a move
  2. copy and delete of dest -> no-op

    • as above, but matching path is the destination
    • remove original copy event and you're done
  3. move and another move

    • get a move event, look up other events indexed by source path
    • find a move whose dest path matches
    • replace move(source1,dest1)+move(dest1,source2) with move(source1,dest2)

I assume you're processing the events in sequence order, so your chain of 4 events will be collapsed pairwise.

You can probably find a nice way to structure and express it as a rules engine or something, but it might take more effort than just coding the transformations you want directly.

  • By rescanning your queue a couple times, you can resolve more complex duplication as well. If round 1 optimized move A->B, move B->C, delete C to move A->C, delete C, round 2 would optimize that to no-op. You'll have to have a maximum evaluation depth and evaluate until either there are no changes or you've hit the maximum limit. Most of the examples would be resolved in 2-3 passes, which would be a reasonable starting limit. – Berin Loritsch Jan 23 '18 at 15:00
  • Yep, if you have a pre-populated sequence to process then looping is sensible: I assumed processing the stream event-by-event, which has largely the same effect (because you do one pass for each event received in order). – Useless Jan 24 '18 at 10:48

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.