segstore 0.2.0

Generic durable segmented store: write-ahead log, immutable segments, tombstones, checkpoint, and compaction
Documentation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155
1156
1157
1158
1159
1160
1161
1162
1163
1164
1165
1166
1167
1168
1169
1170
1171
1172
1173
1174
1175
1176
1177
1178
1179
1180
1181
1182
1183
1184
1185
1186
1187
1188
1189
1190
1191
1192
1193
1194
1195
1196
1197
1198
1199
1200
1201
1202
1203
1204
1205
1206
1207
1208
1209
1210
1211
1212
1213
1214
1215
1216
1217
1218
1219
1220
1221
1222
1223
1224
1225
1226
1227
1228
1229
1230
1231
1232
1233
1234
1235
1236
1237
1238
1239
1240
1241
1242
1243
1244
1245
1246
1247
1248
1249
1250
1251
1252
1253
1254
1255
1256
1257
1258
1259
1260
1261
1262
1263
1264
1265
1266
1267
1268
1269
1270
1271
1272
1273
1274
1275
1276
1277
1278
1279
1280
1281
1282
1283
1284
1285
1286
1287
1288
1289
1290
1291
1292
1293
1294
1295
1296
1297
1298
1299
1300
1301
1302
1303
1304
1305
1306
1307
1308
1309
1310
1311
1312
1313
1314
1315
1316
1317
1318
1319
1320
1321
1322
1323
1324
1325
1326
1327
1328
1329
1330
1331
1332
1333
1334
1335
1336
1337
1338
1339
1340
1341
1342
1343
1344
1345
1346
1347
1348
1349
1350
1351
1352
1353
1354
1355
1356
1357
1358
1359
1360
1361
1362
1363
1364
1365
1366
1367
1368
1369
1370
1371
1372
1373
1374
1375
1376
1377
1378
1379
1380
1381
1382
1383
1384
1385
1386
1387
1388
1389
1390
1391
1392
1393
1394
1395
1396
1397
1398
1399
1400
1401
1402
1403
1404
1405
1406
1407
1408
1409
1410
1411
1412
1413
1414
1415
1416
1417
1418
1419
1420
1421
1422
1423
1424
1425
1426
1427
1428
1429
1430
1431
1432
1433
1434
1435
1436
1437
1438
1439
1440
1441
1442
1443
1444
1445
1446
1447
1448
1449
1450
1451
1452
1453
1454
1455
1456
1457
1458
1459
1460
1461
1462
1463
1464
1465
1466
1467
1468
1469
1470
1471
1472
1473
1474
1475
1476
1477
1478
1479
1480
1481
1482
1483
1484
1485
1486
1487
1488
1489
1490
1491
1492
1493
1494
1495
1496
1497
1498
1499
1500
1501
1502
1503
1504
1505
1506
1507
1508
1509
1510
1511
1512
1513
1514
1515
1516
1517
1518
1519
1520
1521
1522
1523
1524
1525
1526
1527
1528
1529
1530
1531
1532
1533
1534
1535
1536
1537
1538
1539
1540
1541
1542
1543
1544
1545
1546
1547
1548
1549
1550
1551
1552
1553
1554
1555
1556
1557
1558
1559
1560
1561
1562
1563
1564
1565
1566
1567
1568
1569
1570
1571
1572
1573
1574
1575
1576
1577
1578
1579
1580
1581
1582
1583
1584
1585
1586
1587
1588
1589
1590
1591
1592
1593
1594
1595
1596
1597
1598
1599
1600
1601
1602
1603
1604
1605
1606
1607
1608
1609
1610
1611
1612
1613
1614
1615
1616
1617
1618
1619
1620
1621
1622
1623
1624
1625
1626
1627
1628
1629
1630
1631
1632
1633
1634
1635
1636
1637
1638
1639
1640
1641
1642
1643
1644
1645
1646
1647
1648
1649
1650
1651
1652
1653
1654
1655
1656
1657
1658
1659
1660
1661
1662
1663
1664
1665
1666
1667
1668
1669
1670
1671
1672
1673
1674
1675
1676
1677
1678
1679
1680
1681
1682
1683
1684
1685
1686
1687
1688
1689
1690
1691
1692
1693
1694
1695
1696
1697
1698
1699
1700
1701
1702
1703
1704
1705
1706
1707
1708
1709
1710
1711
1712
1713
1714
1715
1716
1717
1718
1719
1720
1721
1722
1723
1724
1725
1726
1727
1728
1729
1730
1731
1732
1733
1734
1735
1736
1737
1738
1739
1740
1741
1742
1743
1744
1745
1746
1747
1748
1749
1750
1751
1752
1753
1754
1755
1756
1757
1758
1759
1760
1761
1762
1763
1764
1765
1766
1767
1768
1769
1770
1771
1772
1773
1774
1775
1776
1777
1778
1779
1780
1781
1782
1783
1784
1785
1786
1787
1788
1789
1790
1791
1792
1793
1794
1795
1796
1797
1798
1799
1800
1801
1802
1803
1804
1805
1806
1807
1808
1809
1810
1811
1812
1813
1814
1815
1816
1817
1818
1819
1820
1821
1822
1823
1824
1825
1826
1827
1828
1829
1830
1831
1832
1833
1834
1835
1836
1837
1838
1839
1840
1841
1842
1843
1844
1845
1846
1847
1848
1849
1850
1851
1852
1853
1854
1855
1856
1857
1858
1859
1860
1861
1862
1863
1864
1865
1866
1867
1868
1869
1870
1871
1872
1873
1874
1875
1876
1877
1878
1879
1880
1881
1882
1883
1884
1885
1886
1887
1888
1889
1890
1891
1892
1893
1894
1895
1896
1897
1898
1899
1900
1901
1902
1903
1904
1905
1906
1907
1908
1909
1910
1911
1912
1913
1914
1915
1916
1917
1918
1919
1920
1921
1922
1923
1924
1925
1926
1927
1928
1929
1930
1931
1932
1933
1934
1935
1936
1937
1938
1939
1940
1941
1942
1943
1944
1945
1946
1947
1948
1949
1950
1951
1952
1953
1954
1955
1956
1957
1958
1959
1960
1961
1962
1963
1964
1965
1966
1967
1968
1969
1970
1971
1972
1973
1974
1975
1976
1977
1978
1979
1980
1981
1982
1983
1984
1985
1986
1987
1988
1989
1990
1991
1992
1993
1994
1995
1996
1997
1998
1999
2000
2001
2002
2003
2004
2005
2006
2007
2008
2009
2010
2011
2012
2013
2014
2015
2016
2017
2018
2019
2020
2021
2022
2023
2024
2025
2026
2027
2028
2029
2030
2031
2032
2033
2034
2035
2036
2037
2038
2039
2040
2041
2042
2043
2044
2045
2046
2047
2048
2049
2050
2051
2052
2053
2054
2055
2056
2057
2058
2059
2060
2061
2062
2063
2064
2065
2066
2067
2068
2069
2070
2071
2072
2073
2074
2075
2076
2077
2078
2079
2080
2081
2082
2083
2084
2085
2086
2087
2088
2089
2090
2091
2092
2093
2094
2095
2096
2097
2098
2099
2100
2101
2102
2103
2104
2105
2106
2107
2108
2109
2110
2111
2112
2113
2114
2115
2116
2117
2118
2119
2120
2121
2122
2123
2124
2125
2126
2127
2128
2129
2130
2131
2132
2133
2134
2135
2136
2137
2138
2139
2140
2141
2142
2143
2144
2145
2146
2147
2148
2149
2150
2151
2152
2153
2154
2155
2156
2157
2158
2159
2160
2161
2162
2163
2164
2165
2166
2167
2168
2169
2170
2171
2172
2173
2174
2175
2176
2177
2178
2179
2180
2181
2182
2183
2184
2185
2186
2187
2188
2189
2190
2191
2192
2193
2194
2195
2196
2197
2198
2199
2200
2201
2202
2203
2204
2205
2206
2207
2208
2209
2210
2211
2212
2213
2214
2215
2216
2217
2218
2219
2220
2221
2222
2223
2224
2225
2226
2227
2228
2229
2230
2231
2232
2233
2234
2235
2236
2237
2238
2239
2240
2241
2242
2243
2244
2245
2246
2247
2248
2249
2250
2251
2252
2253
2254
2255
2256
2257
2258
2259
2260
2261
2262
2263
2264
2265
2266
2267
2268
2269
2270
2271
2272
2273
2274
2275
2276
2277
2278
2279
2280
2281
2282
2283
2284
2285
2286
2287
2288
2289
2290
2291
2292
2293
2294
2295
2296
2297
2298
2299
2300
2301
2302
2303
2304
2305
2306
2307
2308
2309
2310
2311
2312
2313
2314
2315
2316
2317
2318
2319
2320
2321
2322
2323
2324
2325
2326
2327
2328
2329
2330
2331
2332
2333
2334
2335
2336
2337
2338
2339
2340
2341
2342
2343
2344
2345
2346
2347
2348
2349
2350
2351
2352
2353
2354
2355
2356
2357
2358
2359
2360
2361
2362
2363
2364
//! Generic durable segmented store.
//!
//! `segstore` provides the LSM-style lifecycle shared by updatable indexes,
//! immutable segments plus tombstone deletes plus a write-ahead log plus
//! checkpoint and compaction, on top of [`durability`]. It is generic over the
//! segment payload: a consumer implements [`Store`] to say how a batch of items
//! becomes a segment and how segments merge during compaction, and `segstore`
//! owns the durability and the orchestration.
//!
//! The split mirrors the rest of the retrieval stack: a storage substrate
//! (`postings`, a graph index) keeps its own representation while delegating the
//! mutable-and-persistent machinery here, the same way it already delegates the
//! raw WAL/checkpoint primitives to [`durability`].
//!
//! # What it owns vs what the consumer owns
//!
//! - `segstore` owns: the append-only WAL of operations, the in-memory buffer of
//!   not-yet-flushed adds, the ordered list of immutable segments, the tombstone
//!   set, checkpoint snapshots, and crash recovery (replay the WAL past the last
//!   checkpoint).
//! - The consumer owns: the segment representation (an opaque `Serialize` type),
//!   how a batch of live items becomes one segment ([`Store::build_segment`]),
//!   how segments merge while dropping tombstoned ids ([`Store::merge_segments`]),
//!   and querying (iterate [`SegmentedStore::segments`] + [`SegmentedStore::buffer`],
//!   filtering with [`SegmentedStore::is_live`]).
//!
//! # Example
//!
//! ```
//! use segstore::{SegmentedStore, Store};
//! use durability::MemoryDirectory;
//!
//! // A trivial key-value store: a segment is just a batch of (id, item) pairs.
//! struct Kv;
//! impl Store for Kv {
//!     type Id = u32;
//!     type Item = String;
//!     type Segment = Vec<(u32, String)>;
//!     fn build_segment(&self, batch: &[(u32, String)]) -> Vec<(u32, String)> {
//!         batch.to_vec()
//!     }
//!     fn merge_segments(
//!         &self,
//!         segs: &[Vec<(u32, String)>],
//!         live: &dyn Fn(&u32) -> bool,
//!     ) -> Vec<(u32, String)> {
//!         segs.iter().flatten().filter(|(id, _)| live(id)).cloned().collect()
//!     }
//!     fn segment_len(&self, seg: &Vec<(u32, String)>) -> usize { seg.len() }
//! }
//!
//! let dir = MemoryDirectory::arc();
//! let mut s = SegmentedStore::open(dir, Kv, 2).unwrap();
//! s.add(1, "a".into()).unwrap();
//! s.add(2, "b".into()).unwrap();
//! s.delete(2).unwrap();
//! assert!(s.is_live(&1) && !s.is_live(&2));
//! ```
//!
//! # Durability
//!
//! The WAL is rotated by epoch: a checkpoint snapshots the segments + tombstones
//! durably, then a fresh WAL generation (`segstore.wal.<epoch>`) is started and
//! the old one deleted, so the log never grows past one checkpoint interval. The
//! checkpoint records the epoch it covers; recovery replays only that epoch's
//! WAL, so a stale WAL left by a crash mid-rotation is simply never read (no
//! duplicates, no loss). Checkpoints publish atomically (via
//! `Directory::atomic_write`, CRC-checked), and on a filesystem backend also
//! pass a power-loss barrier (fsync of the file and parent dir).
//!
//! [`SyncPolicy`] chooses the WAL write durability: the default [`SyncPolicy::Flush`]
//! is a visibility boundary (userspace -> OS), while [`SyncPolicy::Fsync`] syncs
//! every record to stable storage (filesystem backend only).
//!
//! Recovery is *point-in-time*: the WAL is read best-effort, so a torn final record
//! (the expected damage from a crash mid-write) is truncated and the consistent
//! prefix recovered. This is the same default as RocksDB's `kPointInTimeRecovery`.
//! It does NOT detect corruption *beyond* the torn tail (a bit-flip of an
//! already-committed interior record): each record is CRC-checked, so such a record
//! is never decoded as garbage, but best-effort read stops at it and drops the rest.
//! Media-rot detection (a strict "fail on any corruption" mode) is out of scope for
//! this crash-consistency WAL; a consumer needing it should use checksummed storage.
//!
//! On-disk format note: segstore 0.2 changed the WAL layout (epoch-suffixed
//! files, with the epoch recorded in the checkpoint) from 0.1's single
//! unsuffixed `segstore.wal`. A 0.1 store is detected and rejected with a clear
//! error rather than misread.

