Synchronization of data across microservices

"We are considering creating a queue for each microservice and publishing the messages to the queues via SNS."

Yes, then your queues can subscribe to the notification and you no longer need the message service. Essentially its fan out routing. Your microservices become queue workers

However, lots of queues and notifications can become complicated. SQS + SNS is a bit clunky in some respects. I would be tempted to limit my use of it to cases where I definitely have long running async tasks.

If you can fit 4 or 5 micro-services on one ec2 instance because they are all small simple operations that aren't stressed, you've simply separated them for architectural concerns. Then it might be worth just having them call each other when required.

It's very easy to take queues to the nth degree and have millions of nano services communicating via sns messages. It's not that this doesn't work, but you do have to monitor these queues and worry about dropped and double sent messages, full queues, error queues etc.

After doing a bit more research, I stumbled upon this article from which I've pulled some quotes out that I think is helpful for what I want to accomplish (and for any future readers). This offers a way to adopt a reactive programming model over an imperative programming model.

Event-sourcing

The idea here is to represent every application’s state transition in a form of an immutable event. Events are then stored in a log or journal form as they occur (also referred to as ‘event store’). They can also be queried and stored indefinitely, aiming to represent how the application’s state, as a whole, evolved over time.

What this helps accomplish is that if a microservice goes down yet other events pertinent to it are being published and events are consumed by, say, other instances of that microservice, when that microservice comes back up, it can refer to this event store to retrieve all the events that it missed during the period it went down.

Apache Kafka as Event Broker

Consider the use of Apache Kafka which can store and dispatch thousands of events per second and has built-in replication and fault-tolerance mechanisms. It has a persistent store of events which can be stored on disk indefinitely and consumed at any time (but not removed) from the Topic (Kafka's fancy queue) were delivered to.

The events are then assigned offsets that univocally identify them within the Topic — Kafka can manage the offsets itself, easily providing “at most once” or “at least once” delivery semantics, but they can also be negotiated when an event consumer joins a Topic, allowing microservices to start consuming events from any arbitrary place in time — usually from where the consumer left off. If the last consumed event offset is transactionally persisted in the services’s local storage when the usecases ‘successfully complete’, that offset can easily be used to achieve an “exactly once” event delivery semantics.

In fact, when consumers identify themselves to Kafka, Kafka will record which messages were delivered to which consumer so that it doesn't serve it up again.

Sagas

For more complex usecases where the communication among different services is indeed necessary, the responsibility of finishing the usecase must be well recognized — the usecase is decentralized and only finishes when all the services involved acknowledge their task as successfully completed, otherwise the whole usecase must fail and corrective measures must be triggered to rollback any invalid local state.

This is when saga comes into play. A saga is a sequence of local transactions. Each local transaction updates the database and publishes a message or event to trigger the next local transaction in the saga. If a local transaction fails because it violates a business rule then the saga executes a series of compensating transactions that undo the changes that were made by the preceding local transactions. Read this for more info.