We present OceanStore, a global persistent data store designed to scale to billions of users. This system is based on a utility model in which service providers both compete and cooperate to provide data storage service to clients of the system. One of the most difficult aspects of such a system is \emph{maintenance}. A large system is hard to tune for performance; moreover, on account of its size some subset of its components will be failing at any one time. We claim that maintaining such a system is impossible without automatic software support. To that end, we have designed our system to be largely self-maintaining. It recovers from server and network failures, efficiently incorporates new resources, and adjusts to changing usage patterns, all without manual intervention. We describe our approach and present a general architecture for systems of this type.