A cloud-based, highly consumable queuing service must provide extreme scalability, flexible models of consistency, and high availability in the presence of network partitions. CAP theorem states that at most two of the three properties - Consistency, Availability, and Partition Tolerance - can be achieved at the same time for any shared data system. This paper presents the design and implementation of a scalable cloud-based queuing service, named SilverDove Queuing Service (SDQS). SDQS offers two kinds of consistency levels to applications: the first guarantees exactly-once and no-order delivery and the second exactly-once and in-order delivery. Meanwhile SDQS provides high availability and network partition tolerance. SDQS is designed and developed on top of IBM WebSphere eXtreme Scale, an in-memory data grid system. Performance experiments are carried out in a cloud computing environment and the results show that SilverDove has linear scalability with both of the consistency levels. © 2010 IEEE.