How do you deal with denormalization / secondary indexes in database sharding?

Question

Say I have a "message" table with 2 secondary indexes:

• "recipient_id"
• "sender_id"

I want to shard the "message" table by "recipient_id". That way to retrieve all messages sent to a certain recipient I only need to query one shard.

But at the same time, I want to be able to make a query that ask for all messages sent by a certain sender. Now I don't want to send that query to every single shard of the "message" table. One way to do this is to duplicate the data and have a "message_by_sender" table sharded by "sender_id".

The problem with that approach is that every time a message has been sent, I need to insert the message into both "message" and "message_by_sender" tables.

But what if after inserting into "message" the insertion into "message_by_sender" fail? In that case the message exists in "message" but not in "message_by_sender".

How do I make sure that if a message exists in "message" then it also exists in "message_by_sender" without resorting to 2 phase commit?

This must be a very common issue for anyone who shards their databases. How do you deal woth it?

Answer 1

There is no "silver bullet" to this problem. Some options:

1. Use a message queue to post the changes. Eventually the changes would make it to the different partitions.
2. Have a trigger on the message table partitions that create a "index entry needed" row in a table. Something else would periodically scan this and create the index.

You might want to read this blog entry about doing distributed transactions on Google App Engine: http://blog.notdot.net/2009/9/Distributed-Transactions-on-App-Engine. Basically, if you don't want 2phase commit or Paxos or something like that, then you need to live with some sort of eventually consistent model.

-Dave