Point-in-time recovery restores a checkpoint and replays the write-ahead log only as far as a requested log sequence number. Transactions that had not committed by that point must leave no effect.
Design a PointInTimeRecovery class:
PointInTimeRecovery() creates a stateless recovery helper.int[][] recover(int[][] checkpoint, int[][] records, int targetLsn) returns the recovered live key-value rows sorted by key.
Each checkpoint row is [key, value]. Each WAL record is:
Record types are:
0: begin1: put key = value2: delete key3: commit
Only transactions with a commit record whose LSN is at most targetLsn are winners. Replay winner puts and deletes at or before the target in increasing LSN order. Ignore every operation from a transaction that had not committed by the target.
Example 1:
Input:
Output:
Explanation: Transaction 1 commits by the target and updates key 1. Transaction 2 remains uncommitted, so key 2 is not restored.
Example 2:
Input:
Output:
Explanation: The committed transaction deletes key 1, inserts key 3, and leaves checkpoint key 2 unchanged.
Constraints
0 <= checkpoint.length, records.length <= 10^5- Checkpoint keys are unique.
- Every WAL row has exactly five integers.
- WAL records are sorted by strictly increasing positive LSN.
0 <= type <= 3, and each transaction has at most one commit record.- A transaction's begin and data records precede its commit.
- All keys, values, transaction IDs, and LSNs fit in signed 32-bit integers.
- At most
100 calls are made to recover.
Replay WAL to a Point in Timehard