HN 日本語サマリー

← 一覧へ戻る
プログラミング

TLA+で16年前のSQLite WALバグを追跡する

Hunting a 16-year-old SQLite WAL bug with TLA+ (ubuntu.com)

220 pointsby peterparker20427 コメント

要約

この記事は、Canonicalのdqliteチームが、SQLiteのWrite Ahead Log (WAL) のチェックポイント処理における16年前のバグを、形式手法であるTLA+を用いてどのように特定・再現したかを解説しています。このバグはデータベースの破損を引き起こす可能性がありましたが、影響範囲は限定的でした。しかし、その発見の困難さと長期間存在していた事実から、dqliteチームは自らのシステムへの影響を確認するためにTLA+モデリングを採用し、SQLiteのWALの挙動をモデル化してバグの発生経路を特定しました。

全文翻訳

TLA+ を用いた16年前の SQLite WAL バグの追跡: dqlite は影響を受けるか?


この記事は Canonical の dqlite チーム、Marco Manino と Alberto Carretero によって書かれました。

1. SQLite バグの解剖

最近、SQLite は WAL (Write Ahead Log) のチェックポイント処理における長年のバグを修正する新バージョンを公開しました。このバグはデータベースの破損につながる可能性があります。

このバグの重要な点は、その実世界での影響(非常に低い)ではなく、リポジトリにどれだけ長く存在していたか、発見がどれほど困難だったか、そしてそれを再現するのがどれほど困難だったかということです。実際、このバグは2010年から存在しており、16年間も放置されていました!また、私たち dqlite チームにとっての重要な疑問は、「dqlite はこのバグの影響を受ける可能性があるのか?」ということです。

それを明らかにするために、まずデータベース破損につながる正確な手順を理解する必要があります。そのために、TLA+ を使用して SQLite の動作をモデル化し、バグについて推論できるトレースを迅速に見つけます。次に、dqlite が SQLite をどのように使用するかを記述する別のモデルを作成し、バグが発生する可能性があるかどうかを確認します。

2. WAL と SQLite のチェックポイントの簡単な紹介

SQLite は WAL モードを使用して、リーダーがライターによってブロックされないようにします。これを実現するために、Write Ahead Log (WAL) と呼ばれる特別なステージングエリアに書き込みます。ライターは WAL の末尾に追記でき、リーダーはデータが安定するまで新しいデータを無視できます。最終的に、ステージングエリアはデータベースに移動されます。これはチェックポイントと呼ばれます。WAL が無限に大きくなるのを防ぐために、前のチェックポイントがすべてのページを移動できた場合、ライターは WAL を「リセット」しようとします。つまり、上書きします。詳細を知りたい場合は、公式ドキュメントで非常に明確な説明を見つけることができます。

SQLite はロックと共有メモリを使用して WAL への変更を調整します。私たちのユースケースでは、書き込みとチェックポイントに焦点を当てれば十分です。そのため、2つのロックのみを考慮します。

  • チェックポイントロック (CKPT_LOCK): 同時に複数のチェックポイントが発生するのを防ぐために、チェックポイントを実行する前に取得されます。
  • 書き込みロック (WRITE_LOCK): WAL に新しいページを追記する前に取得されます。

共有メモリには、ライター、チェックポインター、リーダーを調整するために必要な情報と、読み取りパフォーマンスのために WAL 内のページをインデックス付けするデータ構造が含まれています。リーダーは関与しないため、興味深いフィールドは次のとおりです。

  • walSalt: WAL がリセットされるたびにインクリメントされるカウンターが含まれています。
  • mxFrame: WAL の長さを格納します。
  • nBackfill: すでにチェックポイントされたページの量、つまり、この時点までに [nBackfill+1, mxFrame] がデータベースにコピーされていないことを示します。

3. TLA+ でのバグのモデリング

TLA+ の記述の一部は、何をモデル化し、何をモデル化しないかを決定することです。現実を忠実に再現し、モデルから有用な洞察を引き出すことができる、可能な限り最もシンプルな仕様を作成したいと考えています。

最初にモデル化するのは、前のセクションで説明したデータベースと WAL です。

* files.
VARIABLE wal
VARIABLE db

* wal-index variables:
VARIABLE nBackfill
VARIABLE mxFrame
* We will only capture the sequential part of the salt.
VARIABLE walSalt

Init ≜
    * wal and db are initially empty.
    ∧ wal = ⟨⟩
    ∧ db = {}
    ∧ nBackfill = 0
    ∧ mxFrame = 0
    ∧ walSalt = 0

データを生成することはモデルのスコープ外であるため、よりシンプルなアプローチを取ることができます。各データページを単一の一意の番号としてモデル化し、WAL はそのような番号のシーケンス、データベースはそれらのセットとします。特に、チェックポイントは WAL のページを、WAL に追記された順序でデータベースのセットに移動させます。一意の番号を生成するには、常に増加するカウンターを使用すれば十分です。

バグを発生させる2つのアクション、つまり追記とチェックポイントをモデル化する必要があります。まず、WAL にページを追記する SQLite の C コードを見て、TLA+ アクションを定義しましょう。

