Storage system and method of operating thereof

A storage system comprising a plurality of physical storage devices constituting a physical storage space characterized by physical addresses and controlled by a plurality of storage control devices constituting a storage control layer, the storage control layer operable to represent to a plurality of hosts a logical address space divided into one or more logical groups, the system comprising:

• a memory accessible to the storage control layer and configured to accommodate a plurality of data structures, each given data structure being associated with a logical group and informative of a location in the physical storage space of allocation chunks, each of the allocation chunks being characterized by a predefined number K of available consecutive physical addresses, wherein the predefined number K is equal for all of the allocation chunks indicated by the given data structure, and wherein there are at least two data structures such that a first number K predefined for all allocation chunks indicated by a first data structure differs from a second number K predefined for all allocation chunks indicated by a second data structure;
• and
• a processor operatively coupled to the memory and configured to:
• prior to writing to the physical storage space a data chunk associated with a given logical group, identify, among the plurality of data structures, a data structure associated with the given logical group and informative of a location of allocation chunks with the predefined number K equal to a number M of consecutive physical addresses required for storing the data chunk;
• allocate, for the data chunk, M consecutive physical addresses in accordance with the location of the allocation chunk, the location of the allocation chunk being obtained from the identified data structure;
• and
• upon completion of writing the data chunk, update, in accordance with availability of consecutive physical addresses resulted from completion, at least all data structures associated with all logical groups sharing at least part of the physical address space with the identified data structure,
• wherein each data given structure is configured as a hierarchical multilevel bitmap comprising at least two bitmaps,
• wherein a first bitmap of the at least two bit maps is a bitmap of the lowest level,
• wherein each bit in the first bitmap corresponds to a physical address in the physical address space and bears indication of availability of a corresponding data block,
• wherein each bit in a second bitmap, which is a parent of the first bitmap and a higher level bitmap than the first bitmap, corresponds to K bits in the first bitmap and bears indication of availability of an allocation chunk of K consecutive data blocks corresponding to respective K bits in the first bitmap, and
• wherein obtaining location from the identified data structure comprises traversing the hierarchical multilevel bitmap starting from the highest level bitmap of the hierarchical multilevel bitmap and subsequently going to a next lower level bitmap.

A computer program product implemented on a non-transitory computer usable medium having computer readable program code embodied therein to cause the computer to perform a method of operating a storage system comprising a plurality of physical storage devices constituting a physical storage space characterized by physical addresses and controlled by a plurality of storage control devices constituting a storage control layer, the storage control layer operable to represent to a plurality of hosts a logical address space divided into one or more logical groups, the method comprising:

• accommodating, in a memory accessible to the storage control layer, a plurality of data structures, each given data structure being associated with a logical group and informative of a location in the physical storage space of allocation chunks, each of the allocation chunks being characterized by a predefined number K of available consecutive physical addresses, wherein the predefined number K is equal for all of the allocation chunks indicated by the given data structure, and wherein there are at least two data structures such that a first number K predefined for all allocation chunks indicated by a first data structure differs from a second number K predefined for all allocation chunks indicated by a second data structure;
• prior to writing to the physical storage space a data chunk associated with a given logical group, identifying, among the plurality of data structures, a data structure associated with the given logical group and informative of a location of allocation chunks with the predefined number K equal to a number M of consecutive physical addresses required for storing the data chunk;
• allocating, for the data chunk, M consecutive physical addresses in accordance with the location of the allocation chunk, the location of the allocation chunk being obtained from the identified data structure;
• and
• upon completion of writing the data chunk, updating, in accordance with availability of consecutive physical addresses resulted from completion, at least all data structures associated with all logical groups sharing at least part of the physical address space with the identified data structure,
• wherein each given data structure is configured as a hierarchical multilevel bitmap comprising at least two bitmaps,
• wherein a first bitmap of the at least two bit maps is a bitmap of the lowest level,
• wherein each bit in the first bitmap corresponds to a physical address in the physical address space and bears indication of availability of a corresponding data block,
• wherein each bit in a second bitmap, which is a parent of the first bitmap and a higher level bitmap than the first bitmap, corresponds to K bits in the first bitmap and bears indication of availability of an allocation chunk of K consecutive data blocks corresponding to respective K bits in the first bitmap, and
• wherein obtaining location from the identified data structure comprises traversing the hierarchical multilevel bitmap starting from the highest level bitmap of the hierarchical multilevel bitmap and subsequently going to a next lower level bitmap.