1. Consistent Hash algorithm

  • This section introduces Hash algorithms. For example, MD5 and SHA encryption algorithms are used in security encryption, and Hash tables are used in data storage and search.

  • Search efficiency (time & space, time first) : sequential search (for traversal) < binary search (half-search) < direct addressing (array) < open addressing (simple hash) < zipper method (hash+ linked list).

  • If the Hash algorithm is well designed, then the query efficiency will be closer to O(1). If the Hash algorithm is low, then the query efficiency will be very low.

1. Application scenarios of the Hash algorithm

Hash algorithm has been applied in many distributed cluster products, such as distributed cluster architecture Redis, Hadoop, ElasticSearch, Mysql sub-library sub-table, Nginx load balancing, etc

The main application scenarios are summarized as follows:

  • Load balancing of requests (such as Nginx’s IP_hash policy)

    • If there is no IP_hash policy, how can session stickiness be achieved? You can maintain a mapping table that stores the mapping between client IP addresses or sessionids and specific target servers < IP,tomcat1>. However, the disadvantages are obvious, users waste space, need to maintain, the cost is large.
    • This is solved using the hash algorithm.

  • Distributed storage

    Example: There are three Redis servers redis1, redis2, and redis3 in the cluster. Use hash(key1)%3=index to locate the servers using the remainder. Mysql > alter table mysql > alter table mysql > alter table mysql

2. Problems with common Hash

Take ip_hash as an example. If a service is down, the module needs to be recalculated. If there are too many servers, problems may arise in capacity reduction and expansion. For example, user sessions on the original server may be lost.

3. Consistent Hash algorithm

3.1 Design Roadmap

Here’s the idea:

Hash the nearest node simultaneously.

If 3 goes offline, requests made to 3 are rerouted to 4, with no impact on other clients. Avoid mass migration of requests as shown below:

If server 5 is added, a small portion of the route from server 3 to server 5 is migrated, avoiding a large number of requests. The diagram below:

To sum up, each server is responsible for a section, and the consistent hash algorithm only needs to relocate a small part of the data in the ring space for the increase or decrease of nodes, which has good fault tolerance and scalability.

3.2 Data skew

However, when there are too few nodes, data skew will occur. For example, if there are only two servers, a large number of requests will be sent to node 1 based on consistent hash, and node 2 is responsible for very little. This is the problem of data skew.

3.3 Virtual Node Solution

Here comes the virtual node solution: Compute multiple hashes for each node, and each hash is set to the current node, which becomes the virtual node.

For example, three virtual nodes can be calculated for each server, as shown in the following figure:

4. Handwriting consistency hash helps understanding

Github address -> github.com/znbsmd/hand…

5. Nginx configures a consistent Hash load balancing policy

The ngx_HTTP_upstream_consistent_hash module is a load balancer that uses an internal consistent hash algorithm to select the appropriate backend node. The module can map requests evenly to back-end machines in different ways based on configuration parameters,

  • Consistent_hash $remote_ADDR: mapping by client IP address
  • Consistent_hash $request_URI: specifies the URI mapping based on the client request
  • Consistent_hash $args: map according to the parameters carried by the client

