[Haskell] [Haskell-cafe] ANNOUNCE: btree-concurrent

[Alberto G. Corona]

Hi.
That´s fine. I missed an implementation of a  persistent b-tree in haskell.
I planned to do my own, but it is not trivial task.

how the IO and STM is managed? . The serialization- deserialization is
automatic  or programmer must write the cached blocks?  (i suppose that the
block reads are automatic on data requests).

The state in the disk is coherent at every moment?. I mean, if there is a
program failure, the state in the btree in the file would be coherent?

For example, if I write two TVars in two different blocks within the same
STM transaction, do I have the guarantee that either both updated values
will be in the file storage or none of them  will be?


Alberto


2012/10/30 Johan Brinch <brinchj at gmail.com>

> Greetings Haskellers,
>
> We are pleased to announce this new package, featuring a concurrent
> b-tree developed as part of our master's thesis on backup systems. The
> package features code related to STM, caching, QuickCheck and of
> course concurrency and parallelism.
>
> And it's also on Hackage:
> http://hackage.haskell.org/package/btree-concurrent
>
> In case the build fails on Hackage and the documentation doesn't work,
> it's also available here:
> http://hindsight.dk/doc/html/btree-concurrent
>
>
> Credits to Thomas Conway of Melbourne University, for discussions
> related to the implementation, and to our supervisor Ken Friis Larsen
> of University of Copenhagen.
>
>
> And now, the description of the package:
> =====
>
> A backend agnostic, concurrent BTree with relaxed balance[1] written
> in Haskell using a mix of IO operations and pure STM.
>
> Although the code does work, it is neither production-ready nor complete.
>
> Features include:
> * Caching: While nodes are periodically saved on persistent storage
> (e.g. disk) they are cached in-memory during operations.
>
> * Live flushing: It is possible to save the current version of the
> tree to disk and run modifying operations at the same time. The nodes
> are updated buttom-up to ensure a valid tree in the case of a crash.
>
> * Backend agnosticism: A simple API is used as an abstraction for the
> persistent storage.
>
> * Verification: The test-suite uses QuickCheck to compare the trees
> behaviour to that of Data.Map.
>
> Deficients include:
> * Memory greedy. Nodes are not stored in a compact fashion and are
> constantly being serialised/deserialised.
>
> * findMin and findMax are incomplete and may fail (see the TODO for
> details).
>
> * The implementation does not parallelise well.
>
>
> [1] B-trees with relaxed balance, K. S. Larsen & R. Fagerberg,
> Parallel Processing Symposium, 1995. Proceedings., 9th International
>
> --
> Johan Brinch & Morten Brøns-Pedersen
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>



-- 
Alberto.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell/attachments/20121030/9b5b874d/attachment.htm>