Remove the limitation on the number of keys.
[ocaml-ancient.git] / README.txt
1 'Ancient' module for OCaml
2 ----------------------------------------------------------------------
3 $Id: README.txt,v 1.3 2006-10-13 12:28:20 rich Exp $
4
5 What does this module do?
6 ----------------------------------------------------------------------
7
8 This module allows you to use in-memory data structures which are
9 larger than available memory and so are kept in swap.  If you try this
10 in normal OCaml code, you'll find that the machine quickly descends
11 into thrashing as the garbage collector repeatedly iterates over
12 swapped memory structures.  This module lets you break that
13 limitation.  Of course the module doesn't work by magic :-) If your
14 program tries to access these large structures, they still need to be
15 swapped back in, but it is suitable for large, sparsely accessed
16 structures.
17
18 Secondly, this module allows you to share those structures between
19 processes.  In this mode, the structures are backed by a disk file,
20 and any process that has read/write access that disk file can map that
21 file in and see the structures.
22
23 To understand what this module really does, you need to know a little
24 bit of background about the OCaml garbage collector (GC).  OCaml's GC
25 has two heaps, called the minor and major heaps.  The minor heap is
26 used for short-term storage of small objects which are usually created
27 and then quickly become unreachable.  Any objects which persist longer
28 (or objects which are very big to start with) get moved into the major
29 heap.  Objects in the major heap are assumed to be around for some
30 time, and the major heap is GC'd more slowly.
31
32 This module adds a third heap, called the "ancient heap", which is
33 never checked by the GC.  Objects must be moved into ancient manually,
34 using a process called "marking".  Once an object is in the ancient
35 heap, memory allocation is handled manually.  In particular objects in
36 the ancient heap may need to be manually deallocated.  The ancient
37 heap may either exist as ordinary memory, or may be backed by a file,
38 which is how shared structures are possible.
39
40 Structures which are moved into ancient must be treated as STRICTLY
41 NON-MUTABLE.  If an ancient structure is changed in any way then it
42 may cause a crash.
43
44 There are some limitations which apply to ancient data structures.
45 See the section "Shortcomings & bugs" below.
46
47 This module is most useful on 64 bit architectures where large address
48 spaces are the norm.  We have successfully used it with a 38 GB
49 address space backed by a file and shared between processes.
50
51 API
52 ----------------------------------------------------------------------
53
54 Please see file ancient.mli .
55
56 Compiling
57 ----------------------------------------------------------------------
58
59   cd mmalloc && ./configure
60   make
61
62 Make sure you run this command before running any program which
63 uses the Ancient module:
64
65   ulimit -s unlimited
66
67 Example
68 ----------------------------------------------------------------------
69
70 Run:
71
72   ulimit -s unlimited
73   wordsfile=/usr/share/dict/words
74   baseaddr=0x440000000000               # System specific - see below.
75   ./test_ancient_dict_write.opt $wordsfile dictionary.data $baseaddr
76   ./test_ancient_dict_verify.opt $wordsfile dictionary.data
77   ./test_ancient_dict_read.opt dictionary.data
78
79 (You can run several instances of test_ancient_dict_read.opt on the
80 same machine to demonstrate sharing).
81
82 Shortcomings & bugs
83 ----------------------------------------------------------------------
84
85 (0) Stack overflows are common when marking/sharing large structures
86 because we use a recursive algorithm to visit the structures.  If you
87 get random segfaults during marking/sharing, then try this before
88 running your program:
89
90   ulimit -s unlimited
91
92 (1) Ad-hoc polymorphic primitives (structural equality, marshalling
93 and hashing) do not work on ancient data structures, meaning that you
94 will need to provide your own comparison and hashing functions.  For
95 more details see Xavier Leroy's response here:
96
97 http://caml.inria.fr/pub/ml-archives/caml-list/2006/09/977818689f4ceb2178c592453df7a343.en.html
98
99 (2) Ancient.attach suggests setting a baseaddr parameter for newly
100 created files (it has no effect when attaching existing files).  We
101 strongly recommend this because in our tests we found that mmap would
102 locate the memory segment inappropriately -- the basic problem is that
103 because the file starts off with zero length, mmap thinks it can place
104 it anywhere in memory and often does not leave it room to grow upwards
105 without overwriting later memory mappings.  Unfortunately this
106 introduces an unwanted architecture dependency in all programs which
107 use the Ancient module with shared files, and it also requires
108 programmers to guess at a good base address which will be valid in the
109 future.  There are no other good solutions we have found --
110 preallocating the file is tricky with the current mmalloc code.
111
112 (3) The current code requires you to first of all create the large
113 data structures on the regular OCaml heap, then mark them as ancient,
114 effectively copying them out of the OCaml heap, then garbage collect
115 the (hopefully unreferenced) structures on the OCaml heap.  In other
116 words, you need to have all the memory available as physical memory.
117 The way to avoid this is to mark structures as ancient incrementally
118 as they are created, or in chunks, whatever works for you.
119
120 We typically use Ancient to deal with web server logfiles, and in this
121 case loading one file of data into memory and marking it as ancient
122 before moving on to the next file works for us.
123
124 (4) Why do ancient structures need to be read-only / not mutated?  The
125 reason is that you might create a new OCaml heap structure and point
126 the ancient structure at this heap structure.  The heap structure has
127 no apparent incoming pointers (the GC will not by its very nature
128 check the ancient structure for pointers), and so the heap structure
129 gets garbage collected.  At this point the ancient structure has a
130 dangling pointer, which will usually result in some form of crash.
131 Note that the restriction here is on creating pointers from ancient
132 data to OCaml heap data.  In theory it should be possible to modify
133 ancient data to point to other ancient data, but we have not tried
134 this.
135
136 (5) [Limit on number of keys -- issue fixed]
137
138 (6) [Advanced topic] The _mark function in ancient_c.c makes no
139 attempt to arrange the data structures in memory / on disk in a way
140 which optimises them for access.  The worst example is when you have
141 an array of large structures, where only a few fields in the structure
142 will be accessed.  Typically these will end up on disk as:
143
144   array of N pointers
145   structure 1
146   field A
147   field B
148     ...
149   field Z
150   structure 2
151   field A
152   field B
153     ...
154   field Z
155   structure 3
156   field A
157   field B
158     ...
159   field Z
160    ...
161    ...
162    ...
163   structure N
164   field A
165   field B
166     ...
167   field Z
168
169 If you then iterate accessing only fields A, you end up swapping the
170 whole lot back into memory.  A better arrangement would have been:
171
172   array of N pointers
173   structure 1
174   structure 2
175   structure 3
176     ...
177   structure N
178   field A from structure 1
179   field A from structure 2
180   field A from structure 3
181     ...
182   field A from structure N
183   field B from structure 1
184   field B from structure 2
185     etc.
186
187 which avoids loading unused fields at all.  In some circumstances we
188 have shown that this could make a huge difference to performance, but
189 we are not sure how to implement this cleanly in the current library.
190
191 (7) [Advanced topic] Certain techniques such as Address Space
192 Randomisation (http://lwn.net/Articles/121845/) are probably not
193 compatible with the Ancient module and shared files.  Because the
194 ancient data structures contain real pointers, these pointers would be
195 invalidated if the shared file was not mapped in at precisely the same
196 base address in all processes which are sharing the file.
197
198 One solution might be to use private mappings and a list of fixups.
199 In fact, the code actually builds a list of fixups currently while
200 marking, because it needs to deal with precisely this issue (during
201 marking, memory is allocated with realloc which might move the memory
202 segment, thus real pointers cannot be stored while marking, but need
203 to be fixed up afterwards).  The list of fixups would need to be
204 stored alongside the memory segment (currently it is discarded after
205 marking), and the file would need to be mapped in using MAP_PRIVATE
206 (see below).
207
208 A possible problem with this is that because OCaml objects tend to be
209 small and contain a lot of pointers, it is likely that fixing up the
210 pointers would result in every page in the memory segment becoming
211 dirty, which would basically cancel out any benefit of using shared
212 mappings in the first place.  However it is likely that some users of
213 this module have large amounts of opaque data and few pointers, and
214 for them this would be worthwhile.
215
216 (8) Currently mmalloc is implemented so that the file is mapped in
217 PROT_READ|PROT_WRITE and MAP_SHARED.  Ancient data structures are
218 supposed to be immutable so strictly speaking write access shouldn't
219 be required.  It may be worthwhile modifying mmalloc to allow
220 read-only mappings, and private mappings.
221
222 (9) The library assumes that every OCaml object is at least one word
223 long.  This seemed like a good assumption up until I found that
224 zero-length arrays are valid zero word objects.  At the moment you
225 cannot mark structures which contain zero-length arrays -- you will
226 get an assert-failure in the _mark function.
227
228 Possibly there are other types of OCaml structure which are zero word
229 objects and also cannot be marked.  I'm not sure what these will be:
230 for example empty strings are stored as one word OCaml objects, so
231 they are OK.
232
233 The solution to this bug is non-trivial.
234
235 Authors
236 ----------------------------------------------------------------------
237
238 Primary code was written by Richard W.M. Jones <rich at annexia.org>
239 with help from Markus Mottl, Martin Jambon, and invaluable advice from
240 Xavier Leroy and Damien Doligez.
241
242 mmalloc was written by Mike Haertel and Fred Fish.
243
244 License
245 ----------------------------------------------------------------------
246
247 The module is licensed under the LGPL + OCaml linking exception.  This
248 module includes mmalloc which was originally distributed with gdb
249 (although it has since been removed), and that code was distributed
250 under the plain LGPL.
251
252 Latest version
253 ----------------------------------------------------------------------
254
255 The latest version can be found on the website:
256 http://merjis.com/developers/ancient