An online service includes databases that are upgraded while still processing requests. For example, web servers continue to request operations on the database while it is being upgraded. The schema of the database is upgraded before the web servers are upgraded to utilize the upgraded schema. Changes that are made to the upgraded schema are backwards compatible with the schema being used during the upgrade process. Restrictions are placed on the operations performed on the database during the upgrade process. After upgrading the schema, the web servers of the online service are upgraded to use the upgraded schema.