面試官：如何保證冪等性？

作者：磊哥 2023-09-01 15:27:31

本文講了防止數(shù)據(jù)重復(fù)提交的 6 種方法，首先是前端的攔截，通過隱藏和設(shè)置按鈕的不可用來屏蔽正常操作下的重復(fù)提交。但為了避免非正常渠道的重復(fù)提交，我們又實(shí)現(xiàn)了 5 個(gè)版本的后端攔截：HashMap 版、固定數(shù)組版、雙重檢測鎖的數(shù)組版、LRUMap 版和 LRUMap 的封裝版。

前兩天有位讀者問磊哥：在 Java 中，防止重復(fù)提交最簡單的方案是什么？

這句話中包含了兩個(gè)關(guān)鍵信息，第一：防止重復(fù)提交；第二：最簡單。

于是磊哥問他，是單機(jī)環(huán)境還是分布式環(huán)境？

得到的反饋是單機(jī)環(huán)境，那就簡單了，于是磊哥就開始裝*了。

話不多說，我們先來復(fù)現(xiàn)這個(gè)問題。

模擬用戶場景

根據(jù)朋友的反饋，大致的場景是這樣的，如下圖所示：

圖片

簡化的模擬代碼如下（基于 Spring Boot）：

import org.springframework.web.bind.annotation.RequestMapping;
import org.springframework.web.bind.annotation.RestController;

@RequestMapping("/user")
@RestController
public class UserController {
   /**
     * 被重復(fù)請求的方法
     */
    @RequestMapping("/add")
    public String addUser(String id) {
        // 業(yè)務(wù)代碼...
        System.out.println("添加用戶ID:" + id);
        return "執(zhí)行成功！";
    }
}

于是磊哥就想到：通過前、后端分別攔截的方式來解決數(shù)據(jù)重復(fù)提交的問題。

前端攔截

前端攔截是指通過 HTML 頁面來攔截重復(fù)請求，比如在用戶點(diǎn)擊完“提交”按鈕后，我們可以把按鈕設(shè)置為不可用或者隱藏狀態(tài)。

執(zhí)行效果如下圖所示：

圖片

前端攔截的實(shí)現(xiàn)代碼：

<html>
<script>
    function subCli(){
        // 按鈕設(shè)置為不可用
        document.getElementById("btn_sub").disabled="disabled";
        document.getElementById("dv1").innerText = "按鈕被點(diǎn)擊了~";
    }
</script>
<body style="margin-top: 100px;margin-left: 100px;">
    <input id="btn_sub" type="button"  value=" 提 交 "  onclick="subCli()">
    <div id="dv1" style="margin-top: 80px;"></div>
</body>
</html>

但前端攔截有一個(gè)致命的問題，如果是懂行的程序員或非法用戶可以直接繞過前端頁面，通過模擬請求來重復(fù)提交請求，比如充值了 100 元，重復(fù)提交了 10 次變成了 1000 元（瞬間發(fā)現(xiàn)了一個(gè)致富的好辦法）。

所以除了前端攔截一部分正常的誤操作之外，后端的攔截也是必不可少。

后端攔截

后端攔截的實(shí)現(xiàn)思路是在方法執(zhí)行之前，先判斷此業(yè)務(wù)是否已經(jīng)執(zhí)行過，如果執(zhí)行過則不再執(zhí)行，否則就正常執(zhí)行。

我們將請求的業(yè)務(wù) ID 存儲在內(nèi)存中，并且通過添加互斥鎖來保證多線程下的程序執(zhí)行安全，大體實(shí)現(xiàn)思路如下圖所示：

圖片

然而，將數(shù)據(jù)存儲在內(nèi)存中，最簡單的方法就是使用 HashMap 存儲，或者是使用 Guava Cache 也是同樣的效果，但很顯然 HashMap 可以更快的實(shí)現(xiàn)功能，所以我們先來實(shí)現(xiàn)一個(gè) HashMap 的防重（防止重復(fù)）版本。

1.基礎(chǔ)版——HashMap

import org.springframework.web.bind.annotation.RequestMapping;
import org.springframework.web.bind.annotation.RestController;

import java.util.HashMap;
import java.util.Map;

/**
 * 普通 Map 版本
 */
@RequestMapping("/user")
@RestController
public class UserController3 {

    // 緩存 ID 集合
    private Map<String, Integer> reqCache = new HashMap<>();

