Web 前端 – 又不僅限於 Web 前端 – 協程鎖問題

前言

  最近兩天的 web 前端開發中,早前的鎖實現 (自旋鎖) 出現了一些不合理的現象,所以有了這片隨筆

  什麼是協程鎖?能點進這個博客的的你肯定是明白的,不明白的人根本搜不到我這隨筆,不多做贅述。

一些個人認識和實現經驗

  1. 可重入鎖:協程由於沒有像『線程』那樣的變量隔離,即缺少『計數標識』的掛載位置(多線程中計數標識直接或間接掛載在線程對象上),未實現可重入鎖之前,編碼開發中應該避免嵌套相同鎖調用,否則造成死鎖,
    所以『可重入鎖』暫時沒有太好的實現思路,希望有大神可以指點迷津。
  2. 自旋鎖:優點是通俗易懂,一行 while(lock = getLock( lockKey )) await sleep(20) 就可以實現,缺點是不能保證代碼的順序性,造成無法預知的 Bug,如 異步打開遮罩 -> 異步關閉遮罩 的執行順序將不可控,棄用。
  3. 公平鎖:保證 FIFO 策略,使協程對鎖先取先得,解決自旋鎖的缺陷。
  4. 歸一鎖:類似多線程中的雙重檢驗鎖,在多線程中多用於單例的初始化或賦值,在 Web 前端可將重複異步冪等操作消減歸一。如『獲取用戶信息』多個模塊都調用此異步函數,只接發出一個『獲取用戶信息』的請求,多餘 1 個的所有協程將進入 Pending 狀態,一起等待返回結果。
    ( 結合公平鎖,實現順序等待調用)
  5. 等侯鎖:只允許一個協程進入操作,多餘 1 的所有協程進入 Pending 狀態,等待被調用。
    (結合公平鎖,實現順序等待調用)

  暫時想到這麼多,歡迎補充。

設計

  1. 歸一鎖:asyncOne( asyncFunction:AsyncFunction, …keys:any[] )
  2. 等侯鎖:asyncWait( asyncFunction:AsyncFunction, …keys:any[] )

實現

  1. 鎖管理器 ( 核心 ):根據一組 keys ,提供 查、加、解 鎖的能力。
    getPendings(keys) / addPendings(keys) / delPendings(keys)
    // Synchronized async function
    const NEXT = Symbol();
    const PREV = Symbol();
    type LevelsNode = { [NEXT]?: LevelsMap; pendings?: PendingPromise<any>[]; [PREV]?: LevelsNode; key: string };
    type LevelsMap = Map<any, LevelsNode>;
    
    function findSyncNode(syncMap: LevelsMap, keys: any[], creation: false): [LevelsMap | undefined, LevelsNode | undefined, PendingPromise<any>[] | undefined];
    function findSyncNode(syncMap: LevelsMap, keys: any[], creation: true): [LevelsMap, LevelsNode, PendingPromise<any>[]];
    function findSyncNode(syncMap: LevelsMap, keys: any[], creation: boolean) {
      let prntNode: LevelsNode | undefined;
      let map: LevelsMap | undefined = syncMap;
      for (let i = 0; !!map && i < keys.length - 1; i++) {
        let lastNode = prntNode;
        prntNode = map.get(keys[i]);
        if (!prntNode) {
          if (creation) {
            prntNode = { [NEXT]: new Map(), [PREV]: lastNode, key: keys[i] };
            map.set(keys[i], prntNode);
            map = prntNode[NEXT];
          } else {
            map = undefined;
          }
        } else if (!(map = prntNode[NEXT])) {
          if (creation) {
            prntNode[NEXT] = new Map();
            map = prntNode[NEXT];
          } else {
            if (i < keys.length - 2) prntNode = undefined;
          }
        }
      }
      let mapNode = map?.get(keys[keys.length - 1]);
      if (creation) {
        if (!map) {
          Throwable("Impossible Error: No Prev Map.");
        } else if (!mapNode) {
          map.set(keys[keys.length - 1], (mapNode = { pendings: [], [PREV]: prntNode, key: keys[keys.length - 1] }));
        } else if (!mapNode.pendings) {
          mapNode.pendings = [];
        }
      }
      return [map, mapNode, mapNode?.pendings];
    }
    const getPendings = (syncMap: LevelsMap, keys: any[]) => findSyncNode(syncMap, keys, false)[2];
    const addPendings = (syncMap: LevelsMap, keys: any[]) => findSyncNode(syncMap, keys, true)[2];
    const delPendings = (syncMap: LevelsMap, keys: any[]) => {
      const [finalMap, finalVal] = findSyncNode(syncMap, keys, false);
      if (!!finalMap && !!finalVal) {
        // delete pending
        delete finalVal.pendings;
        // delete above including self
        tryDeleteNodeAndAbove(syncMap, finalVal);
      }
    };
    const tryDeleteNodeAndAbove = (syncMap: LevelsMap, node?: LevelsNode) => {
      while (!!node) {
        const nextMap = node[NEXT];
        if (!node.pendings && (!nextMap || nextMap.size === 0)) {
          const nodeKey = node.key;
          node = node[PREV];
          const map = node?.[NEXT] || syncMap;
          map.delete(nodeKey);
        } else {
          break;
        }
      }
    };

     


  2. 歸一鎖算法:
    const asyncOneMap: LevelsMap = new Map<any, LevelsNode>();
    export const asyncOne = async <T>(call: () => Promise<T>, ...keys: any[]): Promise<T> => {
      let pendings = getPendings(asyncOneMap, keys);
      if (!!pendings) {
        return (pendings[pendings.length] = pendingResolve<T>());
      } else {
        pendings = addPendings(asyncOneMap, keys);
        try {
          const result = await call.call(null);
          pendings.forEach(p => setTimeout(() => p.resolve(result)));
          return result;
        } catch (e) {
          pendings.forEach(p => setTimeout(() => p.reject(e)));
          throw e;
        } finally {
          delPendings(asyncOneMap, keys);
        }
      }
    };

     

  3. 等侯鎖算法:
    const asyncWaitMap: LevelsMap = new Map<any, LevelsNode>();
    export const asyncWait = async <T>(call: () => Promise<T>, ...keys: any[]) => {
      let pendings = getPendings(asyncWaitMap, keys);
      /*sleep*/ if (!!pendings) await (pendings[pendings.length] = pendingResolve<void>());
      /*continue-------------*/ else pendings = addPendings(asyncWaitMap, keys);
      try {
        return await call.call(null);
      } finally {
        const next4awaken = pendings.shift();
        /*awaken the next*/ if (next4awaken !== undefined) next4awaken.resolve();
        /*unlock-----------------------------------*/ else delPendings(asyncWaitMap, keys);
      }
    };

     

  4. 依賴項 ( 第二關鍵 ):pendingResolve<T>:  <T>()=>PendingPromise<T>
    返回一個永久 pending 狀態的 Promise, 充當協程斷點的角色,必要時才手動 resolve / reject。
    本文不多贅述,請參考我的另一篇隨筆: Web 前端 – 淺談外部手動控制 Promise 狀態:PendingPromise<T>
  5. 依賴項 ( 輕微重要 ):aw: ( ms: number)=>Promise<void>
    類似於多線程語言中的 sleep( ms:number )
    本文不多贅述,請參考我的另一篇隨筆: Web 前端 – 優雅地 Callback 轉 Promise :aw