-
Notifications
You must be signed in to change notification settings - Fork 7
/
Copy pathlsm-tree.cabal
1095 lines (967 loc) · 36.4 KB
/
lsm-tree.cabal
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
cabal-version: 3.4
name: lsm-tree
version: 0.1.0.0
synopsis: Log-structured merge-trees
description:
This package contains an efficient implementation of on-disk key–value storage, implemented as a log-structured merge-tree or LSM-tree.
An LSM-tree is a data structure for key–value mappings, similar to "Data.Map", but optimized for large tables with a high insertion volume.
It has support for:
* Basic key–value operations, such as lookup, insert, and delete.
* Range lookups, which efficiently retrieve the values for all keys in a given range.
* Monoidal upserts which combine the stored and new values.
* BLOB storage which assocates a large auxiliary BLOB with a key.
* Durable on-disk persistence and rollback via named snapshots.
* Cheap table duplication where all duplicates can be independently accessed and modified.
* High-performance lookups on SSDs using I\/O batching and parallelism.
This package exports two modules:
* "Database.LSMTree.Simple"
This module exports a simplified API which picks sensible defaults for a number of configuration parameters.
It does not support upserts or BLOBs, due to their unintuitive interaction, see [Upsert and BLOB](#upsertandblob).
If you are looking at this package for the first time, it is strongly recommended that you start by reading this module.
* "Database.LSMTree"
This module exports the full API.
== Upsert and BLOB #upsertandblob#
The interaction between upserts and BLOBs is unintuitive.
A upsert updates the value associated with the key by combining the new and old values with a user-specified function.
However, any BLOB associated with the key is simply deleted.
== Portability #portability#
* This package only supports 64-bit, little-endian systems.
* On Windows, the package has only been tested with NTFS filesystems.
* On Linux, executables using this package, including test and benchmark suites, must be compiled with the [@-threaded@](https://downloads.haskell.org/ghc/latest/docs/users_guide/phases.html#ghc-flag-threaded) RTS option enabled.
== Concurrency #concurrency#
LSM-trees can be used concurrently, but with a few restrictions:
* Each session locks its session directory.
This means that a database cannot be accessed from different processes at the same time.
* Tables can be used concurrently and concurrent use of read operations such as lookups is determinstic.
However, concurrent use of write operations such as insert or delete with any other operation results in a race condition.
== Performance #performance#
The worst-case behaviour of the library is described using [big-O notation](http://en.wikipedia.org/wiki/Big_O_notation).
The documentation provides two measures of complexity:
* The time complexity of operations is described in terms of the number of disk I\/O operations and referred to as the disk I\/O complexity.
In practice, the time of the operations on LSM-trees is dominated by the number of disk I\/O actions.
* The space complexity of tables is described in terms of the in-memory size of an LSM-tree table.
Both the in-memory and on-disk size of an LSM-tree table scale linearly with the number of physical entries.
However, the in-memory size of an LSM-tree table is smaller than its on-disk size by a significant constant.
This is discussed in detail below, under [In-memory size of tables](#performance_size).
The complexities are described in terms of the following variables and constants:
* The variable \(n\) refers to the number of /physical/ table entries.
A /physical/ table entry is any key–operation pair, e.g., @Insert k v@ or @Delete k@, whereas a /logical/ table entry is determined by all physical entries with the same key.
If the variable \(n\) is used to describe the complexity of an operation that involves multiple tables, it refers to the sum of all table entries.
* The variable \(o\) refers to the number of open tables and cursors in the session.
* The variable \(s\) refers to the number of snapshots in the session.
* The variable \(b\) usually refers to the size of a batch of inputs\/outputs.
Its precise meaning is explained for each occurrence.
* The constant \(B\) refers to the size of the write buffer, which is a configuration parameter.
* The constant \(T\) refers to the size ratio of the table, which is a configuration parameter.
* The constant \(P\) refers to the the average number of key–value pairs that fit in a page of memory.
=== Disk I\/O cost of operations #performance_time#
The following table summarises the cost of the operations on LSM-trees
measured in the number of disk I\/O operations.
If the cost depends on the merge policy, the table contains one entry for each merge policy.
Otherwise, the merge policy is listed as N\/A.
+----------+------------------------+----------------------------+------------------------------------------------+
| Resource | Operation | Merge policy | Cost in disk I\/O operations |
+==========+========================+============================+================================================+
| Session | Create\/Open | N\/A | \(O(1)\) |
+----------+------------------------+----------------------------+------------------------------------------------+
| | Close | @MergePolicyLazyLevelling@ | \(O(o \: T \: \log_T \frac{n}{B})\) |
+----------+------------------------+----------------------------+------------------------------------------------+
| Table | Create | N\/A | \(O(1)\) |
+----------+------------------------+----------------------------+------------------------------------------------+
| | Close | @MergePolicyLazyLevelling@ | \(O(T \: \log_T \frac{n}{B})\) |
+----------+------------------------+----------------------------+------------------------------------------------+
| | Lookup | @MergePolicyLazyLevelling@ | \(O(T \: \log_T \frac{n}{B})\) |
+----------+------------------------+----------------------------+------------------------------------------------+
| | Range Lookup | @MergePolicyLazyLevelling@ | \(O(T \: \log_T \frac{n}{B} + \frac{b}{P})\)* |
+----------+------------------------+----------------------------+------------------------------------------------+
| | Insert\/Delete\/Update | @MergePolicyLazyLevelling@ | \(O(\frac{1}{P} \: \log_T \frac{n}{B})\) |
+----------+------------------------+----------------------------+------------------------------------------------+
| | Duplicate | N\/A | \(O(0)\) |
+----------+------------------------+----------------------------+------------------------------------------------+
| | Union | N\/A | \(O(\frac{n}{P})\) |
+----------+------------------------+----------------------------+------------------------------------------------+
| Snapshot | Save | @MergePolicyLazyLevelling@ | \(O(T \: \log_T \frac{n}{B})\) |
+----------+------------------------+----------------------------+------------------------------------------------+
| | Open | N\/A | \(O(\frac{n}{P})\) |
+----------+------------------------+----------------------------+------------------------------------------------+
| | Delete | @MergePolicyLazyLevelling@ | \(O(T \: \log_T \frac{n}{B})\) |
+----------+------------------------+----------------------------+------------------------------------------------+
| | List | N\/A | \(O(s)\) |
+----------+------------------------+----------------------------+------------------------------------------------+
| Cursor | Create | @MergePolicyLazyLevelling@ | \(O(T \: \log_T \frac{n}{B})\) |
+----------+------------------------+----------------------------+------------------------------------------------+
| | Close | @MergePolicyLazyLevelling@ | \(O(T \: \log_T \frac{n}{B})\) |
+----------+------------------------+----------------------------+------------------------------------------------+
| | Read next entry | N\/A | \(O(\frac{1}{P})\) |
+----------+------------------------+----------------------------+------------------------------------------------+
(*The variable \(b\) refers to the number of entries retrieved by the range lookup.)
TODO: Document the average-case behaviour of lookups.
=== In-memory size of tables #performance_size#
The in-memory size of an LSM-tree is described in terms of the variable \(n\), which refers to the number of /physical/ database entries.
A /physical/ database entry is any key–operation pair, e.g., @Insert k v@ or @Delete k@, whereas a /logical/ database entry is determined by all physical entries with the same key.
The worst-case in-memory size of an LSM-tree is \(O(n)\).
* The worst-case in-memory size of the write buffer is \(O(B)\).
The maximum size of the write buffer on the write buffer allocation strategy, which is determined by the @confWriteBufferAlloc@ field of @TableConfig@.
Regardless of write buffer allocation strategy, the size of the write buffer may never exceed 4GiB.
[@AllocNumEntries maxEntries@]:
The maximum size of the write buffer is the maximum number of entries multiplied by the average size of a key–operation pair.
* The worst-case in-memory size of the Bloom filters is \(O(n)\).
The total in-memory size of all Bloom filters is the number of bits per physical entry multiplied by the number of physical entries.
The required number of bits per physical entry is determined by the Bloom filter allocation strategy, which is determined by the @confBloomFilterAlloc@ field of @TableConfig@.
[@AllocFixed bitsPerPhysicalEntry@]:
The number of bits per physical entry is specified as @bitsPerPhysicalEntry@.
[@AllocRequestFPR requestedFPR@]:
The number of bits per physical entry is determined by the requested false-positive rate, which is specified as @requestedFPR@.
The false-positive rate scales exponentially with the number of bits per entry:
+---------------------------+---------------------+
| False-positive rate | Bits per entry |
+===========================+=====================+
| \(1\text{ in }10\) | \(\approx 4.77 \) |
+---------------------------+---------------------+
| \(1\text{ in }100\) | \(\approx 9.85 \) |
+---------------------------+---------------------+
| \(1\text{ in }1{,}000\) | \(\approx 15.79 \) |
+---------------------------+---------------------+
| \(1\text{ in }10{,}000\) | \(\approx 22.58 \) |
+---------------------------+---------------------+
| \(1\text{ in }100{,}000\) | \(\approx 30.22 \) |
+---------------------------+---------------------+
* The worst-case in-memory size of the indexes is \(O(n)\).
The total in-memory size of all indexes depends on the index type, which is determined by the @confFencePointerIndex@ field of @TableConfig@.
The in-memory size of the various indexes is described in reference to the size of the database in [/memory pages/](https://en.wikipedia.org/wiki/Page_%28computer_memory%29).
[@OrdinaryIndex@]:
An ordinary index stores the maximum serialised key for each memory page.
The total in-memory size of all indexes is proportional to the average size of one serialised key per memory page.
[@CompactIndex@]:
A compact index stores the 64 most significant bits of the minimum serialised key for each memory page, as well as 1 bit per memory page to resolve clashes, 1 bit per memory page to mark overflow pages, and a negligable amount of memory for tie breakers.
The total in-memory size of all indexes is approximately 66 bits per memory page.
The total size of an LSM-tree must not exceed \(2^{41}\) physical entries.
Violation of this condition /is/ checked and will throw a 'TableTooLargeError'.
== Implementation
The implementation of LSM-trees in this package draws inspiration from:
* Chris Okasaki.
1998.
\"Purely Functional Data Structures\"
[doi:10.1017/CBO9780511530104](https://doi.org/10.1017/CBO9780511530104)
* Niv Dayan, Manos Athanassoulis, and Stratos Idreos.
2017.
\"Monkey: Optimal Navigable Key-Value Store.\"
[doi:10.1145/3035918.3064054](https://doi.org/10.1145/3035918.3064054)
* Subhadeep Sarkar, Dimitris Staratzis, Ziehen Zhu, and Manos Athanassoulis.
2021.
\"Constructing and analyzing the LSM compaction design space.\"
[doi:10.14778/3476249.3476274](https://doi.org/10.14778/3476249.3476274)
license: Apache-2.0
license-file: LICENSE
author:
Duncan Coutts, Joris Dral, Matthias Heinzel, Wolfgang Jeltsch, Wen Kokke, and Alex Washburn
maintainer: TODO: MAINTAINER EMAIL
copyright:
(c) 2023 Input Output Global, Inc. (IOG)
(c) 2023-2025 INTERSECT
category: Database
build-type: Simple
tested-with:
GHC ==8.10 || ==9.2 || ==9.4 || ==9.6 || ==9.8 || ==9.10 || ==9.12
extra-doc-files: CHANGELOG.md
extra-source-files:
xxhash/include/HsXXHash.h
xxhash/xxHash-0.8.2/xxhash.h
license-files:
bloomfilter/LICENSE-bloomfilter
xxhash/xxHash-0.8.2/LICENSE-xxHash
source-repository head
type: git
location: https://github.com/IntersectMBO/lsm-tree
common warnings
ghc-options:
-Wall -Wcompat -Wincomplete-uni-patterns
-Wincomplete-record-updates -Wpartial-fields -Widentities
-Wredundant-constraints -Wmissing-export-lists
-Wno-unticked-promoted-constructors -Wunused-packages
ghc-options: -Werror=missing-deriving-strategies
common wno-x-partial
if impl(ghc >=9.8)
-- No errors for x-partial functions. We might remove this in the future if
-- we decide to refactor code that uses partial functions.
ghc-options: -Wno-x-partial
common language
-- This is at the top-level so that `cabal check` does not complain.
default-language: Haskell2010
-- For newer GHC's, override Haskell2010 with GHC2021
if impl(ghc >=9.2.1)
default-language: GHC2021
else
-- NOTE: FieldSelectors is not supported on ghc-8.10.7, so it is the only
-- language extension that is missing compared to GHC2021
default-extensions:
BangPatterns
BinaryLiterals
ConstrainedClassMethods
ConstraintKinds
DeriveDataTypeable
DeriveFoldable
DeriveFunctor
DeriveGeneric
DeriveLift
DeriveTraversable
DoAndIfThenElse
EmptyCase
EmptyDataDecls
EmptyDataDeriving
ExistentialQuantification
ExplicitForAll
FlexibleContexts
FlexibleInstances
ForeignFunctionInterface
GADTSyntax
GeneralisedNewtypeDeriving
HexFloatLiterals
ImplicitPrelude
ImportQualifiedPost
InstanceSigs
KindSignatures
MonomorphismRestriction
MultiParamTypeClasses
NamedFieldPuns
NamedWildCards
NoExplicitNamespaces
NumericUnderscores
PatternGuards
PolyKinds
PostfixOperators
RankNTypes
RelaxedPolyRec
ScopedTypeVariables
StandaloneDeriving
StandaloneKindSignatures
StarIsType
TraditionalRecordSyntax
TupleSections
TypeApplications
TypeOperators
TypeSynonymInstances
default-extensions:
DeriveAnyClass
DerivingStrategies
DerivingVia
ExplicitNamespaces
GADTs
LambdaCase
RecordWildCards
RoleAnnotations
ViewPatterns
flag bloom-query-fast
description: Use an optimised Bloom filter query implementation
default: True
manual: True
common bloom-query-fast
if (flag(bloom-query-fast) && impl(ghc >=9.4))
cpp-options: -DBLOOM_QUERY_FAST
library
import: language, warnings, wno-x-partial, bloom-query-fast
hs-source-dirs: src
exposed-modules:
Database.LSMTree
Database.LSMTree.Internal.Arena
Database.LSMTree.Internal.Assertions
Database.LSMTree.Internal.BitMath
Database.LSMTree.Internal.BlobFile
Database.LSMTree.Internal.BlobRef
Database.LSMTree.Internal.BloomFilter
Database.LSMTree.Internal.BloomFilterQuery1
Database.LSMTree.Internal.ByteString
Database.LSMTree.Internal.ChecksumHandle
Database.LSMTree.Internal.Chunk
Database.LSMTree.Internal.Config
Database.LSMTree.Internal.Config.Override
Database.LSMTree.Internal.CRC32C
Database.LSMTree.Internal.Cursor
Database.LSMTree.Internal.Entry
Database.LSMTree.Internal.IncomingRun
Database.LSMTree.Internal.Index
Database.LSMTree.Internal.Index.Compact
Database.LSMTree.Internal.Index.CompactAcc
Database.LSMTree.Internal.Index.Ordinary
Database.LSMTree.Internal.Index.OrdinaryAcc
Database.LSMTree.Internal.Lookup
Database.LSMTree.Internal.Map.Range
Database.LSMTree.Internal.Merge
Database.LSMTree.Internal.MergeSchedule
Database.LSMTree.Internal.MergingRun
Database.LSMTree.Internal.MergingTree
Database.LSMTree.Internal.MergingTree.Lookup
Database.LSMTree.Internal.Page
Database.LSMTree.Internal.PageAcc
Database.LSMTree.Internal.PageAcc1
Database.LSMTree.Internal.Paths
Database.LSMTree.Internal.Primitive
Database.LSMTree.Internal.Range
Database.LSMTree.Internal.RawBytes
Database.LSMTree.Internal.RawOverflowPage
Database.LSMTree.Internal.RawPage
Database.LSMTree.Internal.Readers
Database.LSMTree.Internal.Run
Database.LSMTree.Internal.RunAcc
Database.LSMTree.Internal.RunBuilder
Database.LSMTree.Internal.RunNumber
Database.LSMTree.Internal.RunReader
Database.LSMTree.Internal.Serialise
Database.LSMTree.Internal.Serialise.Class
Database.LSMTree.Internal.Snapshot
Database.LSMTree.Internal.Snapshot.Codec
Database.LSMTree.Internal.Types
Database.LSMTree.Internal.UniqCounter
Database.LSMTree.Internal.Unsafe
Database.LSMTree.Internal.Unsliced
Database.LSMTree.Internal.Vector
Database.LSMTree.Internal.Vector.Growing
Database.LSMTree.Internal.WriteBuffer
Database.LSMTree.Internal.WriteBufferBlobs
Database.LSMTree.Internal.WriteBufferReader
Database.LSMTree.Internal.WriteBufferWriter
Database.LSMTree.Simple
build-depends:
, base >=4.14 && <4.22
, bitvec ^>=1.1
, bytestring ^>=0.11.4.0 || ^>=0.12.1.0
, cborg ^>=0.2.10.0
, containers ^>=0.6 || ^>=0.7
, contra-tracer ^>=0.2
, crc32c ^>=0.2.1
, deepseq ^>=1.4 || ^>=1.5
, filepath
, fs-api ^>=0.3
, io-classes ^>=1.6 || ^>=1.7
, io-classes:strict-mvar
, lsm-tree:blockio-api
, lsm-tree:bloomfilter
, lsm-tree:control
, lsm-tree:kmerge
, primitive ^>=0.9
, text ^>=2.1.1
, vector ^>=0.13
, vector-algorithms ^>=0.9
if (flag(bloom-query-fast) && impl(ghc >=9.4))
-- The bulk bloom filter query uses some fancy stuff
exposed-modules:
Database.LSMTree.Internal.BloomFilterQuery2
Database.LSMTree.Internal.StrictArray
build-depends: data-elevator ^>=0.1.0.2 || ^>=0.2
-- this exists due windows
library xxhash
import: language
visibility: private
include-dirs: xxhash/xxHash-0.8.2/ xxhash/include/
includes:
HsXXHash.h
xxhash.h
exposed-modules: XXH3
if (arch(x86_64) && !os(osx))
-- Cabal doesn't pass cc-options to "ordinary" Haskell source compilation
-- https://github.com/haskell/cabal/issues/9801
ghc-options: -optc=-mavx2 -optc=-O3
other-modules: FFI
hs-source-dirs: xxhash/src
build-depends:
, base <5
, bytestring
, primitive ^>=0.9
test-suite xxhash-tests
import: language
type: exitcode-stdio-1.0
hs-source-dirs: xxhash/tests
main-is: xxhash-tests.hs
build-depends:
, base <5
, bytestring
, lsm-tree:xxhash
, primitive
, tasty
, tasty-hunit
, tasty-quickcheck
-- this fork doesn't work on 32bit systems
library bloomfilter
import: language
visibility: private
hs-source-dirs: bloomfilter/src
build-depends:
, base >=4.5 && <5
, bitvec ^>=1.1.5.0
, bytestring >=0.9
, data-array-byte
, deepseq
, lsm-tree:xxhash
, primitive
, vector ^>=0.13.0.0
exposed-modules:
Data.BloomFilter
Data.BloomFilter.BitVec64
Data.BloomFilter.Calc
Data.BloomFilter.Easy
Data.BloomFilter.Hash
Data.BloomFilter.Internal
Data.BloomFilter.Mutable
Data.BloomFilter.Mutable.Internal
ghc-options: -O2 -Wall
test-suite bloomfilter-tests
import: language
type: exitcode-stdio-1.0
hs-source-dirs: bloomfilter/tests
main-is: bloomfilter-tests.hs
other-modules: QCSupport
build-depends:
, base <5
, bytestring
, lsm-tree:bloomfilter
, QuickCheck
, quickcheck-instances
, random
, tasty
, tasty-quickcheck
, vector
test-suite bloomfilter-primes
import: language
type: exitcode-stdio-1.0
hs-source-dirs: bloomfilter/tests
main-is: primes.hs
build-depends:
, base <5
, primes ^>=0.2.1.0
test-suite bloomfilter-spell
import: language
type: exitcode-stdio-1.0
hs-source-dirs: bloomfilter/examples
main-is: spell.hs
build-depends:
, base
, lsm-tree:bloomfilter
library extras
import: language, warnings
visibility: private
hs-source-dirs: src-extras
exposed-modules:
Database.LSMTree.Extras
Database.LSMTree.Extras.Generators
Database.LSMTree.Extras.Index
Database.LSMTree.Extras.MergingRunData
Database.LSMTree.Extras.MergingTreeData
Database.LSMTree.Extras.NoThunks
Database.LSMTree.Extras.Orphans
Database.LSMTree.Extras.Random
Database.LSMTree.Extras.ReferenceImpl
Database.LSMTree.Extras.RunData
Database.LSMTree.Extras.UTxO
build-depends:
, base >=4.14 && <4.22
, bitvec
, bytestring
, containers
, contra-tracer
, deepseq
, fs-api
, fs-sim
, io-classes:strict-mvar
, io-classes:strict-stm
, lsm-tree
, lsm-tree:blockio-api
, lsm-tree:bloomfilter
, lsm-tree:control
, lsm-tree:kmerge
, lsm-tree:prototypes
, nonempty-containers
, nothunks
, primitive
, QuickCheck
, quickcheck-instances
, random
, vector
, wide-word
test-suite lsm-tree-test
import: language, warnings, wno-x-partial, bloom-query-fast
type: exitcode-stdio-1.0
hs-source-dirs: test
main-is: Main.hs
other-modules:
Database.LSMTree.Class
Database.LSMTree.Class.Common
Database.LSMTree.Model
Database.LSMTree.Model.IO
Database.LSMTree.Model.Session
Database.LSMTree.Model.Table
Test.Database.LSMTree.Class
Test.Database.LSMTree.Generators
Test.Database.LSMTree.Internal
Test.Database.LSMTree.Internal.Arena
Test.Database.LSMTree.Internal.BlobFile.FS
Test.Database.LSMTree.Internal.BloomFilter
Test.Database.LSMTree.Internal.Chunk
Test.Database.LSMTree.Internal.CRC32C
Test.Database.LSMTree.Internal.Entry
Test.Database.LSMTree.Internal.Index.Compact
Test.Database.LSMTree.Internal.Index.Ordinary
Test.Database.LSMTree.Internal.Lookup
Test.Database.LSMTree.Internal.Merge
Test.Database.LSMTree.Internal.MergingRun
Test.Database.LSMTree.Internal.MergingTree
Test.Database.LSMTree.Internal.PageAcc
Test.Database.LSMTree.Internal.PageAcc1
Test.Database.LSMTree.Internal.RawBytes
Test.Database.LSMTree.Internal.RawOverflowPage
Test.Database.LSMTree.Internal.RawPage
Test.Database.LSMTree.Internal.Readers
Test.Database.LSMTree.Internal.Run
Test.Database.LSMTree.Internal.RunAcc
Test.Database.LSMTree.Internal.RunBloomFilterAlloc
Test.Database.LSMTree.Internal.RunBuilder
Test.Database.LSMTree.Internal.RunReader
Test.Database.LSMTree.Internal.Serialise
Test.Database.LSMTree.Internal.Serialise.Class
Test.Database.LSMTree.Internal.Snapshot.Codec
Test.Database.LSMTree.Internal.Snapshot.Codec.Golden
Test.Database.LSMTree.Internal.Snapshot.FS
Test.Database.LSMTree.Internal.Unsliced
Test.Database.LSMTree.Internal.Vector
Test.Database.LSMTree.Internal.Vector.Growing
Test.Database.LSMTree.Internal.WriteBufferBlobs.FS
Test.Database.LSMTree.Internal.WriteBufferReader.FS
Test.Database.LSMTree.Model.Table
Test.Database.LSMTree.Resolve
Test.Database.LSMTree.StateMachine
Test.Database.LSMTree.StateMachine.DL
Test.Database.LSMTree.StateMachine.Op
Test.Database.LSMTree.UnitTests
Test.FS
Test.System.Posix.Fcntl.NoCache
Test.Util.Arbitrary
Test.Util.FS
Test.Util.FS.Error
Test.Util.Orphans
Test.Util.PrettyProxy
Test.Util.QC
Test.Util.QLS
Test.Util.RawPage
Test.Util.TypeFamilyWrappers
build-depends:
, ansi-terminal
, barbies
, base <5
, bitvec
, bytestring
, cborg
, constraints
, containers
, contra-tracer
, crc32c
, cryptohash-sha256
, deepseq
, directory
, filepath
, fs-api
, fs-sim
, io-classes
, io-classes:strict-mvar
, io-classes:strict-stm
, io-sim
, lsm-tree
, lsm-tree:blockio-api
, lsm-tree:blockio-sim
, lsm-tree:bloomfilter
, lsm-tree:control
, lsm-tree:extras
, lsm-tree:prototypes
, mtl
, nothunks
, primitive
, QuickCheck
, quickcheck-classes
, quickcheck-dynamic
, quickcheck-instances
, quickcheck-lockstep
, random
, safe-wild-cards
, semialign
, split
, stm
, tasty
, tasty-golden
, tasty-hunit
, tasty-quickcheck
, temporary
, text
, these
, transformers
, vector
, vector-algorithms
, wide-word
if !os(windows)
build-depends: lsm-tree:fcntl-nocache
ghc-options: -threaded
benchmark lsm-tree-micro-bench
import: language, warnings, wno-x-partial
type: exitcode-stdio-1.0
hs-source-dirs: bench/micro
main-is: Main.hs
other-modules:
Bench.Database.LSMTree
Bench.Database.LSMTree.Internal.BloomFilter
Bench.Database.LSMTree.Internal.Index
Bench.Database.LSMTree.Internal.Index.Compact
Bench.Database.LSMTree.Internal.Lookup
Bench.Database.LSMTree.Internal.Merge
Bench.Database.LSMTree.Internal.RawPage
Bench.Database.LSMTree.Internal.Serialise
Bench.Database.LSMTree.Internal.WriteBuffer
build-depends:
, base <5
, bytestring
, containers
, contra-tracer
, criterion
, deepseq
, directory
, fs-api
, lsm-tree
, lsm-tree:blockio-api
, lsm-tree:bloomfilter
, lsm-tree:control
, lsm-tree:extras
, QuickCheck
, random
, temporary
, vector
ghc-options: -rtsopts -with-rtsopts=-T -threaded
benchmark lsm-tree-bench-bloomfilter
import: language, warnings, wno-x-partial, bloom-query-fast
type: exitcode-stdio-1.0
hs-source-dirs: bench/macro
main-is: lsm-tree-bench-bloomfilter.hs
build-depends:
, base <5
, lsm-tree
, lsm-tree:bloomfilter
, lsm-tree:extras
, random
, time
, vector
, wide-word
ghc-options: -rtsopts -with-rtsopts=-T -threaded
benchmark lsm-tree-bench-lookups
import: language, warnings, wno-x-partial
type: exitcode-stdio-1.0
hs-source-dirs: bench/macro
main-is: lsm-tree-bench-lookups.hs
build-depends:
, base <5
, deepseq
, fs-api
, io-classes
, lsm-tree
, lsm-tree:blockio-api
, lsm-tree:bloomfilter
, lsm-tree:control
, lsm-tree:extras
, primitive
, random
, time
, vector
, vector-algorithms
ghc-options: -rtsopts -with-rtsopts=-T -threaded
library mcg
import: language, warnings, wno-x-partial
hs-source-dirs: src-mcg
exposed-modules: MCG
build-depends:
, base <5
, primes
flag measure-batch-latency
description:
Measure the latency for individual batches of updates and lookups
default: False
manual: True
common measure-batch-latency
if flag(measure-batch-latency)
cpp-options: -DMEASURE_BATCH_LATENCY
benchmark lsm-tree-bench-wp8
import: language, warnings, wno-x-partial, measure-batch-latency
type: exitcode-stdio-1.0
hs-source-dirs: bench/macro
main-is: lsm-tree-bench-wp8.hs
build-depends:
, async
, base <5
, bytestring
, clock
, containers
, contra-tracer
, deepseq
, fs-api
, lsm-tree
, lsm-tree:blockio-api
, lsm-tree:extras
, lsm-tree:mcg
, optparse-applicative
, pretty-show
, primitive
, random
, transformers
, vector
ghc-options: -rtsopts -with-rtsopts=-T -threaded
flag rocksdb
description: Build components that rely on RocksDB (only on Linux)
default: True
manual: False
benchmark rocksdb-bench-wp8
import: language, warnings, wno-x-partial
type: exitcode-stdio-1.0
hs-source-dirs: bench/macro
main-is: rocksdb-bench-wp8.hs
if !((os(linux) && flag(rocksdb)) && impl(ghc >=9.2.0))
buildable: False
build-depends:
, base <5
, binary
, bytestring
, clock
, containers
, cryptohash-sha256
, deepseq
, directory
, lsm-tree:mcg
, lsm-tree:rocksdb
, optparse-applicative
, split
ghc-options: -rtsopts -with-rtsopts=-T -threaded
library rocksdb
import: language, warnings
hs-source-dirs: src-rocksdb
exposed-modules: RocksDB
other-modules: RocksDB.FFI
if !((os(linux) && flag(rocksdb)) && impl(ghc >=9.2.0))
buildable: False
-- Ubuntu 22.04 doesn't have pkgconfig files for rocksdb
extra-libraries: rocksdb
build-depends:
, base <5
, bytestring
, indexed-traversable
library kmerge
import: language, warnings, wno-x-partial
hs-source-dirs: src-kmerge
exposed-modules:
KMerge.Heap
KMerge.LoserTree
build-depends:
, base <5
, indexed-traversable
, primitive
test-suite kmerge-test
import: language, warnings, wno-x-partial
type: exitcode-stdio-1.0
hs-source-dirs: test
main-is: kmerge-test.hs
build-depends:
, base >=4.14 && <4.22
, deepseq
, heaps
, lsm-tree:kmerge
, primitive
, splitmix
, tasty
, tasty-bench
, tasty-hunit
, tasty-quickcheck
, vector
benchmark kmerge-bench
import: language, warnings, wno-x-partial
type: exitcode-stdio-1.0
hs-source-dirs: test
main-is: kmerge-test.hs
cpp-options: -DKMERGE_BENCHMARKS
build-depends:
, base >=4.14 && <4.22
, deepseq
, heaps
, lsm-tree:kmerge
, primitive
, splitmix
, tasty
, tasty-bench
, tasty-hunit
, tasty-quickcheck
, vector
test-suite map-range-test
import: language, warnings, wno-x-partial
type: exitcode-stdio-1.0
hs-source-dirs: test
main-is: map-range-test.hs
build-depends:
, base >=4.14 && <4.22
, bytestring
, containers
, lsm-tree
, QuickCheck
, tasty
, tasty-hunit
, tasty-quickcheck
library prototypes
import: language, warnings, wno-x-partial
hs-source-dirs: prototypes
exposed-modules:
FormatPage
ScheduledMerges
ScheduledMergesTest
ScheduledMergesTestQLS
build-depends:
, base <5
, binary
, bytestring
, constraints
, containers
, contra-tracer
, QuickCheck
, quickcheck-dynamic
, quickcheck-lockstep
, tasty
, tasty-hunit
, tasty-quickcheck
, transformers
ghc-options:
-Wno-incomplete-uni-patterns -Wno-partial-fields
-Wno-missing-export-lists
test-suite lsm-prototypes-tests
import: language, warnings, wno-x-partial
type: exitcode-stdio-1.0
hs-source-dirs: test
main-is: lsm-prototypes-tests.hs
build-depends:
, base
, lsm-tree:prototypes
, tasty
flag serialblockio
description: Use serial HasBlockIO regardless of the operating system
default: False
manual: True
library blockio-api
import: language, warnings, wno-x-partial
visibility: private
hs-source-dirs: blockio-api/src
exposed-modules:
System.FS.BlockIO.API
System.FS.BlockIO.IO
System.FS.BlockIO.Serial
build-depends:
, base >=4.14 && <4.22
, deepseq ^>=1.4 || ^>=1.5
, fs-api ^>=0.3
, io-classes ^>=1.6 || ^>=1.7
, primitive ^>=0.9
, vector ^>=0.13
if os(linux)
hs-source-dirs: blockio-api/src-linux
other-modules: System.FS.BlockIO.Internal
build-depends:
, lsm-tree:fcntl-nocache
, unix ^>=2.8
if !flag(serialblockio)
other-modules: System.FS.BlockIO.Async
build-depends: blockio-uring ^>=0.1
elif os(osx)
hs-source-dirs: blockio-api/src-macos
build-depends:
, lsm-tree:fcntl-nocache
, unix ^>=2.8
other-modules: System.FS.BlockIO.Internal
elif os(windows)
hs-source-dirs: blockio-api/src-windows
build-depends: Win32 ^>=2.14
other-modules: System.FS.BlockIO.Internal
if flag(serialblockio)
cpp-options: -DSERIALBLOCKIO
test-suite blockio-api-test