use std::cmp::Ordering;
use std::collections::HashSet;
use std::hash::Hash;
use std::sync::Arc;

use durability::checkpoint::CheckpointFile;
use durability::recordlog::{RecordLogReadMode, RecordLogReader, RecordLogWriter};
use durability::{Directory, PersistenceError, PersistenceResult};
use serde::{de::DeserializeOwned, Deserialize, Serialize};

/// Prefix for epoch-suffixed WAL files (`segstore.wal.<epoch>`).
const WAL_PREFIX: &str = "segstore.wal.";
/// The single unsuffixed WAL of the 0.1 on-disk format; its presence flags a
/// store written by segstore 0.1, which 0.2 cannot read.
const LEGACY_WAL_PATH: &str = "segstore.wal";
const CKPT_PATH: &str = "segstore.ckpt";

/// The WAL file path for a given epoch.
fn wal_path(epoch: u64) -> String {
    format!("{WAL_PREFIX}{epoch}")
}

/// How durable each WAL write is before [`SegmentedStore::add`] / [`SegmentedStore::delete`]
/// returns.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum SyncPolicy {
    /// Flush each record to the underlying writer (userspace -> OS). The default;
    /// works on every [`Directory`] backend.
    Flush,
    /// fsync each record to stable storage. Stronger (survives power loss) and
    /// slower; requires a filesystem-backed [`Directory`] (one that provides
    /// `file_path()`), else [`SegmentedStore::open_with_options`] errors.
    Fsync,
}

/// Size-tiered compaction tuning. Defaults follow Cassandra's SizeTieredCompactionStrategy
/// (`min_threshold = 4`, `max_threshold = 32`, bucket band `0.5x .. 1.5x`) and Lucene's
/// `TieredMergePolicy` (a max merged-segment cap, above half of which a segment is frozen
/// out of further tier merges).
///
/// The size metric is item count ([`Store::segment_len`]); these are item counts, not
/// bytes. Because a query scans every segment, the per-tier segment count is paid on every
/// read, so `min_merge` is kept small.
#[derive(Debug, Clone, Copy)]
pub struct TierConfig {
    /// Minimum segments in a size bucket before it is eligible to merge (Cassandra
    /// `min_threshold`). 2 degenerates tiering into leveling, so 4 is the practical floor.
    pub min_merge: usize,
    /// Maximum segments merged in one job (Cassandra `max_threshold`), bounding per-merge
    /// cost and pause.
    pub max_merge: usize,
    /// Lower size-band multiplier for bucket membership (Cassandra `bucket_low`).
    pub bucket_low: f64,
    /// Upper size-band multiplier for bucket membership (Cassandra `bucket_high`).
    pub bucket_high: f64,
    /// Cap on a merged segment's item count. A segment larger than half of this is frozen
    /// out of tier merges (Lucene's rule), so the largest segment is never rewritten by
    /// tiering, only by a full [`SegmentedStore::compact`]. Without this, top-tier merges
    /// rewrite the whole dataset (O(N^2) write amplification).
    pub max_merged_len: usize,
}

impl Default for TierConfig {
    fn default() -> Self {
        Self {
            min_merge: 4,
            max_merge: 32,
            bucket_low: 0.5,
            bucket_high: 1.5,
            max_merged_len: 10_000_000,
        }
    }
}

/// What a compaction did, for the consumer to track merge cost vs corpus size (the signal
/// that a multi-segment store is outgrowing the search-all-segments model).
#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
pub struct CompactionStats {
    /// Number of merge operations performed.
    pub merges: usize,
    /// Segment count before the compaction.
    pub segments_before: usize,
    /// Segment count after the compaction.
    pub segments_after: usize,
    /// Total items written into the merged output segment(s).
    pub items_merged: usize,
}

/// Options for opening a [`SegmentedStore`].
#[derive(Debug, Clone, Copy)]
pub struct Options {
    /// Buffered-add count that seals a new segment.
    pub flush_threshold: usize,
    /// Per-write WAL durability.
    pub sync: SyncPolicy,
    /// Size-tiered compaction tuning (used by [`SegmentedStore::compact_tiers`]).
    pub tiering: TierConfig,
    /// When true, [`SegmentedStore::add`] runs `compact_tiers` after sealing a segment if a
    /// bucket is eligible, on the calling thread. Default false: the consumer drives
    /// `compact_tiers` when convenient (e.g. on a background thread), so the merge latency
    /// never lands on the ingest hot path.
    pub auto_compact: bool,
}

impl Options {
    /// Options with the given flush threshold and defaults for the rest (`Flush` sync,
    /// default tiering, no auto-compaction).
    pub fn new(flush_threshold: usize) -> Self {
        Self {
            flush_threshold,
            sync: SyncPolicy::Flush,
            tiering: TierConfig::default(),
            auto_compact: false,
        }
    }
}

/// The consumer-defined payload model: how items batch into a segment and how
/// segments merge during compaction.
///
/// `segstore` never inspects a segment's contents; it only stores, snapshots,
/// and hands segments back to these two methods, so the representation is
/// entirely the consumer's (posting lists, a graph delta, a vector block, ...).
pub trait Store {
    /// Stable identity of an item, used for tombstones and WAL replay.
    type Id: Clone + Eq + Hash + Serialize + DeserializeOwned;
    /// The per-item payload carried in the WAL until it is flushed to a segment.
    type Item: Clone + Serialize + DeserializeOwned;
    /// An immutable batch of items. Opaque to `segstore`.
    type Segment: Clone + Serialize + DeserializeOwned;

    /// Build one immutable segment from a batch of live `(id, item)` pairs.
    fn build_segment(&self, batch: &[(Self::Id, Self::Item)]) -> Self::Segment;

    /// Merge `segments` into one during compaction, keeping only ids for which
    /// `live(id)` is true (i.e. dropping tombstoned ids).
    fn merge_segments(
        &self,
        segments: &[Self::Segment],
        live: &dyn Fn(&Self::Id) -> bool,
    ) -> Self::Segment;

    /// The number of items in `segment`. This is the size metric size-tiered
    /// compaction groups segments by, so a count of *live* items (after any
    /// tombstone drop a merge applied) is the right answer. For the common
    /// `Vec`-backed segment this is just `segment.len()`.
    fn segment_len(&self, segment: &Self::Segment) -> usize;

    /// The number of items in `segment` for which `live` is true (i.e. excluding
    /// tombstoned ids), if the consumer can compute it cheaply. Returning `Some`
    /// enables space-amplification reporting ([`SegmentedStore::space_amplification`])
    /// and tombstone-reclaiming compaction ([`SegmentedStore::reclaim_tombstones`]).
    /// The default `None` disables both; the size-tiered path does not need it.
    /// For a `Vec`-backed segment: `Some(segment.iter().filter(|(id, _)| live(id)).count())`.
    fn live_len(
        &self,
        _segment: &Self::Segment,
        _live: &dyn Fn(&Self::Id) -> bool,
    ) -> Option<usize> {
        None
    }
}

/// One write-ahead-log operation.
#[derive(Serialize, Deserialize)]
enum Op<Id, Item> {
    Add(Id, Item),
    Delete(Id),
}

/// The persisted checkpoint snapshot (segments + tombstones; the buffer is
/// always flushed before a checkpoint, so it is never part of the snapshot).
#[derive(Serialize, Deserialize)]
struct Snapshot<Id, Seg> {
    segments: Vec<Seg>,
    tombstones: Vec<Id>,
}

/// The reader-visible published state: the segments and tombstones as of the last
/// mutation, behind `Arc`s so a [`View`] is a cheap, consistent snapshot.
struct PubState<S: Store> {
    segments: Arc<Vec<Arc<S::Segment>>>,
    tombstones: Arc<HashSet<S::Id>>,
}

/// A consistent, point-in-time read view of the store, independent of the writer.
///
/// A [`Reader`] hands these out; holding one keeps its segments alive for the whole
/// query even as the writer adds, deletes, or compacts concurrently (single-writer,
/// many-readers, like Lucene's `SearcherManager` / Tantivy's `Searcher`). Visibility
/// is *commit-style*: a view reflects the state as of the last [`SegmentedStore::checkpoint`]
/// (which compaction also performs), so adds and deletes since then become visible
/// after the next checkpoint. Publishing only at the checkpoint keeps it off the
/// ingest hot path (republishing per write made bulk ingest quadratic).
pub struct View<S: Store> {
    segments: Arc<Vec<Arc<S::Segment>>>,
    tombstones: Arc<HashSet<S::Id>>,
}

impl<S: Store> View<S> {
    /// The snapshot's immutable segments, oldest first. Query these (each derefs to
    /// `S::Segment`), filtering with [`Self::is_live`].
    pub fn segments(&self) -> &[Arc<S::Segment>] {
        &self.segments
    }

    /// Whether `id` is not tombstoned in this snapshot.
    pub fn is_live(&self, id: &S::Id) -> bool {
        !self.tombstones.contains(id)
    }

    /// Number of segments in this snapshot.
    pub fn segment_count(&self) -> usize {
        self.segments.len()
    }
}

/// A cloneable, thread-safe handle for concurrent snapshot reads while the writer
/// mutates. Obtain via [`SegmentedStore::reader`]; clone freely across threads.
pub struct Reader<S: Store> {
    published: Arc<std::sync::RwLock<Arc<PubState<S>>>>,
}

impl<S: Store> Clone for Reader<S> {
    fn clone(&self) -> Self {
        Reader {
            published: self.published.clone(),
        }
    }
}

impl<S: Store> Reader<S> {
    /// Take a consistent [`View`] of the store as of the last published mutation.
    /// Cheap (a couple of `Arc` clones under a brief read lock); the view is then
    /// held lock-free for the query's duration.
    pub fn view(&self) -> View<S> {
        let state = self.published.read().unwrap().clone();
        View {
            segments: state.segments.clone(),
            tombstones: state.tombstones.clone(),
        }
    }
}

/// A generic, durable, segmented mutable store.
pub struct SegmentedStore<S: Store> {
    store: S,
    dir: Arc<dyn Directory>,
    /// Live adds not yet flushed into a segment.
    buffer: Vec<(S::Id, S::Item)>,
    /// Immutable segments, oldest first.
    segments: Vec<Arc<S::Segment>>,
    /// Logically-deleted ids.
    tombstones: HashSet<S::Id>,
    /// Published snapshot for concurrent readers (rebuilt on each mutation).
    published: Arc<std::sync::RwLock<Arc<PubState<S>>>>,
    wal: RecordLogWriter,
    /// Current WAL generation; the live WAL is `segstore.wal.<epoch>` and the
    /// checkpoint records the epoch it covers.
    epoch: u64,
    /// Per-write WAL durability.
    sync: SyncPolicy,
    /// Buffer size that triggers a flush into a new segment.
    flush_threshold: usize,
    /// Size-tiered compaction tuning.
    tiering: TierConfig,
    /// Whether `add` auto-runs `compact_tiers` when a bucket is eligible.
    auto_compact: bool,
}

impl<S: Store> SegmentedStore<S> {
    /// Open (or create) a store backed by `dir`, recovering any prior state from
    /// the checkpoint plus the write-ahead log.
    ///
    /// `flush_threshold` is the buffered-add count that triggers a new segment.
    pub fn open(
        dir: Arc<dyn Directory>,
        store: S,
        flush_threshold: usize,
    ) -> PersistenceResult<Self> {
        Self::open_with_options(dir, store, Options::new(flush_threshold))
    }