static int walFrames(
  Wal *pWal,                      /* Wal handle to write to */
  int szPage,                     /* Database page-size in bytes */
  PgHdr *pList,                   /* List of dirty pages to write */
  Pgno nTruncate,                 /* Database size after this commit */
  int isCommit,                   /* True if this is a commit */
  int sync_flags                  /* Flags to pass to OsSync() (or 0) */
){
  int rc;                         /* Used to catch return codes */
  u32 iFrame;                     /* Next frame address */
  PgHdr *p;                       /* Iterator to run through pList with. */
  PgHdr *pLast = 0;               /* Last frame in list */
  int nExtra = 0;                 /* Number of extra copies of last page */
  int szFrame;                    /* The size of a single frame */
  i64 iOffset;                    /* Next byte to write in WAL file */
  WalWriter w;                    /* The writer */
  u32 iFirst = 0;                 /* First frame that may be overwritten */
  WalIndexHdr *pLive;             /* Pointer to shared header */

  assert( pList );
  assert( pWal->writeLock );

  /* If this frame set completes a transaction, then nTruncate>0.  If
  ** nTruncate==0 then this frame set does not complete the transaction. */
  assert( (isCommit!=0)==(nTruncate!=0) );

#if defined(SQLITE_TEST) && defined(SQLITE_DEBUG)
  {
    int cnt;
    for(cnt=0, p=pList; p; p=p->pDirty){}
    WALTRACE(("WAL%p: frame write begin. %d frames. mxFrame=%d. %s\n",
              pWal, cnt, pWal->hdr.mxFrame, isCommit ? "Commit" : "Spill"));
  }
#endif

  pLive = (WalIndexHdr*)walIndexHdr(pWal);
  if( memcmp(&pWal->hdr, (void *)pLive, sizeof(WalIndexHdr))!=0 ){
    iFirst = pLive->mxFrame+1;
  }

  /* See if it is possible to write these frames into the start of the
  ** log file, instead of appending to it at pWal->hdr.mxFrame.
  */
  if( SQLITE_OK!=(rc = walRestartLog(pWal)) ){
    return rc;
  }

  /* If this is the first frame written into the log, write the WAL
  ** header to the start of the WAL file. See comments at the top of
  ** this source file for a description of the WAL header format.
  */
  iFrame = pWal->hdr.mxFrame;
  if( iFrame==0 ){
    u8 aWalHdr[WAL_HDRSIZE];      /* Buffer to assemble wal-header in */
    u32 aCksum[2];                /* Checksum for wal-header */

    sqlite3Put4byte(&aWalHdr[0], (WAL_MAGIC | SQLITE_BIGENDIAN));
    sqlite3Put4byte(&aWalHdr[4], WAL_MAX_VERSION);
    sqlite3Put4byte(&aWalHdr[8], szPage);
    sqlite3Put4byte(&aWalHdr[12], pWal->nCkpt);
    if( pWal->nCkpt==0 ) sqlite3_randomness(8, pWal->hdr.aSalt);
    memcpy(&aWalHdr[16], pWal->hdr.aSalt, 8);
    walChecksumBytes(1, aWalHdr, WAL_HDRSIZE-2*4, 0, aCksum);
    sqlite3Put4byte(&aWalHdr[24], aCksum[0]);
    sqlite3Put4byte(&aWalHdr[28], aCksum[1]);

    pWal->szPage = szPage;
    pWal->hdr.bigEndCksum = SQLITE_BIGENDIAN;
    pWal->hdr.aFrameCksum[0] = aCksum[0];
    pWal->hdr.aFrameCksum[1] = aCksum[1];
    pWal->truncateOnCommit = 1;

    rc = sqlite3OsWrite(pWal->pWalFd, aWalHdr, sizeof(aWalHdr), 0);
    WALTRACE(("WAL%p: wal-header write %s\n", pWal, rc ? "failed" : "ok"));
    if( rc!=SQLITE_OK ){
      return rc;
    }

    /* Sync the header (unless SQLITE_IOCAP_SEQUENTIAL is true or unless
    ** all syncing is turned off by PRAGMA synchronous=OFF).  Otherwise
    ** an out-of-order write following a WAL restart could result in
    ** database corruption.  See the ticket:
    **
    **     https://sqlite.org/src/info/ff5be73dee
    */
    if( pWal->syncHeader ){
      rc = sqlite3OsSync(pWal->pWalFd, CKPT_SYNC_FLAGS(sync_flags));
      if( rc ) return rc;
    }
  }
  if( (int)pWal->szPage!=szPage ){
    return SQLITE_CORRUPT_BKPT;  /* TH3 test case: cov1/corrupt155.test */
  }

  /* Setup information needed to write frames into the WAL */
  w.pWal = pWal;
  w.pFd = pWal->pWalFd;
  w.iSyncPoint = 0;
  w.syncFlags = sync_flags;
  w.szPage = szPage;
  iOffset = walFrameOffset(iFrame+1, szPage);
  szFrame = szPage + WAL_FRAME_HDRSIZE;

  /* Write all frames into the log file exactly once */
  for(p=pList; p; p=p->pDirty){
    int nDbSize;   /* 0 normally.  Positive == commit flag */

    /* Check if this page has already been written into the wal file by
    ** the current transaction. If so, overwrite the existing frame and
    ** set Wal.writeLock to WAL_WRITELOCK_RECKSUM - indicating that
    ** checksums must be recomputed when the transaction is committed.  */
    if( iFirst && (p->pDirty || isCommit==0) ){
      u32 iWrite = 0;
      VVA_ONLY(rc =) walFindFrame(pWal, p->pgno, &iWrite);
      assert( rc==SQLITE_OK || iWrite==0 );
      if( iWrite>=iFirst ){
        i64 iOff = walFrameOffset(iWrite, szPage) + WAL_FRAME_HDRSIZE;
        void *pData;
        if( pWal->iReCksum==0 || iWrite<pWal->iReCksum ){
          pWal->iReCksum = iWrite;
        }
        pData = p->pData;
        rc = sqlite3OsWrite(pWal->pWalFd, pData, szPage, iOff);
        if( rc ) return rc;
        p->flags &= ~PGHDR_WAL_APPEND;
        continue;
      }
    }

    iFrame++;
    assert( iOffset==walFrameOffset(iFrame, szPage) );
    nDbSize = (isCommit && p->pDirty==0) ? nTruncate : 0;
    rc = walWriteOneFrame(&w, p, nDbSize, iOffset);
    if( rc ) return rc;
    pLast = p;
    iOffset += szFrame;
    p->flags |= PGHDR_WAL_APPEND;
  }

  /* Recalculate checksums within the wal file if required. */
  if( isCommit && pWal->iReCksum ){
    rc = walRewriteChecksums(pWal, iFrame);
    if( rc ) return rc;
  }

  /* If this is the end of a transaction, then we might need to pad
  ** the transaction and/or sync the WAL file.
  **
  ** Padding and syncing only occur if this set of frames complete a
  ** transaction and if PRAGMA synchronous=FULL.  If synchronous==NORMAL
  ** or synchronous==OFF, then no padding or syncing are needed.
  **
  ** If SQLITE_IOCAP_POWERSAFE_OVERWRITE is defined, then padding is not
  ** needed and only the sync is done.  If padding is needed, then the
  ** final frame is repeated (with its commit mark) until the next sector
  ** boundary is crossed.  Only the part of the WAL prior to the last
  ** sector boundary is synced; the part of the last frame that extends
  ** past the sector boundary is written after the sync.
  */
  if( isCommit && WAL_SYNC_FLAGS(sync_flags)!=0 ){
    int bSync = 1;
    if( pWal->padToSectorBoundary ){
      int sectorSize = sqlite3SectorSize(pWal->pWalFd);
      w.iSyncPoint = ((iOffset+sectorSize-1)/sectorSize)*sectorSize;
      bSync = (w.iSyncPoint==iOffset);
      testcase( bSync );
      while( iOffset<w.iSyncPoint ){
        rc = walWriteOneFrame(&w, pLast, nTruncate, iOffset);
        if( rc ) return rc;
        iOffset += szFrame;
        nExtra++;
        assert( pLast!=0 );
      }
    }
    if( bSync ){
      assert( rc==SQLITE_OK );
      rc = sqlite3OsSync(w.pFd, WAL_SYNC_FLAGS(sync_flags));
    }
  }

  /* If this frame set completes the first transaction in the WAL and
  ** if PRAGMA journal_size_limit is set, then truncate the WAL to the
  ** journal size limit, if possible.
  */
  if( isCommit && pWal->truncateOnCommit && pWal->mxWalSize>=0 ){
    i64 sz = pWal->mxWalSize;
    if( walFrameOffset(iFrame+nExtra+1, szPage)>pWal->mxWalSize ){
      sz = walFrameOffset(iFrame+nExtra+1, szPage);
    }
    walLimitSize(pWal, sz);
    pWal->truncateOnCommit = 0;
  }

  /* Append data to the wal-index. It is not necessary to lock the
  ** wal-index to do this as the SQLITE_SHM_WRITE lock held on the wal-index
  ** guarantees that there are no other writers, and no data that may
  ** be in use by existing readers is being overwritten.
  */
  iFrame = pWal->hdr.mxFrame;
  for(p=pList; p && rc==SQLITE_OK; p=p->pDirty){
    if( (p->flags & PGHDR_WAL_APPEND)==0 ) continue;
    iFrame++;
    rc = walIndexAppend(pWal, iFrame, p->pgno);
  }
  assert( pLast!=0 || nExtra==0 );
  while( rc==SQLITE_OK && nExtra>0 ){
    iFrame++;
    nExtra--;
    rc = walIndexAppend(pWal, iFrame, pLast->pgno);
  }

  if( rc==SQLITE_OK ){
    /* Update the private copy of the header. */
    pWal->hdr.szPage = (u16)((szPage&0xff00) | (szPage>>16));
    testcase( szPage<=32768 );
    testcase( szPage>=65536 );
    pWal->hdr.mxFrame = iFrame;
    if( isCommit ){
      pWal->hdr.iChange++;
      pWal->hdr.nPage = nTruncate;
    }
    /* If this is a commit, update the wal-index header too. */
    if( isCommit ){
      walIndexWriteHdr(pWal);
      pWal->iCallback = iFrame;
    }
  }

  WALTRACE(("WAL%p: frame write %s\n", pWal, rc ? "failed" : "ok"));
  return rc;
}

