A method and apparatus for message cache sizing are provided. A plurality of messages from one or more enqueuers are enqueued in a queue comprising at least one shard. Each shard includes one or more subshards. A message cache configured to store a plurality of cached subshards is maintained in memory. The plurality of messages is dequeued from the message cache by one or more dequeuers. An estimated enqueue rate is determined for each shard. An estimated dequeue rate is determined for each dequeuer-shard pair. Estimated restore overhead data is determined over a range of candidate message cache sizes based on the estimated enqueue rate for each shard and the estimated dequeue rate for each dequeuer-shard pair. A preferred message cache size is determined based on the estimated restore overhead data.