What is idempotent

Baidu Baike:

Idempotent (idempotence) is a mathematical and computer concept commonly found in abstract algebra.

The characteristic of an idempotent operation in programming is that any number of executions have the same effect as a single execution. An idempotent function, or idempotent method, is a function that can be executed repeatedly with the same parameters and achieve the same results.

These functions do not affect system state, nor do they have to worry about system changes caused by repeated execution. For example, the “setTrue()” function is an idempotent function that gives the same result no matter how many times it is executed. More complex operational idempotent guarantees are implemented using unique transaction numbers (serial numbers).

The mathematical concept of idempotent

Idempotent is derived from a mathematical concept. There are two main definitions

If in a unary operation, x is any number in a set, if f(f(x))=f(x)f(f(x))=f(x) f(f(x))=f(x), then the f operation is idempotent, So the absolute value operation abs(a)= ABS (abs(a))abs(a) =abs(abs(a))abs(a) =abs(abs(a)) is idempotent.

If, in a binary operation,x is any number in a set, f(x,x)=xf(x,x) =xf(x,x) =x, if both parameters of f operation are x, then f operation is also said to be idempotent, For example, if I take the function Max (x,x)=xmax(x,x) =x Max (x,x)=x is idempotent.

Idempotent business concepts

Idempotence is not just one or more operations that have no impact on the resource, but also the first operation that has an impact and subsequent operations that have no impact. And idempotent is concerned with whether the resource is affected, not the result.

For example, the server may perform retry operations or the client may perform multiple click submit operations. If this is done multiple times, the final data result must be consistent, such as the payment scenario. This needs to be done by ensuring the business idempotent scheme.

Idempotent dimensions

  • time
  • space

Time domain uniqueness

Define an idempotent validity period. Some services require permanent idempotent guarantees, such as orders, payments, etc. And some businesses only need to be idempotent for a period of time. How long do you want to keep an operation idempotent?

Spatial uniqueness

Idempotent ranges are defined so that duplicate orders are not allowed if orders are generated. One operation = service method + incoming business data

At the same time, the use of idempotent is usually accompanied by the concept of occurrence lock to solve the problem of concurrency security.

Semantic idempotency of HTTP protocol

Quote from:

  • Http / 1.1 document www.w3.org/Protocols/r…
  • Zh.wikipedia.org/wiki/%E8%B6…

Safe way

For the GET and HEAD methods, these requests should have no meaning beyond retrieving resource information. That is, these methods should be considered “safe.” Client may use other “safe” method, such as POST, PUT and DELETE, should be in a special way (usually a button rather than a hyperlink) inform the customer the likely consequences (such as a button control money trading), or request the operation may be unsafe (for example, a file will be uploaded, or DELETE). However, you can’t take it for granted that a server can handle a GET request without any side effects. In fact, many dynamic resources feature this as their feature. The important difference here is that the user did not request this side effect and therefore should not be held responsible for it. Side effects Several request methods can be considered idempotence if they have the same or no side effects as a single request, regardless of issues such as errors or expiration. The GET, HEAD, PUT, and DELETE methods all have such idempotent properties, and OPTIONS and TRACE are idempotent because they have no side effects by protocol. A sequence of requests is idempotent if the result of a sequence of requests remains unchanged after repeated execution of the sequence or any one or more of the requests. However, it is possible to have a sequence of requests that is “non-idempotent”, even if all of the request methods executed in the sequence are idempotent. For example, the result of this sequence of requests depends on a variable that will be modified the next time the sequence is executed.

Summary:

HTTP Method Idempotent Safe
OPTIONS yes yes
GET yes yes
HEAD yes yes
PUT yes no
POST no no
DELETE yes no
PATCH no no

Common idempotent problems

On the business

  • When a user places an order for shopping, the user performs multiple operations, but the order system can only generate one order for this operation (no control will lead to malicious brushing).
  • When a user pays for an order, the payment system should only charge the user once, no matter what happens.
  • When the inventory deduction is successfully paid, the inventory system can only deduct the inventory quantity of the goods in the order once.
  • When delivering goods, ensure that the logistics system has only one delivery.

technical

  • The front-end submits the form repeatedly, causing the same piece of data to be submitted repeatedly.
  • When a retry mechanism is added, a request is retried multiple times, resulting in inconsistent data.
  • When using MQ message-oriented middleware, repeated consumption occurs if the message-oriented middleware fails to submit consumption information in a timely manner.

Front-end solutions

The front against the heavy

To ensure idempotent through the front end is the simplest way to achieve, front-end related attributes and JS code can be set. Reliability is not good, and experienced people can skip pages with the tool and still re-submit. It is mainly applicable to repeated forms submission or button clicking.

These RPG mode