static int walRestartLog(Wal *pWal){
  int rc = SQLITE_OK;
  int cnt;

  if( pWal->readLock==0 ){
    volatile WalCkptInfo *pInfo = walCkptInfo(pWal);
    assert( pInfo->nBackfill==pWal->hdr.mxFrame );
    if( pInfo->nBackfill>0 ){
      u32 salt1;
      sqlite3_randomness(4, &salt1);
      rc = walLockExclusive(pWal, WAL_READ_LOCK(1), WAL_NREADER-1);
      if( rc==SQLITE_OK ){
        /* If all readers are using WAL_READ_LOCK(0) (in other words if no
        ** readers are currently using the WAL), then the transactions
        ** frames will overwrite the start of the existing log. Update the
        ** wal-index header to reflect this.
        **
        ** In theory it would be Ok to update the cache of the header only
        ** at this point. But updating the actual wal-index header is also
        ** safe and means there is no special case for sqlite3WalUndo() 
        ** to handle if this transaction is rolled back.  */
        walRestartHdr(pWal, salt1);
        walUnlockExclusive(pWal, WAL_READ_LOCK(1), WAL_NREADER-1);
      }else if( rc!=SQLITE_BUSY ){
        return rc;
      }
    }
    walUnlockShared(pWal, WAL_READ_LOCK(0));
    pWal->readLock = -1;
    cnt = 0;
    do{
      int notUsed;
      rc = walTryBeginRead(pWal, &notUsed, 1, &cnt);
    }while( rc==WAL_RETRY );
    assert( (rc&0xff)!=SQLITE_BUSY ); /* BUSY not possible when useWal==1 */
    testcase( (rc&0xff)==SQLITE_IOERR );
    testcase( rc==SQLITE_PROTOCOL );
    testcase( rc==SQLITE_OK );
  }
  return rc;
}