    /// Like [`Self::open`], but with full [`Options`] (per-write durability,
    /// size-tiered compaction tuning, auto-compaction).
    ///
    /// [`SyncPolicy::Fsync`] requires a filesystem-backed `Directory`; opening
    /// with it on a backend that lacks `file_path()` (e.g. an in-memory
    /// directory) returns an error rather than silently degrading to a flush.
    pub fn open_with_options(
        dir: Arc<dyn Directory>,
        store: S,
        opts: Options,
    ) -> PersistenceResult<Self> {
        let Options {
            flush_threshold,
            sync,
            tiering,
            auto_compact,
        } = opts;
        if sync == SyncPolicy::Fsync && dir.file_path(CKPT_PATH).is_none() {
            return Err(PersistenceError::InvalidConfig(
                "SyncPolicy::Fsync requires a filesystem-backed Directory".into(),
            ));
        }
        // A 0.1 store wrote a single unsuffixed WAL; 0.2 changed the format.
        // Reject it explicitly rather than misread its ops as an epoch.
        if dir.exists(LEGACY_WAL_PATH) {
            return Err(PersistenceError::InvalidConfig(
                "segstore 0.1 on-disk store detected (unsuffixed segstore.wal); the 0.2 \
                 on-disk format is epoch-suffixed and cannot read it"
                    .into(),
            ));
        }

        // Load the checkpoint snapshot if one exists. The checkpoint records the
        // WAL epoch it covers; recovery replays only that epoch's WAL.
        let mut segments: Vec<Arc<S::Segment>> = Vec::new();
        let mut tombstones: HashSet<S::Id> = HashSet::new();
        let mut epoch = 0u64;
        if dir.exists(CKPT_PATH) {
            let ckpt = CheckpointFile::new(dir.clone());
            let (e, snap): (u64, Snapshot<S::Id, S::Segment>) = ckpt.read_postcard(CKPT_PATH)?;
            epoch = e;
            segments = snap.segments.into_iter().map(Arc::new).collect();
            tombstones = snap.tombstones.into_iter().collect();
        }

        // Replay the current epoch's WAL in full. It holds exactly the ops since
        // the checkpoint, so every record is applied (no skip offset).
        let mut buffer: Vec<(S::Id, S::Item)> = Vec::new();
        let live_wal = wal_path(epoch);
        if dir.exists(&live_wal) {
            let reader = RecordLogReader::new(dir.clone(), live_wal.clone());
            let ops: Vec<Op<S::Id, S::Item>> =
                reader.read_all_postcard(RecordLogReadMode::BestEffort)?;
            for op in ops {
                apply(&mut buffer, &mut tombstones, op);
            }
        }

        // Best-effort GC of stale WAL generations a crash may have left behind
        // (any `segstore.wal.<k>` with k != epoch is superseded by the checkpoint).
        if let Ok(names) = dir.list_dir("") {
            for name in names {
                if let Some(k) = name
                    .strip_prefix(WAL_PREFIX)
                    .and_then(|s| s.parse::<u64>().ok())
                {
                    if k != epoch {
                        let _ = dir.delete(&name);
                    }
                }
            }
        }

        let wal = RecordLogWriter::new(dir.clone(), live_wal);
        let published = Arc::new(std::sync::RwLock::new(Arc::new(PubState {
            segments: Arc::new(segments.clone()),
            tombstones: Arc::new(tombstones.clone()),
        })));
        Ok(Self {
            store,
            dir,
            buffer,
            segments,
            tombstones,
            wal,
            epoch,
            sync,
            flush_threshold,
            tiering,
            auto_compact,
            published,
        })
    }

    /// A cloneable handle for concurrent snapshot reads while this writer mutates.
    /// Clone it across threads; each [`Reader::view`] is a consistent snapshot.
    pub fn reader(&self) -> Reader<S> {
        Reader {
            published: self.published.clone(),
        }
    }

    /// Rebuild the published snapshot from the current segments + tombstones. Called
    /// only at the checkpoint (commit point). Segments are held as `Arc`, so this
    /// shares them by refcount (no data clone) and an *unchanged* segment keeps its
    /// `Arc` identity across checkpoints -- which lets a consumer cache per-segment
    /// state (a built index) keyed by that identity and rebuild only new segments.
    fn republish(&self) {
        let state = Arc::new(PubState {
            segments: Arc::new(self.segments.clone()),
            tombstones: Arc::new(self.tombstones.clone()),
        });
        *self.published.write().unwrap() = state;
    }

    /// Add (or re-add) an item. Durably logged before it becomes visible.
    pub fn add(&mut self, id: S::Id, item: S::Item) -> PersistenceResult<()> {
        self.wal
            .append_postcard(&Op::Add(id.clone(), item.clone()))?;
        self.sync_wal()?;
        apply(&mut self.buffer, &mut self.tombstones, Op::Add(id, item));
        if self.buffer.len() >= self.flush_threshold {
            self.flush_buffer();
            if self.auto_compact && self.has_eligible_tier() {
                self.compact_tiers()?;
            }
        }
        Ok(())
    }

    /// Add (or re-add) many items, syncing the WAL once for the whole batch
    /// instead of per item. This is the bulk-ingest path (the build phase of an
    /// index, e.g. lexir/sporse loading a corpus): per-item flush is the dominant
    /// cost there, and one sync per batch is several times faster on a real disk.
    ///
    /// The durability boundary is the batch's final sync, so a crash mid-batch may
    /// leave a *prefix* of the batch durable (each item is an independently
    /// CRC-checked WAL record); recovery yields a consistent prefix, never a
    /// half-written item. Auto-compaction (if enabled) still runs when a segment
    /// seals during the batch.
    pub fn extend(
        &mut self,
        items: impl IntoIterator<Item = (S::Id, S::Item)>,
    ) -> PersistenceResult<()> {
        let mut any = false;
        for (id, item) in items {
            self.wal
                .append_postcard(&Op::Add(id.clone(), item.clone()))?;
            apply(&mut self.buffer, &mut self.tombstones, Op::Add(id, item));
            any = true;
            if self.buffer.len() >= self.flush_threshold {
                self.flush_buffer();
                if self.auto_compact && self.has_eligible_tier() {
                    self.sync_wal()?; // make the sealed batch durable before a merge rewrites it
                    self.compact_tiers()?;
                }
            }
        }
        if any {
            self.sync_wal()?;
        }
        Ok(())
    }

    /// Tombstone an item. Durably logged before it takes effect.
    pub fn delete(&mut self, id: S::Id) -> PersistenceResult<()> {
        self.wal
            .append_postcard::<Op<S::Id, S::Item>>(&Op::Delete(id.clone()))?;
        self.sync_wal()?;
        apply(&mut self.buffer, &mut self.tombstones, Op::Delete(id));
        Ok(())
    }

    /// Make the just-appended WAL record durable per the [`SyncPolicy`].
    fn sync_wal(&mut self) -> PersistenceResult<()> {
        match self.sync {
            SyncPolicy::Flush => self.wal.flush(),
            SyncPolicy::Fsync => self.wal.flush_and_sync(),
        }
    }

    /// Drain the buffer into a fresh immutable segment (no-op when empty).
    fn flush_buffer(&mut self) {
        if self.buffer.is_empty() {
            return;
        }
        let seg = self.store.build_segment(&self.buffer);
        self.segments.push(Arc::new(seg));
        self.buffer.clear();
    }

    /// Merge ALL segments into one, dropping tombstoned ids and purging the
    /// tombstone set, then checkpoint. This is the full compaction; it is the only
    /// path that touches frozen (over-cap) segments and the only one that purges
    /// tombstones (a partial tier merge cannot, since a tombstoned id may live in a
    /// segment it did not merge).
    pub fn compact(&mut self) -> PersistenceResult<CompactionStats> {
        self.flush_buffer();
        let before = self.segments.len();
        let mut stats = CompactionStats {
            segments_before: before,
            ..Default::default()
        };
        // Nothing to do for 0/1 segments with no tombstones to purge.
        if before > 1 || (before == 1 && !self.tombstones.is_empty()) {
            let tombstones = std::mem::take(&mut self.tombstones);
            let owned: Vec<S::Segment> = self.segments.iter().map(|a| (**a).clone()).collect();
            let merged = self
                .store
                .merge_segments(&owned, &|id| !tombstones.contains(id));
            stats.merges = 1;
            stats.items_merged = self.store.segment_len(&merged);
            // Drop a fully-tombstoned merge result rather than keep an empty segment.
            self.segments = if stats.items_merged > 0 {
                vec![Arc::new(merged)]
            } else {
                vec![]
            };
        }
        // After a full compaction no segment references a tombstoned id, so the set
        // is purged even if there was nothing to merge (stale tombstones for ids that
        // were only ever buffered).
        self.tombstones.clear();
        self.checkpoint()?;
        stats.segments_after = self.segments.len();
        Ok(stats)
    }

    /// Run all currently-eligible size-tier merges (size-tiered compaction) per the
    /// [`TierConfig`], persisting the result if anything merged. Segments are grouped
    /// into size buckets (a Cassandra-style `bucket_low .. bucket_high` band around a
    /// running average, with a [`Options::flush_threshold`] floor); a bucket with at
    /// least `min_merge` segments is merged (smallest first, up to `max_merge` at once,
    /// never exceeding `max_merged_len` items), dropping tombstoned ids from the merged
    /// output. Segments above `max_merged_len / 2` are frozen out, so the largest segment
    /// is never rewritten here. The global tombstone set is NOT purged (only [`Self::compact`]
    /// can); a tombstoned id surviving in a frozen segment stays filtered by [`Self::is_live`].
    ///
    /// Scheduling is the consumer's: call this when convenient (e.g. on a background
    /// thread) so merge latency stays off the ingest path, or set [`Options::auto_compact`].
    pub fn compact_tiers(&mut self) -> PersistenceResult<CompactionStats> {
        self.flush_buffer();
        let mut stats = CompactionStats {
            segments_before: self.segments.len(),
            ..Default::default()
        };
        while let Some(group) = self.next_merge_group() {
            stats.items_merged += self.merge_group(group);
            stats.merges += 1;
        }
        if stats.merges > 0 {
            self.checkpoint()?;
        }
        stats.segments_after = self.segments.len();
        Ok(stats)
    }

    /// Consolidate on demand: merge segments until at most `max_segments` remain,
    /// ignoring the size band, the per-bucket minimum, and the [`TierConfig`] cap
    /// (this is explicit user intent, e.g. before a read-heavy phase, so it may
    /// produce a segment larger than `max_merged_len`). Merging to a single segment
    /// (`max_segments <= 1`) also purges the tombstone set, exactly like
    /// [`Self::compact`]; merging to more keeps the set (an id may live in a segment
    /// the call did not merge). Smallest segments are merged first to keep the work
    /// down. A no-op when already at or below `max_segments`.
    pub fn force_merge_to(&mut self, max_segments: usize) -> PersistenceResult<CompactionStats> {
        if max_segments <= 1 {
            return self.compact();
        }
        self.flush_buffer();
        let mut stats = CompactionStats {
            segments_before: self.segments.len(),
            ..Default::default()
        };
        while self.segments.len() > max_segments {
            let mut idx: Vec<usize> = (0..self.segments.len()).collect();
            idx.sort_by_key(|&i| self.store.segment_len(&self.segments[i]));
            // Merging k segments drops the count by k-1; to remove `over` segments we
            // merge `over + 1`, bounded by max_merge and what's available.
            let over = self.segments.len() - max_segments;
            let k = (over + 1)
                .min(self.tiering.max_merge.max(2))
                .min(self.segments.len());
            let group: Vec<usize> = idx.into_iter().take(k).collect();
            stats.items_merged += self.merge_group(group);
            stats.merges += 1;
        }
        if stats.merges > 0 {
            self.checkpoint()?;
        }
        stats.segments_after = self.segments.len();
        Ok(stats)
    }

    /// Merge the segments at `indices` into one (dropping tombstoned ids), replacing
    /// them in place with the single result. Returns the merged item count.
    fn merge_group(&mut self, indices: Vec<usize>) -> usize {
        let segs: Vec<S::Segment> = indices
            .iter()
            .map(|&i| (*self.segments[i]).clone())
            .collect();
        let merged = {
            let tombstones = &self.tombstones;
            self.store
                .merge_segments(&segs, &|id| !tombstones.contains(id))
        };
        let n = self.store.segment_len(&merged);
        // Rebuild the segment list in one O(n) pass (filtering the merged indices)
        // instead of k O(n) `Vec::remove` calls, then append the result unless it is
        // empty (a fully-tombstoned group leaves no segment behind).
        let mut merged_idx = indices;
        merged_idx.sort_unstable();
        let old = std::mem::take(&mut self.segments);
        self.segments = old
            .into_iter()
            .enumerate()
            .filter(|(i, _)| merged_idx.binary_search(i).is_err())
            .map(|(_, seg)| seg)
            .collect();
        if n > 0 {
            self.segments.push(Arc::new(merged));
        }
        n
    }

    /// Whether at least one size bucket is eligible to merge right now.
    pub fn has_eligible_tier(&self) -> bool {
        self.next_merge_group().is_some()
    }