PRG is the post-redirect-get mode. When a user submits a form, it is redirected to another successful submission page instead of staying on the original form page. This avoids repeated commits caused by user refreshes. It also prevents the form from being submitted repeatedly by pushing forward/back through the browser buttons. It is a common front – end anti – weight strategy.

Token mode

The token mode is mainly used to prevent duplication.

This requires a degree of interaction between the front and back ends. Redis is needed.

Specific process steps:

  1. The client will first send a request to obtain the token, and the server will generate a globally unique ID stored in Redis as the token, and return this ID to the client
  2. The client must carry this token the second time it invokes a business request
  3. The server verifies the token. If the verification succeeds, services are executed and the token in redis is deleted
  4. If the verification fails, there is no corresponding token in redis. The operation is repeated and the specified result is directly returned to the client

Note:

  • In the concurrent case, performing Redis lookup and deletion needs to be atomically guaranteed, otherwise idempotent may not be guaranteed in the concurrent case. It can be implemented using distributed locks or Lua expressions to unregister queries and deletes.

  • The global unique ID can be generated by baidu’s UID-Generator and Meituan’s Leaf

Redis distributed locks can be utilized: typical implementations of setnx + getSet or Redisson

Here are two core methods of implementation, the first using Redisson’s:

/** * Create a Token to store in Redis and return the Token *@paramValue Value used for authentication *@returnThe generated Token string */
    public String generateToken(String value) {
    
        String token = UUID.randomUUID().toString();
        String key = IDEMPOTENT_TOKEN_PREFIX + token;
        /** * Use unique tokens such as serial number */ in real business
        redisTemplate.opsForValue().set(key, value, 5, TimeUnit.MINUTES);
        return token;
    }

    /** * Distributed locking implements idempotency */
    @PostMapping("/distributeLock")
    @apiOperation (value = "Distributed lock implements idempotency ")
    public String distributeLock(HttpServletRequest request) {
    
        String token = request.getHeader("token");
        // Get user information (using simulated data here)
        String userInfo = "mydlq";
        RLock lock = redissonClient.getLock(token);
        lock.lock(10, TimeUnit.SECONDS);
        try {
    
           Boolean flag = tokenUtilService.validToken2(token, userInfo);
            // Respond to different information according to the verification result
            if (flag) {
    
                /** * Perform normal logic */
                log.info("Perform normal logic ………………");
            }
            return flag ? "Normal call" : "Repeat call";
        } catch (Exception e) {
    
            e.printStackTrace();
            return  "Repeat call";
        } finally{ lock.unlock(); }}Copy the code

Then there’s the Lua script

  /** * Verify Token correctness **@paramToken Token character string *@paramValue value Secondary authentication information stored in Redis *@returnVerify the result */
    public Boolean validToken(String token, String value) {
    
        KEYS[1] = KEYS[2]; KEYS[1] = KEYS[2]; KEYS[2] = KEYS[1]; Return KEYS[1] if equal and delete KEYS[1] in redis, otherwise return 0
        String script = "if redis.call('get',KEYS[1]) == KEYS[2] then return redis.call('del', KEYS[1]) else return 0 end";
        RedisScript<Long> redisScript = new DefaultRedisScript<>(script, Long.class);
        // Splice the Key according to the Key prefix
        String key = IDEMPOTENT_TOKEN_PREFIX + token;
        // Execute the Lua script
        Long result = redisTemplate.execute(redisScript, Arrays.asList(key, value));
        // Check whether the Redis key/value pair is successfully matched and delete it. If the result is not null or 0, the verification succeeds
        if(result ! =null&& result ! =0L) {
    
            log.info(Verify token={},key={},value={} successfully, token, key, value);
            return true;
        }
        log.info("Failed to validate token={},key={},value={}", token, key, value);

        return false;
    }
Copy the code

Redissonclient.getlock (” myLockKey “); redissonClient.getLock(” myLockKey “); redissonClient.getLock(” myLockKey “); redissonClient.getLock(” myLockKey “); Redisson locks are acquired internally by lua scripting language. Because the lock acquisition process involves multiple steps, Lua scripts are used to ensure atomicity of the execution process.

Here it is:

<T> RFuture<T> tryLockInnerAsync(long waitTime, long leaseTime, TimeUnit unit, long threadId, RedisStrictCommand<T> command) {
        return this.evalWriteAsync(this.getRawName(), LongCodec.INSTANCE, command, "if (redis.call('exists', KEYS[1]) == 0) then redis.call('hincrby', KEYS[1], ARGV[2], 1); redis.call('pexpire', KEYS[1], ARGV[1]); return nil; end; if (redis.call('hexists', KEYS[1], ARGV[2]) == 1) then redis.call('hincrby', KEYS[1], ARGV[2], 1); redis.call('pexpire', KEYS[1], ARGV[1]); return nil; end; return redis.call('pttl', KEYS[1]);", Collections.singletonList(this.getRawName()), new Object[]{unit.toMillis(leaseTime), this.getLockName(threadId)});
    }
