Optimistic locking based on database

Optimistic locking based on database

• 1 Introduction to Optimistic Locking and Pessimistic Locking
• Two optimistic locking practice cases
• • 2.1 The problem of oversold inventory recurred
  • • 2.1.1 Simulation analysis of flash sales orders
    • 2.1.2 Lightning code
    • 2.1.3 Unit test results
  • 2.2 Analysis of oversold inventory
  • 2.3 Optimistic lock solves oversold problem
  • • 2.3.1 Version number method
• Case source code
• sql script in the case

An introduction to optimistic locking and pessimistic locking

Pessimistic lock:

Pessimistic locks can implement serialized execution of data. For example, syn and lock are representatives of pessimistic locks. At the same time, pessimistic locks can be subdivided into fair locks, unfair locks, reentrant locks, etc.

Optimistic lock:

Optimistic locking is generally implemented using the version number mechanism or the CAS algorithm. There are relatively more CAS algorithms, so special attention needs to be paid here.

• version number mechanism

Generally, a data version number version field is added to the data table to indicate the number of times the data has been modified. When the data is modified, the version value will increase by one. When thread A wants to update the data value, it will also read the version value while reading the data. When submitting the update, if the version value just read is equal to the version value in the current database, it will be updated, otherwise retry Update operations until the update succeeds.

• CAS algorithm

A typical representative of optimistic locking: cas, using cas to lock the lock-free mechanism, var5 is the memory value read before the operation, var1 + var2 in while is the estimated value, if the estimated value == memory value, then It means that it has not been modified in the middle, and at this time, the new value is replaced by the memory value. The do while is to perform the spin operation again when the operation fails, that is, to operate the previous logic again.

int var5;
do {<!-- -->
   var5 = this. getIntVolatile(var1, var2);
} while(!this.compareAndSwapInt(var1, var2, var5, var5 + var4));

return var5;

Optimistic lock based on database method and Redis method
Optimistic locking and pessimistic locking

Two optimistic locking practice cases

2.1 Recurrence of inventory oversold

2.1.1 Simulation analysis of seckill orders

Things to think about when placing an order in seckill:

When placing an order, you need to judge two points:

• Whether the flash sale has started or ended, if it has not started or has ended, you cannot place an order
• Whether the inventory is sufficient, if not enough, the order cannot be placed

Order core logic analysis:

When the user starts to place an order, we should query the coupon information, find out the coupon information, and judge whether the flash sale conditions are met

For example, whether the time is sufficient, if the time is sufficient, further judge whether the inventory is sufficient, if both are satisfied, then deduct the inventory, create an order, and then return the order id, if one of the conditions is not met, it will end directly.

2.1.2 Second kill code

@Override
    public Result seckillVoucher(Long voucherId) {<!-- -->
        // 1. Query coupons
        SeckillVoucher voucher = seckillVoucherService.getById(voucherId);
        // 2. Determine whether the seckill has started
        if (voucher.getBeginTime().isAfter(LocalDateTime.now())) {<!-- -->
            // not yet started
            return Result.fail("Second Kill has not started yet!");
        }
        // 3. Determine whether the seckill has ended
        if (voucher.getEndTime().isBefore(LocalDateTime.now())) {<!-- -->
            // not yet started
            return Result.fail("Second Kill is over!");
        }
        // 4. Determine whether the inventory is sufficient
        if (voucher. getStock() < 1) {<!-- -->
            // Inventory shortage
            return Result.fail("Insufficient inventory!");
        }
        //5, deduct inventory
        boolean success = seckillVoucherService. update()
                .setSql("stock= stock -1")
                .eq("voucher_id", voucherId).update();
        if (!success) {<!-- -->
            //Deduct inventory
            return Result.fail("Insufficient inventory!");
        }
        //6. Create an order
        VoucherOrder voucherOrder = new VoucherOrder();
        // 6.1. Order id
        Random ra = new Random();
        long orderId = ra. nextLong();
        voucherOrder.setId(orderId);
        // 6.2. User ID
        Long userId = ra. nextLong();
        voucherOrder.setUserId(userId);
        // 6.3. Coupon id
        voucherOrder.setVoucherId(voucherId);
        save(voucherOrder);

        return Result.ok(orderId);

    }