    /// Choose the next group of segment indices to merge (size-tiered selection), or
    /// `None` if no bucket is eligible. Smallest-average bucket first.
    fn next_merge_group(&self) -> Option<Vec<usize>> {
        let cfg = self.tiering;
        // A group of 1 would merge a segment into itself (no progress), so the loop
        // in `compact_tiers` would not terminate. 2 is the floor regardless of config.
        let min_merge = cfg.min_merge.max(2);
        let floor = self.flush_threshold.max(1);
        let cap_half = cfg.max_merged_len / 2;
        // (raw size, floored size, index) for segments not frozen by the cap.
        let mut elig: Vec<(usize, f64, usize)> = self
            .segments
            .iter()
            .enumerate()
            .map(|(i, s)| {
                let raw = self.store.segment_len(s);
                (raw, raw.max(floor) as f64, i)
            })
            .filter(|&(raw, _, _)| raw <= cap_half)
            .collect();
        if elig.len() < min_merge {
            return None;
        }
        elig.sort_by(|a, b| a.1.partial_cmp(&b.1).unwrap_or(Ordering::Equal));

        // Cassandra-style bucketing: join the first bucket whose running average is
        // within the size band, else open a new bucket.
        let mut buckets: Vec<(f64, Vec<(usize, usize)>)> = Vec::new();
        'item: for &(raw, sz, idx) in &elig {
            for b in buckets.iter_mut() {
                if sz > b.0 * cfg.bucket_low && sz < b.0 * cfg.bucket_high {
                    let n = b.1.len() as f64;
                    b.0 = (b.0 * n + sz) / (n + 1.0);
                    b.1.push((raw, idx));
                    continue 'item;
                }
            }
            buckets.push((sz, vec![(raw, idx)]));
        }
        buckets.sort_by(|a, b| a.0.partial_cmp(&b.0).unwrap_or(Ordering::Equal));

        for (_, mut members) in buckets {
            if members.len() < min_merge {
                continue;
            }
            members.sort_by_key(|&(raw, _)| raw); // smallest first
            let mut chosen = Vec::new();
            let mut total = 0usize;
            for &(raw, idx) in &members {
                if chosen.len() >= cfg.max_merge {
                    break;
                }
                if !chosen.is_empty() && total + raw > cfg.max_merged_len {
                    break;
                }
                total += raw;
                chosen.push(idx);
            }
            if chosen.len() >= min_merge {
                return Some(chosen);
            }
        }
        None
    }

    /// Total items physically stored across segments and the buffer. This counts
    /// tombstoned-but-not-yet-purged items (segstore cannot see inside an opaque
    /// segment to subtract them); pair with [`Self::tombstone_count`] to gauge
    /// space amplification.
    pub fn stored_len(&self) -> usize {
        let in_segments: usize = self
            .segments
            .iter()
            .map(|s| self.store.segment_len(s))
            .sum();
        in_segments + self.buffer.len()
    }

    /// The current WAL generation.
    pub fn epoch(&self) -> u64 {
        self.epoch
    }

    /// Space amplification = stored items / live items, or `None` if any segment's
    /// [`Store::live_len`] returns `None` (the default). A value near 1.0 means
    /// little dead data; a higher value means tombstoned/obsolete items are
    /// accumulating, reclaimable with [`Self::reclaim_tombstones`] or [`Self::compact`].
    pub fn space_amplification(&self) -> Option<f64> {
        let mut stored = 0usize;
        let mut live = 0usize;
        for seg in &self.segments {
            let l = self
                .store
                .live_len(seg, &|id| !self.tombstones.contains(id))?;
            stored += self.store.segment_len(seg);
            live += l;
        }
        // Buffer items are always live (a delete removes from the buffer).
        stored += self.buffer.len();
        live += self.buffer.len();
        if live == 0 {
            return Some(if stored == 0 { 1.0 } else { f64::INFINITY });
        }
        Some(stored as f64 / live as f64)
    }

    /// Merge segments whose live ratio (`live_len / segment_len`) is below
    /// `min_live_ratio`, reclaiming their dead (tombstoned) entries into one fresh
    /// segment. The cheap alternative to [`Self::compact`] when only a few segments
    /// are tombstone-heavy. Requires [`Store::live_len`]; a no-op if it returns
    /// `None` or nothing qualifies. Keeps the tombstone set (a reclaimed id may
    /// still live in a segment this did not touch); only `compact` purges it.
    pub fn reclaim_tombstones(
        &mut self,
        min_live_ratio: f64,
    ) -> PersistenceResult<CompactionStats> {
        self.flush_buffer();
        let mut stats = CompactionStats {
            segments_before: self.segments.len(),
            ..Default::default()
        };
        let mut targets = Vec::new();
        for (i, seg) in self.segments.iter().enumerate() {
            let total = self.store.segment_len(seg);
            if total == 0 {
                continue;
            }
            let live = match self
                .store
                .live_len(seg, &|id| !self.tombstones.contains(id))
            {
                Some(l) => l,
                None => {
                    // Consumer can't report live counts; reclaim is unavailable.
                    stats.segments_after = self.segments.len();
                    return Ok(stats);
                }
            };
            if (live as f64) < min_live_ratio * total as f64 {
                targets.push(i);
            }
        }
        if targets.is_empty() {
            stats.segments_after = self.segments.len();
            return Ok(stats);
        }
        // Even a single tombstone-heavy segment is worth rewriting to drop dead data.
        stats.items_merged += self.merge_group(targets);
        stats.merges = 1;
        self.checkpoint()?;
        stats.segments_after = self.segments.len();
        Ok(stats)
    }

    /// Per-segment item counts, oldest segment first. The size distribution the
    /// consumer needs to watch the crossover signal (segment count + per-query
    /// fan-out vs corpus size) that says a multi-segment store is outgrowing the
    /// search-all-segments model.
    pub fn segment_sizes(&self) -> Vec<usize> {
        self.segments
            .iter()
            .map(|s| self.store.segment_len(s))
            .collect()
    }

    /// Snapshot the current segments + tombstones durably, then rotate the WAL:
    /// start a fresh epoch and delete the old log so it cannot grow unbounded.
    ///
    /// The checkpoint is the commit point. It records the *new* epoch, so once it
    /// is durable, recovery replays only the new (initially empty) WAL; the old
    /// WAL is superseded. A crash after the checkpoint but before the old WAL is
    /// deleted is safe: recovery never reads the old epoch, and the stale file is
    /// GC'd on the next open.
    pub fn checkpoint(&mut self) -> PersistenceResult<()> {
        self.flush_buffer();
        let new_epoch = self.epoch + 1;
        let snap = Snapshot {
            segments: self.segments.iter().map(|a| (**a).clone()).collect(),
            tombstones: self.tombstones.iter().cloned().collect::<Vec<_>>(),
        };
        let ckpt = CheckpointFile::new(self.dir.clone());
        // The checkpoint publishes atomically (atomic_write + CRC). On a
        // filesystem backend, also pass a power-loss barrier; in-memory backends
        // have no such barrier, so fall back to the atomic-only write.
        if self.dir.file_path(CKPT_PATH).is_some() {
            ckpt.write_postcard_durable(CKPT_PATH, new_epoch, &snap)?;
        } else {
            ckpt.write_postcard(CKPT_PATH, new_epoch, &snap)?;
        }

        // Past the commit point: start the new WAL generation and drop the old.
        let old_epoch = self.epoch;
        self.wal = RecordLogWriter::new(self.dir.clone(), wal_path(new_epoch));
        self.epoch = new_epoch;
        let _ = self.dir.delete(&wal_path(old_epoch));
        // Publish the post-compaction segment set to readers (the commit point).
        self.republish();
        Ok(())
    }

    /// The immutable segments, oldest first (each derefs to `S::Segment`). Query
    /// these plus [`Self::buffer`], filtering with [`Self::is_live`]. Segments are
    /// `Arc`-shared: an unchanged segment keeps its identity across mutations, so a
    /// consumer can cache per-segment state keyed by `Arc::as_ptr` and rebuild only
    /// new segments. For a consistent view while another thread mutates, use a
    /// [`Reader`] / [`View`] instead.
    pub fn segments(&self) -> &[Arc<S::Segment>] {
        &self.segments
    }

    /// Live adds not yet flushed into a segment.
    pub fn buffer(&self) -> &[(S::Id, S::Item)] {
        &self.buffer
    }

    /// Whether `id` is not tombstoned.
    pub fn is_live(&self, id: &S::Id) -> bool {
        !self.tombstones.contains(id)
    }

    /// Number of immutable segments.
    pub fn segment_count(&self) -> usize {
        self.segments.len()
    }

    /// Number of tombstoned ids.
    pub fn tombstone_count(&self) -> usize {
        self.tombstones.len()
    }
}

