Virtualized storage system and method of operating thereof
There are provided a storage system and a method of operating thereof. The method comprises: a) representing to a plurality of hosts an available logical address space divided into one or more logical groups (e.g. logical volumes, virtual partitions, snapshots, combinations of a given logical volume and its respective snapshot(s), etc.), and b) mapping between one or more contiguous ranges of addresses related to the logical address space and one or more contiguous ranges of addresses related to the physical address space, wherein said mapping is provided with the help of one or more mapping trees, each tree assigned to a separate logical group in the logical address space. Mapping between contiguous ranges of addresses related to the logical address space and contiguous ranges of addresses related to the physical address space can be a) mapping between LBA and DBA addresses; b) mapping between VUA and VDA addresses; c) mapping between LBA and VDA addresses; and d) mapping between VUA and DBA addresses, wherein virtual unit addresses (VUA) characterize a first virtual layer operable to represent the logical address space, and virtual disk addresses (VDA) characterize a second virtual layer operable to represent the physical storage space.
1. A storage system comprising a plurality of physical storage devices constituting a physical storage space, and one or more storage control devices constituting a storage control layer, the one or more storage control devices are coupled to the plurality of physical storage devices, the storage control layer is configured to handle a logical address space divided into one or more logical groups, wherein the storage control layer further comprises an allocation module configured to provide a mapping between logical address ranges of different lengths within the logical address space and physical address ranges indicative of locations in the physical storage space, said mapping is provided by using one or more mapping trees,
wherein each mapping tree of the one or more mapping trees is assigned to a logical group of the one or more logical groups and comprises one or more leaf nodes;
wherein each leaf node of the one or more leaf nodes represents a mapping between a logical address range and a physical address range;
wherein the logical address range comprises contiguous logical addresses within the logical group;
wherein a depth of each leaf node within each one of the one or more mapping trees is indicative of a length of a logical address range represented by the leaf node; and
wherein a certain mapping tree of the at least one mapping trees has at least two leaf nodes that (a) represent logical address ranges of different lengths and (b) are located at different depths within the certain mapping tree.
2. The system of claim 1 wherein the logical group is selected from a group consisting of: one or more logical volumes, one or more virtual partitions, one or more snapshots, one or more combinations of a given logical volume and its respective one or more snapshots.
3. The system of claim 1 wherein the logical address space is has a plurality of logical block addresses (LBAs) and the physical storage space has a plurality of disk block addresses (DBAs), wherein the control layer further comprises a first virtual layer operable to represent the logical address space, said first virtual layer has a plurality of virtual unit addresses (VUA), and/or further comprises a second virtual layer operable to represent the physical storage space, said second virtual layer has a plurality of virtual disk addresses (VDA), and wherein mapping between the logical address ranges the physical address ranges comprises at least one of the mapping options selected from a group consisting of:
a) mapping between LBA and DBA addresses;
b) mapping between VUA and VDA addresses;
c) mapping between LBA and VDA addresses; and
d) mapping between VUA and DBA addresses.
4. The system of claim 1 wherein a given path followed from a root of a mapping tree of the one or more mapping trees to a given leaf node indicates an offset of a given logical address range that is represented by the given leaf node within the logical group; and wherein a value associated with the given leaf node is indicative of an offset of a given physical address range that is mapped to the given logical address range in the physical storage space.
5. The system of claim 4 wherein the given path is represented as a string of binary values, wherein different binary values represent right and left branches respectively that are comprised in the given path.
6. The system of claim 4 wherein the offset of the given logical address range within the logical group is calculated in accordance with the given path with the help of the following expression:
∑
i
=
0
d
-
1
r
i
·
2
(
M
-
i
-
1
)
where M is an exponent for representing a value of a maximum address admissible in the given logical group when used as a power of two, d is a depth of the given leaf node, successive values of i, from zero to d minus one, are successive nodes in the mapping tree leading to the given leaf node, and r, is a value equal to zero for one-side branching and equal to one for another side branching.
7. The system of claim 1 wherein a depth of a given leaf node is in inverse relation to a length of a logical address range represented by the given leaf node.
8. The system of claim 1 wherein a mapping tree of the at least one mapping trees comprises at least one leaf node with at least two associated values indicating offsets of two different physical address ranges corresponding to a same logical address range.
9. The system of claim 1 wherein the allocation module further comprises an allocation table indicating allocated and free addresses in the physical storage space, and wherein said one or more trees are associated with the allocation table.
10. A method of operating a storage system comprising a plurality of physical storage devices constituting a physical storage space, and one or more storage control devices constituting a storage control layer, coupled to a plurality of hosts and to the plurality of physical storage devices, the method comprising:
a) representing to said plurality of hosts a logical address space divided into one or more logical groups; and
b) mapping between logical address ranges of different lengths within the logical address space and physical address ranges indicative of locations in the physical address space, wherein said mapping comprises using one or more mapping trees, and assigning a mapping tree, that comprises one or more leaf nodes, to each logical group of the one or more logical groups;
wherein each leaf node of the one or more leaf nodes represents a mapping between a logical address range and a physical address range;
wherein the logical address range comprises contiguous logical addresses within the logical group;
wherein a depth of each leaf node within each one of the one or more mapping trees is indicative of a length of a logical address range represented by the leaf node; and
wherein a certain mapping tree of the one or more mapping trees has at least two leaf nodes that (a) represent logical address ranges of different lengths and (b) are located at different depths within the certain mapping tree.
11. The method of claim 10 wherein the logical groups are selected from a group consisting of: one or more logical volumes, one or more virtual partitions, one or more snapshots, one or more combinations of a given logical volume and its respective one or more snapshots.
12. The method of claim 10 wherein:
a) the logical address space has a plurality of logical block addresses (LBAs) and the physical storage space has a plurality of disk block addresses (DBAs);
b) the control layer further comprises a first virtual layer operable to represent the logical address space, said first virtual layer has plurality of virtual unit addresses (VUA), and/or further comprises a second virtual layer operable to represent the physical storage space, said second virtual layer has plurality of virtual disk addresses (VDA), and
c) mapping between the logical address and the physical address ranges comprises at least one of the mapping options selected from a group consisting of:
d) mapping between LBA and DBA addresses;
e) mapping between VUA and VDA addresses;
f) mapping between LBA and VDA addresses; and
g) mapping between VUA and DBA addresses.
13. The method of claim 10 wherein a given path followed from a root of a mapping tree of the one or more mapping trees to a given leaf node indicates an offset of a given logical address range represented by the given leaf node within the logical group; and a value associated with the given leaf node indicates an offset of a given physical address range that is mapped to the given logical address in the physical storage space.
14. The method of claim 13 wherein the given path is represented as a string of binary values, wherein different binary values represent right and left branches respectively that are comprised in the given path.
15. The method of claim 13 wherein the offset of the given logical address range within the logical group is calculated in accordance with the given path with the help of the following expression:
∑
i
=
0
d
-
1
r
i
·
2
(
M
-
i
-
1
)
where M is an exponent for presenting a value of a maximum address in the logical group when used as a power of two, d is a depth of the given leaf node, successive values of i, from zero to d minus one are successive nodes in the mapping tree leading to the given leaf node, and ri is a value equal to zero for one-side branching and equal to one for another side branching.
16. The method of claim 10 wherein a depth of a given leaf node is in inverse relation to a length of a logical address range represented by the given leaf node.
17. The method of claim 10 wherein a mapping tree of the one or more mapping trees comprises at least one leaf node with at least two associated values indicating offsets of two different physical address ranges corresponding to a same logical address range.
18. A non-transitory computer readable medium that stores computer program code that once executed on a computer causes the computer to perform:
representing, by a storage system to a plurality of hosts, a logical address space divided into one or more logical groups; and
b) mapping between logical address ranges of different lengths within the logical address space and physical address ranges indicative of locations in a physical address space that comprises one or more physical storage devices, wherein said mapping comprises using one or more mapping trees, and assigning a mapping tree, that comprises one or more leaf nodes, to each logical group of the one or more logical groups;
wherein each leaf node of the one or more leaf nodes represents a mapping between a logical address range and a physical address range;
wherein the logical address range comprises contiguous logical addresses within the logical group;
wherein a depth of each leaf node within each one of the one or more mapping trees is indicative of a length of a logical address range represented by the leaf node; and
wherein a certain mapping tree of the one or more mapping trees has at least two leaf nodes that (a) represent logical address ranges of different lengths and (b) are located at different depths within the certain mapping tree.