Understanding local and distributed locks

1. Differences between local locks and distributed locks.

1.1. Significance of local locks

In a single-process system, when multiple threads can change a variable (variable shared variable) at the same time, it is necessary to synchronize the variable or code block so that the variable can be modified linearly to prevent data inconsistency or data pollution caused by concurrent variable modification. And in order to realize the multiple threads in the same block of code at a time can have only one thread can perform, so need somewhere to make a mark, the mark must be each thread can be seen, when there is no tag can set the tag, the rest of the subsequent threads found has a tag is waiting for the end of the thread that owns tag synchronized code block cancel to try to set up again after marking. This tag can be understood as a lock.

1.2. The significance of distributed locks

In the case of a single machine (single JVM), where memory is shared between threads, the concurrency problem can be solved by simply using thread locks. However, if the situation is distributed (multiple JVMS), thread A and thread B are probably not in the same JVM, so the thread lock will not work, and the distributed lock will be used to solve the problem.

Distributed lock is a way to control distributed system’s synchronous access to shared resources.

2. The local lock

2.1. What are the common local locks?

Synchronized and lock

2.2. What does the local lock lock?

In non-static methods, objects are locked; in non-static methods, bytecodes are locked

2.3. Lock How does lock work?

Learned by looking at the source of fair lock in Java. The util. Concurrent. The locks AbstractQueuedSynchronizer in an abstract class, there is a state of type int values, then to judge the state of the lock.

Java ReenttrantLock uses the constructor to specify whether the lock is fair or not. By default, an unfair lock has the advantage of higher throughput than a fair lock and is also an unfair lock for synchronized

2.4. What does volatile mean? What’s it for?

2.41 volatile definition

Is a lightweight synchronization mechanism provided by the Java virtual machine. Visibility is guaranteed, atomicity is not guaranteed, instruction rearrangement is prohibited.

​ jmm

2.42 Visibility of Volatile

Because the JVM to run the program of the entity is a thread, and every thread creation when the JVM to create a working memory (also called stack space), the working memory is the private data area each thread, while the Java memory model that all variables are stored in main memory, main memory is Shared memory region, all threads can access, But thread operations on variables (reading assignments, etc.) must take place in working memory. There are three steps to the process.

1. Start by copying variables from main memory into your own working memory space.
2. The variable is then manipulated.
3. Write variables back to the main memory after the operation is complete. You cannot directly operate variables in the main memory.

The working memory of each thread stores a copy of the variables in the main memory. Therefore, different threads cannot access each other’s working memory. Communication between threads must be done through the main memory, which is briefly accessed as follows.

2.43 Atomicity is not guaranteed by volatile

Atomicity definition: indivisible, integrity, that is, when a thread is doing a specific business, the middle can not be added or divided, it needs to be completed specifically, either successful or failed at the same time.

2.44 How can Volatile Guarantee atomicity

1. The easiest way is to add sync locks.
2. You can wrap classes using atoms under JUC.

2.45 Volatile disables instruction reordering

In a single-threaded environment, ensure that the final execution results are consistent with the code sequence

The processor must consider the data dependencies between instructions when reordering

In a multithreaded environment, threads are executed alternately. Because of the rearrangement of compiler optimizations, it is uncertain whether the variables used in the two threads can guarantee consistency, and the results are unpredictable.

public void mySort() {
	int x = 11;
	int y = 12;
	x = x + 5;
	y = x * x;
}
Copy the code

In a normal single-threaded environment, the order of execution is 1, 2, 3, and 4

But in a multithreaded environment, the following order may occur:

• 1 2 3 4
• 1 3 2 4

The above process can be thought of as a reordering of instructions, the internal order of execution, which is different from our code order

However, instruction reordering is also limited, that is, the following order does not occur

• 4 3 2 1

Because the processor must take into account the data dependencies between instructions when rearranging

Because step 4: requires a declaration that depends on y, as well as the declaration of X, it cannot be executed first because of data dependencies

2.5. Principle of synchronized

Common usage methods:

Copy the code

Java object layout?

The total number of consolidated objects is 16B, with 12B in the object header and 4B in aligned bytes (64-bit virtual machine objects must be multiples of 8 in size).

What is stored in the object header?

The object header is the common part of the beginning of all objects.