The ngx_HTTP_upstream_consistent_hash module is a third-party module that needs to be downloaded and installed using ->github.com/replay/ngx_… The steps are as follows:

  • Unzip to the nginx source directory
  • . / configure – add – the module = / root/ngx_http_consistent_hash – master
  • make
  • make install
  • In the nginx.conf file 
    upstream zjnServer {
    consistent_hash $request_uri; // Map server 127.0.0.1:8080 according to the uri requested by the client; Server 127.0.0.1:8081; }Copy the code

2. Cluster clock synchronization

1. Problems caused by clock insynchronization

The order is distributed to different servers. The creation time is based on the system time, which leads to data confusion.

2. Configure clock synchronization for the cluster

  • Cluster clock synchronization roadmap

    • Each server node in a distributed cluster can connect 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

      Finally, use the crontab scheduled task to synchronize data

    • A server node in a distributed cluster can access the Internet or all nodes cannot access the Internet

      Select Node1 as the primary time server (if the server has Internet access, synchronize the server with the network time, if not manually set a time).

      • Set the node1 time
      • Configure A as the time server (modify the /etc/ntp.conf file)
      Restrict Default Ignore, comment it out
# 2. Add the following linesRestrict 172.17.0.0 mask 255.255.255.0 nomodify notrap172.17.0.0 is your LAN segmentServer 127.127.1.0# local clockFudge 127.127.1.0 stratum 10# 3. Restart to take effect and configure the NTPD service to start automatically upon startup
service ntpd restart
chkconfig ntpd on
Copy the code
      • The other nodes in the cluster can synchronize time with server A
      Ntpdate 172.17.0.17Copy the code

Distributed ID solution

The IDS must be unique

  • UUID(available) 
    public class MyTest {
    public static void main(String[] args) { System.out.println(java.util.UUID.randomUUID().toString()); }}Copy the code
  • Set a separate database. Insert the database first before inserting it. Maintain it separately (not recommended)
  • SnowFlake algorithm (optional, recommended)
  • Snowflake algorithm is an algorithm, based on this algorithm can generate ID, the generated ID is a long, so in Java, a long is 8 bytes, calculated down is 64bit, the following is the binary form of an ID generated using snowflake algorithm:

Some Internet companies have also packaged distributed ID generators based on the above solution, such as Didi’s TinyId (based on the database implementation), Baidu’s UidGenerator (based on SnowFlake) and Meituan’s Leaf (based on the database and SnowFlake)

  • Redis.incr (recommended)

    • The introduction of jedis jar 
      Clients </groupId> <artifactId>jedis</artifactId> <version>2.9.0</version> </dependency>Copy the code
    • Jedis jedis = new Jedis("127.0.0.1", 6379); try { long id = jedis.incr("id");
        System.out.println("The distributed ID obtained from Redis is:" + id);
        } 
    finally {
        if (null != jedis) {
        jedis.close();
    }
}
Copy the code

Fourth, distributed scheduling problem

1. Distributed scheduling has two meanings

  • Multiple scheduled tasks are deployed for the same task, and only one task is running
  • Scheduled tasks are split and executed simultaneously

2. Differences between scheduled tasks and message queues

The nature is different. A scheduled task is time driven while MQ is event driven. Timed task jobs tend to be batch processing, MQ tends to be itemized processing;

3. Implementation of scheduled tasks

Task scheduling framework Quartz

4. Distributed scheduling framework Elastic-Job

Elastice-job is an open-source distributed scheduling solution developed by Dangdang based on Quartz. It consists of two independent subitems, elastice-Job-Lite and Elastice-job-Cloud. Address -> : github.com/elasticjob

Main functions:

  • Distributed distribution prevents the same task from being executed repeatedly
  • Based on cron expressions
  • Elastic expansion, increase or decrease, can be transferred to another instance execution
  • Failover: If execution fails, transfer to another instance for execution
  • Missed job retriggering If a job is missed 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.

4.1 Elastic – Job – Lite application

Jar package (API) + Install ZK software

Elastic-Job depends on Zookeeper for distributed coordination. Therefore, Install Zookeeper software (version 3.4.6 or later).

  • Install and configure ZK

  • The introduction of the jar

    < the dependency > < groupId > com. Dangdang < / groupId > < artifactId > elastic - job - lite - core < / artifactId > < version > 2.1.5 < / version > </dependency>Copy the code

  • Scheduled Task Instances…

  • Leader Node election mechanism Each Elastice-job task execution instance App operates the Zookeeper ZNode as the Zookeeper client

    • Multiple instances simultaneously create/Leader nodes
    • Only one leader node can be created. The later one fails to be created. The successfully created instance is selected as the Leader node to execute tasks

4.2 Elastice-Job-Lite lightweight decentralization

4.2 Task Sharding

The ElasticJob can be divided into multiple tasks (each task is a task fragment), and each task is assigned to a specific machine instance (a machine instance can handle multiple tasks), but the logic of each task is specified by us.

The Strategy policy defines how these sharding items are allocated to each machine. The default is equal allocation and can be customized, for example, if a machine has a high load or a high preconfiguration, the policy can be written. Sharding and jobs themselves are coordinated through a registry, because in a distributed environment, the state data must be centralized in order to communicate in a distributed environment.

4.3 Elastic Capacity Expansion

Add a new instance app3 and it will automatically register with the registry. The registry will notify ElasticJob to re-fragment when a new service comes online. Can be divided into 1000 pieces, so you can make 1000 machines to execute the operation together

Note:

  1. The sharding item is also a JOB configuration. After the configuration is modified, the sharding algorithm is called again before the next scheduled run. The result of the sharding algorithm is as follows: The result of which machine runs which shard is stored in the ZK, the master node divides the shard and places it in the registry, and the executing node gets the information from the registry (the executing node gets the corresponding shard when the scheduled task is started).
  2. If all nodes fail and one node is left, all fragments point to the remaining node, which is also highly available for ElasticJob.

5. Session sharing

1. Cause analysis of Session problems

Because Http is stateless, why is Http designed to be stateless? 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.

Using the nginx default polling policy, Session calls to different servers will occur.

2. Solution to Session consistency

  • Nginx IP_Hash policy (available)

    • Advantages: Simple configuration, does not invade applications, and does not require additional code modification
    • Disadvantages:
      • The Session is lost after the server restarts
      • Risk of high single-point load (malicious attacks)
      • Single point of failure (rehash, resulting in session loss)

  • Session replication (not recommended)

    • Big data era has a lot of disadvantages, I won’t go into detail

  • Redis, Session sharing, Session centralized storage (recommended)

    • The only disadvantage: intrusion into the application, the introduction of interactive code with Redis (there is a special JAR package, no disadvantages)
    • The introduction of the jar
    <dependency>
    <groupId>org.springframework.boot</groupId>
    <artifactId>spring-boot-starter-data-redis</artifactId>
</dependency>
<dependency>
    <groupId>org.springframework.session</groupId>
    <artifactId>spring-session-data-redis</artifactId>
</dependency>
Copy the code
    • Configure redis
    Spring. Redis. Database = 0 spring. Redis. Host = 127.0.0.1 spring. Redis. Port = 6379Copy the code
    • The main run method adds annotations
    @EnableRedisHttpSession
Copy the code
    • Principle: Mainly in the filter for request interception

Lagouedu distributed solutions summary