A method comprising: enqueueing messages from a plurality of enqueuers in a plurality of shards (202, 204, 206) of a particular queue, wherein the ordering of the messages within each shard (202, 204, 206) is preserved, but the ordering of messages between shards (202, 204, 206) is not preserved; assigning a first enqueuer of the plurality of enqueuers to a first shard of the plurality of shards (202, 204, 206), wherein all messages from the first enqueuer are stored in only the first shard; assigning a second enqueuer of the plurality of enqueuers to a second shard of the plurality of shards (202, 204, 206), wherein all messages from the second enqueuer are stored only in the second shard; maintaining, in volatile memory, a first message cache for the first shard and a second message cache for the second shard; assigning a plurality of partitions of a queue table to the plurality of shards (202, 204, 206); wherein enqueueing messages from the first enqueuer includes: for each persistent message, inserting a row that corresponds to the message in a partition (302, 304) associated with the first shard, and for each message, adding a cache entry for the message to the first message cache; wherein enqueueing messages from the second enqueuer includes: for each persistent message, inserting a row that corresponds to the message in a partition (306, 308) associated with the second shard, and for each message, adding a cache entry for the message to the second message cache; causing at least one subscriber of subscribers of the particular queue to dequeue messages from each of the plurality of shards (202, 204, 206), wherein all messages enqueued in the same shard (202, 204, 206) are dequeued in the same order as they were enqueued; wherein the method is performed by one or more computing devices. enqueueing messages from a plurality of enqueuers in a plurality of shards (202, 204, 206) of a particular queue, wherein the ordering of the messages within each shard (202, 204, 206) is preserved, but the ordering of messages between shards (202, 204, 206) is not preserved; assigning a first enqueuer of the plurality of enqueuers to a first shard of the plurality of shards (202, 204, 206), wherein all messages from the first enqueuer are stored in only the first shard; assigning a second enqueuer of the plurality of enqueuers to a second shard of the plurality of shards (202, 204, 206), wherein all messages from the second enqueuer are stored only in the second shard; maintaining, in volatile memory, a first message cache for the first shard and a second message cache for the second shard; assigning a plurality of partitions of a queue table to the plurality of shards (202, 204, 206); wherein enqueueing messages from the first enqueuer includes: for each persistent message, inserting a row that corresponds to the message in a partition (302, 304) associated with the first shard, and for each message, adding a cache entry for the message to the first message cache; for each persistent message, inserting a row that corresponds to the message in a partition (302, 304) associated with the first shard, and for each message, adding a cache entry for the message to the first message cache; wherein enqueueing messages from the second enqueuer includes: for each persistent message, inserting a row that corresponds to the message in a partition (306, 308) associated with the second shard, and for each message, adding a cache entry for the message to the second message cache; for each persistent message, inserting a row that corresponds to the message in a partition (306, 308) associated with the second shard, and for each message, adding a cache entry for the message to the second message cache; causing at least one subscriber of subscribers of the particular queue to dequeue messages from each of the plurality of shards (202, 204, 206), wherein all messages enqueued in the same shard (202, 204, 206) are dequeued in the same order as they were enqueued; wherein the method is performed by one or more computing devices.