Reference site: openjdk.java.net/groups/hots…

2.5. What is the difference between bit and Byte?

Bit, meaning ‘bit’ or ‘bit’, is the basis of computer operations.

Byte means “byte” and is the basic unit of calculation for the size of a computer file.

Byte = byte means 1byte=8bits. The conversion between the two is 1:8.

3. Lock type:

Whether a thread needs to lock resources can be divided into pessimistic locking and optimistic locking.

The fairness of locks can be divided into fair locks and unfair locks.

Whether multiple threads can obtain the same lock can be divided into shared locks and exclusive locks

If the slave resource is locked, whether the thread is blocked can be classified as a spinlock.

3.1. Pessimistic locks and optimistic locks.

3.11 pessimistic locks

Pessimistic lock is a kind of negative thinking, it always think the worst may appear, it was assumed that the data could be modified by others, so pessimistic locks in holding data always lock the resources, or data, so that other threads want to request this resource will be blocked, until when pessimistic locks release resources. Traditional relational database inside used a lot of this locking mechanism, ** such as row lock, table lock, read lock, write lock, etc., are in operation before the first lock. The realization of pessimistic locking often depends on the locking function of the database itself.

Exclusive locks such as Synchronized and ReentrantLock in Java are also implementations of the pessimistic locking concept because Synchronzied and ReetrantLock attempt to lock regardless of whether they hold resources. Afraid of their beloved treasure is taken away by others.

3.12 optimistic locking

On the contrary, optimistic lock always believes that resources and data will not be modified by others, so the read will not be locked. However, optimistic lock will judge whether the current data has been modified during the write operation (how to judge the details will be discussed below). Generally speaking, there are two implementation schemes of optimistic locking: version number mechanism and CAS implementation. Optimistic locking is suitable for multi-read applications to improve throughput. Mybaits-plus, for example, supports optimistic locking.

Optimistic lock implementation: version number mechanism, reference code

3.2. Fair locks and unfair locks.

3.21 Fair Lock Definition

In a concurrent environment, multiple threads need to access the same resource, and only one thread can acquire the lock and access the resource at a time. What about the remaining threads? This is like the model of the canteen line. The first person who arrives at the canteen has the right to buy the food first, so the rest of the people need to queue behind the first person. This is the ideal situation, that is, everyone can buy the food. Then the reality is that while you are waiting in line, there will be a few dishonest people who want to take a shortcut and jump the queue for dinner. If the person who jumps the queue has no one to stop him or her, he or she will be able to buy dinner. If someone stops him or her, he or she will have to go to the back of the queue.

According to the above summary, fair lock means that in the concurrent environment, each thread will first check the waiting queue maintained by the lock when acquiring the lock. If it is empty, or the current thread is the first one in the waiting queue, it will occupy the lock. Otherwise, it will join the waiting queue and fetch itself from the queue in accordance with THE RULES of FIFO

3.22 Fair lock use

In Java, we typically implement lock fairness through ReetrantLock.

Public class MyFairLock extends Thread {private ReentrantLock lock = new ReentrantLock(true);

    public void fairLock() {
        try {
            lock.lock();
            System.out.println(Thread.currentThread().getName() + "Holding lock");
        } finally {
            System.out.println(Thread.currentThread().getName() + "Release the lock.");
            lock.unlock();
        }
    }
    public static void main(String[] args) {
        MyFairLock myFairLock = new MyFairLock();
        Runnable runnable = () -> {
            System.out.println(Thread.currentThread().getName() + "Start");
            myFairLock.fairLock();
        };
        Thread[] thread = new Thread[10];
        for (int i = 0; i < 10; i++) {
            thread[i] = new Thread(runnable);
        }
        for(int i = 0; i < 10; i++) { thread[i].start(); }}}Copy the code

If true, a fair lock for ReentrantLock will be created and a FairSync will be created, which is an inner class of Sync. Its main purpose is to synchronize objects to obtain fair locks.

Reviewing the FairSync and NonfairSync source code, it is clear that the only difference between the lock() method of a fair lock and that of an unfair lock is that the fair lock has an additional constraint on acquiring the synchronous state: Hasqueued24 ().