    @RequestMapping("/add")
    public String addUser(String id) {
        // 非空判斷(忽略)...
        synchronized (this.getClass()) {
            // 重復(fù)請求判斷
            if (reqCache.containsKey(id)) {
                // 重復(fù)請求
                System.out.println("請勿重復(fù)提交！！！" + id);
                return "執(zhí)行失敗";
            }
            // 存儲請求 ID
            reqCache.put(id, 1);
        }
        // 業(yè)務(wù)代碼...
        System.out.println("添加用戶ID:" + id);
        return "執(zhí)行成功！";
    }
}

實(shí)現(xiàn)效果如下圖所示：

圖片

存在的問題：此實(shí)現(xiàn)方式有一個(gè)致命的問題，因?yàn)?nbsp;HashMap 是無限增長的，因此它會(huì)占用越來越多的內(nèi)存，并且隨著 HashMap 數(shù)量的增加查找的速度也會(huì)降低，所以我們需要實(shí)現(xiàn)一個(gè)可以自動(dòng)“清除”過期數(shù)據(jù)的實(shí)現(xiàn)方案。

2.優(yōu)化版——固定大小的數(shù)組

此版本解決了 HashMap 無限增長的問題，它使用數(shù)組加下標(biāo)計(jì)數(shù)器（reqCacheCounter）的方式，實(shí)現(xiàn)了固定數(shù)組的循環(huán)存儲。

當(dāng)數(shù)組存儲到最后一位時(shí)，將數(shù)組的存儲下標(biāo)設(shè)置 0，再從頭開始存儲數(shù)據(jù)，實(shí)現(xiàn)代碼如下：

import org.springframework.web.bind.annotation.RequestMapping;
import org.springframework.web.bind.annotation.RestController;

import java.util.Arrays;

@RequestMapping("/user")
@RestController
public class UserController {

    private static String[] reqCache = new String[100]; // 請求 ID 存儲集合
    private static Integer reqCacheCounter = 0; // 請求計(jì)數(shù)器（指示 ID 存儲的位置）

    @RequestMapping("/add")
    public String addUser(String id) {
        // 非空判斷(忽略)...
        synchronized (this.getClass()) {
            // 重復(fù)請求判斷
            if (Arrays.asList(reqCache).contains(id)) {
                // 重復(fù)請求
                System.out.println("請勿重復(fù)提交！！！" + id);
                return "執(zhí)行失敗";
            }
            // 記錄請求 ID
            if (reqCacheCounter >= reqCache.length) reqCacheCounter = 0; // 重置計(jì)數(shù)器
            reqCache[reqCacheCounter] = id; // 將 ID 保存到緩存
            reqCacheCounter++; // 下標(biāo)往后移一位
        }
        // 業(yè)務(wù)代碼...
        System.out.println("添加用戶ID:" + id);
        return "執(zhí)行成功！";
    }
}

3.擴(kuò)展版——雙重檢測鎖(DCL)

上一種實(shí)現(xiàn)方法將判斷和添加業(yè)務(wù)，都放入 synchronized 中進(jìn)行加鎖操作，這樣顯然性能不是很高，于是我們可以使用單例中著名的 DCL（Double Checked Locking，雙重檢測鎖）來優(yōu)化代碼的執(zhí)行效率，實(shí)現(xiàn)代碼如下：

import org.springframework.web.bind.annotation.RequestMapping;
import org.springframework.web.bind.annotation.RestController;

import java.util.Arrays;

@RequestMapping("/user")
@RestController
public class UserController {

    private static String[] reqCache = new String[100]; // 請求 ID 存儲集合
    private static Integer reqCacheCounter = 0; // 請求計(jì)數(shù)器（指示 ID 存儲的位置）

    @RequestMapping("/add")
    public String addUser(String id) {
        // 非空判斷(忽略)...
        // 重復(fù)請求判斷
        if (Arrays.asList(reqCache).contains(id)) {
            // 重復(fù)請求
            System.out.println("請勿重復(fù)提交！！！" + id);
            return "執(zhí)行失敗";
        }
        synchronized (this.getClass()) {
            // 雙重檢查鎖（DCL,double checked locking）提高程序的執(zhí)行效率
            if (Arrays.asList(reqCache).contains(id)) {
                // 重復(fù)請求
                System.out.println("請勿重復(fù)提交！！！" + id);
                return "執(zhí)行失敗";
            }
            // 記錄請求 ID
            if (reqCacheCounter >= reqCache.length) reqCacheCounter = 0; // 重置計(jì)數(shù)器
            reqCache[reqCacheCounter] = id; // 將 ID 保存到緩存
            reqCacheCounter++; // 下標(biāo)往后移一位
        }
        // 業(yè)務(wù)代碼...
        System.out.println("添加用戶ID:" + id);
        return "執(zhí)行成功！";
    }
}

