Collation of distributed problem solutions

preface

Article content output source: Pull hook education Java high salary training camp;

During the interview, you will be asked questions about distribution, such as how to ensure session consistency in a distributed environment, distributed ids, etc. When I was studying at the hook camp, the teacher happened to talk about it, so I sorted it out.

Consistent Hash algorithm

Resolving hash conflicts:

Open addressing: 1 goes in, 6 comes in, goes forward or backward and finds a free place to put it, bad place, if the array length is fixed

For example, 10, the length can not be extended, 11 data, regardless of whether the Hash conflict or not, there is no way to store that much data

Zipper method: The length of the data is defined, how to store more content, calculate the Hash value, put a linked list where the array elements are stored. That is, when there is a repeat, we store it in a linked list, also known as chained address. Hashmap uses this structure.

Hash algorithm application scenarios

Load balancing for Nginx

We know that NGINx implements load balancing in three ways. Round search, set weights, and configure IP_hash. ‘ ‘

The HASH algorithm is used to configure ip_hash. The IP_hash policy of Nginx can always route requests sent by clients to the same destination server when the CLIENT IP address remains unchanged, thus realizing sticky sessions and avoiding session sharing problems. The hash value of the IP address or sessionID is calculated, the hash value and the number of servers are modular operation, the value is the number of the server to which the current request should be routed, so that the request sent from the same client IP can be routed to the same target server, to achieve session sticky.

Distributed storage

Take distributed memory database Redis as an example, there are three Redis servers redis1, redis2 and reDIS3 in the cluster. Then, when storing data, which server does <key1, Value1 > store data to? Hash hash(key1)%3=index to lock the server node with the remainder index.

Simple implementation of ordinary Hash

Let’s write a simple implementation of a normal hash.

public class GeneralHash {