It is mainly used to query if there is any thread waiting for acquiring a lock time is longer than the current thread, this means each waiting thread is in a queue, this method is to determine the queue in the current thread for the lock, if there is a waiting for the lock time is longer than his queue, if the current thread before have a queue of threads, returns true, Returns false if the current thread is at the beginning of the queue or if the queue is empty.

To sum up, fair lock is to achieve multiple threads to obtain locks in accordance with the order of lock application through synchronization queue, so as to achieve fair characteristics. Unfair lock does not consider the queuing problem when adding the lock, directly try to obtain the lock, so there is the situation of obtaining the lock first after applying.

3.22 Definition of unfair lock

Unfair lock is a kind of preemption mechanism to obtain the lock, which is random. Unlike fair lock, the first to get the lock does not necessarily get the lock first. In this way, some threads may not get the lock all the time, and the result is unfair.

3.4 Exclusive locks and shared locks

3.4.1 Exclusive Lock Definition

An exclusive lock, also known as an exclusive lock, means that the lock can only be owned by one thread at a time, and other threads that want to access resources will be blocked. The implementation classes for synchronized in the JDK and Lock in JUC are mutex.

3.4.2 Shared Lock Definition

A shared lock means that the lock can be owned by multiple threads. If a thread adds a shared lock to a resource, other threads can only add a shared lock to the resource, not an exclusive lock. The thread that acquires the shared lock can only read the data, not modify it.

Rule 3.4.3 instance

		ReadWriteLock lock=new ReentrantReadWriteLock();
        Lock readLock = lock.readLock();
        Lock writeLock = lock.writeLock();
Copy the code

ReentrantReadWriteLock has two locks: ReadLock and WriteLock. A ReadLock and a WriteLock are called read and write locks. Read lock is shared lock, write lock is exclusive lock, because read lock and write lock are separated. So ReentrantReadWriteLock is a huge increase in concurrency over regular mutex.

3.5 spinlocks.

3.5.1 Spin Lock Definition

A spin lock is a non-blocking lock. When a thread tries to acquire a lock, if the lock has already been acquired by someone else, the thread will not be suspended. The thread will not be able to acquire the lock and will try again after a certain period of time. This mechanism of cyclic locking -> waiting is called spinlock.

3.5.2 Advantages of spin locks

Spin-locking minimizes thread blocking, which is a significant performance improvement for code blocks that are less competitive for locks and have a very short lock time, because the spin cost is less than the cost of a thread blocking, suspending and waking up. In general, spin-locking is designed to address the performance loss caused by frequent thread switching, so it keeps the current thread occupied.

3.5.3 Disadvantages of spin locks

If locked for long periods of time, spin locks can be very costly in performance, preventing other threads from running and scheduling. The longer a thread holds the lock, if the thread holding the lock breaks, the other threads will keep spinning (repeatedly trying to acquire the lock) and the thread holding the lock will not release it, resulting in an indefinite delay.

A good way to solve this problem is to set a spin time for the spin lock and release the spin lock immediately. The purpose of a spin lock is to hold CPU resources without releasing them until the lock is acquired. But how do you choose spin time? If the spin execution time is too long, a large number of threads in the spin state will occupy CPU resources, which will affect the overall system performance. So the cycle of spin is extra important! The JDK introduced adaptive spin locking in 1.6. Adaptive spin locking means that the spin time is not fixed, but is determined by the previous spin time on the same lock and the state the lock has. It is generally considered that the optimal time for a thread to switch context is the time.

3.5.4 Spin Lock Demo

