3

Update I updated my question to reflect the fact I'm working with a database. I need to process user actions:

  1. The actions for each user change the user's balance which is then persisted to a database.
  2. A user's action must be processed sequentially. Otherwise, we might corrupt the balance in the database.
  3. Some actions are associated with 2 users in which case they can't run in parallel with either user's actions.
  4. The volume of actions per user varies considerably during the day.
  5. Update The processes are going to be distributed over several machines.

I am trying to find a way to distribute the actions between processes so that the above requirements are met.

Is there a known paradigm, architecture or algorithm that solves such a problem?

I'm looking for a solution that does not involve processes talking to each other except through a message queue or some other scalable mediator.

daramasala
  • 273
  • 2
  • 7
  • You can try bin packing algorithms. Instead of physical objects, try to envision your actions as an object with actions that have dependencies taking up two slots. Then define how many threads you can run in parallel to be the rows and time to be the columns and try packing actions so that they don't overlap – slebetman May 06 '15 at 05:53
  • I can't tell when a process finished a group of actions. Or at least it is very hard to do since the processes will live on different machines. – daramasala May 06 '15 at 08:07
  • What you've described is too vague to have an "algorithm". But the solution you've asked for is an example of "communicating sequential processes" (google it). – Simon B May 06 '15 at 09:13

2 Answers2

1

A simple greedy approach should fulfill your requirements. I assume you have an ordered input queue with all actions to process, and a list of actions associated with corresponding users currently under (parallel) processing (lets call these "users under processing"). Whenever the processing of one action is done, it is removed, and you check the next elements from your input queue which ones can be added as next without a collision with the users under processing. Note that you check the full queue in order, not just the top element.

You can add new actions to the processing list as long you have actions for users currently not under processing. If you need to restrict the number of processes in parallel to some number N, that's easily done by not adding more than N actions to the currently processed acctions.

Doc Brown
  • 199,015
  • 33
  • 367
  • 565
  • I am thinking about distributed processing. So I can't "look" in the "users under processing" queue which will be a message queue. – daramasala May 06 '15 at 08:03
  • When you can look into the "users under processing" queue, you easily get the information when a process is finished - it is whenever the number of users under processing decreases. You can at least get that information by polling. So what you wrote in the comment below your question ("I can't tell when a process finished a group of actions") does not make sense to me. – Doc Brown May 06 '15 at 11:01
0

I would suggest you look into scheduling algorithms: a list of scheduling algorithms by category here

and partial order relations to make sure the order of the actions of a given user is respected. You can generate a tree of dependencies using the relations which would help you in scheduling.

Hicham Hammouche
  • 1
  • 1