static void walRestartHdr(Wal *pWal, u32 salt1){
  volatile WalCkptInfo *pInfo = walCkptInfo(pWal);
  int i;                          /* Loop counter */
  u32 *aSalt = pWal->hdr.aSalt;   /* Big-endian salt values */
  pWal->nCkpt++;
  pWal->hdr.mxFrame = 0;
  sqlite3Put4byte((u8*)&aSalt[0], 1 + sqlite3Get4byte((u8*)&aSalt[0]));
  memcpy(&pWal->hdr.aSalt[1], &salt1, 4);
  walIndexWriteHdr(pWal);
  AtomicStore(&pInfo->nBackfill, 0);
  pInfo->nBackfillAttempted = 0;
  pInfo->aReadMark[1] = 0;
  for(i=2; i<WAL_NREADER; i++) pInfo->aReadMark[i] = READMARK_NOT_USED;
  assert( pInfo->aReadMark[0]==0 );
}

上記の関連部分をハイライトしましたが、これを TLA+ にどう落とし込むかを見てみましょう。モデル化に必要な動作は、WalAppendTakeLock と WalAppend の2つのアクションです。また、書き込みロックを表す新しい変数も必要です(上記の最初の assert)。

* Lock needed to write to the WAL.
VARIABLE writeLock
    
WalAppendTakeLock ≜
    ∧ writeLock = "notTaken"
    ∧ writeLock' = "takenForAppend"
    ∧ UNCHANGED ⟨ wal, db, nBackfill, mxFrame, frameNumber, checkPointState, safeMxFrame, walSalt, pWalSalt ⟩

WalAppend ≜
    ∧ writeLock = "takenForAppend"
    * The if condition is written as an assert in the sqlite code because
    * checking for pWal->readLock == 0 gives us the same guarantee. If the
    * writer has taken the read lock at 0 it means there are no frames in the
    * wal that were not checkpointed.
    ∧ IF (nBackfill > 0 ∧ mxFrame = nBackfill)
       THEN
        * Restart the Wal and Append.
        * We don't have readers so every writer after a checkpoint will
        * restart the wal.
        ∧ wal' = ⟨ frameNumber ⟩
        ∧ mxFrame' = 1
        ∧ nBackfill' = 0
        ∧ walSalt' = walSalt + 1
       ELSE
        ∧ wal' = Append(wal, frameNumber)
        ∧ mxFrame' = mxFrame + 1
        ∧ UNCHANGED ⟨ nBackfill, walSalt ⟩
    ∧ frameNumber' = frameNumber + 1
    ∧ writeLock' = "notTaken"
    ∧ UNCHANGED ⟨ db, checkpoint_vars ⟩

次に、パズルのもう一方のピースであるチェックポイントに焦点を当てましょう。

