Another company that didn’t start red envelope!!

Problem analysis

From this conversation, can you guess the cause of all cache penetration? Before we answer that, let’s look at the code for the cache policy

Cache server IP= Hash (key)% Number of servers

The value of key can be designed according to specific services. For example, if I want to do load balancing, the key can be the server IP of the caller; Obtain user information. Key can be the user ID. And so on.

With the same number of servers, there is no problem with the above design. But remember, the real world for programmers is miserable, and the only constant is that the business changes all the time. I had no choice but to rely on technology to change this situation.

Suppose we now have 10 servers, and when we request a server with key 6, the result is 4. Now we add another server, and the number of servers becomes 11. When we request a server with key 6 again, the result is 5. It is not hard to see that not only the request with key 6, but almost all the requests have changed results. This is the problem we need to solve, and this is the main problem we need to pay attention to when designing distributed cache and similar scenarios.

Our ultimate design goal is to change the number of servers

  1. Maximize cache hit ratio (minimum data transferred)
  2. Cache data should be evenly distributed as much as possible

The solution

From the above analysis, we know that the root cause of a large number of cache failures is the change in the denominator of the formula. If we keep the denominator unchanged, we can basically reduce the amount of data being moved

Denominator invariant scheme

If we keep the denominator the same based on the formula: Cache server IP= Hash (key)% number of servers, we can basically improve the situation. Our policy for selecting a cache server becomes:

Cache server IP=hash(key)%N (N is constant)

N. You can select a value that meets the requirements for specific services. For example: we are sure that the number of servers will not exceed 100 in the future, so N can be set to 100. What’s the problem with that?

The situation can be thought of as server number is continuous, any request will hit a server, or above as an example, our server now whether 10 or increased to 11, the key to the request of the 6 can always get a server information, but our strategy formula the denominator is 100 now, if the quantity is 11, The result of the request with key 20 is 20. The server with key 20 does not exist.

That’s the problem with a simple hash strategy (a simple cohashing strategy can be abstracted as a sequence of array elements, accessed by subscripts)

To solve these problems, the industry has long had a solution, that is, consistent hashing.

Consistent hashing algorithm was proposed by Karger et al., MIT in 1997 in the solution to distributed Cache. It was designed to solve the Hot spot problem in the Internet. Consistent hashing fixes the problem with the simple hashing algorithm used by CARP, making DHT truly useful in a P2P environment.

Consistency hash specific characteristics, please baidu, here is not in detail. As for the idea of solving the problem, here should also be emphasized:

  1. First compute the hash of the server (node) and configure it to the ring, which has 2^32 nodes.
  2. The hash of the key storing the data is computed in the same way and mapped to the same circle.
  3. It then searches clockwise from the location to which the data is mapped, saving the data to the first server it finds. If no server is found after 2^32, the server is saved to the first server

What happens when you add a new server?

From the figure above we can see that the only changes are shown in yellow. Deleting a server is similar.

Consistent hashing is a solution to our current problem. There are thousands of solutions, so long as they solve the problem.

Optimization scheme

So far the plan seems perfect, but the reality is harsh. All this is good, but there are flaws. Suppose we have 3 servers, ideally the server allocation on the hash ring looks like this:

But the reality is this:

This is called hash ring skew. Uneven distribution can overwhelm servers in turn in some scenarios, which must be taken care of in real production environments. To solve this problem, virtual nodes came into being.

As shown in the figure above, the hash ring is no longer the actual server information, but the mapping information of the server information, such as servera-1, servera-2 are both mapped to ServerA, which is A replica of ServerA on the ring. This solution is to use the quantity to achieve the purpose of uniform distribution, and the subsequent need for memory may be slightly larger, which is a solution of space for design.

Further reading

  • If multiple server nodes have the same hash value, what can be done? We can use a hash table addressing scheme that searches for empty positions clockwise from the current position until an empty position is found. If not, you might wonder if your hash ring needs to be expanded, or if your denominator parameter is too small.
  • In real business, the operation of adding or removing servers is much less than finding servers, so the search speed of the data structure that we store the hash ring must be fast. Specifically speaking, the essence is: from a value of the hash ring, it can quickly find the first element that is not empty.
  • If you do a search, you’ll see that there are a lot of virtual hash links on the web that have the same number of points as 2^32. Can’t it be anything other than this number? As far as Caicai is concerned, this number is absolutely necessary to be so large as long as it meets our business needs and business data.
  • Consistent hash hash function, not only to ensure relatively high performance, but also to maintain the hash value as far as possible even distribution, this is an industrial hash function requirements, the code example of the hash function is not the best, interested students can optimize.
  • The native GetHashCode () method for consistent hashing is problematic in some languages, such as c#. The hash value of the same string changes after the program restarts. All require a more stable string to int hash algorithm.

Consistent hashing solves the essential problem that the same key can be correctly routed to the same target through the same hash function. As we usually use the database sub-table strategy, sub-library strategy, load balancing, data fragmentation and so on can be used to solve the consistency hash.

Combining theory with Practice is the Real deal

The following code can be applied directly to the production environment of small and medium projects with a few modifications

Public abstract class NodeInfo {public abstract string NodeName {get; }}Copy the code

Node information used in the test program:

class Server : NodeInfo { public string IP { get; set; } public override string NodeName { get => IP; }}Copy the code

The following is the consistent hashing core code:

/// 1. Use virtual node mode 2. 3. The number of virtual nodes for each physical node can be customized /// </summary> public class ConsistentHash {// VirtualNode information for the hash ring public class VirtualNode { public string VirtualNodeName { get; set; } public NodeInfo Node { get; set; ObjLock = new object(); private objLock = new object(); // Total number of virtual link points, default is 100 int ringNodeCount; // Number of virtual nodes for each physical node int virtualNodeNumber; Public VirtualNode[] Nodes = null; public ConsistentHash(int _ringNodeCount = 100, int _virtualNodeNumber = 3) { if (_ringNodeCount <= 0 || _virtualNodeNumber <= 0) { throw new Exception("_ringNodeCount and _virtualNodeNumber must be greater than 0"); } this.ringNodeCount = _ringNodeCount; this.virtualNodeNumber = _virtualNodeNumber; nodes = new VirtualNode[_ringNodeCount]; } // Obtain node information according to the consistent hash key, please handle the timeout problem by the business side, because in multi-threaded environment, Public NodeInfo GetNode(String Key) {var ringStartIndex = math.abs (GetKeyHashCode(key) % ringNodeCount); var vNode = FindNodeFromIndex(ringStartIndex); return vNode == null ? null : vNode.Node; } public void AddNode(NodeInfo newNode) {var nodeName = newNode. nodeName; int virtualNodeIndex = 0; Lock (objLock) {// Convert physical nodes to virtual nodes while (virtualNodeIndex < virtualNodeNumber) {var vNodeName = $"{nodeName}#{virtualNodeIndex}"; var findStartIndex = Math.Abs(GetKeyHashCode(vNodeName) % ringNodeCount); var emptyIndex = FindEmptyNodeFromIndex(findStartIndex); If (emptyIndex < 0) {// Break is exceeded; } nodes[emptyIndex] = new VirtualNode() { VirtualNodeName = vNodeName, Node = newNode }; virtualNodeIndex++; Public void RemoveNode(NodeInfo node) {var nodeName = node.nodename; int virtualNodeIndex = 0; List<string> lstRemoveNodeName = new List<string>(); while (virtualNodeIndex < virtualNodeNumber) { lstRemoveNodeName.Add($"{nodeName}#{virtualNodeIndex}"); virtualNodeIndex++; Int startFindIndex = 0; // startFindIndex = 0; lock (objLock) { while (startFindIndex < nodes.Length) { if (nodes[startFindIndex] ! = null && lstRemoveNodeName.Contains(nodes[startFindIndex].VirtualNodeName)) { nodes[startFindIndex] = null; } startFindIndex++; }} // Hash ring to get the hash value method, because the system has gethashcode, Protected virtual int GetKeyHashCode(string key) {var sh = new SHA1Managed(); byte[] data = sh.ComputeHash(Encoding.Unicode.GetBytes(key)); return BitConverter.ToInt32(data, 0); } # region private methods / / search for the first node in the virtual ring somewhere private VirtualNode FindNodeFromIndex (int startIndex) {if (nodes = = null | | nodes.Length <= 0) { return null; } VirtualNode node = null; while (node == null) { startIndex = GetNextIndex(startIndex); node = nodes[startIndex]; } return node; } private int FindEmptyNodeFromIndex(int startIndex) {while (true) {if (Nodes [startIndex] == null) { return startIndex; } var nextIndex = GetNextIndex(startIndex); NextIndex == startIndex {return -1; nextIndex == startIndex; } startIndex = nextIndex; Private int GetNextIndex(int preIndex) {int nextIndex = 0; If (preIndex! = nodes.Length - 1) { nextIndex = preIndex + 1; } return nextIndex; } #endregion }Copy the code

Test the generated nodes

ConsistentHash h = new ConsistentHash(200, 5); H.addnode (new Server() {IP = "192.168.1.1"}); H.addnode (new Server() {IP = "192.168.1.2"}); H.addnode (new Server() {IP = "192.168.1.3"}); H.addnode (new Server() {IP = "192.168.1.4"}); H.addnode (new Server() {IP = "192.168.1.5"}); for (int i = 0; i < h.nodes.Length; i++) { if (h.nodes[i] ! = null) { Console.WriteLine($"{i}===={h.nodes[i].VirtualNodeName}"); }}Copy the code

The output (somewhat uniform) :

2 = = = = 10 = = = = 192.168.1.1 192.168.1.3 # 4 # 0 = = = = 15 192.168.1.3 24 = = = = 192.168.1.2 instead # 2 # 3 = = = = 29 192.168.1.3 = = = = 192.168.1.4 33 # 2 # 4 64 = = 73 = = = = = = 192.168.1.5 # 1 192.168.1.4 # 3 75 = = = 77 = = = = = 192.168.1.2 instead # 0 192.168.1.1 # 3 85 = = = = 88 = = = = 192.168.1.5 192.168.1.1 # 4 # 4 117 = = 118 = = = = = = 192.168.1.4 # 1 192.168.1.2 instead # 4, 137 = = 152 = = = = = = 192.168.1.1 # 1 192.168.1.2 instead # 1 157 = = = = 192.168.1.5 # 2 158 = = = = 159 = = = = 192.168.1.3 192.168.1.2 instead # 3 # 0 = = = = 162 192.168.1.5 # 0 165 = = = 166 = = = = = 192.168.1.1 # 2 192.168.1.3 # 1 177 = = 185 = = = = = = 192.168.1.5 # 3 192.168.1.4 # 0 = = = = 196 192.168.1.4 # 2Copy the code

Test the performance

            Stopwatch w = new Stopwatch();
            w.Start();
            for (int i = 0; i < 100000; i++)
            {
                var aaa = h.GetNode("test1");
            }
            w.Stop();
            Console.WriteLine(w.ElapsedMilliseconds);
Copy the code

Output (657 ms for 100,000 calls) :

657
Copy the code

Write in the last

There is room for improvement in this code

  1. The hash function
  2. Temporary variables for many for loops

Interested in optimization of the students can leave a message!!

More interesting articles

  • Distributed large concurrent series
  • Architectural Design Series
  • Series of interesting algorithms and data structures
  • Design Pattern series