2.1.3 Unit test results

@SpringBootTest
class LockApplicationTests {<!-- -->

    //A custom thread pool should be used in the actual project
    ExecutorService threadPool = Executors. newFixedThreadPool(100);
    @Autowired
    private IVoucherOrderService voucherOrderService;


    @Test
    void testIdWorker() throws InterruptedException {<!-- -->

        CountDownLatch latch = new CountDownLatch(100);

        Runnable task = new Runnable() {<!-- -->
            @Override
            public void run() {<!-- -->
                Result result = voucherOrderService.seckillVoucher(2L);
                System.out.println("result = " + result);
            latch. countDown();
            }
        } ;
        long begin = System. currentTimeMillis();
        for (int i = 0; i < 100; i ++ ) {<!-- -->
            threadPool. execute(task);
        }
        latch. await();
        long end = System. currentTimeMillis();
        System.out.println("time = " + (end - begin));
    }
}

Observe the ideal console

Observe the data in the table

2.2 Analysis of oversold inventory

Analysis of the overselling problem: this is written in our original code

 if (voucher.getStock() < 1) {<!-- -->
        // Inventory shortage
        return Result.fail("Insufficient inventory!");
    }
    //5, deduct inventory
    boolean success = seckillVoucherService. update()
            .setSql("stock= stock -1")
            .eq("voucher_id", voucherId).update();
    if (!success) {<!-- -->
        //Deduct inventory
        return Result.fail("Insufficient inventory!");
    }

Suppose thread 1 comes to check the inventory, judges that the inventory is greater than 1, and is about to deduct the inventory, but has not had time to deduct it. At this time, thread 2 comes, and thread 2 also checks the inventory, and finds that the quantity must be greater than 1, then These two threads will deduct the inventory, and finally multiple threads are equivalent to deducting the inventory together. At this time, the problem of oversold inventory will appear.

2.3 Optimistic lock to solve oversold problem

Use pessimistic locks to solve thread safety problems under high concurrency conditions. Some are too heavy. Click to lock the entire business. Only the thread that grabs the lock can be exclusive, and other threads can only wait. This is obviously a bit overbearing; use optimistic locks The way to judge whether there are other threads to modify the data when updating the data, does not affect the efficiency in the case of high concurrency;

2.3.1 version number method

The operation logic is to perform +1 operation on the version number during the operation, and then require the version to be 1 to operate, then the first thread after the operation, the version in the database becomes 2, but he himself satisfies version=1, so there is no problem. At this time, thread 2 executes, and thread 2 needs to add the condition version=1 at the end, but now thread 1 has already operated, so thread 2 does not satisfy the condition of version=1 when operating , so thread 2 cannot execute successfully

Since the scenario in our case is to reduce inventory, the plan is a bit special, and the version number can be replaced by the stock field stock; When updating, add conditional judgment: the version number queried and the version number in the table Compare, if they are equal, the update is successful, if they are not equal, the update fails

Modify the code scheme one,

When VoucherOrderServiceImpl deducts inventory, change it to:

boolean success = seckillVoucherService. update()
            .setSql("stock= stock -1") //set stock = stock -1
            .eq("voucher_id", voucherId).eq("stock",voucher.getStock()).update(); //where id = ? and stock = ?

The core meaning of the above logic is: as long as the inventory when I deduct the inventory is the same as the inventory I queried before, it means that no one has modified the inventory in the middle, then it is safe at this time, but the above method passes The test found that there will be many failures. The reason for the failure is: in the process of using optimistic locking, it is assumed that 100 threads have obtained 100 inventory at the same time, and then everyone will deduct it together, but only 1 person in 100 can deduct it. Success, when other people are processing, when they are deducting, the inventory has been modified, so other threads will fail at this time;

In other scenarios, it is no problem to use the version number scheme with a low success rate; but this is a spike scenario, and the low success rate does not meet business requirements;

Modify code scheme two,

The previous method should be consistent before and after modification, but we have analyzed that the probability of success is too low, so our optimistic lock needs to be changed to a stock greater than 0.

boolean success = seckillVoucherService. update()
                .setSql("stock= stock -1")
                .eq("voucher_id", voucherId).gt("stock", 0).update(); //where id = ? and stock > 0