注意：DCL 適用于重復(fù)提交頻繁比較高的業(yè)務(wù)場景，對于相反的業(yè)務(wù)場景下 DCL 并不適用。

4.完善版——LRUMap

上面的代碼基本已經(jīng)實(shí)現(xiàn)了重復(fù)數(shù)據(jù)的攔截，但顯然不夠簡潔和優(yōu)雅，比如下標(biāo)計(jì)數(shù)器的聲明和業(yè)務(wù)處理等，但值得慶幸的是 Apache 為我們提供了一個(gè) commons-collections 的框架，里面有一個(gè)非常好用的數(shù)據(jù)結(jié)構(gòu) LRUMap 可以保存指定數(shù)量的固定的數(shù)據(jù)，并且它會(huì)按照 LRU 算法，幫你清除最不常用的數(shù)據(jù)。

小貼士：LRU 是 Least Recently Used 的縮寫，即最近最少使用，是一種常用的數(shù)據(jù)淘汰算法，選擇最近最久未使用的數(shù)據(jù)予以淘汰。

首先，我們先來添加 Apache commons collections 的引用：

<!-- 集合工具類 apache commons collections -->
<!-- https://mvnrepository.com/artifact/org.apache.commons/commons-collections4 -->
<dependency>
  <groupId>org.apache.commons</groupId>
  <artifactId>commons-collections4</artifactId>
  <version>4.4</version>
</dependency>

實(shí)現(xiàn)代碼如下：

import org.apache.commons.collections4.map.LRUMap;
import org.springframework.web.bind.annotation.RequestMapping;
import org.springframework.web.bind.annotation.RestController;

@RequestMapping("/user")
@RestController
public class UserController {

    // 最大容量 100 個(gè)，根據(jù) LRU 算法淘汰數(shù)據(jù)的 Map 集合
    private LRUMap<String, Integer> reqCache = new LRUMap<>(100);

    @RequestMapping("/add")
    public String addUser(String id) {
        // 非空判斷(忽略)...
        synchronized (this.getClass()) {
            // 重復(fù)請求判斷
            if (reqCache.containsKey(id)) {
                // 重復(fù)請求
                System.out.println("請勿重復(fù)提交！！！" + id);
                return "執(zhí)行失敗";
            }
            // 存儲請求 ID
            reqCache.put(id, 1);
        }
        // 業(yè)務(wù)代碼...
        System.out.println("添加用戶ID:" + id);
        return "執(zhí)行成功！";
    }
}

使用了 LRUMap 之后，代碼顯然簡潔了很多。

5.最終版——封裝

以上都是方法級別的實(shí)現(xiàn)方案，然而在實(shí)際的業(yè)務(wù)中，我們可能有很多的方法都需要防重，那么接下來我們就來封裝一個(gè)公共的方法，以供所有類使用：

import org.apache.commons.collections4.map.LRUMap;

/**
 * 冪等性判斷
 */
public class IdempotentUtils {

    // 根據(jù) LRU(Least Recently Used，最近最少使用)算法淘汰數(shù)據(jù)的 Map 集合，最大容量 100 個(gè)
    private static LRUMap<String, Integer> reqCache = new LRUMap<>(100);

    /**
     * 冪等性判斷
     * @return
     */
    public static boolean judge(String id, Object lockClass) {
        synchronized (lockClass) {
            // 重復(fù)請求判斷
            if (reqCache.containsKey(id)) {
                // 重復(fù)請求
                System.out.println("請勿重復(fù)提交！！！" + id);
                return false;
            }
            // 非重復(fù)請求，存儲請求 ID
            reqCache.put(id, 1);
        }
        return true;
    }
}

調(diào)用代碼如下：

import com.example.idempote.util.IdempotentUtils;
import org.springframework.web.bind.annotation.RequestMapping;
import org.springframework.web.bind.annotation.RestController;

@RequestMapping("/user")
@RestController
public class UserController4 {
    @RequestMapping("/add")
    public String addUser(String id) {
        // 非空判斷(忽略)...
        // -------------- 冪等性調(diào)用（開始） --------------
        if (!IdempotentUtils.judge(id, this.getClass())) {
            return "執(zhí)行失敗";
        }
        // -------------- 冪等性調(diào)用（結(jié)束） --------------
        // 業(yè)務(wù)代碼...
        System.out.println("添加用戶ID:" + id);
        return "執(zhí)行成功！";
    }
}

