Powered by Tachyonic Project Luxon Framework v0.0.0

Luxon Framework for rapid application development. (luxon)

Version

Sharding

Sharding is a method for distributing data across multiple machines. Luxon provides utilities for sharding to support deployments with very large data sets and high throughput operations.

Database systems with large data sets or high throughput applications can challenge the capacity of a single server. For example, high query rates can exhaust the CPU capacity of the server. Working set sizes larger than the system’s RAM stress the I/O capacity of disk drives.

There are two methods for addressing system growth: vertical and horizontal scaling.

Vertical Scaling involves increasing the capacity of a single server, such as using a more powerful CPU, adding more RAM, or increasing the amount of storage space. Limitations in available technology may restrict a single machine from being sufficiently powerful for a given workload. Additionally, Cloud-based providers have hard ceilings based on available hardware configurations. As a result, there is a practical maximum for vertical scaling.

Horizontal Scaling involves dividing the system dataset and load over multiple servers, adding additional servers to increase capacity as required. While the overall speed or capacity of a single machine may not be high, each machine handles a subset of the overall workload, potentially providing better efficiency than a single high-speed high-capacity server. Expanding the capacity of the deployment only requires adding additional servers as needed, which can be a lower overall cost than high-end hardware for a single machine. The trade off is increased complexity in infrastructure and maintenance for the deployment.

Consistent hashing ring utilities module.

Consistent hashing on a ring is used by a lot of NoSQL type datastores use it. The idea is that you have a ring that is numbered 0 to a huge number (2**22) and the piece of data is assigned a number/slot on that ring. As you add new nodes to the system they are given a number on that ring and will basically be declared as the owner of certain range of ‘slots’ on that ring.

class luxon.utils.sharding.NodesTree(nodes_path=None, ring_power=22, replicas=2)[source]

NodesTree.

Nodes and zones are stored in the NodesTree. Howeveer these are placed in prepared lists. The prepared list is a set of a empty items with a value of None. New nodes/zones are placed at the last empty entry. This is a deliberate attempt to ensure nodes/zones are within a consistant order and can be referenced by the index.

All prepared lists are created based on the relevent size of the ring determined by the ring_power. The Ring Power has a direct impact on the maximum zones and nodes.

The Ring provides the ability to:
  • Add/Updata/Delete zones.
  • Add/Updata/Delete nodes.
  • Ensure zones and nodes are always in consistant order.
  • Provide replica nodes for ring to build.
Parameters:
  • nodes_path (str) – Load exisiting nodes from pickle file.
  • ring_power (int) – Bits for size of ring. (should never change)
  • replicas (int) – Duplicate nodes to distribute.
add_node(zone, weight=1, node_id=None, **kwargs)[source]

Add node.

Parameters:
  • zone (str) – Exisiting Zone name.
  • weight (float/int) – Weight for element.
  • node_id (str) – Unique ID or automatically provided UUID. (optional)
  • **kwargs – Arbitrary options for nodes.
Returns:

Node with property value pairs.

Return type:

dict

add_zone(zone)[source]

Add zone.

Parameters:zone (str) – Zone name.
build_replicates()[source]

Build nodes into individual replicas for Ring Builder.

Ring builder builds composite Rings where individual rings will be built for each replica. The purpose of this method is return the nodes grouped together for the composite rings.

It is recommended that replicates is evenly deviseable between zones for even distribution and or replicates are equal zones.

The algorithem ensures that no replicate has the same zone. If more replicates than zones, then it create copies of previous replicates within order. Its important to ensure replicates have unique zones as much as possible to ensure data is spread over the zones and not within the same zone only. If more zones than replicates then these are appended to replicates.

Returns:replica to nodes.
Return type:list
delete_node(node_id)[source]

Delete node.

Parameters:node_id (str) – Unique Node Identifier.
delete_zone(zone)[source]

Delete zone.

Parameters:zone (str) – Exisiting zone name.
get_node(node, raw=False)[source]

Return node.

Parameters:raw (bool) – If raw do not format for user-friendly view.
Returns:Node with property value pairs.
Return type:dict
get_nodes(raw=False)[source]

Get all nodes.

Parameters:raw (bool) – If raw do not format for user-friendly view.
Returns:All nodes.
Return type:tuple
get_zone_slot(zone)[source]

Get zone slot.

