A method that includes instructing multiple compute entities, by an expansion manager and during a first phase of the stored entity metadata re-balancing, to: lookup any stored entity metadata by using: (a) a current translation function for linking identifiers of stored entities to stored entities metadata; wherein the current translation function is based on a size of a current storage space allocated to stored entities metadata; and (b) a next translation function for linking identifiers of stored entities to stored entities metadata; wherein the next translation function is based on a size of a next storage space allocated to stored entities metadata; wherein the current space is expanded during the expansion of the storage system to provide the next storage space, and to update any stored entity metadata accessed using the current translation function without updating stored entity metadata accessed using the next translation function.