static int walCheckpoint(
  Wal *pWal,                      /* Wal connection */
  sqlite3 *db,                    /* Check for interrupts on this handle */
  int eMode,                      /* One of PASSIVE, FULL or RESTART */
  int (*xBusy)(void*),            /* Function to call when busy */
  void *pBusyArg,                 /* Context argument for xBusyHandler */
  int sync_flags,                 /* Flags for OsSync() (or 0) */
  u8 *zBuf                        /* Temporary buffer to use */
){
  int rc = SQLITE_OK;             /* Return code */
  int szPage;                     /* Database page-size */
  WalIterator *pIter = 0;         /* Wal iterator context */
  u32 iDbpage = 0;                /* Next database page to write */
  u32 iFrame = 0;                 /* Wal frame containing data for iDbpage */
  u32 mxSafeFrame;                /* Max frame that can be backfilled */
  u32 mxPage;                     /* Max database page to write */
  int i;                          /* Loop counter */
  volatile WalCkptInfo *pInfo;    /* The checkpoint status information */

  szPage = walPagesize(pWal);
  testcase( szPage<=32768 );
  testcase( szPage>=65536 );
  pInfo = walCkptInfo(pWal);
  if( pInfo->nBackfill<pWal->hdr.mxFrame ){

    /* EVIDENCE-OF: R-62920-47450 The busy-handler callback is never invoked
    ** in the SQLITE_CHECKPOINT_PASSIVE mode. */
    assert( eMode!=SQLITE_CHECKPOINT_PASSIVE || xBusy==0 );

    /* Compute in mxSafeFrame the index of the last frame of the WAL that is
    ** safe to write into the database.  Frames beyond mxSafeFrame might
    ** overwrite database pages that are in use by active readers and thus
    ** cannot be backfilled from the WAL.
    */
    mxSafeFrame = pWal->hdr.mxFrame;
    mxPage = pWal->hdr.nPage;
    for(i=1; i<WAL_NREADER; i++){
      u32 y = AtomicLoad(pInfo->aReadMark+i); SEH_INJECT_FAULT;
      if( mxSafeFrame>y ){
        assert( y<=pWal->hdr.mxFrame );
        rc = walBusyLock(pWal, xBusy, pBusyArg, WAL_READ_LOCK(i), 1);
        if( rc==SQLITE_OK ){
          u32 iMark = (i==1 ? mxSafeFrame : READMARK_NOT_USED);
          AtomicStore(pInfo->aReadMark+i, iMark); SEH_INJECT_FAULT;
          walUnlockExclusive(pWal, WAL_READ_LOCK(i), 1);
        }else if( rc==SQLITE_BUSY ){
          mxSafeFrame = y;
          xBusy = 0;
        }else{
          goto walcheckpoint_out;
        }
      }
    }

    /* Allocate the iterator */
    if( pInfo->nBackfill<mxSafeFrame ){
      rc = walIteratorInit(pWal, pInfo->nBackfill, &pIter);
      assert( rc==SQLITE_OK || pIter==0 );
    }

    if( pIter
     && (rc = walBusyLock(pWal,xBusy,pBusyArg,WAL_READ_LOCK(0),1))==SQLITE_OK
    ){
      u32 nBackfill = pInfo->nBackfill;
      pInfo->nBackfillAttempted = mxSafeFrame; SEH_INJECT_FAULT;

      /* Sync the WAL to disk */
      rc = sqlite3OsSync(pWal->pWalFd, CKPT_SYNC_FLAGS(sync_flags));

      /* If the database may grow as a result of this checkpoint, hint
      ** about the eventual size of the db file to the VFS layer.
      */
      if( rc==SQLITE_OK ){
        i64 nReq = ((i64)mxPage * szPage);
        i64 nSize;                    /* Current size of database file */
        sqlite3OsFileControl(pWal->pDbFd, SQLITE_FCNTL_CKPT_START, 0);
        rc = sqlite3OsFileSize(pWal->pDbFd, &nSize);
        if( rc==SQLITE_OK && nSize<nReq ){
          if( (nSize+65536+(i64)pWal->hdr.mxFrame*szPage)<nReq ){
            /* If the size of the final database is larger than the current
            ** database plus the amount of data in the wal file, plus the
            ** maximum size of the pending-byte page (65536 bytes), then
            ** must be corruption somewhere.  */
            rc = SQLITE_CORRUPT_BKPT;
          }else{
            sqlite3OsFileControlHint(pWal->pDbFd, SQLITE_FCNTL_SIZE_HINT,&nReq);
          }
        }

      }

      /* Iterate through the contents of the WAL, copying data to the db file */
      while( rc==SQLITE_OK && 0==walIteratorNext(pIter, &iDbpage, &iFrame) ){
        i64 iOffset;
        assert( walFramePgno(pWal, iFrame)==iDbpage );
        SEH_INJECT_FAULT;
        if( AtomicLoad(&db->u1.isInterrupted) ){
          rc = db->mallocFailed ? SQLITE_NOMEM_BKPT : SQLITE_INTERRUPT;
          break;
        }
        if( iFrame<=nBackfill || iFrame>mxSafeFrame || iDbpage>mxPage ){
          continue;
        }
        iOffset = walFrameOffset(iFrame, szPage) + WAL_FRAME_HDRSIZE;
        /* testcase( IS_BIG_INT(iOffset) ); // requires a 4GiB WAL file */
        rc = sqlite3OsRead(pWal->pWalFd, zBuf, szPage, iOffset);
        if( rc!=SQLITE_OK ) break;
        iOffset = (iDbpage-1)*(i64)szPage;
        testcase( IS_BIG_INT(iOffset) );
        rc = sqlite3OsWrite(pWal->pDbFd, zBuf, szPage, iOffset);
        if( rc!=SQLITE_OK ) break;
      }
      sqlite3OsFileControl(pWal->pDbFd, SQLITE_FCNTL_CKPT_DONE, 0);

      /* If work was actually accomplished... */
      if( rc==SQLITE_OK ){
        if( mxSafeFrame==walIndexHdr(pWal)->mxFrame ){
          i64 szDb = pWal->hdr.nPage*(i64)szPage;
          testcase( IS_BIG_INT(szDb) );
          rc = sqlite3OsTruncate(pWal->pDbFd, szDb);
          if( rc==SQLITE_OK ){
            rc = sqlite3OsSync(pWal->pDbFd, CKPT_SYNC_FLAGS(sync_flags));
          }
        }
        if( rc==SQLITE_OK ){
          AtomicStore(&pInfo->nBackfill, mxSafeFrame); SEH_INJECT_FAULT;
        }
      }

      /* Release the reader lock held while backfilling */
      walUnlockExclusive(pWal, WAL_READ_LOCK(0), 1);
    }

    if( rc==SQLITE_BUSY ){
      /* Reset the return code so as not to report a checkpoint failure
      ** just because there are active readers.  */
      rc = SQLITE_OK;
    }
  }

  /* If this is an SQLITE_CHECKPOINT_RESTART or TRUNCATE operation, and the
  ** entire wal file has been copied into the database file, then block
  ** until all readers have finished using the wal file. This ensures that
  ** the next process to write to the database restarts the wal file.
  */
  if( rc==SQLITE_OK && eMode!=SQLITE_CHECKPOINT_PASSIVE ){
    assert( pWal->writeLock );
    SEH_INJECT_FAULT;
    if( pInfo->nBackfill<pWal->hdr.mxFrame ){
      rc = SQLITE_BUSY;
    }else if( eMode>=SQLITE_CHECKPOINT_RESTART ){
      u32 salt1;
      sqlite3_randomness(4, &salt1);
      assert( pInfo->nBackfill==pWal->hdr.mxFrame );
      rc = walBusyLock(pWal, xBusy, pBusyArg, WAL_READ_LOCK(1), WAL_NREADER-1);
      if( rc==SQLITE_OK ){
        if( eMode==SQLITE_CHECKPOINT_TRUNCATE ){
          /* IMPLEMENTATION-OF: R-44699-57140 This mode works the same way as
          ** SQLITE_CHECKPOINT_RESTART with the addition that it also
          ** truncates the log file to zero bytes just prior to a
          ** successful return.
          **
          ** In theory, it might be safe to do this without updating the
          ** wal-index header in shared memory, as all subsequent reader or
          ** writer clients should see that the entire log file has been
          ** checkpointed and behave accordingly. This seems unsafe though,
          ** as it would leave the system in a state where the contents of
          ** the wal-index header do not match the contents of the
          ** file-system. To avoid this, update the wal-index header to
          ** indicate that the log file contains zero valid frames.  */
          walRestartHdr(pWal, salt1);
          rc = sqlite3OsTruncate(pWal->pWalFd, 0);
        }
        walUnlockExclusive(pWal, WAL_READ_LOCK(1), WAL_NREADER-1);
      }
    }
  }

 walcheckpoint_out:
  SEH_FREE_ON_ERROR(pIter, 0);
  walIteratorFree(pIter);
  return rc;
}