/** * handwritten spin lock * loop comparison get until successful, nothing similar towaitThread A calls myLock and holds the lock for 5 seconds. Thread B then comes in and finds that there is A thread holding the lock, which is not null, so it can only spin wait. */ public class SpinLock {// Public class SpinLock Thread; <Thread> AtomicReference = new AtomicReference<>(); public voidmyLockThread.currentthread (); thread.currentThread (); System.out.println(Thread.currentThread().getName() +"\t come in "); // Start spin, expected value is null, update value is current thread, if null, update to current thread, otherwise spinwhile(! AtomicReference.com pareAndSet (null, the thread)) {}} / * * * unlocked * / public voidmyUnLockThread.currentthread (); thread.currentThread (); / / himself out, turn atomicReference to null atomicReference.com pareAndSet (thread, null); System.out.println(Thread.currentThread().getName() +"\t invoked myUnlock()"); } public static void main(String[] args) { SpinLock spinLockDemo = new SpinLock(); New Thread(() -> {// start holding lock spinlockdemo.mylock (); try { TimeUnit.SECONDS.sleep(5); } catch (InterruptedException e) { e.printStackTrace(); } // Start unlocking spinlockdemo.myunlock (); },"t1").start(); Try {timeunit.seconds.sleep (5); } catch (InterruptedException e) { e.printStackTrace(); New Thread(() -> {// Start to hold lock spinlockdemo.mylock (); // Start unlocking spinlockdemo.myunlock (); },"t2").start(); }}Copy the code

4. Distributed lock

4.1 What are common Distributed locks?

1. Implement distributed lock based on database
2. Distributed locking based on cache (Redis, etc.)
3. Distributed lock based on Zookeeper

4.2 Conditions of distributed locks

1. Exclusivity: Only one client can obtain the lock at a time. Other clients cannot obtain the lock at the same time.
2. Deadlock avoidance: The lock must be released after a certain period of time, otherwise a deadlock will occur. This includes normal release and abnormal release of the lock, for example, even if a client fails to release the lock while holding the lock, ensure that subsequent clients can lock it.
3. Unlock yourself: lock and unlock should be the same client to complete, not to unlock others.
4. High availability: Lock acquisition and release must be high availability and excellent.

4.3 Distributed Database Lock?

Create a table in the database, and create a unique index on the field, want to execute a method, use the name of the method to insert data into the table, successfully insert the lock, delete the corresponding row data release lock after the completion of execution.

4.2 Distributed Lock in Zookeeper?

4.2.1 Zookeeper Node Types and watch mechanism

Zookeeper node types:

PERSISTENT_SEQUENTIAL automatic numbering PERSISTENT nodes, which are automatically EPHEMERAL based on the number of existing nodes, EPHEMERAL_SEQUENTIAL nodes are automatically deleted when the client session times outCopy the code

Watch mechanism of ZooKeeper:

Znode changes (additions, deletions, and modifications of the Znode itself, as well as changes of its child ZNodes) can be notified to clients through the Watch mechanism. So to realize the Watch, it must implement the org. Apache. Zookeeper. Watcher interface, and the implementation class object into the approach to Watch on. The Watch option can be set for all read operations (getData(), getChildren(), exists()) in Zookeeper. The Watch event has the feature of a one-time trigger. If the Znode monitored by the Watch changes, the client setting the Watch will be notified.Copy the code

4.2.2 Implementation Idea

Define the lock:

In common Concurrent Java programming, there are two common ways to define locks: the synchronized mechanism and the ReetrantLock provided by JDK5. However, in ZooKeeper, there is no such API to use directly. Instead, a lock is represented by a data node on ZooKeeper. For example, the /exclusive_lock/lock node can be defined as a lock.

Acquiring a lock

When the lock is needed, all clients attempt to create a temporary child node /exclusive_lock/lock under the /exclusive_lock node by calling the create() interface. Zookeeper ensures that only one client can be successfully created, and the client is considered to have acquired the lock. At the same time, all clients that have not obtained the lock need to register a Watcher listener on the /exclusive_lock node for child node changes, in order to listen to the lock node changes in real time.

Release the lock

In the lock definition section, we mentioned that /exclusive_lock/lock is a temporary node, so it is possible to release the lock in either of the following cases.

1. If the client that obtains the lock is down, the temporary node on Zookeeper is removed.

2. After the service logic is executed, the client automatically deletes the created temporary node

4.2.3 Reference sample code

Reference ReentrantLock design ideas, using the template method design mode.

4.3 Redission Distributed Lock?

4.31 Reasons for using Redis

1. Redis has high performance;
2. The Redis command supports this well and is easy to implement

4.32 Implementation Idea

1. When obtaining the lock, use setnx to add the lock, and use the expire command to add a timeout period for the lock. The lock will be automatically released after the timeout period. The value of the lock is a randomly generated UUID, which can be used to determine the lock release.
2. A timeout period is set when the lock is acquired. If the timeout period is exceeded, the lock will be abandoned.
3. When releasing a lock, the UUID is used to determine whether the lock is correct. If the lock is correct, run delete to release the lock.

4.33 Sample code

You can also use Redis’s distributed locking framework –Redission code example