/// Apply one operation to the in-memory buffer + tombstone set. Shared by live
/// writes and WAL replay so the two paths cannot diverge.
fn apply<Id: Clone + Eq + Hash, Item>(
    buffer: &mut Vec<(Id, Item)>,
    tombstones: &mut HashSet<Id>,
    op: Op<Id, Item>,
) {
    match op {
        Op::Add(id, item) => {
            // A re-add revives a previously-deleted id.
            tombstones.remove(&id);
            buffer.push((id, item));
        }
        Op::Delete(id) => {
            buffer.retain(|(bid, _)| bid != &id);
            tombstones.insert(id);
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use durability::MemoryDirectory;

    struct Kv;
    impl Store for Kv {
        type Id = u32;
        type Item = String;
        type Segment = Vec<(u32, String)>;
        fn build_segment(&self, batch: &[(u32, String)]) -> Vec<(u32, String)> {
            batch.to_vec()
        }
        fn merge_segments(
            &self,
            segs: &[Vec<(u32, String)>],
            live: &dyn Fn(&u32) -> bool,
        ) -> Vec<(u32, String)> {
            segs.iter()
                .flatten()
                .filter(|(id, _)| live(id))
                .cloned()
                .collect()
        }
        fn segment_len(&self, seg: &Vec<(u32, String)>) -> usize {
            seg.len()
        }
        fn live_len(&self, seg: &Vec<(u32, String)>, live: &dyn Fn(&u32) -> bool) -> Option<usize> {
            Some(seg.iter().filter(|(id, _)| live(id)).count())
        }
    }

    /// A store that does NOT implement `live_len` (uses the default `None`).
    struct OpaqueKv;
    impl Store for OpaqueKv {
        type Id = u32;
        type Item = String;
        type Segment = Vec<(u32, String)>;
        fn build_segment(&self, batch: &[(u32, String)]) -> Vec<(u32, String)> {
            batch.to_vec()
        }
        fn merge_segments(
            &self,
            segs: &[Vec<(u32, String)>],
            live: &dyn Fn(&u32) -> bool,
        ) -> Vec<(u32, String)> {
            segs.iter()
                .flatten()
                .filter(|(id, _)| live(id))
                .cloned()
                .collect()
        }
        fn segment_len(&self, seg: &Vec<(u32, String)>) -> usize {
            seg.len()
        }
    }

    /// A `Directory` that fails its Nth mutating operation (and every one after),
    /// to test IO-error propagation and crash atomicity. Reads always succeed.
    struct FaultDir {
        inner: Arc<dyn Directory>,
        countdown: std::sync::atomic::AtomicUsize,
    }
    impl FaultDir {
        fn arc(inner: Arc<dyn Directory>, fail_after: usize) -> Arc<dyn Directory> {
            Arc::new(FaultDir {
                inner,
                countdown: std::sync::atomic::AtomicUsize::new(fail_after),
            })
        }
        fn gate(&self) -> PersistenceResult<()> {
            use std::sync::atomic::Ordering::Relaxed;
            let n = self.countdown.load(Relaxed);
            if n == 0 {
                return Err(PersistenceError::InvalidState("injected IO fault".into()));
            }
            self.countdown.store(n - 1, Relaxed);
            Ok(())
        }
    }
    impl Directory for FaultDir {
        fn create_file(&self, p: &str) -> PersistenceResult<Box<dyn std::io::Write + Send>> {
            self.gate()?;
            self.inner.create_file(p)
        }
        fn open_file(&self, p: &str) -> PersistenceResult<Box<dyn std::io::Read + Send>> {
            self.inner.open_file(p)
        }
        fn exists(&self, p: &str) -> bool {
            self.inner.exists(p)
        }
        fn delete(&self, p: &str) -> PersistenceResult<()> {
            self.gate()?;
            self.inner.delete(p)
        }
        fn atomic_rename(&self, a: &str, b: &str) -> PersistenceResult<()> {
            self.gate()?;
            self.inner.atomic_rename(a, b)
        }
        fn create_dir_all(&self, p: &str) -> PersistenceResult<()> {
            self.inner.create_dir_all(p)
        }
        fn list_dir(&self, p: &str) -> PersistenceResult<Vec<String>> {
            self.inner.list_dir(p)
        }
        fn append_file(&self, p: &str) -> PersistenceResult<Box<dyn std::io::Write + Send>> {
            self.gate()?;
            self.inner.append_file(p)
        }
        fn atomic_write(&self, p: &str, d: &[u8]) -> PersistenceResult<()> {
            self.gate()?;
            self.inner.atomic_write(p, d)
        }
        fn file_path(&self, p: &str) -> Option<std::path::PathBuf> {
            self.inner.file_path(p)
        }
    }

    /// Collect the live `(id, item)` set across segments + buffer.
    fn live_set(s: &SegmentedStore<Kv>) -> Vec<(u32, String)> {
        let mut out: Vec<(u32, String)> = Vec::new();
        for seg in s.segments() {
            for (id, it) in seg.iter() {
                if s.is_live(id) {
                    out.push((*id, it.clone()));
                }
            }
        }
        for (id, it) in s.buffer() {
            if s.is_live(id) {
                out.push((*id, it.clone()));
            }
        }
        out.sort();
        out
    }

    #[test]
    fn buffer_flushes_into_a_segment_at_threshold() {
        let dir = MemoryDirectory::arc();
        let mut s = SegmentedStore::open(dir, Kv, 2).unwrap();
        s.add(1, "a".into()).unwrap();
        assert_eq!(
            s.segment_count(),
            0,
            "one add stays buffered below threshold"
        );
        s.add(2, "b".into()).unwrap();
        assert_eq!(
            s.segment_count(),
            1,
            "second add hits threshold 2 and flushes"
        );
        assert!(s.buffer().is_empty());
    }

    #[test]
    fn delete_tombstones_and_hides_from_live_set() {
        let dir = MemoryDirectory::arc();
        let mut s = SegmentedStore::open(dir, Kv, 2).unwrap();
        s.add(1, "a".into()).unwrap();
        s.add(2, "b".into()).unwrap();
        s.delete(2).unwrap();
        assert!(s.is_live(&1) && !s.is_live(&2));
        assert_eq!(live_set(&s), vec![(1, "a".into())]);
    }

    #[test]
    fn compaction_physically_drops_tombstoned_ids() {
        let dir = MemoryDirectory::arc();
        let mut s = SegmentedStore::open(dir, Kv, 2).unwrap();
        s.add(1, "a".into()).unwrap();
        s.add(2, "b".into()).unwrap();
        s.add(3, "c".into()).unwrap();
        s.delete(2).unwrap();
        s.compact().unwrap();
        assert_eq!(s.segment_count(), 1, "compaction merges into one segment");
        assert_eq!(s.tombstone_count(), 0, "compaction purges tombstones");
        // The merged segment no longer carries id 2 at all.
        let flat: Vec<u32> = s.segments()[0].iter().map(|(id, _)| *id).collect();
        assert!(!flat.contains(&2));
        assert_eq!(live_set(&s), vec![(1, "a".into()), (3, "c".into())]);
    }

    #[test]
    fn recovers_from_checkpoint_plus_wal_replay() {
        let dir = MemoryDirectory::arc();
        {
            let mut s = SegmentedStore::open(dir.clone(), Kv, 2).unwrap();
            s.add(1, "a".into()).unwrap();
            s.add(2, "b".into()).unwrap(); // flushes a segment
            s.checkpoint().unwrap(); // checkpoint covers ids 1,2
            s.add(3, "c".into()).unwrap(); // post-checkpoint, only in the WAL
            s.delete(2).unwrap(); // post-checkpoint tombstone
        } // drop without a second checkpoint: 3 and delete(2) live only in the WAL

        // Reopen: checkpoint gives {1,2}; WAL replay applies add(3) + delete(2).
        let s2 = SegmentedStore::open(dir, Kv, 2).unwrap();
        assert_eq!(live_set(&s2), vec![(1, "a".into()), (3, "c".into())]);
        assert!(!s2.is_live(&2));
    }

    /// A unique scratch directory under the OS temp dir (no tempfile dep).
    fn temp_root(tag: &str) -> std::path::PathBuf {
        let mut p = std::env::temp_dir();
        p.push(format!("segstore-test-{}-{}", std::process::id(), tag));
        let _ = std::fs::remove_dir_all(&p);
        p
    }

    #[test]
    fn recovers_on_real_disk_via_fs_directory() {
        let root = temp_root("fs-recover");
        {
            let dir = durability::FsDirectory::arc(&root).unwrap();
            let mut s = SegmentedStore::open(dir, Kv, 2).unwrap();
            s.add(1, "a".into()).unwrap();
            s.add(2, "b".into()).unwrap(); // flushes a segment
            s.checkpoint().unwrap();
            s.add(3, "c".into()).unwrap(); // post-checkpoint, WAL only
            s.delete(2).unwrap();
        } // process-style drop: nothing in memory, only the on-disk WAL + checkpoint

        // A fresh FsDirectory on the same root must reconstruct the live set.
        let dir = durability::FsDirectory::arc(&root).unwrap();
        let s2 = SegmentedStore::open(dir, Kv, 2).unwrap();
        assert_eq!(live_set(&s2), vec![(1, "a".into()), (3, "c".into())]);
        assert!(!s2.is_live(&2));

        let _ = std::fs::remove_dir_all(&root);
    }

    #[test]
    fn torn_wal_tail_is_dropped_not_fatal() {
        let root = temp_root("torn-wal");
        // Threshold high enough that every op stays in the WAL (no checkpoint,
        // no segment files), so the WAL is the single source of truth.
        {
            let dir = durability::FsDirectory::arc(&root).unwrap();
            let mut s = SegmentedStore::open(dir, Kv, 100).unwrap();
            s.add(1, "aaaa".into()).unwrap();
            s.add(2, "bbbb".into()).unwrap();
            s.add(3, "cccc".into()).unwrap();
            s.add(4, "dddd".into()).unwrap(); // this record's tail gets corrupted
        }

        // Corrupt the final WAL record by chopping bytes off the end of the file.
        // postcard records are length-prefixed, so a truncated final payload makes
        // the BestEffort reader stop before it rather than decode garbage.
        let wal = root.join(wal_path(0));
        let bytes = std::fs::read(&wal).unwrap();
        assert!(bytes.len() > 3, "WAL should hold four records");
        std::fs::write(&wal, &bytes[..bytes.len() - 3]).unwrap();

        // Recovery must succeed (no panic, no Err) and recover the intact prefix.
        let dir = durability::FsDirectory::arc(&root).unwrap();
        let s2 = SegmentedStore::open(dir, Kv, 100).unwrap();
        // id 4 never made it into the store: the torn final record was dropped,
        // so the live set is exactly the intact prefix. (`is_live` only reports
        // tombstone state, so it is not the right probe for "never added".)
        assert_eq!(
            live_set(&s2),
            vec![(1, "aaaa".into()), (2, "bbbb".into()), (3, "cccc".into())],
            "the torn final record is dropped; the prefix survives"
        );

        let _ = std::fs::remove_dir_all(&root);
    }

    /// Each checkpoint rotates the WAL, so at most one generation file exists.
    #[test]
    fn wal_is_bounded_to_one_generation_across_checkpoints() {
        let dir = MemoryDirectory::arc();
        let mut s = SegmentedStore::open(dir.clone(), Kv, 100).unwrap();
        for i in 0..10u32 {
            s.add(i, format!("v{i}")).unwrap();
            s.checkpoint().unwrap();
        }
        let wals: Vec<String> = dir
            .list_dir("")
            .unwrap()
            .into_iter()
            .filter(|n| n.starts_with(WAL_PREFIX))
            .collect();
        assert!(
            wals.len() <= 1,
            "rotation bounds the WAL to the current generation, got {wals:?}"
        );
    }

    /// A stale WAL from an earlier epoch (the crash-mid-rotation leftover) is
    /// never replayed and is garbage-collected on open.
    #[test]
    fn stale_wal_generation_is_ignored_and_gced() {
        let dir = MemoryDirectory::arc();
        {
            let mut s = SegmentedStore::open(dir.clone(), Kv, 100).unwrap();
            s.add(1, "a".into()).unwrap();
            s.add(2, "b".into()).unwrap();
            s.add(3, "c".into()).unwrap();
            s.checkpoint().unwrap(); // epoch 0 -> 1; snapshot holds {1,2,3}
        }
        // Forge a stale wal.0 (the generation a clean rotation deleted) carrying a
        // ghost op, as a crash mid-rotation would leave behind.
        {
            let mut ghost = RecordLogWriter::new(dir.clone(), wal_path(0));
            ghost
                .append_postcard(&Op::Add(99u32, "ghost".to_string()))
                .unwrap();
            ghost.flush().unwrap();
        }
        assert!(dir.exists(&wal_path(0)), "the stale WAL exists pre-open");

        let s2 = SegmentedStore::open(dir.clone(), Kv, 100).unwrap();
        assert_eq!(
            live_set(&s2),
            vec![(1, "a".into()), (2, "b".into()), (3, "c".into())],
            "the ghost op in the stale epoch is never replayed"
        );
        assert!(
            !dir.exists(&wal_path(0)),
            "the stale WAL generation is GC'd on open"
        );
    }

    #[test]
    fn fsync_policy_round_trips_on_filesystem() {
        let root = temp_root("fsync");
        {
            let dir = durability::FsDirectory::arc(&root).unwrap();
            let opts = Options {
                sync: SyncPolicy::Fsync,
                ..Options::new(2)
            };
            let mut s = SegmentedStore::open_with_options(dir, Kv, opts).unwrap();
            s.add(1, "a".into()).unwrap();
            s.add(2, "b".into()).unwrap(); // flush
            s.checkpoint().unwrap();
            s.add(3, "c".into()).unwrap();
            s.delete(2).unwrap();
        }
        let dir = durability::FsDirectory::arc(&root).unwrap();
        let opts = Options {
            sync: SyncPolicy::Fsync,
            ..Options::new(2)
        };
        let s2 = SegmentedStore::open_with_options(dir, Kv, opts).unwrap();
        assert_eq!(live_set(&s2), vec![(1, "a".into()), (3, "c".into())]);
        assert!(!s2.is_live(&2));
        let _ = std::fs::remove_dir_all(&root);
    }

    #[test]
    fn fsync_policy_rejected_without_filesystem_backend() {
        let dir = MemoryDirectory::arc();
        let opts = Options {
            sync: SyncPolicy::Fsync,
            ..Options::new(2)
        };
        let err = SegmentedStore::open_with_options(dir, Kv, opts);
        assert!(
            matches!(err, Err(PersistenceError::InvalidConfig(_))),
            "Fsync on an in-memory directory is a config error"
        );
    }

    #[test]
    fn legacy_v01_unsuffixed_wal_is_rejected() {
        let dir = MemoryDirectory::arc();
        // Simulate a 0.1 store: a single unsuffixed WAL file.
        {
            let mut legacy = RecordLogWriter::new(dir.clone(), LEGACY_WAL_PATH);
            legacy
                .append_postcard(&Op::Add(1u32, "x".to_string()))
                .unwrap();
            legacy.flush().unwrap();
        }
        let err = SegmentedStore::open(dir, Kv, 2);
        assert!(
            matches!(err, Err(PersistenceError::InvalidConfig(_))),
            "a 0.1 on-disk store is rejected, not misread"
        );
    }

    // ---- size-tiered compaction ----

    /// The live `(id, item)` multiset, sorted, for invariant comparisons.
    fn live_multiset(s: &SegmentedStore<Kv>) -> Vec<(u32, String)> {
        live_set(s)
    }

    fn tier_opts(flush: usize, cfg: TierConfig, auto: bool) -> Options {
        Options {
            tiering: cfg,
            auto_compact: auto,
            ..Options::new(flush)
        }
    }

    #[test]
    fn compact_tiers_merges_a_full_bucket_and_is_idempotent() {
        let dir = MemoryDirectory::arc();
        let cfg = TierConfig {
            min_merge: 4,
            ..Default::default()
        };
        let mut s = SegmentedStore::open_with_options(dir, Kv, tier_opts(2, cfg, false)).unwrap();
        // 8 adds at flush=2 -> 4 segments of size 2: one full bucket.
        for i in 0..8u32 {
            s.add(i, format!("v{i}")).unwrap();
        }
        assert_eq!(
            s.segment_count(),
            4,
            "four size-2 segments before compaction"
        );
        let stats = s.compact_tiers().unwrap();
        assert_eq!(stats.merges, 1, "the full bucket merges once");
        assert_eq!(s.segment_count(), 1, "into a single segment");
        assert_eq!(stats.items_merged, 8);
        // Idempotent: nothing eligible now.
        assert!(!s.has_eligible_tier());
        let again = s.compact_tiers().unwrap();
        assert_eq!(again.merges, 0, "second call is a no-op");
    }

    #[test]
    fn tier_merge_respects_max_merged_len_cap() {
        let dir = MemoryDirectory::arc();
        // cap = 8 -> segments above 4 are frozen; 4 size-2 segments merge to exactly 8.
        let cfg = TierConfig {
            min_merge: 4,
            max_merged_len: 8,
            ..Default::default()
        };
        let mut s = SegmentedStore::open_with_options(dir, Kv, tier_opts(2, cfg, true)).unwrap();
        for i in 0..64u32 {
            s.add(i, format!("v{i}")).unwrap();
        }
        s.compact_tiers().unwrap();
        for seg in s.segments() {
            assert!(
                seg.len() <= cfg.max_merged_len,
                "no segment exceeds the cap; got {}",
                seg.len()
            );
        }
    }

    #[test]
    fn auto_compact_bounds_segment_count() {
        let dir = MemoryDirectory::arc();
        let cfg = TierConfig::default(); // min_merge 4, large cap
        let mut s = SegmentedStore::open_with_options(dir, Kv, tier_opts(2, cfg, true)).unwrap();
        // 200 adds at flush=2 would be 100 segments without compaction.
        for i in 0..200u32 {
            s.add(i, format!("v{i}")).unwrap();
        }
        s.compact_tiers().unwrap();
        assert!(
            s.segment_count() <= 20,
            "tiering bounds segment count well below the uncompacted 100; got {}",
            s.segment_count()
        );
        // No data lost.
        assert_eq!(live_multiset(&s).len(), 200);
    }

    #[test]
    fn tier_merge_preserves_live_set_and_keeps_tombstones() {
        let dir = MemoryDirectory::arc();
        let cfg = TierConfig {
            min_merge: 4,
            max_merged_len: 8, // force some frozen segments
            ..Default::default()
        };
        let mut s = SegmentedStore::open_with_options(dir, Kv, tier_opts(2, cfg, false)).unwrap();
        let mut expect: std::collections::BTreeMap<u32, String> = Default::default();
        for i in 0..40u32 {
            s.add(i, format!("v{i}")).unwrap();
            expect.insert(i, format!("v{i}"));
        }
        // Delete a spread of ids (some land in soon-to-be-frozen segments).
        for i in (0..40u32).step_by(5) {
            s.delete(i).unwrap();
            expect.remove(&i);
        }
        s.compact_tiers().unwrap();
        let want: Vec<(u32, String)> = expect.into_iter().collect();
        assert_eq!(live_multiset(&s), want, "tier merge preserves the live set");
        assert!(
            s.tombstone_count() > 0,
            "partial tier merge keeps the tombstone set (ids may live in frozen segments)"
        );
        // Full compaction purges the tombstones.
        s.compact().unwrap();
        assert_eq!(s.tombstone_count(), 0, "full compact purges tombstones");
        assert_eq!(live_multiset(&s), want, "and preserves the live set");
    }

    #[test]
    fn min_merge_below_two_terminates() {
        let dir = MemoryDirectory::arc();
        let cfg = TierConfig {
            min_merge: 1, // would group-of-1 forever without the clamp
            ..Default::default()
        };
        let mut s = SegmentedStore::open_with_options(dir, Kv, tier_opts(1, cfg, false)).unwrap();
        for i in 0..8u32 {
            s.add(i, format!("v{i}")).unwrap();
        }
        // Must terminate (clamp forces min_merge >= 2).
        let stats = s.compact_tiers().unwrap();
        assert!(stats.segments_after <= stats.segments_before);
        assert_eq!(live_multiset(&s).len(), 8);
    }

    #[test]
    fn large_scale_random_simulation_holds_invariants() {
        let dir = MemoryDirectory::arc();
        let cfg = TierConfig {
            min_merge: 4,
            max_merge: 8,
            max_merged_len: 64,
            ..Default::default()
        };
        let mut s = SegmentedStore::open_with_options(dir, Kv, tier_opts(3, cfg, true)).unwrap();
        // Unique ids per add (segstore makes no dedup promise; identity is the
        // Store impl's job, and the toy Kv appends duplicates on re-add). A
        // monotonic id keeps the reference model exact while still exercising
        // insert/delete/merge invariants.
        let mut expect: std::collections::BTreeMap<u32, String> = Default::default();
        let mut live_ids: Vec<u32> = Vec::new();
        let mut next_id = 0u32;
        // Deterministic LCG (no rand dep, no Math.random).
        let mut state: u64 = 0x9E3779B97F4A7C15;
        let mut next = || {
            state = state
                .wrapping_mul(6364136223846793005)
                .wrapping_add(1442695040888963407);
            (state >> 33) as u32
        };
        for _ in 0..2000 {
            if next() % 4 == 0 && !live_ids.is_empty() {
                let pos = (next() as usize) % live_ids.len();
                let id = live_ids.swap_remove(pos);
                s.delete(id).unwrap();
                expect.remove(&id);
            } else {
                let id = next_id;
                next_id += 1;
                let v = format!("v{id}");
                s.add(id, v.clone()).unwrap();
                expect.insert(id, v);
                live_ids.push(id);
            }
            if next() % 50 == 0 {
                s.compact_tiers().unwrap();
            }
            // Invariant: every segment is within the cap.
            for seg in s.segments() {
                assert!(
                    seg.len() <= cfg.max_merged_len,
                    "seg size {} exceeds cap {}",
                    seg.len(),
                    cfg.max_merged_len
                );
            }
        }
        s.compact().unwrap();
        let want: Vec<(u32, String)> = expect.into_iter().collect();
        assert_eq!(
            live_multiset(&s),
            want,
            "after a long random run, the live set matches the reference"
        );
    }

    #[test]
    fn segment_sizes_reports_per_segment_counts() {
        let dir = MemoryDirectory::arc();
        let mut s = SegmentedStore::open(dir, Kv, 2).unwrap();
        for i in 0..6u32 {
            s.add(i, format!("v{i}")).unwrap(); // 3 segments of size 2
        }
        assert_eq!(s.segment_sizes(), vec![2, 2, 2]);
        assert_eq!(s.stored_len(), 6);
    }

    /// The store must be `Send` so the consumer can drive `compact_tiers` on a
    /// background thread (the whole point of consumer-driven scheduling).
    #[test]
    fn store_is_send() {
        fn assert_send<T: Send>() {}
        assert_send::<SegmentedStore<Kv>>();
    }

    // ---- checkpoint integrity (crash injection) ----

    #[test]
    fn corrupt_checkpoint_is_rejected_not_misread() {
        let root = temp_root("corrupt-ckpt");
        {
            let dir = durability::FsDirectory::arc(&root).unwrap();
            let mut s = SegmentedStore::open(dir, Kv, 2).unwrap();
            s.add(1, "a".into()).unwrap();
            s.add(2, "b".into()).unwrap();
            s.checkpoint().unwrap();
        }
        // Flip a byte in the middle of the checkpoint payload (past the header).
        let ckpt = root.join(CKPT_PATH);
        let mut bytes = std::fs::read(&ckpt).unwrap();
        let mid = bytes.len() / 2;
        bytes[mid] ^= 0xFF;
        std::fs::write(&ckpt, &bytes).unwrap();

        let dir = durability::FsDirectory::arc(&root).unwrap();
        let res = SegmentedStore::open(dir, Kv, 2);
        assert!(
            res.is_err(),
            "a CRC-corrupt checkpoint is an error, not silently misread"
        );
        let _ = std::fs::remove_dir_all(&root);
    }

    #[test]
    fn stale_checkpoint_tmp_is_ignored() {
        let root = temp_root("stale-tmp");
        {
            let dir = durability::FsDirectory::arc(&root).unwrap();
            let mut s = SegmentedStore::open(dir, Kv, 2).unwrap();
            s.add(1, "a".into()).unwrap();
            s.add(2, "b".into()).unwrap();
            s.checkpoint().unwrap();
        }
        // A crash mid atomic_write can leave a `<ckpt>.tmp` next to the real file.
        std::fs::write(root.join(format!("{CKPT_PATH}.tmp")), b"garbage").unwrap();

        let dir = durability::FsDirectory::arc(&root).unwrap();
        let s2 = SegmentedStore::open(dir, Kv, 2).unwrap();
        assert_eq!(live_set(&s2), vec![(1, "a".into()), (2, "b".into())]);
        let _ = std::fs::remove_dir_all(&root);
    }

    #[test]
    fn recovers_consistently_from_io_fault_at_every_step() {
        // FoundationDB-style fault injection: fail the Nth IO op, then reopen on
        // the underlying (un-faulted) directory and assert the recovered live set
        // is EXACTLY the durably-acked adds -- every Ok(add) survives, no failed add
        // appears, recovery never panics and never sees corruption. Sweeps the
        // fault point across the whole op sequence.
        for fail_after in 0..30usize {
            let mem = MemoryDirectory::arc();
            let dir = FaultDir::arc(mem.clone(), fail_after);
            let mut acked: Vec<u32> = Vec::new();
            if let Ok(mut s) = SegmentedStore::open(dir, Kv, 2) {
                for i in 0..10u32 {
                    if s.add(i, format!("v{i}")).is_err() {
                        break;
                    }
                    acked.push(i);
                    if i % 3 == 0 && s.compact_tiers().is_err() {
                        break;
                    }
                }
            }
            // Reopen on the clean underlying directory (the partial on-disk state).
            let s2 = SegmentedStore::open(mem, Kv, 2)
                .expect("recovery after an injected IO fault must not fail");
            let mut live: Vec<u32> = live_set(&s2).into_iter().map(|(id, _)| id).collect();
            live.sort_unstable();
            assert_eq!(
                live, acked,
                "fail_after={fail_after}: recovered set must be exactly the durably-acked adds"
            );
        }
    }

    #[test]
    fn no_space_leak_across_crash_recovery_cycles() {
        // After many crash+recover cycles, deleting everything and a full compaction
        // returns the store to baseline: no leaked segments, items, tombstones, or WAL
        // generations. This is redb's canonical invariant and the bug class targeted
        // crash tests structurally miss (a slow leak across recovery cycles).
        let mem = MemoryDirectory::arc();
        for cycle in 0..20u32 {
            // "Crash": run a few ops under an IO fault and drop the store mid-flight.
            let dir = FaultDir::arc(mem.clone(), (cycle as usize % 5) + 1);
            if let Ok(mut s) = SegmentedStore::open(dir, Kv, 2) {
                for j in 0..4u32 {
                    let id = cycle * 100 + j;
                    let _ = s.add(id, format!("v{id}"));
                    let _ = s.compact_tiers();
                }
            }
            // Recover on the clean directory between cycles.
            let _ = SegmentedStore::open(mem.clone(), Kv, 2).unwrap();
        }
        // Delete every surviving id, then full-compact.
        let mut s = SegmentedStore::open(mem.clone(), Kv, 2).unwrap();
        let live: Vec<u32> = live_set(&s).into_iter().map(|(id, _)| id).collect();
        for id in live {
            s.delete(id).unwrap();
        }
        s.compact().unwrap();
        assert_eq!(
            s.segment_count(),
            0,
            "no leaked segments after delete-all + compact"
        );
        assert_eq!(s.stored_len(), 0, "no leaked stored items");
        assert_eq!(s.tombstone_count(), 0, "compact purged the tombstone set");
        let wals: Vec<String> = mem
            .list_dir("")
            .unwrap()
            .into_iter()
            .filter(|n| n.starts_with(WAL_PREFIX))
            .collect();
        assert!(wals.len() <= 1, "no leaked WAL generations: {wals:?}");
    }
    // ---- tombstone reclamation (optional live_len) ----

    #[test]
    fn space_amplification_tracks_dead_data() {
        let dir = MemoryDirectory::arc();
        let mut s = SegmentedStore::open(dir, Kv, 2).unwrap();
        for i in 0..10u32 {
            s.add(i, format!("v{i}")).unwrap();
        }
        assert_eq!(
            s.space_amplification(),
            Some(1.0),
            "no deletes, no dead data"
        );
        for i in 0..5u32 {
            s.delete(i).unwrap();
        }
        // 10 stored, 5 live -> amplification 2.0.
        assert_eq!(s.space_amplification(), Some(2.0));
        s.compact().unwrap();
        assert_eq!(s.space_amplification(), Some(1.0), "compaction reclaims it");
    }

    #[test]
    fn space_amplification_is_none_without_live_len() {
        let dir = MemoryDirectory::arc();
        let mut s = SegmentedStore::open(dir, OpaqueKv, 2).unwrap();
        s.add(1, "a".into()).unwrap();
        s.add(2, "b".into()).unwrap();
        assert_eq!(
            s.space_amplification(),
            None,
            "a store without live_len cannot report it"
        );
    }

    #[test]
    fn reclaim_tombstones_rewrites_only_heavy_segments() {
        let dir = MemoryDirectory::arc();
        let mut s = SegmentedStore::open(dir, Kv, 2).unwrap();
        // 5 segments of size 2 (ids 0..10).
        for i in 0..10u32 {
            s.add(i, format!("v{i}")).unwrap();
        }
        // Tombstone both items in the first two segments (ids 0,1,2,3) -> those
        // segments are fully dead; the rest are fully live.
        for i in 0..4u32 {
            s.delete(i).unwrap();
        }
        let before_stored = s.stored_len();
        let stats = s.reclaim_tombstones(0.5).unwrap();
        assert!(stats.merges > 0, "the dead segments were reclaimed");
        assert!(
            s.stored_len() < before_stored,
            "dead data dropped: {} < {}",
            s.stored_len(),
            before_stored
        );
        // Live set unchanged; tombstones kept (no full purge).
        let live: Vec<u32> = live_set(&s).into_iter().map(|(id, _)| id).collect();
        assert_eq!(live, (4..10).collect::<Vec<_>>());
    }

    #[test]
    fn reclaim_tombstones_is_noop_without_live_len() {
        let dir = MemoryDirectory::arc();
        let mut s = SegmentedStore::open(dir, OpaqueKv, 2).unwrap();
        for i in 0..6u32 {
            s.add(i, format!("v{i}")).unwrap();
        }
        s.delete(0).unwrap();
        let before = s.segment_count();
        let stats = s.reclaim_tombstones(0.9).unwrap();
        assert_eq!(stats.merges, 0, "no live_len -> reclaim is a no-op");
        assert_eq!(s.segment_count(), before);
    }

    #[test]
    fn reclaim_drops_a_fully_dead_segment() {
        let dir = MemoryDirectory::arc();
        let mut s = SegmentedStore::open(dir, Kv, 2).unwrap();
        for i in 0..4u32 {
            s.add(i, format!("v{i}")).unwrap(); // segment A=[0,1], B=[2,3]
        }
        assert_eq!(s.segment_count(), 2);
        s.delete(0).unwrap();
        s.delete(1).unwrap(); // segment A is now 0% live
        s.reclaim_tombstones(0.5).unwrap();
        // A's merge produces an empty segment, which is dropped (not kept as empty).
        assert_eq!(s.segment_count(), 1, "the fully-dead segment is dropped");
        assert_eq!(s.stored_len(), 2, "only the live segment remains");
    }

    // ---- force-merge / on-demand consolidation ----

    #[test]
    fn force_merge_to_consolidates_without_data_loss() {
        let dir = MemoryDirectory::arc();
        let mut s = SegmentedStore::open(dir, Kv, 2).unwrap();
        for i in 0..20u32 {
            s.add(i, format!("v{i}")).unwrap(); // 10 segments of size 2
        }
        assert_eq!(s.segment_count(), 10);
        let stats = s.force_merge_to(3).unwrap();
        // Minimum work: consolidates to exactly 3 in a single merge (k = over+1 = 8
        // segments at once), like Lucene's least-number-of-merges force-merge.
        assert_eq!(s.segment_count(), 3, "consolidated to exactly 3");
        assert_eq!(stats.merges, 1, "one merge suffices (minimum work)");
        assert!(stats.items_merged > 0, "merged work is reported");
        assert_eq!(live_multiset(&s).len(), 20, "no data lost");
    }

    #[test]
    fn force_merge_to_one_purges_tombstones() {
        let dir = MemoryDirectory::arc();
        let mut s = SegmentedStore::open(dir, Kv, 2).unwrap();
        for i in 0..10u32 {
            s.add(i, format!("v{i}")).unwrap();
        }
        for i in 0..5u32 {
            s.delete(i).unwrap();
        }
        s.force_merge_to(1).unwrap();
        assert_eq!(s.segment_count(), 1);
        assert_eq!(s.tombstone_count(), 0, "merge to one purges tombstones");
        let live: Vec<u32> = live_set(&s).into_iter().map(|(id, _)| id).collect();
        assert_eq!(live, (5..10).collect::<Vec<_>>());
    }

    #[test]
    fn force_merge_to_is_noop_when_already_small() {
        let dir = MemoryDirectory::arc();
        let mut s = SegmentedStore::open(dir, Kv, 2).unwrap();
        for i in 0..4u32 {
            s.add(i, format!("v{i}")).unwrap(); // 2 segments
        }
        let e = s.epoch();
        let stats = s.force_merge_to(5).unwrap();
        assert_eq!(stats.merges, 0, "already at/below target, nothing to merge");
        assert_eq!(s.segment_count(), 2);
        assert_eq!(s.epoch(), e, "no merge -> no checkpoint");
    }

    #[test]
    fn force_merge_persists_across_reopen() {
        let dir = MemoryDirectory::arc();
        {
            let mut s = SegmentedStore::open(dir.clone(), Kv, 2).unwrap();
            for i in 0..20u32 {
                s.add(i, format!("v{i}")).unwrap(); // 10 segments
            }
            s.force_merge_to(2).unwrap();
            assert_eq!(s.segment_count(), 2);
        }
        let s = SegmentedStore::open(dir, Kv, 2).unwrap();
        assert_eq!(s.segment_count(), 2, "force-merge result was checkpointed");
        assert_eq!(live_multiset(&s).len(), 20);
    }

    /// Tiering rewrites each item O(log) times, so the total merged work over N
    /// inserts is O(N log N) -- far below the O(N^2) of rebuilding everything on
    /// each compaction, which is the cliff the max_merged_len cap exists to avoid.
    #[test]
    fn tiered_write_amplification_is_subquadratic() {
        let dir = MemoryDirectory::arc();
        let cfg = TierConfig::default(); // min_merge 4, large cap (no freezing here)
        let mut s = SegmentedStore::open_with_options(dir, Kv, tier_opts(4, cfg, false)).unwrap();
        let n: u32 = 4000;
        let mut total_merged = 0usize;
        for i in 0..n {
            s.add(i, format!("v{i}")).unwrap();
            if i % 16 == 0 {
                total_merged += s.compact_tiers().unwrap().items_merged;
            }
        }
        total_merged += s.compact_tiers().unwrap().items_merged;
        let n = n as usize;
        assert!(total_merged > 0, "compaction actually ran");
        assert!(
            total_merged < 20 * n,
            "tiered merge work {total_merged} is ~O(N log N) (< 20*N = {}), not O(N^2={})",
            20 * n,
            n * n
        );
        assert_eq!(live_multiset(&s).len(), n, "no data lost");
    }

    // ---- mutation-driven: pin behavior the live-set tests left unobserved ----

    #[test]
    fn epoch_advances_per_checkpoint() {
        let dir = MemoryDirectory::arc();
        let mut s = SegmentedStore::open(dir, Kv, 2).unwrap();
        assert_eq!(s.epoch(), 0);
        s.add(1, "a".into()).unwrap();
        s.checkpoint().unwrap();
        assert_eq!(s.epoch(), 1);
        s.checkpoint().unwrap();
        assert_eq!(s.epoch(), 2);
    }

    #[test]
    fn stored_len_and_space_amp_count_the_buffer() {
        let dir = MemoryDirectory::arc();
        let mut s = SegmentedStore::open(dir, Kv, 100).unwrap(); // stays buffered
        s.add(1, "a".into()).unwrap();
        s.add(2, "b".into()).unwrap();
        assert_eq!(s.segment_count(), 0, "all buffered");
        assert_eq!(s.stored_len(), 2, "stored_len counts the buffer");
        assert_eq!(
            s.space_amplification(),
            Some(1.0),
            "buffered items are live"
        );
    }

    #[test]
    fn space_amp_of_empty_store_is_one() {
        let dir = MemoryDirectory::arc();
        let s = SegmentedStore::open(dir, Kv, 2).unwrap();
        assert_eq!(s.space_amplification(), Some(1.0));
    }

    #[test]
    fn space_amp_is_infinite_when_all_dead() {
        let dir = MemoryDirectory::arc();
        let mut s = SegmentedStore::open(dir, Kv, 2).unwrap();
        s.add(1, "a".into()).unwrap();
        s.add(2, "b".into()).unwrap(); // 1 segment, size 2
        s.delete(1).unwrap();
        s.delete(2).unwrap(); // stored 2, live 0
        assert!(
            s.space_amplification().unwrap().is_infinite(),
            "an all-dead segment is infinite amplification"
        );
    }

    #[test]
    fn has_eligible_tier_is_true_when_a_bucket_is_full() {
        let dir = MemoryDirectory::arc();
        let cfg = TierConfig {
            min_merge: 4,
            ..Default::default()
        };
        let mut s = SegmentedStore::open_with_options(dir, Kv, tier_opts(2, cfg, false)).unwrap();
        for i in 0..8u32 {
            s.add(i, format!("v{i}")).unwrap(); // 4 size-2 segments = one full bucket
        }
        assert!(s.has_eligible_tier());
    }

    #[test]
    fn compact_merges_only_when_there_is_work() {
        let dir = MemoryDirectory::arc();
        let mut s = SegmentedStore::open(dir, Kv, 2).unwrap();
        s.add(1, "a".into()).unwrap();
        s.add(2, "b".into()).unwrap(); // 1 segment, no tombstones
        assert_eq!(
            s.compact().unwrap().merges,
            0,
            "a single clean segment: nothing to merge"
        );
        s.delete(1).unwrap();
        assert_eq!(
            s.compact().unwrap().merges,
            1,
            "a tombstone present: merge to purge it"
        );
    }

    #[test]
    fn reclaim_respects_the_live_ratio_threshold() {
        let dir = MemoryDirectory::arc();
        let mut s = SegmentedStore::open(dir, Kv, 4).unwrap();
        for i in 0..12u32 {
            s.add(i, format!("v{i}")).unwrap(); // 3 segments: [0-3] [4-7] [8-11]
        }
        // A: delete 0,1,2 -> 1/4 = 0.25 live. B: delete 4 -> 3/4 = 0.75. C: delete 8,9 -> 2/4 = 0.5.
        for i in [0u32, 1, 2, 4, 8, 9] {
            s.delete(i).unwrap();
        }
        let stats = s.reclaim_tombstones(0.5).unwrap();
        // Only A (0.25 < 0.5) qualifies; C (0.5) is at the threshold, not below; B (0.75) is above.
        assert_eq!(
            stats.merges, 1,
            "only the sub-threshold segment is reclaimed"
        );
        assert_eq!(stats.items_merged, 1, "A's single live item is rewritten");
        assert_eq!(
            s.segment_count(),
            3,
            "A rewritten in place; B and C untouched"
        );
        assert_eq!(s.stored_len(), 1 + 4 + 4, "only A's dead entries dropped");
    }

    #[test]
    fn compact_tiers_persists_across_reopen() {
        let dir = MemoryDirectory::arc();
        let cfg = TierConfig {
            min_merge: 4,
            ..Default::default()
        };
        {
            let mut s =
                SegmentedStore::open_with_options(dir.clone(), Kv, tier_opts(2, cfg, false))
                    .unwrap();
            for i in 0..8u32 {
                s.add(i, format!("v{i}")).unwrap();
            }
            assert_eq!(s.compact_tiers().unwrap().merges, 1);
            assert_eq!(s.segment_count(), 1);
        }
        let s = SegmentedStore::open_with_options(dir, Kv, tier_opts(2, cfg, false)).unwrap();
        assert_eq!(s.segment_count(), 1, "the tier merge was checkpointed");
        assert_eq!(live_multiset(&s).len(), 8);
    }

    #[test]
    fn compact_tiers_without_eligible_bucket_does_not_checkpoint() {
        let dir = MemoryDirectory::arc();
        let mut s = SegmentedStore::open(dir, Kv, 100).unwrap();
        s.add(1, "a".into()).unwrap();
        let e = s.epoch();
        assert_eq!(s.compact_tiers().unwrap().merges, 0);
        assert_eq!(s.epoch(), e, "no merge -> no checkpoint -> epoch unchanged");
    }

    // ---- research failure modes: the cap is the O(N^2) write-amp preventer ----

    #[test]
    fn cap_freezes_large_segments_from_tier_merges() {
        let dir = MemoryDirectory::arc();
        // cap = 8 -> a segment above cap/2 = 4 is frozen out of tier merges, so the
        // biggest segment is never rewritten by tiering (the O(N^2) cliff guard).
        let cfg = TierConfig {
            min_merge: 4,
            max_merged_len: 8,
            ..Default::default()
        };
        let mut s = SegmentedStore::open_with_options(dir, Kv, tier_opts(2, cfg, false)).unwrap();
        for i in 0..8u32 {
            s.add(i, format!("v{i}")).unwrap();
        }
        s.force_merge_to(1).unwrap(); // one size-8 segment, now frozen (> cap/2)
        assert_eq!(s.segment_sizes(), vec![8]);
        for i in 8..20u32 {
            s.add(i, format!("v{i}")).unwrap(); // 6 more size-2 segments
        }
        s.compact_tiers().unwrap();
        assert!(
            s.segment_sizes().contains(&8),
            "the frozen segment is never selected for a tier merge"
        );
        for sz in s.segment_sizes() {
            assert!(sz <= cfg.max_merged_len, "no segment exceeds the cap");
        }
        assert_eq!(live_multiset(&s).len(), 20, "no data lost");
    }

    #[test]
    fn without_compaction_fan_out_grows_then_collapses() {
        // The failure mode tiering exists to prevent: with no compaction every
        // flush adds a segment, and a query scans all segments, so fan-out grows
        // linearly with the corpus. Compaction collapses it.
        let dir = MemoryDirectory::arc();
        let mut s = SegmentedStore::open(dir, Kv, 2).unwrap();
        for i in 0..40u32 {
            s.add(i, format!("v{i}")).unwrap();
        }
        assert_eq!(
            s.segment_count(),
            20,
            "no compaction: 40 adds / flush 2 = 20 segments to scan per query"
        );
        s.compact_tiers().unwrap();
        assert!(
            s.segment_count() < 20,
            "tiered compaction collapses the fan-out, got {}",
            s.segment_count()
        );
        assert_eq!(live_multiset(&s).len(), 40, "without losing data");
    }

    // ---- concurrent snapshot reads ----

    #[test]
    fn view_reflects_segments_minus_tombstones() {
        let mut s = SegmentedStore::open(MemoryDirectory::arc(), Kv, 2).unwrap();
        for i in 0..6u32 {
            s.add(i, format!("v{i}")).unwrap();
        }
        s.delete(2).unwrap();
        s.checkpoint().unwrap(); // commit-visibility: publish to readers
        let v = s.reader().view();
        let mut live: Vec<u32> = Vec::new();
        for seg in v.segments() {
            for (id, _) in seg.iter() {
                if v.is_live(id) {
                    live.push(*id);
                }
            }
        }
        live.sort_unstable();
        assert_eq!(
            live,
            vec![0, 1, 3, 4, 5],
            "view = checkpointed segments minus tombstones"
        );
    }

    #[test]
    fn view_is_a_stable_snapshot_across_writes() {
        let mut s = SegmentedStore::open(MemoryDirectory::arc(), Kv, 2).unwrap();
        for i in 0..6u32 {
            s.add(i, format!("v{i}")).unwrap(); // 3 segments
        }
        s.checkpoint().unwrap(); // publish the 3 segments to readers
        let reader = s.reader();
        let v1 = reader.view();
        let before = v1.segment_count();
        assert_eq!(before, 3);
        // Mutate heavily while v1 is held.
        for i in 6..30u32 {
            s.add(i, format!("v{i}")).unwrap();
        }
        s.compact().unwrap();
        assert_eq!(v1.segment_count(), before, "the held view never changes");
        assert_eq!(
            reader.view().segment_count(),
            1,
            "a fresh view sees the compacted state"
        );
    }

    #[test]
    fn unchanged_segments_keep_arc_identity_across_checkpoints() {
        // The point of Arc-internal segments: an unchanged segment keeps its Arc
        // identity across mutations, so a consumer can cache per-segment state keyed
        // by it and rebuild only new segments.
        let mut s = SegmentedStore::open(MemoryDirectory::arc(), Kv, 2).unwrap();
        for i in 0..6u32 {
            s.add(i, format!("v{i}")).unwrap(); // 3 segments
        }
        s.checkpoint().unwrap();
        let r = s.reader();
        let ptrs1: Vec<*const _> = r.view().segments().iter().map(Arc::as_ptr).collect();
        assert_eq!(ptrs1.len(), 3);

        // A no-op checkpoint must keep every segment's identity.
        s.checkpoint().unwrap();
        let ptrs2: Vec<*const _> = r.view().segments().iter().map(Arc::as_ptr).collect();
        assert_eq!(
            ptrs1, ptrs2,
            "a no-op checkpoint keeps all segment identities"
        );

        // Sealing a new segment leaves the originals' identities intact.
        s.add(10, "x".into()).unwrap();
        s.add(11, "y".into()).unwrap(); // seals a 4th segment
        s.checkpoint().unwrap();
        let ptrs3: Vec<*const _> = r.view().segments().iter().map(Arc::as_ptr).collect();
        assert_eq!(ptrs3.len(), 4);
        assert_eq!(
            &ptrs3[..3],
            &ptrs1[..],
            "the original segments keep identity; only the new one is fresh"
        );
    }

    #[test]
    fn concurrent_reader_during_writes_stays_consistent() {
        use std::sync::atomic::{AtomicBool, Ordering};
        let mut s = SegmentedStore::open_with_options(
            MemoryDirectory::arc(),
            Kv,
            Options {
                tiering: TierConfig {
                    min_merge: 4,
                    ..Default::default()
                },
                ..Options::new(4)
            },
        )
        .unwrap();
        for i in 0..40u32 {
            s.add(i, format!("v{i}")).unwrap();
        }
        let reader = s.reader();
        let stop = Arc::new(AtomicBool::new(false));
        let stop2 = stop.clone();
        // Reader thread: take views and fully scan them while the writer mutates.
        // Each view is an internally-consistent snapshot, so scanning never panics
        // and never sees a torn segment list.
        let handle = std::thread::spawn(move || {
            let mut iters = 0u64;
            while !stop2.load(Ordering::Relaxed) {
                let v = reader.view();
                let mut count = 0usize;
                for seg in v.segments() {
                    for (id, _) in seg.iter() {
                        if v.is_live(id) {
                            count += 1;
                        }
                    }
                }
                std::hint::black_box(count);
                iters += 1;
            }
            iters
        });
        // Writer: add + compact concurrently with the reader.
        for i in 40..400u32 {
            s.add(i, format!("v{i}")).unwrap();
            if i % 20 == 0 {
                s.compact_tiers().unwrap();
            }
        }
        s.compact().unwrap();
        stop.store(true, Ordering::Relaxed);
        handle.join().unwrap();
        // Final snapshot sees every live item.
        let v = s.reader().view();
        let mut live = 0usize;
        for seg in v.segments() {
            for (id, _) in seg.iter() {
                if v.is_live(id) {
                    live += 1;
                }
            }
        }
        assert_eq!(live, 400, "all 400 items live after the concurrent run");
    }

    // ---- bulk ingest (extend) + harder corruption ----

    #[test]
    fn extend_matches_individual_adds() {
        let mut s1 = SegmentedStore::open(MemoryDirectory::arc(), Kv, 2).unwrap();
        let mut s2 = SegmentedStore::open(MemoryDirectory::arc(), Kv, 2).unwrap();
        for i in 0..20u32 {
            s1.add(i, format!("v{i}")).unwrap();
        }
        s2.extend((0..20u32).map(|i| (i, format!("v{i}")))).unwrap();
        assert_eq!(live_set(&s1), live_set(&s2), "extend == individual adds");
        assert_eq!(s1.segment_count(), s2.segment_count());
    }

    #[test]
    fn extend_is_durable_across_reopen() {
        let dir = MemoryDirectory::arc();
        {
            let mut s = SegmentedStore::open(dir.clone(), Kv, 4).unwrap();
            s.extend((0..20u32).map(|i| (i, format!("v{i}")))).unwrap();
        }
        let s = SegmentedStore::open(dir, Kv, 4).unwrap();
        assert_eq!(
            live_set(&s).len(),
            20,
            "the whole batch is durable after sync"
        );
    }

    #[test]
    fn garbled_wal_record_is_caught_by_crc() {
        // Harder than truncation: flip a byte inside a committed WAL record. Each
        // record carries a CRC, so recovery detects the bad record and (BestEffort)
        // stops there -- yielding a consistent PREFIX of the adds, never a panic or
        // a decoded-garbage record. This also documents the interior-corruption
        // behavior: records after the corruption are dropped (treated as a torn tail).
        let root = temp_root("garble-wal");
        {
            let dir = durability::FsDirectory::arc(&root).unwrap();
            let mut s = SegmentedStore::open(dir, Kv, 100).unwrap(); // all in one WAL
            for i in 1..=6u32 {
                s.add(i, format!("v{i}")).unwrap();
            }
        }
        let wal = root.join(wal_path(0));
        let mut bytes = std::fs::read(&wal).unwrap();
        let mid = bytes.len() / 2;
        bytes[mid] ^= 0xFF; // corrupt an interior record
        std::fs::write(&wal, &bytes).unwrap();

        // Recovery is SAFE either way: it returns a hard error (a corrupted length
        // field is not a clean torn tail) OR a consistent contiguous prefix of the
        // adds -- but NEVER a panic, a decoded-garbage id, or the corrupted record.
        // (Which of the two depends on where in the record the byte landed; the
        // safe-behavior invariant is what matters and is what we assert.)
        let dir = durability::FsDirectory::arc(&root).unwrap();
        match SegmentedStore::open(dir, Kv, 100) {
            Ok(s2) => {
                let mut live: Vec<u32> = live_set(&s2).into_iter().map(|(id, _)| id).collect();
                live.sort_unstable();
                assert!(
                    live.len() < 6,
                    "the corrupted record + tail are dropped: {live:?}"
                );
                assert_eq!(
                    live,
                    (1..=live.len() as u32).collect::<Vec<_>>(),
                    "survivors are the contiguous prefix before the corruption: {live:?}"
                );
            }
            Err(_) => { /* hard fault on corruption: acceptable, never garbage */ }
        }
        let _ = std::fs::remove_dir_all(&root);
    }

    // ---- property-based: random op sequences vs a reference model ----

    use proptest::prelude::*;

    /// An op applied to both the store and a reference model. `Add` uses a fresh
    /// unique id (segstore makes no dedup promise, and compaction reorders
    /// segments, so re-adds of one id have no last-write-wins guarantee); `Delete`
    /// targets the k-th currently-live id.
    #[derive(Debug, Clone)]
    enum SimOp {
        Add,
        Delete(usize),
        Compact,
        CompactTiers,
        Reopen,
    }

    fn op_strategy() -> impl Strategy<Value = SimOp> {
        prop_oneof![
            3 => Just(SimOp::Add),
            2 => (0usize..100).prop_map(SimOp::Delete),
            1 => Just(SimOp::Compact),
            1 => Just(SimOp::CompactTiers),
            1 => Just(SimOp::Reopen),
        ]
    }

    proptest! {
        #![proptest_config(ProptestConfig::with_cases(512))]
        /// For any sequence of add/delete/compact/compact_tiers/reopen, the live set
        /// equals the reference model and every segment stays within the cap.
        #[test]
        fn live_set_matches_reference_under_random_ops(
            ops in proptest::collection::vec(op_strategy(), 0..200)
        ) {
            let dir = MemoryDirectory::arc();
            let cfg = TierConfig {
                min_merge: 4,
                max_merge: 8,
                max_merged_len: 64,
                ..Default::default()
            };
            let mk = || Options { tiering: cfg, ..Options::new(3) };
            let mut s = SegmentedStore::open_with_options(dir.clone(), Kv, mk()).unwrap();
            let mut model: std::collections::BTreeMap<u32, String> = Default::default();
            let mut live_ids: Vec<u32> = Vec::new();
            let mut next_id = 0u32;
            for op in ops {
                match op {
                    SimOp::Add => {
                        let id = next_id;
                        next_id += 1;
                        let v = format!("v{id}");
                        s.add(id, v.clone()).unwrap();
                        model.insert(id, v);
                        live_ids.push(id);
                    }
                    SimOp::Delete(k) => {
                        if !live_ids.is_empty() {
                            let id = live_ids.swap_remove(k % live_ids.len());
                            s.delete(id).unwrap();
                            model.remove(&id);
                        }
                    }
                    SimOp::Compact => {
                        s.compact().unwrap();
                    }
                    SimOp::CompactTiers => {
                        s.compact_tiers().unwrap();
                    }
                    SimOp::Reopen => {
                        s = SegmentedStore::open_with_options(dir.clone(), Kv, mk()).unwrap();
                    }
                }
                for sz in s.segment_sizes() {
                    prop_assert!(sz <= cfg.max_merged_len);
                }
            }
            let want: Vec<(u32, String)> = model.into_iter().collect();
            prop_assert_eq!(live_set(&s), want);
        }
    }
}