A dynamically expandable and contractible fault-tolerant storage system employs a virtual hot spare that is created from unused storage capacity across a plurality of storage devices. This unused storage capacity is available if and when a storage device fails for storage of data recovered from the remaining storage device(s). On an ongoing basis, the storage system may determine the amount of unused storage capacity that would be required for the virtual hot spare (e.g., based on the number of storage devices, the capacities of the various storage devices, the amount of data stored, and the manner in which the data is stored) and generate a signal if additional storage capacity is needed for a virtual hot spare.