A technique allocates storage from a plurality of storage pools of a data storage assembly to host storage. The technique involves receiving an allocation request and, in response to the allocation request, performing a set of probability-based allocation attempt operations that attempts to allocate a storage portion from one of the plurality of storage pools to the host storage. Each storage pool of the plurality of storage pools provides multiple storage portions of physical storage to store host data. The technique further involves, based on a result of the set of probability-based allocation attempt operations, provisioning the host storage with a storage portion from a particular pool of the plurality of storage pools to satisfy the allocation request.