After the inventory is sold out, other threads will return the prompt of insufficient inventory if they spike again!

Small expansion of knowledge:

For the excessive spin pressure in cas, we can use the Longaddr class to solve it

An improved class of AtomicLong provided by Java8, LongAdder

When a large number of threads concurrently update an atomicity, the natural problem is spin, which will cause concurrency problems. Of course, this is better than using syn directly.

So use such a class, LongAdder to optimize

If a value is obtained, the value of cell and base will be incremented, and finally a complete value will be returned
Small expansion of knowledge:

For the excessive spin pressure in cas, we can use the LongAdder class to solve an improved AtomicLong class provided by Java8. When a large number of LongAdder threads update an atomicity concurrently, the natural problem is spin, which will cause Concurrency issues, of course, this is better than using syn directly
So use such a class, LongAdder to optimize
If a value is obtained, the value of cell and base will be incremented, and finally a complete value will be returned

Analysis of LongAdder Principle

Case source code

Case source code

Sql script in the case

tb_voucher_order: order table
tb_seckill_voucher: Coupon inventory, start time, and end time.

• tb_seckill_voucher

DROP TABLE IF EXISTS `tb_seckill_voucher`;
CREATE TABLE `tb_seckill_voucher` (
  `voucher_id` bigint(20) UNSIGNED NOT NULL COMMENT 'the id of the associated coupon',
  `stock` int(8) NOT NULL COMMENT 'stock',
  `create_time` timestamp NOT NULL DEFAULT CURRENT_TIMESTAMP COMMENT 'create time',
  `update_time` timestamp NOT NULL DEFAULT CURRENT_TIMESTAMP ON UPDATE CURRENT_TIMESTAMP COMMENT 'update time',
  `begin_time` datetime NOT NULL COMMENT 'effective time',
  `end_time` datetime NOT NULL COMMENT 'expiration time',
  PRIMARY KEY (`voucher_id`) USING BTREE
) ENGINE = InnoDB CHARACTER SET = utf8mb4 COLLATE = utf8mb4_general_ci COMMENT = 'Second kill coupon table, and the coupon is a one-to-one relationship' ROW_FORMAT = COMPACT;

-- ----------------------------
-- Records of tb_seckill_voucher
-- ----------------------------
INSERT INTO `tb_seckill_voucher` VALUES (2, 100, '2022-01-04 10:09:17', '2023-05-23 03:07:53', '2023-05-23 09: 09:04', '2023-05-31 10:09:17');

SET FOREIGN_KEY_CHECKS = 1;

• tb_voucher_order

DROP TABLE IF EXISTS `tb_voucher_order`;
CREATE TABLE `tb_voucher_order` (
  `id` bigint(20) NOT NULL COMMENT 'primary key',
  `user_id` bigint(20) UNSIGNED NOT NULL COMMENT 'user id who placed the order',
  `voucher_id` bigint(20) UNSIGNED NOT NULL COMMENT 'purchased voucher id',
  `pay_type` tinyint(1) UNSIGNED ZEROFILL NULL DEFAULT NULL COMMENT 'Payment method 1: balance payment; 2: Alipay; 3: WeChat',
  `status` tinyint(1) UNSIGNED NULL DEFAULT 1 COMMENT 'Order status, 1: not paid; 2: paid; 3: written off; 4: canceled; 5: refunding; 6: refunded\ ',
  `create_time` timestamp NULL DEFAULT CURRENT_TIMESTAMP COMMENT 'order time',
  `pay_time` timestamp NULL DEFAULT NULL COMMENT 'pay time',
  `use_time` timestamp NULL DEFAULT NULL COMMENT 'write-off time',
  `refund_time` timestamp NULL DEFAULT NULL COMMENT 'refund time',
  `update_time` timestamp NULL DEFAULT CURRENT_TIMESTAMP ON UPDATE CURRENT_TIMESTAMP COMMENT 'update time',
  PRIMARY KEY (`id`) USING BTREE
) ENGINE = InnoDB CHARACTER SET = utf8mb4 COLLATE = utf8mb4_general_ci ROW_FORMAT = COMPACT;

-- ----------------------------
-- Records of tb_voucher_order
-- ----------------------------

SET FOREIGN_KEY_CHECKS = 1;