1

I have a system in which some data is inserted into database. Whenever that data is inserted subscribers should be notified about that (it doesn't have to happen just after inserting, but there is a time limit so I can wait like 10 s and then notify about X number of data inserted).

Problem is that each subscriber may have a filter. So lets say that new record was inserted to database and it is a product of type: shoes. I have 1 k of subscribers who are interested in that so they should receive email with that information but some of them have filter so that only if it is size 10.

What would be the best design for that to make it scallable?

Right now I have a process that keeps on looking for new records in database and for each one it iterates through all subscribers trying to find out if this user should be notified and if yes I send message to the queue with record and subscriber ID so that another component will receive it and send to that user.

This way I can have X number of components looking for new data and Y number of components receiving events from queue and sending notifications to users so it can be scalled out but still I think that it is not the optimal way for doing that.

Thanks for help

  • How scalable do you need? Thousands of mails a day is different to hundreds of thousands. If you really need scalability look at something like Twitter heron, but that is probably overkill for what you need. – user1937198 Jun 15 at 15:20
1

NFSA

Non-deterministic Finite State Machine.

That is what your current algorithm looks like. You are in one node (the item just inserted), and that node has a very large number of edges, one per each subscription, with a activation rule (the filter).

Now you can execute the filter on each edge, every time you are in that node, but this is slow.

Like you pointed out there are a set of subscribers who are interested in any node, and a set who are only interested in size 10 nodes. The take away is that both of these sets don't change. The set interested in everything is still interested in everything, and the set of size 10s is only interested in size 10s.

So lets flip the question. What groups of subscribbers do you have?

Compile to DFSA

What we would like to do is have a data-structure where each node represents one question (or piece of the filter) and that question has an array of answers. Taking your shoe analogy, we want a node Size of Shoe and it has an array of shoe sizes [5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]. We want to place each subscriber into the bucket corresponding to the answer. This way when we look at the shoe, and it size 10, the size 10 bucket will have every subscriber interested in size 10 shoes.

This can be iterated a little. You can setup separate indicies per question, and join them. Which is excellent if you have a relational database.

Alternately, you can this setup as a tree. Each answer contains either a pointer to the next branch, or a bucket of subscribers (perhaps both a bucket of subscribbers that are always interested, and a pointer to those who might be interested given...). This is better for situation where it needs to be done without a database.

An optimisation you might want to make is that people who have no filter preference are placed in a special answer bucket. This bucket has to be searched and subscribers added to the bucket corresponding to the answer. Technically this brings us back to a NFSA approach, just a much more nuanced approach.

The downside to this approach is that every change to the filter requires maintenance of this data-structure, which slows down filter amendments. The upside is that execution will be orders of magnitude faster.

| improve this answer | |
  • Hello thanks for idea, I think that it will work great if buckets size is well known. But what if filter would be like regex for example companyName = "pattern". Shoe is just simplified example you know that I'm working on different domain but it doesn;t matter. – Witos May 15 at 6:08
  • Then you could try a dynamic approach. Have a special bucket that just keeps all of the maybes. First try to answer the query by looking up the bucket associated with the answer. If it exists great, that's the answer. Otherwise you have to pickup the maybes and generate the answer the hard way. Once you've made it memorise it and add it to the direct lookup. You can get fancy with approach and manage the total amount of space dedicated to precomputed answers and thin it out when it grows too large. take a read of Russ Cox on regex it might help. – Kain0_0 May 15 at 6:17

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.