Parameters:zone (str) – Exisiting Zone name.
rename_zone(zone, to_zone)[source]

Rename zone to zone.

Parameters:
  • zone (str) – Exisiting zone name.
  • to_zone (str) – New zone name.
save(nodes_path)[source]

Save nodes to pickle.

Parameters:nodes_path (str) – Path to ring pickle file.
test_create_nodes(nodes=1, zone=1)[source]

Create Test node entries.

Parameters:
  • nodes (int) – Number of Nodes to create.
  • zone (int) – zone to create or add nodes to.
update_node(node_id, zone=None, weight=None, **kwargs)[source]

Update node.

Parameters:
  • node_id (str) – Unique Node Identifier.
  • zone (str) – Exisiting zone name.
  • weight (float/int) – Weight for element.
  • **kwargs – Arbitrary options for nodes.
Returns:

Node with property value pairs.

Return type:

dict

zones

Return zones.

Returns:List of zones, zone being tuple ( ‘name’, slot )
Return type:tuple
zones2nodes

Zones to nodes.

Provides a tuple of zones with nodes in each zone.

class luxon.utils.sharding.Ring(nodes, ring_path=None, ring_power=22, replicas=2)[source]

Ring is used to build a consistent hashing ring and manage through out its life span. Its important the nodes are added in specific exact same order to ensure minimal changes to the ring. For speed and consistancy a ring should be saved and loaded from previous ring.

The Ring provides the ability to:
  • Snapshots to ensure previous known slot locations are availible.
  • Get Nodes for specific hashed data_id.
  • Ability to check if slot location has changed for node.
  • Provide remote replicas for Node slots.
  • Versioning of Ring on adding of nodes or build/rebalance.

When rebuilding/rebalancing the Ring using the build method a snapshot is created. (Only 4 snapshots are kept) An Object store could use snapshots to try locate a missing or moved object by iterating the snapshots. The more snapshots you need to iterate to find slot containing object in object store the slower the lookup will be. Ensure you make all changes required for rebuilding/rebalancing the ring. If you need to add 3 nodes for example, ensure you add all of them at once before rebuilding/rebalancing.

Versioning could be used to determine if the Ring is upto date with other endpoints using the Ring. All endpoints should have same copy of the ring. Endpoints being nodes/devices that contain distribute load of objects for example.

The ring has some test methods to validate and test the algorithems.

Each node can be assigned to a zone. Zones are preferred for replica copies. If more replicas exist than zones, then some zones will be re-used for repica copies.

Its recommended to ensure equal amount of zones than duplicate copies. For example using replicas 2 then 3 zones should be used.

Altering the replicas and zones will increase the amount of slots being re-assigned. In an object store this means more data will be moved around during a reblance/rebuild. This functionality is not allowed.

The ring_power determiens the size of each replica ring. A ring_power of 16 bits is used by default. This ensures each ring has 65535 slots. Using this ring_power ensures if 4096 nodes in replica have equal weight, they can occupy 16 slots each. Its not recommended to have more than 4096 nodes in a zone using 16bit Ring Size.

Parameters:

nodes (NodesTree) – NodesTree Object.

Keyword Arguments:
 
  • ring_path (str/bytes) – Load exisiting ring from pickle file.
  • ring_power (int) – Bits for size of ring. (should never change)
  • replicas (int) – Duplicate nodes to distribute.
build()[source]

Build/Rebalance ring.

Build composite Ring, which consists of ‘replica’ rings.

get(data_id, duplicate=False)[source]

Get nodes by consistant hash.

Parameters:
  • data_id (int,str) – Unique id to hash to slot.
  • duplicate (bool) – Remove Duplicate nodes in older snapshots. (dafault: False)
Returns:

Snapshots with value of replica nodes in tuple.

Return type:

tuple

get_composite_slot(slot, duplicate=False)[source]

Gets nodes by composite slot in ring.

Parameters:
  • slot (int) – Ring slot number.
  • duplicate (bool) – Remove duplicate nodes in older snapshots. (dafault: False)
Returns:

Snapshots with value of replica nodes in tuple.

Return type:

tuple

get_ring_slot(slot, duplicate=False)[source]

Get nodes by slot for composite ring.

Parameters:
  • slot (int) – Ring slot number.
  • duplicate (bool) – Remove duplicate nodes in older snapshots. (dafault: False)
