Scale-out datacenter applications are of enormous commercial interest, yet they are frustratingly hard to build. A common design pattern is to locate most of the application logic in a middle tier of soft-state servers and to provide storage using a separate backend system. The Partitioning and Recovery Service (PRS) is an infrastructure service that makes it easier to build these middle tier applications: it provides strong consistency on the soft state, supports arbitrary operations, and helps in recovery if state is ever lost. The PRS manages scaling out the middle tier across many machines, and hides the complexities of scale-out through a simple and powerful abstraction. We have built and evaluated the PRS, and other developers have built and deployed four scale-out soft-state datacenter applications using the PRS. Our experience with these applications confirms that the PRS significantly simplifies the construction of scale-out soft-state datacenter applications.