Copy the code

There are several advanced concepts about Redisson lock such as “red lock”, interested friends can look at: redis.cn/topics/dist…

Back-end solutions

Using the database implementation of the scheme

Go to the heavy table

The implementation idea of de-duplicating table is also very simple. First, create a table as de-duplicating table, and create the unique index of one or more fields in the table as anti-duplicating field to ensure that there is only one data in the case of concurrency. Before inserting data into the service table, insert data into the deduplication table. If the insert fails, it indicates that the data is duplicated.

For example, if the same user cannot order the same item twice in the same minute, user_id, product_id, and created_AT should be used as the de-duplication fields.

Insert and DELETE scenarios with unique primary keys

This can be done by setting a unique primary key constraint or unique index constraint on the database so that duplicate keys cannot be inserted successfully. For example, if you insert data with userId 1 and it succeeds the first time, try again and it won’t succeed.

This scheme can prevent new dirty data and has the effect of anti-gravity.

There’s a difference between anti-redesigning and idempotent design. Anti-redesign is mainly to avoid duplicate data and does not have too many requirements on interface return. Idempotent design, in addition to avoiding duplicate data, requires that the same result be returned every time a request is made

Optimistic lock Update scenario

Optimistic database locking scheme is generally only applicable to update operations. We can add an extra field in the corresponding data table in advance to act as the version identifier of the current data.

The basic idea is: version number + condition, implementation idea is based on MySQL line lock idea to achieve. Take orders minus inventory for example:

If we only condition the update on the version number

update tb_stock set amount=amount-#{num},version=version+1 where goods_id=#{goodsId} and version=#{version}

Copy the code

Then only one user who orders at the same time can successfully reduce inventory, and the others all fail. In this case, we can add another condition to judge. For example:

update tb_stock set amount=amount-#{num} where goods_id=#{goodsId} and amount-#{num}> =0
Copy the code

As long as it doesn’t oversold.

This can also be used when the order is paid only once, but under different conditions (also known as state identification or state machine idempotent), for example:

update table item set item.status=:newstatus where item.id = :id and item.status = oldstatus
Copy the code

Of course, this is only to ensure the idempotent interface. In a real distributed environment, the calls between services are likely to involve distributed transactions, so it is necessary to add distributed transaction solutions on the basis of idempotent, such as SEATA, which is not the focus of this article. But idempotent is an important foundation for consistency of business data.

Why not pessimistic lock?

First, pessimistic locks may lock the table, which has performance problems.

For example, select for Update

Since InnoDB defaults to row-level locking, MySQL will only execute Row Lock if primary key is “explicitly” specified, otherwise MySQL will execute Table Locck Lock

Second, using pessimistic locks may cause deadlocks

For example, user A accesses table A (locks table A) and then attempts to access table B; Another user B accesses table B (locks table B) and then attempts to access table A. For user A, table B has been locked by user B, so user A must wait for user B to release table B. For user B, table A has been locked by user A, so user B can access table A only after user A releases table A. At this point a deadlock has occurred.

Redis distributed lock implementation

Specific process steps:

  1. The client requests the server first and gets a unique field that represents the requested business
  2. This field is stored in Redis in SETNX mode, and the corresponding timeout time is set according to the business
  3. If the setup is successful and proves that this is the first request, the subsequent business logic is executed
  4. If the setting fails, it indicates that the current request has been executed

On the whole, it is similar to redis used in the token scheme above, which is basically distributed ID+ distributed lock.

It is more suitable for interface idempotent between services, such as order transfer inventory, order call payment, etc.

For example, the order man becomes an ID identifier (such as the order number). The ID identifier can be generated by the distributed ID generator, and then request the inventory together with this identifier. If the inventory has not been stored in Redis before, it will be normally executed. Redis returns a failure indicating repeated requests.

The important thing to remember here is to set the expiration time of redis according to

  • Service execution time
  • Retry times and time of the upstream system or the entire system

Suppose we set it to 2 seconds, then the same business is: for example, the same order (id identifier is the order number), more than 2 times of inventory reduction within 2 seconds, obviously a repeated operation, need idempotent processing (return failure indicates repeated request).

Regardless of the number and time of retries, once the Redis key expires due to timeout, the calling service cannot guarantee idempotent if it tries again.

Message idempotent

The message push repeats when the message is received. If the interface handling the message is not idempotent, the impact of repeated consumption of the message can be significant.

For specific solutions, see the next section.

reference

  • www.bianchengquan.com/article/133…
  • Baike.baidu.com/item/%E5%B9…
  • Mp.weixin.qq.com/s/vsvfnj5RL…
  • Mp.weixin.qq.com/s/xq2ks76hT…