Returns:

Snapshots with value of replica nodes in tuple.

Return type:

tuple

save(ring_path)[source]

Save ring to pickle file.

Parameters:ring_path (str) – Path to ring pickle file.
test_compare()[source]

Test snapshot comparison.

When two or more snapshots are created this function is used to determine how many objects have moved. The simulation is is based on a small amunt of of data_id(s) and therefor expected no have perfect results.

iterations_to_match: Iterations needed to match a original node. moved_objects: Moved objects. percent_moved: Percent moved. object_found_first: Object found first. object_found_first_percent: Object found first found percent.

Returns:
(iterations to match, moved_objects, percent_moved,
object_found_first, object_found_first_percent)
Return type:tuple
test_distribution()[source]

Test Distribution.

Test distirbution of objects between nodes and zones.

Returns:(nodes, zones)
Return type:tuple
version

Return version.

luxon.utils.sharding.build_empty_array(size)[source]

Build empty array.

Parameters:size (int) – Size.
Returns:Array of size with ‘None’ values.
Return type:Array
luxon.utils.sharding.build_empty_list(size)[source]

Build empty List.

Parameters:size (int) – Size.
Returns:List of size with ‘None’ values.
Return type:list
luxon.utils.sharding.build_ring(nodes, ring_power, replica=None)[source]

Build ring with slots.

The slots are references to nodes and the total number of slots is determined by the ring_power. If the slot power is 16(bits) then 65536 slots will be placed in a list known as the ring.

If we have 2 nodes, and the ring_power is 16bits. Then node 1 will be placed in items range of 0 to 32767 and node 2 will be in items range of 32768 to 65535.

get_slot(ring_power, data_id) function is used to select a node slot.

Nodes are required to be a list / tuple. ( weight, node_id )

Example of nodes list:
[ ( 1.0, ‘1’ ), ( 1.0, ‘2’ ) ]

The weight determines how to evenly distribute the nodes in the ring. If node 1 has double the weight of node 2, then effectively node 1 will occupy two thirds of the ring, while node 2 will only have one third of the ring.

Example usage:
nodes = [ ( 1.0, '1' ), ( 1.0, '2' ), ]

ring = build_ring(nodes, 2)

for node in ring:
    print(node)
Parameters:
  • nodes (list) – List of nodes.
  • ring_power (int) – Bits of ring size.
  • replica (int) – Replica for informational purposes (logging).
Returns:

Ring.

Return type:

list

luxon.utils.sharding.get_slot(ring_power, data_id)[source]

Obtain ring slot.

This function uses consistent hashing to hash the ‘data_id’ provided.

Since data ids are often textual names and not numbers, like paths for files or URLs, it makes sense to use a “real” hashing algorithm to convert the names to numbers first. The benefit of using a hashing algorithm like MD5 is that the resulting hashes have a known even distribution, meaning your ids will be evenly distributed.

Since the ‘slot’ count is always a power of two, it is easy to use bit manipulation on the hash to determine the ‘slot’ rather than modulus. It isn’t much faster, but it is a little.

The ‘slot’ shift value is known internally to the ring. This value is used to shift an MD5 hash of a ‘data_id’ to calculate the partition on which the data for that item should reside. Only the top four bytes of the hash are used in this process.

We only byte shift the top four bytes of the hash with the ‘ring_power’ which defines the ring size.

Any data_id values provided will be converted to string.

Parameters:
  • ring_power (int) – Bits of ring size.
  • data_id (int,str) – Unique id to hash to slot.
Returns:

Ring slot number.

Return type:

int

luxon.utils.sharding.parse_id(node_id)[source]

Validate node id and format to str.

Parameters:node_id (str,int) – node unique id.
Returns:Correctly formatted node id.
Return type:str
Raises:ValueError – Invalid node id.
luxon.utils.sharding.parse_weight(weight)[source]

Validate node weight and format to float.

Parameters:weight (str,int,float) – node weight.
Returns:Correctly formatted node weight.
Return type:float
Raises:ValueError – Invalid node weight.
luxon.utils.sharding.parse_zone(zone)[source]

Validate zone name and format to str.

Parameters:zone (str,int) – zone name.
Returns:Correctly formatted zone name.
Return type:str
Raises:ValueError – Invalid zone name.