# US 10,482,012 B1 · Storage system and method of operating thereof > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 10,482,012 B1 - Document ID: US10482012B1 - Status: Granted - Kind: B1 - Application number: 14/969,957 - Filed: 2015-12-15 - Granted: 2019-11-19 - Earliest claimed: 2014-12-31 - Assignees: Storone Ltd. - Applicants: Storone Ltd. - Inventors: Raz Gordon - Web page: https://patentgrep.com/patent/US10482012B1 ## CPC - G06F 3/061: {Improving I/O performance} - G06F 12/0292: {using tables or multilevel address translation means (G06F12/023 takes precedence; address translation in virtual memory systems G06F12/10)} - G06F 3/0608: {Saving storage space on storage systems} - G06F 3/0631: {by allocating resources to storage systems} - G06F 3/064: {Management of blocks} - G06F 3/0644: {Management of space entities, e.g. partitions, extents, pools} - G06F 3/0665: {at area level, e.g. provisioning of virtual or logical volumes} - G06F 3/0683: {Plurality of storage devices} - G06F 3/0689: {Disk arrays, e.g. RAID, JBOD} - G06F 12/0284: {Multiple user address space allocation, e.g. using different base addresses (interprocessor communication G06F15/163)} - G06F 12/0868: Data transfer between cache memory and other subsystems, e.g. storage devices or host systems - G06F 2212/1041: Resource optimization - G06F 2212/151: Emulated environment, e.g. virtual machine - G06F 2212/254: Distributed memory - G06F 2212/261: Storage comprising a plurality of storage devices - G06F 2212/651: Multi-level translation tables - G06F 2212/657: Virtual address space management - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract Disclosing a storage system, method of operating thereof and data structures usable for the operating. The method includes: accommodating a plurality of data structures informative of location of allocation chunks, each allocation chunk characterized by a predefined number K of available consecutive physical addresses; wherein the predefined number K is equal for all allocation chunks indicated by the same data structure and wherein there are at least two data structures informative of location of allocation chunks with a different predefined number K; identifying, prior to writing a data chunk, a data structure associated with respective logical group and informative of location of allocation chunks with the predefined number K equal to number M of consecutive physical addresses required for storing the data chunk; and allocating for the data chunk M consecutive physical addresses in accordance with the location of the allocation chunk, the location obtained from the identified data structure. ## Claims ### Claim 1 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. ### Claim 2 (depends on 1) The method of claim 1, wherein the identified data structure further comprises a third bitmap, which is a parent of the second bitmap and a higher level bitmap than the second bitmap, and wherein each bit of the third bitmap corresponds to a predefined number N of bits in the second bitmap and bears an indication of an aggregated availability status of corresponding N data chunks mapped by the second bitmap. ### Claim 3 (depends on 1) The method of claim 1, wherein the identified data structure comprises a plurality of third bitmaps organized in hierarchical manner, wherein each bit in a third bitmap, which is a parent of the second bitmap, corresponds to a predefined number N of bits in the second bitmap and bears an indication of an aggregated availability status of corresponding N data chunks mapped by the second bitmap, and wherein each bit in a third bitmap of a next hierarchical level corresponds to a predefined number N of bits in a previous hierarchical level and bears an indication of an aggregated availability status of corresponding N data chunks mapped by N bits of the previous level bitmap. ### Claim 4 (depends on 2) The method of claim 2, wherein a number of levels in the data structure are defined by Log N(Y), where Y is the total number of bits in the first bitmap and N=K. ### Claim 5 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. ### Claim 6 (depends on 5) The system of claim 5, wherein the identified data structure further comprises a third bitmap, which is a parent of the second bitmap and a higher level bitmap than the second bitmap, and wherein each bit of the third bitmap corresponds to a predefined number N of bits in the second bitmap and bears an indication of an aggregated availability status of corresponding N data chunks mapped by the second bitmap. ### Claim 7 (depends on 5) The system of claim 5, wherein the identified data structure comprises a plurality of third bitmaps organized in hierarchical manner, wherein each bit in a third bitmap, which is a parent of the second bitmap, corresponds to a predefined number N of bits in the second bitmap and bears an indication of an aggregated availability status of corresponding N data chunks mapped by the second bitmap, and wherein each bit in a third bitmap of a next hierarchical level corresponds to a predefined number N of bits in a previous hierarchical level and bears an indication of an aggregated availability status of corresponding N data chunks mapped by N bits of the previous level bitmap. ### Claim 8 (depends on 6) The system of claim 6, wherein a number of levels in the data structure are defined by Log N(Y), where Y is the total number of bits in the first bitmap and N=K. ### Claim 9 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. ### Claim 10 (depends on 9) The computer program product of claim 9, wherein the identified data structure further comprises a third bitmap, which is a parent of the second bitmap and a higher level bitmap than the second bitmap, and wherein each bit of the third bitmap corresponds to a predefined number N of bits in the second bitmap and bears an indication of an aggregated availability status of corresponding N data chunks mapped by the second bitmap. ### Claim 11 (depends on 9) The computer program product of claim 9, wherein the identified data structure comprises a plurality of third bitmaps organized in hierarchical manner, wherein each bit in a third bitmap, which is a parent of the second bitmap, corresponds to a predefined number N of bits in the second bitmap and bears an indication of an aggregated availability status of corresponding N data chunks mapped by the second bitmap, and wherein each bit in a third bitmap of a next hierarchical level corresponds to a predefined number N of bits in a third bitmap of a previous hierarchical level and bears an indication of an aggregated availability status of corresponding N data chunks mapped by N bits in the third bitmap of the previous level.