TLA+ では、共有メモリからの読み取りをモデル化するために、関数をいくつかの異なるアクションに分割する必要があります。これは、共有メモリへのポインタ pInfo が volatile であり、ロックを取得しなくても、例えば同時実行ライターによって変更される可能性があるためです。一方、pWal は WAL-index ヘッダーのコピーであり、実行開始後には変更されません。

* checkpoint variables:
* It is set using a copy of the wal-index header (pWal->hdr.mxFrame) when
* starting the checkpoint.
VARIABLE safeMxFrame
* It is set using a copy of the wal-index header (pWal->aSalt) when
* starting the checkpoint.
VARIABLE pWalSalt
* Running a checkpoint will move the state:
*    notStarted -> copiedHeader -> waitingForLock -> (finished) -> notStarted
* Note that only one checkpoint can happen at a time, which is why this is a
* global variable and that appends can happen concurrently with checkpoints,
* the exclusion zones correspond to our atomic actions.
VARIABLE checkPointState

CheckPointCopyHeader ≜
    ∧ checkPointState = "notStarted"
    ∧ safeMxFrame' = mxFrame
    ∧ pWalSalt' = walSalt
    ∧ checkPointState' = "copiedHeader"
    ∧ UNCHANGED ⟨ wal, nBackfill, db, mxFrame, frameNumber, walSalt, writeLock ⟩

StartCheckpoint ≜
    ∧ checkPointState = "copiedHeader"
    * Important: here backfill is read from the live header while safeMxFrame
    * is read from the stale copy of the header.
    ∧ IF nBackfill < safeMxFrame
       THEN checkPointState' = "waitingForLock"
       ELSE checkPointState' = "notStarted"
    ∧ UNCHANGED ⟨ wal, nBackfill, db, mxFrame, frameNumber, safeMxFrame, walSalt, pWalSalt, writeLock ⟩

Checkpoint ≜
    ∧ checkPointState = "waitingForLock"
    * Move pages from wal into db.
    ∧ db' = db ∪ { wal[j] : j ∈ nBackfill+1‥Len(wal) }
    ∧ nBackfill' = safeMxFrame
    * Reset the checkpoint state.
    ∧ safeMxFrame' = 0
    ∧ pWalSalt' = 0
    ∧ checkPointState' = "notStarted"
    ∧ UNCHANGED ⟨ mxFrame, wal, frameNumber, walSalt, writeLock ⟩

モデルが配置されたら、データ損失やデータベース破損が発生した場合にトリガーされる不変条件を定義できます。

* There are no "holes" in the database.
* All the frames that were added to the WAL have landed in order.
NoPageIsLost ≜ ∀ f ∈ 1‥Cardinality(db) : f ∈ db

モデルチェッカーを実行すると、すぐにカウンター例が見つかります。データベースにページが欠落していることを示すのにわずか20ステートしかかかりません。これは、ドキュメントに記載されているように、データベース破損につながる可能性があります。ステートのシーケンスは、SQLite 自身のバグ報告に含まれているものと非常によく似ています。これはモデルが検証されていることを示しています。SQLite のドキュメントのバグの説明に従って、それを分解してみましょう。

