Shulou(Shulou.com)06/02 Report--

This article was first posted on the official account of Wechat, vivo Internet technology.

Link: https://mp.weixin.qq.com/s/LGLqEOlGExKob8xEXXWckQ

Author: Qian Xingchuan

In a distributed environment, we often define data distribution through certain rules. The modular algorithm and consistency Hash (Consistent Hash) described in this paper generate a key through certain rules, and perform regular operations on the key to figure out where the data should go.

This article uses the software environment: Java 8

I. Overview of the definition of data distribution interface

In the distributed environment, we often define the data distribution through certain rules, such as the data of user 1 is stored in database 1 and the data of user 2 is stored in database 2.

In general, there are several common ways:

There is a unique central distribution node in a distributed environment. Every time the data is stored, the central node is asked where the data should go, and the distribution node explicitly tells the data where to go.

Generate a key through certain rules, and perform regular operations on the key to figure out where the data should go. The modular algorithm and consistent Hash described in this paper is such a way. Interface definition / * * data distribution hash algorithm interface definition * @ author xingchuan.qxc**/public interface HashNodeService {/ * add a data storage node * @ param node*/public void addNode (Node node) to the cluster; / * find out which node is used to store data * @ param key* @ return*/public Node lookupNode (String key) / * * hash algorithm * @ param key* @ return*/public Long hash (String key); / * simulate unexpected circumstances to cut off a node to test the cache hit rate * @ param node*/public void removeNodeUnexpected (Node node);} II. Implementation of data distribution algorithm-- Overview of modular algorithm

The application scenarios of the modularization algorithm are described as follows:

Need to achieve a user data storage load balancing in the cluster, there are n storage nodes in the cluster, how to evenly distribute each data to these n nodes?

The implementation steps are roughly divided into two steps:

Fetch a hash value through the user's key

The number of storage nodes n is modeled by this hash value, and an index is obtained.

The index above is the ID of the node to be stored

Note: this article is an example of the way I generate hash values, and I use the CRC32 approach.

Code implementation: * @ author xingchuan.qxc**/public class NormalHashNodeServiceImpl implements HashNodeService {/ * * Storage Node list * / private List nodes = new ArrayList (); @ Overridepublic void addNode (Node node) {this.nodes.add (node);} @ Overridepublic Node lookupNode (String key) {long k = hash (key); int index = (int) (k% nodes.size ()); return nodes.get (index) @ Overridepublic Long hash (String key) {CRC32 crc32 = new CRC32 (); crc32.update (key.getBytes ()); return crc32.getValue ();} @ Overridepublic void removeNodeUnexpected (Node node) {nodes.remove (node);}}

From the above example, we can see that when lookupNode, it is necessary to first take the value of the CRC32 of the key, then modulo the number of nodes in the cluster to get r, and finally return the Node with the subscript r.

The test code is as follows:

HashNodeService nodeService = new NormalHashNodeServiceImpl (); Node addNode1 = new Node ("xingchuan.node1", "192.168.0.11"); Node addNode2 = new Node ("xingchuan.node2", "192.168.0.12"); Node addNode3 = new Node ("xingchuan.node3", "192.168.0.13"); Node addNode4 = new Node ("xingchuan.node4", "192.168.0.14"); Node addNode5 = new Node ("xingchuan.node5", "192.168.0.15") Node addNode6 = new Node ("xingchuan.node6", "192.168.0.16"); Node addNode7 = new Node ("xingchuan.node7", "192.168.0.17"); Node addNode8 = new Node ("xingchuan.node8", "192.168.0.18"); nodeService.addNode (addNode1); nodeService.addNode (addNode2); nodeService.addNode (addNode3); nodeService.addNode (addNode4); nodeService.addNode (addNode5); nodeService.addNode (addNode6); nodeService.addNode (addNode7); nodeService.addNode (addNode8) / / used to check data distribution Map countmap = new HashMap (); Node node = null;for (int I = 1; I

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.