I am reading about scaling of database and came to know about sharding technique. But I also read about consistent hashing technique. So how practically sharding is implemented? Do we arrange nodes in ring like consistent hashing and then assign servers to rings and then data to servers? Because as I see if my number of shards changes at run time, and if consistent hashing technique is not there, then it will mess up a lot of stuff. Can someone please throw some light on this?
Add a comment
|
1 Answer
Consider sharding as a form of distributed hash table, or distributed range table.
Now it depends on which one the above the sharding is doing.
For a distributed hash table, for each new piece of data added, it hashes the data and based on that hash directs the data to that machine/set of machines for persistence.
When a query comes in it is sent to all servers, and the results are combined, and depending on how complex the query is some post-processing may occur (because each machine must be over selective as query data may be split between two shards) before sending back to the user.
In this scheme you don't need perfect hashing, because every database is being asked. However you might want to optimise some queries like select * from X where id = '123'. If you don't have perfect hashing you must ask all shards the question, as while the hash might not point at them now, it might have when the data was added.
For a distributed range table, for each new piece of data added, it is sent to a machine/set of machine based on which part of the range it is in. For example 1-15 -> shard A 16-22 -> shard B. Shard might become unbalanced using this method and its not uncommon to have a background process splitting large shards into smaller shards and relocating a portion to a less utilised set of machines. In this sense a set of machines may be responsible for numerous sub sections of the range.
When a query comes in it is decomposed into simpler queries, and those simpler queries are directed to only those machines how could possibly have matching data. But instead of sending the results back to the co-ordinator, those machines might be directed to send results to each other so that then next subquery can be run on the proper shard. At the end of this the final queries data can be directly streamed back to the user.
In this scheme I would not call the partitioning function a Hash. For those properties that are part of partition, then it is possible to identify the exact shard/s that the value/s might be in, if it exists at all. But for those properties not in the partition all shards must be checked.
Of course real life databases are much more complicated than this. This is just a bed time story to help in the understanding of what's going on. A real system has to do this while also managing transactions, synchronisation, networks, etc.., and be fast.
-
so for hash based method 1 you explained, we need to arrange them in form of ring as in consistent hashing and then allocate ranges to each nodes,am i correct? Feb 10, 2021 at 17:40
-
Not sure I can parse your question. In method 1, the hash points to the machine/machine set its located on. When the number of machine/machine sets change in the database it can change to which machine/machine set the same hashed value points to. You could make each shard independent of a machine/machine set with a cross-walk table, but if that is the case you are better to follow method 2, and partition the data instead.– Kain0_0Feb 10, 2021 at 21:31
-
method 2 can can have unbalanced partitions. What i asked was our hash fxn will be of form hash(key)%n, and now if n changes by adding or deletion of db nodes, it will effect all mappings, as new has fxn will be hash(key)%(n+1) ,assume a new db server is added, how can we make sure we get min. change in existing mappings by change of hash fxn. IS consistent hashing is the answer to this? Feb 11, 2021 at 16:07
-
Method 2: yes, the reason for having a background process break/merge/load balancing them. Method 1: Yes the reason why every shard has to be checked. There is no way to perform consistent hashing because there is no way to obtain a consistent list, except by fiat. And if you are this far, go to method 2.– Kain0_0Feb 12, 2021 at 1:09
-
I think we are on different track.What do you mean by "consistent list",If i want to scale my server count up/down later, I would need min. keys movement, so somehow i think strategy like consistent hashing might help. By consistent hashing i mean, servers are arranged in a ring by hash fxn and then keys are also arranged in similar way by going in clockwise direction if no server at hashed location. Feb 13, 2021 at 12:15