2

Suppose I have an application that accepts an arbitrary stream of objects. Some of those objects appear multiple times in this stream. The job of my application is to filter out those duplicate objects from the stream and pass a duplicate-free version of the stream to the next application. This is usually trivial, but for the sake of redundancy I want to create multiple instances of this duplicate-checker on multiple machines so that it can continue running when one machine dies for whatever reason. How would I make such a duplicate check if it is run in parallel? How can you synchronize this without constantly blocking all instances except for one? Is this even possible?

Note: I'm not looking for a particular implementation or a solution in some language, this is more a conceptual question.

Improve this question
7
  • Just so we're clear. There is one stream of objects and when an object has passed the filter before, it should then never be allowed to pass again?
    – Jonathan van de Veen
    Commented Feb 23, 2018 at 12:00
  • @JonathanvandeVeen Yes, exactly. If it helps: possible duplicates would occur relatively close to each other, so it's possible to see the same object again a couple seconds later on the input stream, but after a while (minutes, tops) it will definitely not come in again.
    – Shadowigor
    Commented Feb 23, 2018 at 12:44
  • Have a circular buffer at the input-gathering or the consuming end which is large enough to hold a minute of input. Ignore ones that are already in the buffer. There is only one app at the consuming end, right? If you want multiple machines to do the sifting, store just the identifying info for the objects in a database accessible to all machines. Instead of trying to delete, just mark an object to be ignored. (Distributing deletes is an unsolvable problem.) Check the database before consuming an object. In other words: use a database, that is what they are for.
    – user251748
    Commented Feb 23, 2018 at 14:14
  • Just so we're clear part 2: "it should then never be allowed to pass again" How long is "never"? Is there some sort of finite time frame here, and if so, what is it? For the duration of a request? For a day? A month? Couple of years? Or is it really indefinite? Also, do you process these streams on the go, not knowing when they will end, or can you read all the data first, and then work with everything at once?
    – Filip Milovanović
    Commented Feb 23, 2018 at 17:22
  • @nocomprende But if the same object appears twice in a very short time and is handled by two different machines, couldn't the object slip through one machine before the other machine can mark it as invalid? How do you synchronize this?
    – Shadowigor
    Commented Feb 26, 2018 at 12:04

1 Answer 1

Reset to default
2

You want a distributed cache, such as memcached. However, in contrast to the normal use case,

  1. instead of documents to serve, you'll want to store hash values of each object seen.
  2. you want to use the service to ensure correctness, not just to speed up thing, i.e. it is not OK to miss a few duplicated requests (as would be the case for a page cache)

Unfortunately, cache coherency is one of the proverbially hard things in computing. Before you use a standard solution, you must make sure that it can actually guarantee you that requests are processed in some defined order, i.e. a duplicate cannot slip through merely because it was queried on two different nodes in quick succession. Depending on how strict your requirements are, many such aches may not be able to give such a guarantee.

Improve this answer
1
  • Use a database to store the hashes?
    – user251748
    Commented Feb 23, 2018 at 14:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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