writeLock notTaken checkPointState notStarted mxFrame 0 safeMxFrame 0 pWalSalt 0 nBackfill 0 walSalt 0 pageNumber 1 wal [] db {} writeLock takenForAppend checkPointState notStarted mxFrame 0 safeMxFrame 0 pWalSalt 0 nBackfill 0 walSalt 0 pageNumber 1 wal [] db {} writeLock notTaken checkPointState notStarted mxFrame 1 safeMxFrame 0 pWalSalt 0 nBackfill 0 walSalt 0 pageNumber 2 wal [1] db {} writeLock takenForAppend checkPointState notStarted mxFrame 1 safeMxFrame 0 pWalSalt 0 nBackfill 0 walSalt 0 pageNumber 2 wal [1] db {} writeLock notTaken checkPointState notStarted mxFrame 2 safeMxFrame 0 pWalSalt 0 nBackfill 0 walSalt 0 pageNumber 3 wal [1, 2] db {} writeLock takenForAppend checkPointState notStarted mxFrame 2 safeMxFrame 0 pWalSalt 0 nBackfill 0 walSalt 0 pageNumber 3 wal [1, 2] db {} writeLock takenForAppend checkPointState copiedHeader mxFrame 2 safeMxFrame 2 pWalSalt 0 nBackfill 0 walSalt 0 pageNumber 3 wal [1, 2] db {} writeLock takenForAppend checkPointState waitingForLock mxFrame 2 safeMxFrame 2 pWalSalt 0 nBackfill 0 walSalt 0 pageNumber 3 wal [1, 2] db {} writeLock takenForAppend checkPointState notStarted mxFrame 2 safeMxFrame 0 pWalSalt 0 nBackfill 2 walSalt 0 pageNumber 3 wal [1, 2] db {1, 2} Wal Append Take Lock Wal Append Wal Append Take Lock Wal Append Wal Append Take Lock Checkpoint Copy Header Start Checkpoint Checkpoint writeLock takenForAppend checkPointState copiedHeader mxFrame 2 safeMxFrame 2 pWalSalt 0 nBackfill 2 walSalt 0 pageNumber 3 wal [1, 2] db {1, 2} writeLock notTaken checkPointState copiedHeader mxFrame 1 safeMxFrame 2 pWalSalt 0 nBackfill 0 walSalt 1 pageNumber 4 wal [3] db {1, 2} writeLock takenForAppend checkPointState copiedHeader mxFrame 1 safeMxFrame 2 pWalSalt 0 nBackfill 0 walSalt 1 pageNumber 4 wal [3] db {1, 2} Wal Append Take Lock writeLock takenForAppend checkPointState waitingForLock mxFrame 1 safeMxFrame 2 pWalSalt 0 nBackfill 0 walSalt 1 pageNumber 4 wal [3] db {1, 2} writeLock takenForAppend checkPointState notStarted mxFrame 1 safeMxFrame 0 pWalSalt 0 nBackfill 2 walSalt 1 pageNumber 4 wal [3] db {1, 2, 3} writeLock takenForAppend checkPointState copiedHeader mxFrame 1 safeMxFrame 1 pWalSalt 1 nBackfill 2 walSalt 1 pageNumber 4 wal [3] db {1, 2, 3} Checkpoint Checkpoint Copy Header writeLock notTaken checkPointState copiedHeader mxFrame 2 safeMxFrame 1 pWalSalt 1 nBackfill 2 walSalt 1 pageNumber 5 wal [3, 4] db {1, 2, 3} writeLock takenForAppend checkPointState copiedHeader mxFrame 2 safeMxFrame 1 pWalSalt 1 nBackfill 2 walSalt 1 pageNumber 5 wal [3, 4] db {1, 2, 3} writeLock notTaken checkPointState copiedHeader mxFrame 1 safeMxFrame 1 pWalSalt 1 nBackfill 0 walSalt 2 pageNumber 6 wal [5] db {1, 2, 3} Wal Append Take Lock Wal Append writeLock notTaken checkPointState waitingForLock mxFrame 1 safeMxFrame 1 pWalSalt 1 nBackfill 0 walSalt 2 pageNumber 6 wal [5] db {1, 2, 3} writeLock notTaken checkPointState notStarted mxFrame 1 safeMxFrame 0 pWalSalt 0 nBackfill 1 walSalt 2 pageNumber 6 wal [5] db {1, 2, 3, 5} Checkpoint Checkpoint Copy Header Wal Append Start Checkpoint Wal Append Start Checkpoint STEP 1: One connection does a checkpoint. This first checkpoint must be complete. In other words, the checkpoint must successfully copy all content from the WAL file back into the database and leave the WAL file in a state where it can potentially be reset. STEP 2: Shortly after the first checkpoint completes, a second checkpoint is started. STEP 3: While the second checkpoint from step 2 is starting up, another database connection commits a transaction that resets the WAL file and writes new content into the beginning of the WAL file. STEP 4: Due to a data race, the second checkpoint from step 2 does not realize that the WAL file has been reset by the transaction commit in step 3. The second checkpoint leaves a field in the header of the WAL-Index set incorrectly. That field indicates that part of the WAL file has already been checkpointed, when in fact it has not been. STEP 5: Additional transactions are committed to increase the number of pages in the WAL file to be more than were present for the first checkpoint from step 1. STEP 6: Later when a third checkpoint occurs, the third checkpoint skips all or part of the transaction that was written in step 3. Thus parts of the transaction from step 3 never reach the database file, and the database file goes corrupt.

そして、最も重要な質問…

## 5. dqlite は影響を受けるか?

この質問に適切に答えるために、SQLite 自体との違いを捉える dqlite のモデルを作成します。次に、不変条件が破れるかどうかを確認するために、再度モデルチェックを行います。