小貼士：一般情況下代碼寫到這里就結(jié)束了，但想要更簡潔也是可以實(shí)現(xiàn)的，你可以通過自定義注解，將業(yè)務(wù)代碼寫到注解中，需要調(diào)用的方法只需要寫一行注解就可以防止數(shù)據(jù)重復(fù)提交了，老鐵們可以自行嘗試一下（需要磊哥擼一篇的，評論區(qū)留言 666）。

擴(kuò)展知識——LRUMap 實(shí)現(xiàn)原理分析

既然 LRUMap 如此強(qiáng)大，我們就來看看它是如何實(shí)現(xiàn)的。

LRUMap 的本質(zhì)是持有頭結(jié)點(diǎn)的環(huán)回雙鏈表結(jié)構(gòu)，它的存儲結(jié)構(gòu)如下：

AbstractLinkedMap.LinkEntry entry;

當(dāng)調(diào)用查詢方法時(shí)，會(huì)將使用的元素放在雙鏈表 header 的前一個(gè)位置，源碼如下：

public V get(Object key, boolean updateToMRU) {
    LinkEntry<K, V> entry = this.getEntry(key);
    if (entry == null) {
        return null;
    } else {
        if (updateToMRU) {
            this.moveToMRU(entry);
        }

        return entry.getValue();
    }
}
protected void moveToMRU(LinkEntry<K, V> entry) {
    if (entry.after != this.header) {
        ++this.modCount;
        if (entry.before == null) {
            throw new IllegalStateException("Entry.before is null. This should not occur if your keys are immutable, and you have used synchronization properly.");
        }

        entry.before.after = entry.after;
        entry.after.before = entry.before;
        entry.after = this.header;
        entry.before = this.header.before;
        this.header.before.after = entry;
        this.header.before = entry;
    } else if (entry == this.header) {
        throw new IllegalStateException("Can't move header to MRU This should not occur if your keys are immutable, and you have used synchronization properly.");
    }

}

如果新增元素時(shí)，容量滿了就會(huì)移除 header 的后一個(gè)元素，添加源碼如下：

protected void addMapping(int hashIndex, int hashCode, K key, V value) {
     // 判斷容器是否已滿 
     if (this.isFull()) {
         LinkEntry<K, V> reuse = this.header.after;
         boolean removeLRUEntry = false;
         if (!this.scanUntilRemovable) {
             removeLRUEntry = this.removeLRU(reuse);
         } else {
             while(reuse != this.header && reuse != null) {
                 if (this.removeLRU(reuse)) {
                     removeLRUEntry = true;
                     break;
                 }
                 reuse = reuse.after;
             }
             if (reuse == null) {
                 throw new IllegalStateException("Entry.after=null, header.after=" + this.header.after + " header.before=" + this.header.before + " key=" + key + " value=" + value + " size=" + this.size + " maxSize=" + this.maxSize + " This should not occur if your keys are immutable, and you have used synchronization properly.");
             }
         }
         if (removeLRUEntry) {
             if (reuse == null) {
                 throw new IllegalStateException("reuse=null, header.after=" + this.header.after + " header.before=" + this.header.before + " key=" + key + " value=" + value + " size=" + this.size + " maxSize=" + this.maxSize + " This should not occur if your keys are immutable, and you have used synchronization properly.");
             }
             this.reuseMapping(reuse, hashIndex, hashCode, key, value);
         } else {
             super.addMapping(hashIndex, hashCode, key, value);
         }
     } else {
         super.addMapping(hashIndex, hashCode, key, value);
     }
 }

判斷容量的源碼：

public boolean isFull() {
  return size >= maxSize;
}

容量未滿就直接添加數(shù)據(jù)：

super.addMapping(hashIndex, hashCode, key, value);

如果容量滿了，就調(diào)用 reuseMapping 方法使用 LRU 算法對數(shù)據(jù)進(jìn)行清除。

綜合來說：LRUMap 的本質(zhì)是持有頭結(jié)點(diǎn)的環(huán)回雙鏈表結(jié)構(gòu)，當(dāng)使用元素時(shí)，就將該元素放在雙鏈表 header 的前一個(gè)位置，在新增元素時(shí)，如果容量滿了就會(huì)移除 header 的后一個(gè)元素。

小結(jié)

特殊說明：本文所有的內(nèi)容僅適用于單機(jī)環(huán)境下的重復(fù)數(shù)據(jù)攔截，如果是分布式環(huán)境需要配合數(shù)據(jù)庫或 Redis 來實(shí)現(xiàn)，想看分布式重復(fù)數(shù)據(jù)攔截的老鐵們，請給磊哥一個(gè)「贊」，如果點(diǎn)贊超過 50 個(gè)，咱們更新分布式環(huán)境下重復(fù)數(shù)據(jù)的處理方案。