On 8/21/07, Ben
some basic questions: you have limits on key and value size? fixed page sizes per tree?
I have chosen Yes and Yes respectively, though these are *choices*. Personally, I think fixed sized pages are fine. Handling unlimited sized keys is not hard, especially if you think they will be rare: you use a bit to flag an immediate key vs a remote key, and keep an overflow file for long keys. Another idea that I've had, though I have not had the opportunity to implement it is to use arithmetic coding on the keys. If you carve up the zero-to-one interval in sorted order, then the arithmetic coded bitstrings sort (lexicographically) in the same order as the uncompressed strings. From the top of my head, most *english* words can compress in this fashion with a 0 order model to about 2-3 bits per character. This doesn't eliminate a key length by itself, but it should increase the limit dramatically in practice. My implementation uses 64K pages, with a limit of 32K - 8 bytes on the size of an individual key.
on point 2: it sounds like you'r suggesting using STM after all. not sure if i understand what you've said:
something like type PagePtr t = TVar (Address, Maybe t) data Node = Node (PagePtr Node) [(Key,PagePtr Node)] | Leaf [(Key,Data)]
work with a page cache. do the various b-tree algorithms in STM transactions on the cached pages. retry STM transactions when pages aren't loaded. on successful STM transaction completion, write out the dirty pages.
Yes, except you might want to be clever about flushing dirty pages more lazily. My implementation isn't crash-proof (i.e. doesn't support crash recovery - the environment in which my code operated means that if something bad happens, I can rebuild from external data).
probably use the trick where the STM transaction returns an IO action which you then perform. probably use ordinary page-level locks to deal with concurrency on IO -- STM doesn't help.
Maybe. See the SPJ video on STM. His basic point is that STM helps get rid of the stupid concurrency bugs, leaving just the "more interesting" ones for you to deal with. :-) Actually, using relaxed balance and making all the tree updates local, means that my btree code successfully supports a very high degree of concurrency.
as far as implementing the page cache: using a TVar Map would essentially be creating a global lock on the entire cache.
Exactly, which is why you want to push the TVars down.
so you suggest using other implementations. your suggestion sounds like an array with linear search, or probably something more sophisticated. i would imagine a balanced binary tree where the nodes are TVars might work nice, though rebalacing would touch a lot of nodes. (it does seem strange haskell doesn't have more concurrent data structures.)
Yes, I've chatted with Andrew Bromage about the need for Data.Map.Concurrent Data.Set.Concurrent etc. I have a concurrent hash table which works very nicely. Think class Hashable t where hash :: t -> Word64 type HashTable k v = TArray Word64 [(k,v)] Another alternative that others have suggested are Tries (radix trees). Something along the lines: type Trie v = .... insert :: [Bit] -> v -> Trie v -> STM ()
on point 1: you're saying relaxed balance is better for STM-style optimistic transactions? i'm using
B-Trees with Relaxed Balance (1993) Kim S. Larsen, Rolf Fagerberg IPPS: 9th International Parallel Processing Symposium
Yes. There's a tech report version which includes details of deletion which IIRC the one you mention does not. citeseer... google.... The reason I believe relaxed balance works particularly well with STM is that all the operations (insert, delete, rebalance) operate *locally*. That is, they only modify a single node or a couple of proximate nodes. In STM terms, this means a given operation only *writes* a couple of TVars close to where the operation took place. One of the cool things is that Larsen et al prove that as you progress up the tree the number of rebalancing operations drops geometrically. Effectively, this means you very rarely need to get a write-lock on the root (or top few nodes) of the tree, so randomly dispersed operations are unlikely to conflict with one another. Also, by separating the insert/delete bits from the rebalance bits, both are simpler to code, and you have fewer edge cases to think about. cheers, T -- Dr Thomas Conway drtomc@gmail.com Silence is the perfectest herald of joy: I were but little happy, if I could say how much.