dqlite は Raft と書き込みを調整する必要があるため、どの操作が同時に進行できるかに関して、より制限が必要です。このため、dqlite はユーザーが開始したチェックポイントをすべてブロックし、自動チェックポイントを無効にします。さらに、チェックポイント中に読み取りと書き込みの両方が発生しないようにするために、SQLite が通常必要とするよりも多くのロックを取得します。実際には、dqlite におけるチェックポイントは「stop-the-world」アクションです。

VFS からチェックポイントをトリガーする dqlite コード

```c
static int vfsCheckpoint(sqlite3 *conn, struct vfsMainFile *f)
{
    PRE(f->sharedMask == 0);
    PRE(f->exclMask == 0);
    tracef("[database %p] checkpoint start", (void*)f->database);

    /* Try to lock everything, so that nothing can proceed. */
    int rv = vfsShmLock(&f->database->shm, 0, SQLITE_SHM_NLOCK, true);
    if (rv != SQLITE_OK) {
        tracef("[database %p] checkpoint busy", (void*)f->database);
        return rv;
    }
    f->exclMask = VFS__CHECKPOINT_MASK;

    PRE(f->database->wal.n_tx == 0);

    int wal_size;
    int ckpt;
    rv = sqlite3_wal_checkpoint_v2(conn, NULL, SQLITE_CHECKPOINT_TRUNCATE,
                       &wal_size, &ckpt);
    /* Since no reader transaction is in progress, we must be able to
     * checkpoint the entire WAL */
    dqlite_assert(rv == SQLITE_OK);
    dqlite_assert(wal_size == 0);
    dqlite_assert(ckpt == 0);
    tracef("[database %p] checkpointed", (void*)f->database);

    f->exclMask = 0;
    rv = vfsShmUnlock(&f->database->shm, 0, SQLITE_SHM_NLOCK, true);
    dqlite_assert(rv == SQLITE_OK);

    return SQLITE_OK;
}

上記からわかるように、モデルにとって唯一の違いは、書き込みロックがチェックポイントの開始前に取得されることだけです。TLA+ には、INSTANCE キーワードを使用して既存の仕様を拡張するための便利なメカニズムがあります。ベース仕様を、追加されたロックとともに使用します。

SQLITE ≜ INSTANCE sqlite

DqliteCheckpointTakeLock ≜
    ∧ writeLock = "notTaken"
    ∧ writeLock' = "takenForCheckpoint"
    ∧ UNCHANGED ⟨ wal, db, nBackfill, mxFrame, frameNumber, checkPointState, safeMxFrame, walSalt, pWalSalt ⟩

DqliteCheckpointReleaseLock ≜
    ∧ writeLock = "takenForCheckpoint"
    ∧ checkPointState = "notStarted"
    ∧ writeLock' = "notTaken"
    ∧ UNCHANGED ⟨ wal, db, nBackfill, mxFrame, frameNumber, checkPointState, safeMxFrame, walSalt, pWalSalt ⟩

* Overwrite the action in the original model by making sure the lock is taken.
DqliteCheckPointCopyHeader ≜
    ∧ writeLock = "takenForCheckpoint"
    ∧ SQLITE!CheckPointCopyHeader

* Add two new actions for taking and releasing the lock.
DqliteNext ≜
    ∨ DqliteCheckpointTakeLock
    ∨ DqliteCheckpointReleaseLock
    ∨ SQLITE!Next

以前に定義したのと同じ不変条件を再利用することで、仕様への変更がバグに影響するかどうかを確認できます。モデルチェックを行うと、dqlite はこのバグの影響をまったく受けないことがわかります!これは、追記とチェックポイントの両方で書き込みロックを取得するため、同時に進行できず、データ競合が発生しないためです。

6. ボーナス: SQLite ではバグはどのように修正されたか?

2026年3月5日、SQLite はバグを開示し、修正を公開しました。チェックポイントの開始以降に WAL のリセットが発生しなかったことを確認することで、データ競合を回避するのに十分な単一の追加チェックが必要です。

      WalIndexHdr *pLive = (WalIndexHdr*)walIndexHdr(pWal);

      /* Now that read-lock slot 0 is locked, check that the wal has not been
      ** wrapped since the header was read for this checkpoint. If it was, then
      ** there was no work to do anyway.  In this case the
      ** (pInfo->nBackfill<pWal->hdr.mxFrame) test above only passed because
      ** pInfo->nBackfill had already been set to 0 by the writer that wrapped
      ** the wal file. It would also be dangerous to proceed, as there may be
      ** fewer than pWal->hdr.mxFrame valid frames in the wal file.  */
      int bChg = memcmp(pLive->aSalt, pWal->hdr.aSalt, sizeof(pWal->hdr.aSalt));
      if( 0==bChg ){
          pInfo->nBackfillAttempted = mxSafeFrame; SEH_INJECT_FAULT
Checkpoint ≜
    ∧ checkPointState = waitingForLock"
    ∧ IF walSalt = pWalSalt
       THEN
        * Move pages from wal into db.
        ∧ db' = db ∪ { wal[j] : j ∈ nBackfill+1‥Len(wal) }
        ∧ nBackfill' = safeMxFrame
       ELSE
        * Salt changed, we skip the checkpoint.
        ∧ UNCHANGED ⟨ nBackfill, db ⟩
    * Reset the checkpoint state.
    ∧ safeMxFrame' = 0
    ∧ pWalSalt' = 0
    ∧ checkPointState' = notStarted"
    ∧ UNCHANGED ⟨ mxFrame, wal, pageNumber, walSalt, writeLock ⟩

同じ不変条件で TLA+ モデルのモデルチェッカーを実行すると、エラーは発生しなくなり、修正が確認されました。