    public static void main(String[] args) {
  // Define the client IP address String[] clients = new String[]{  "192.168.1.61". "192.168.1.48". "192.168.1.44". "192.168.1.42". "192.168.1.43". "192.168.1.73". "192.168.1.83". "192.168.1.23"};   // Number of servers int count =5;    for (String client : clients) {  int hash = Math.abs(client.hashCode());  int index=hash%count;  System.out.println("IP for:"+client+ "Server number is:"+index);  }  } } Copy the code

Results:

The IP address is 192.168.1.61. The server number is 2The IP address is 192.168.1.48. The server number is 2The IP address is 192.168.1.44. The server number is 3The IP address is 192.168.1.42. The server number is 1The IP address is 192.168.1.43. The server number is 2The IP address is 192.168.1.73. The server number is 0The IP address is 192.168.1.83. The server number is 1The IP address is 192.168.1.23. The server number is 0Copy the code

Problems with common hash algorithms

For example, the above ip_hash is modded, but will be rehash if a service is down or expanded or shrunk. The original session will be lost.

Consistent hash algorithm

So I have a line and a line. It’s 0 to 2 to the 32nd minus 1. Then connect the ends together to form a closed loop, the hash ring.

As shown below, our server nodes are scattered across the ring. When the requested IP address uses a consistent hash to find the node closest to it, it can access it.

When the service is down or scaled down. Only some IP addresses are redirected.

Similarly, when you add servers, only some IP addresses will be reassigned.

The demo implementation

We use code to implement a consistent hash algorithm that retrieves a subset of the SortedMap tailMap(K fromKey). All of its objects have keys greater than or equal to fromKey. Then firstKey() gets the minimum key

/ * ** No virtual node* /public class ConsistentHashNoVirtual {
   public static void main(String[] args) {   // Step 1: Save the server node tohashIn the ring. // Define the server node String[] servers = new String[]{  "192.168.1.10.". "192.168.1.30". "192.168.1.50.". "192.168.1.70". "192.168.1.90". "192.168.2.10". "192.168.1.30". "192.168.2.80"};  // Define onehash 环  SortedMap<Integer, String> hashServerMap = new TreeMap<>();   for (String server : servers) {  int hash = Math.abs(server.hashCode());  hashServerMap.put(hash,server);  }   // Step 2: Map the client IP address tohashIn the ring.  String[] clients = new String[]{  "10.168.1.10". "10.168.2.10". "10.168.3.10". "10.168.4.10". "10.168.5.10". "10.168.6.10". "10.168.7.10". "192.168.1.40". "192.168.1.60". "192.168.1.80". "192.168.2.00". "192.168.2.30". "192.168.2.50". "192.168.3.50". "192.168.4.50". "192.168.2.90"};    for (String client : clients) { //step3 for the client, find the server that can handle the current client request (clockwise on the hash ring)// Use the client IP hash to find out which server node can handle () int clienthash = Math.abs(client.hashCode());  //tailMap(K fromKey) retrieves a subset. All of its objects have keys greater than or equal to fromKey SortedMap<Integer, String> tailMap = hashServerMap.tailMap(clienthash);  Integer firstKey = hashServerMap.firstKey();  if(! tailMap.isEmpty()){ firstKey = tailMap.firstKey();  }  System.out.println("Client:" + client + "Routed to server:" + hashServerMap.get(firstKey));  }  } }  Copy the code

Results:

The problem

According to the above results, there is a problem with this kind of meeting, that is, data skew may occur. When there are too few service nodes, the consistency hashing algorithm is easy to cause the data skew problem because the nodes are not evenly distributed. For example, if there are only two servers in the system, the loop distribution is as follows, node 2 can only handle a very small segment, and a large number of client requests fall on node 1. This is the data (request) skew problem.

The solution

The consistent hash algorithm introduces the virtual node mechanism. Multiple hashes are computed for each service node, and each hash places a server point, called a virtual node.

This can be done by adding a number after the server IP address or host name. For example, three virtual nodes can be calculated for each server, so the hash values of “ip#1 of node 1”, “ip#2 of node 1”, “ip#3 of node 1”, “ip#1 of node 2”, “ip#2 of node 2”, and “ip#3 of node 2” can be calculated respectively, forming six virtual nodes. When a client is routed to a virtual node, it is actually routed to the real node corresponding to the virtual node

The demo implementation

We add virtual nodes to the code above. The rehash algorithm here needs to be tweaked, so I’m just writing it up here.

So let’s just add this code to the original, and let’s run it again. And you can see that this was reassigned.

Cluster clock synchronization is faulty

When our services are deployed on multiple servers, inconsistent times on those servers can certainly cause problems.

Therefore, ensure that the server time of the cluster is consistent.

Can be connected to the Internet

Use the ntpdate command to synchronize network time
ntpdate -u ntp.api.bz Synchronize time from a time server
Copy the code

Not connected to the Internet

1. If restrict Default Ignore exists, comment it out2. Add the following linesRestrict 172.17.0.0 mask 255.255.255.0 nomodify notrap# open bureau
For LAN synchronization,172.17.0.0 is your LAN segmentServer 127.127.1.0# local clock
Fudge 127.127.1.0 stratum 103. Restart the service to take effect and configure the NTPD service to start automatically upon startup service ntpd restart  chkconfig ntpd on Copy the code

Distributed ID solution

Solutions:

• UUID The UUID is the primary key, which is randomly generated each time.
• The increment ID of the standalone database
• SnowFlake Algorithm

Snowflake algorithm is an algorithm based on which ID can be generated. The generated ID is a long, so in Java, a long is 8 bytes, which is 64-bit. The following is the binary representation of an ID generated using snowflake algorithm

• Get the globally unique ID with Redis Incr command

Distributed scheduling problem

What is distributed scheduling

• Scheduling tasks running in a distributed cluster environment (Only one scheduled task should be executed when multiple scheduled tasks are deployed for the same scheduled task program)
• Distributed scheduling – > Distributed scheduling of scheduled tasks – > Split scheduled tasks (that is, to split a large job into several small jobs and execute them at the same time)

The difference between scheduled tasks and message queues

Thing in common:

• Asynchronous processing. Such as registration, order events
• Apply decoupling. Either a scheduled task job or MQ can be used as a gear between the two applications to decouple the application. The gear can transfer data between the two applications. Of course, individual services do not need to take this into account, which is often taken into account when services are split
• Flow peak clipping. On Double 11, both tasks and MQ can be used to carry traffic. The back-end system will process orders periodically according to service capacity or an order arrival event will be triggered when an order is captured from MQ. For the front-end user, the result is that the order has been placed successfully, and the order is not affected

Difference:

Timed task jobs are time driven, whereas MQ is event driven;

The time drive is irreplaceable. For example, the daily interest settlement of the financial system is not calculated by an interest (interest arrival event), but often by batch calculation of scheduled tasks. So, timed task jobs tend to be batch processing and MQ tends to be itemized processing;

Distributed scheduling framework Elastice-Job

Elastic-job is an open-source distributed scheduling solution developed by Dangdang based on Quartz. It consists of two independent subprojects, elastic-Job-Lite and Elastic-Job-Cloud. We will learn about Elastice-Job-Lite, which is positioned as a lightweight decentralised solution to coordinate distributed tasks in the form of Jar packages. Elastice-job-cloud subprojects need to be used in the Cloud in combination with Mesos and Docker.

The github address of an Elastic-Job:

https://github.com/elasticjob
Copy the code

Main Functions

• Distributed scheduling coordination. In a distributed environment, tasks can be executed according to specified scheduling policies, and multiple instances of the same task can be avoided
• Rich scheduling policies perform scheduled tasks based on mature Scheduled task job framework Quartz Cron expression
• Elastic capacity scaling When an instance is added to a cluster, it can be elected to perform tasks. When a cluster is reduced by an instance, the tasks it performs can be moved to another instance.
• Failover If a task fails to be executed on an instance, it will be transferred to another instance for execution. Missed job Retrigger If a job fails to be executed due to some reason, the missed job is automatically recorded and triggered after the last job is completed.
• Parallel scheduling Supports task sharding, which divides a task into multiple small tasks and executes them simultaneously in multiple instances.
• Job fragmentation consistency After a task is fragmented, ensure that only one execution instance of the same fragment exists in the distributed environment.

reference

<! -- https://mvnrepository.com/artifact/com.dangdang/elastic-job-lite-core-->
<dependency>
 <groupId>com.dangdang</groupId>
 <artifactId>elastic-job-lite-core</artifactId>
The < version > 2.1.5 < / version ></dependency> Copy the code

Session Sharing Problem

Session loss problem

Basically because Http is a stateless protocol. The data generated by the client and server during one session is not retained, so the server cannot realize that you have been there on the second request. Why is Http designed as a stateless protocol? In the early days, static pages did not matter whether they were stateless or not. Later, dynamic pages were richer and needed to be stateful. There emerged two technologies for maintaining Http state, namely Cookie and Session. The above problem of continuous login is analyzed as follows:

Solution to Session consistency

• Nginx IP_Hash policy (available)

  Requests from the same client IP address are routed to the same target server, also known as session stickiness

  Advantages:

  The configuration is simple, does not invade the application, does not need to modify the codeCopy the code

  Disadvantages:

  Session loss during server restart High single point load single point failureCopy the code

• Session replication (not recommended)

  The configuration files of multiple Tomcats can be modified to replicate sessions

Advantages:

Applications are not invaded to facilitate horizontal expansion of the server. It ADAPTS to various load balancing policies and does not cause Session loss due to server restart or downtimeCopy the code

Disadvantages:

Low performance Low memory consumption Do not store too much data; otherwise, more data affects the performance delayCopy the code

• Session sharing and centralized storage (recommended)

  

  Advantages:

  It can adapt to various load balancing policies, preventing Session loss due to server restart or downtimeCopy the code

  Disadvantages:

  There was an intrusion into the application, introducing code to interact with RedisCopy the code

  conclusion

  These are the most frequently asked questions not to be asked in an interview, so get on with it

This article is formatted using MDNICE