diff options
| -rw-r--r-- | camel/ChangeLog | 5 | ||||
| -rw-r--r-- | camel/devel-docs/camel-index.txt | 407 |
2 files changed, 412 insertions, 0 deletions
diff --git a/camel/ChangeLog b/camel/ChangeLog index c2b7d9d9c3..fbfe9c60ce 100644 --- a/camel/ChangeLog +++ b/camel/ChangeLog @@ -1,3 +1,8 @@ +2002-04-19 Not Zed <NotZed@Ximian.com> + + * devel-docs/camel-index.txt: Start of a white-paperish document + describing camel-index and older libibex. + 2002-04-18 Not Zed <NotZed@Ximian.com> * providers/local/camel-local-store.c (rename_folder): If we get a diff --git a/camel/devel-docs/camel-index.txt b/camel/devel-docs/camel-index.txt new file mode 100644 index 0000000000..0ebc250db0 --- /dev/null +++ b/camel/devel-docs/camel-index.txt @@ -0,0 +1,407 @@ + +The history of text-indexing in evolution. + +CamelTextIndex was written to address several shortcomings in the +existing libibex (referred to as libibex2), which had been written to +address shortcomings in the original libibex. + +Mail indexing characteristics + +First, i'll cover some of the scenarios that a mail indexing system +must cover. They are slightly different from other indexing systems, +at least we wanted them to be. + +1. Indexing a few new messages, they may potentially reference most of + the alphabet in the index. +2. Indexing a whole mailbox for the first time +3. Unindexing anywhere from a few to all existing messages during expunge. +4. Searching. + +Cases 1, 3, and 4 occur the most often, however 2 is the most noticeable +at first use, or if the index must be reset. So the code needs to +work fast in all cases, which generally leads to trade-offs being +made. Each implementation aimed to address or ignore these +requirements in different ways, with the final implementation probably +having the best balance so far. + +The main issue is that the indexing be performed real time. We index +as we add the messages. We index before we open the mailbox. We +index as we remove messages. Because of this we need to approach +things differently to many other indexing systems; most of which work +with static data in an off-line mode. This allows them to index the +whole body of content and use as much memory and cpu time as required. + +We probably need to look at doing offline, or at least delayed +indexing in the future - but this introduces some coherency problems +with vFolders and any body searches. However, having the indexing +library a base part of Camel helps in implementing a mechanism to +achieve this. + +Ibex the first + +The original ibex used a memory-based hash table to store words. This made +the index very fast for both lookups and modifications. However any +queries required a full load of the index into memory, and any updates +required a full write of the index to disk. After about 5-10 000 +messages occasionaly adding to the index became appreciably slower as +the whole index needed to be loaded into memory first. This obviously +took a toll on memory as well. + +I wont cover the algorithms used, they were all pretty basic, the only +real smarts were that index deletes were only flagged and that data +not written to disk when the index saved. + +Evolution 1.x, ibex 2. + +In an attempt to rectify the incremental update performance of +libibex, it was completely rewritten to use an on-disk block-based +filesystem. + +Note: the first attempt used libdb - however performance was so slow +and the indices were so large it was dropped in favour of a custom +filesystem-like data file. + +The motivation was that a few extra disk lookups during +retrieval wouldn't be noticeably slower, however it should be able to +scale up to many more messages with lower memory overhead and slower +startup time. + +The block filesystem contains 3 major components: + +1. A hash table that mapped message's to a word id sequence list. +2. A hash table that mapped word's to a message id sequence list. +3. A sequence filesystem that stored sequences of id's. + +The id's are 32 bit identifiers that are unique for each word or +message. They are also designed to be reversible and static. +That is, given the id, you can map it to the string identifier that it +represents directly, without having to look it up in the hash table. + +Other features of this design is that the database file should be +kept in sync at all times with the state of the index. The message to +wordid tables are used to remove the messageid's from the word's it +contains when the message is expunged, and so on. + +Indexing operation + +The indexing operation consists of the basic steps: + +1. Lookup the messageid from the message name, using the messageid table. +2. Generate a list of words in the message +3. For each word: +4. Lookup the wordid and sequence information +5. If the word doesn't exist, create a new word/wordid +6. Add the messageid to the word sequence. +7. Add the wordid to the message sequence. + +The initial implementation only used caching at the disk-block level. +Unfortunately, the simple hash table design chosen (fixed sized base +table with chained buckets) scaled very poorly above about 10 000 +messages. So this approach proved to be too i/o intensive for +practical use, and several other caches were added to improve +performance: + +1. Stage (1) above is done entirely in memory. At initial startup + the whole list of potential names is read into an in-memory hash + table. +2. Stage (4) above is also done entirely in memory. Even a large + cache provided little benefit due to wide distribution of potential + words. This cache is only created when adding to the index. +3. Stage (6) uses the table from stage (4) and concatenates upto + approximately one disk blocks worth of messageid's before writing + them out to the word sequence. +4. Stage (7) concatenates all wordid's for a given message before + writing them out at once. + +As you can see, the added complexity meant we nearly have to cache as +much as the original version! This also almost removed all of the +startup-time benefit for incremental update of the index, as the table +was not stored as compactly on disk as the original version. + +However, we only ever stored a subset of the index in memory, and only +during updates, with some tricks to reduce memory usage for very rare +words, so the overall memory use was still much lower. + +Removing a message + +Removing a message is fairly involved: + +1. Lookup the messageid and word sequence list from the messageid table. +2. For each wordid in the sequence list +3. Lookup the message sequence list directly from the wordid table. +4. Scan each block in the sequence, and remove any instances of the + messageid. +5. Remove the message to messageid mapping in the messageid table. + +Unfortunately caching helped very little here, particularly if many +messages were removed. Also note that the file could never shrink as +the data could be spread randomly over it. Removal is an extremely +expensive an unbounded process. Deleting all of the messages in a +mailbox is extremely i/o intensive, with blocks potentially being +accessed dozens of times. + +Performing a query + +Performing a query is fast: + +1. Lookup the messageid sequence list from the wordid table. +2. For each messageid +3. Lookup the message name directly from the messageid table. + +Even without caching this performs at a very acceptable level. + +Summary + +This index performs reasonably well upto about 10 000 messages for a +complete re-index. However with incremental updates it degrads much +faster, only a few thousand messages added and it becomes tiresomely +slow and i/o bound. The index becomes more fragmented with random +updates and removals and heavily bogs down the system as you go much +beyond those few thousand messages. + +The code is also very complicated and hard to follow. There are too +many special cases, and it is buggy. Detected on-disk structure +errors result in the index being reset, which although it shrinks the +index, is very slow. + +The indices created are bulky, and never shrink. Because of the +reverse index used for message removal, there is 50% redundant data at +all times. Some overly tricky techniques (very much like ReiserFS's +tail packing) are used to waste as little space as possible, with a +great impact on performance. + +One other problem is that because the index is disk based, we +use a file descriptor continuously. With some users having +>100 folders, they quickly run out of process file descriptors and +evolution fails. To get around this a cache of least recently used +index files is used to flush away and free file descriptors so they +can be re-used. This makes it hard to lock the files; this problem +still exists with the next implementation. + +Anyway, a better solution is required. + +CamelIndex + +The first problem to address was the api. It was starting to age. +Although adequate, the api wasn't terribly clean, reusable, or +scalable. The first thing was to objectise the library, and since we +needed to use it in Camel, the best way was to create a CamelObject. + +CamelIndex was born. A mostly abstract class that provides a simple +common interface for accessing indices, including cursors and utility +and maintenance functions. + +In addition, a number of the features in libibex2 were simplified or +rewritten and abstracted into the re-usable classes that follow. + +By providing simple cursors, more complex queries were easier to write +and can execute more efficiently; camel searching now does sub-string +searches for all body queries, and still runs at a very healthy speed +and uses less memory than before. + +CamelBlockFile + +This is basically the same block filesystem used in libibex2. It +handles disk i/o based on blocks (CamelBlock), flushing modified +blocks to disk, and caching of recently accessed blocks. It was +enhanced slightly to allow blocks to be locked in memory. + +CamelKeyFile + +This is a simple reverse-linked list of sequences of keyid's. + +The main property of this file is that updates are only ever appended +to the end of the file, which improves i/o characteristics markedly. + +When an existing keyid sequence is updated, it simply points back to +the start of the previous one, and provides a pointer to the new +entry. i.e. a simple linked list. + +CamelKeyTable + +This is taken from the libibex2 code for mapping keys, with few +changes. It uses a CamelBlockFile for its i/o. + +The key table is a linked list of blocks (CamelKeyBlock) which contain +key strings and and a data pointer and flags for each key. Each block +is a packed array of string descriptors (CamelKeyKey's). + +A keyid (camel_key_t) is a 32 bit descriptor which identifies this key +in a reversible way. In this case the bottom 10 bits are used to +identify the index of the key within the key block, and the top 22 +bits are used to identify the key block itself. In this way, given +the 32 bit key id, we can reference the block containing the key +directly (with at most 1 access), and access the flags and key string +using the key index. + +Keys can potentially be removed and their keyid's reused by simply +re-packing the key block. This was used in libibex2, but not in +CamelIndex. + +[diagram - camelkeyblock] + +CamelPartitionTable + +An implementation of a scalable, on-disk 'perfect' hash table. It +uses the CamelBlockFile to handle its i/o. This is a completely new +hash table implementation which was not present in libibex2. + +[FIXME: Reference the original paper the algorithm is based on.] + +A partition table consists of a list of mapping blocks +(CamelPartitionMapBlock), which is a compact table that maps a range +of hashid's to a partition block (CamelPartitionKeyBlock), which +contains hashid's of that range. + +[diagram - camelpartitiontable] + +The partition block only maps the hashid to a keyid (see CamelKeyTable) +which means it can store a lot of keys in each block. + +To add a new value to the partition table: + +1. Calculate the hash value of the key +2. Find out which partition block the key will fit into, using the + partition table. +3. If the partition block is full: +4. If there is room in the next or previous block: +5. Merge the 2 blocks together, and split at the half-way point +6. Update the partition table hash indices to match the blocks +7. Else +8. Create a new block, and split the existing block across it +9. Insert the new block into the partition table +10. Else +11. Just add the key to the end of the block. + +Steps 5 and 8 perform a sorting of the partition key entries by hashid +to find the midpoint. It may be beneficial to store the hashid's +sorted always, it would then not require a sort to split the blocks. +This would also benefit key lookups by being able to use a binary +search. However, the incremental sort may be more expensive. + +If the partition table itself fills up, then perform a similar +splitting function on its blocks, and store it over multiple blocks. +With a block size of 1024 bytes, we can fit 127 blocks pointers, each +with 127 keys in it - around 16000 keys. So we only need 1024 bytes +of memory for each 16000 on-disk keys (assuming full tables). + +Removal is basically the same, but if we end up with an empty block we +just remove it from the partition table. CamelTextIndex doesn't +actually use removal although it is implemented in +CamelPartitionTable. + +Lookup is very simple. We basically follow steps 1 and 2, and then +perform a linear search through the block to find a matching hash id. +That is our key. This is assuming a perfect hash, additionally the +code could use the keyid to lookup in a keytable to verify the key is +indeed the right one. This would require having to support duplicate +hashid's and would make block splitting slightly more complex, but +only by a couple of lines of code. This is something that will +probably have to be addressed in the future. + +Using a partition table means that we can tell with 1 disk access +whether or not a key exists (assuming a perfect hash function), and 1 +more access to look up all of the details of the key since the keyid +is reversible. Another feature is that the partition table is always +self-balancing for any data processed in any order. + +Yet one more feature is that it is quite easy to order the writes to +the partition table so that its structure is always consistent, even +in the event of program failure. Although this has been disabled in +the current code to take maximal advantage of the block cache. + +CamelTextIndex + +CamelTextIndex is the implementation of CamelIndex now used by camel +for indexing mail. It shares some features with the second +incarnation of libibex, but is generally simpler. It uses the +previously described classes to implement the CamelIndex interface. + +Indexing operation + +Indexing operation is similar to libibex2, but without the requirement +to maintain the reverse index. + +1. Lookup the messageid from the message name, using the messageid + partition table. +2. Generate a list of words in the message +3. For each word +4. Lookup the wordid and sequence information. +5. Append the messageid to the word sequence. + +In practice we also have a word cache which caches upto 32 messageid's +for each word before it is written to the key file. + +Removing a message + +Removal is not immediate. This is one of the major performance +improvements in CamelIndex. + +1. Lookup the messageid from the message name partition table +2. Use the messageid to set a flag in the message key table to + indicate the message has been deleted. +3. Remove the key hash from the partition table. + +This comes down to a maximum of 2 disk reads and 2 disk writes. +libibex2 had unbounded maximums, depending on the number of words in a +given message. The key file is not changed. + +Because data is not removed from the files at all, an additional +optional step is required, that of compressing the indices. + +Performing a query + +Performing a query is much the same as with libibex2. We usually have +slightly less disk i/o because of a more efficient and scalable hash +table implementation, and improved locality of reference of the key +table data. + +1. Lookup the messageid from the message name partition table +2. Use the messageid to get the data pointer directly from the key + table. +3. Iterate through the key file, reading blocks backwards through the + file. + +Compressing + +Although it could have benefited from it, libibex2 did not ever +compress indices - the only way to compress an index was to remove it +and have it be rebuilt. + +CamelIndex requires a compression stage as data is never removed from +it otherwise. Because of the much greater locality of reference, the +compression stage is actually much faster than an incremental removal +of data inside the data files. + +Compressing comprises the following steps: + +1. Open a new temporary index, an index block file and an index key + file. +2. For each message in the message partition table +3. If the message is not marked deleted, add it to the new message + partition table, and recored the old messageid to new messageid + mapping. +4. For each word in the word partition table +5. For each messageid's in the word sequence list +6. If the messageid maps to a new messageid, remap the messageid, + else discard it. +7. Concatenate upto 256 messageid's in a row before writing to the + key file, to improve lookups. +8. Create a new word in the new word key table +9. Add the wordid and new sequence id to the word partition table. + +Note that at step 8 we could (should?) also check if the word has any +messages associated with it, and discard the word from the new index. + +After compression, the name partition index only contains names which +are not deleted, and the key file is compressed into larger blocks +which takes up less space and is faster to retrieve. + +During index operations a number of statistics are taken which trigger +an automatic compress when the file fragmentation or number of deleted +messages exceed a threshold. So the index maintains itself, and does +not need manual compression. + + + + |