Version française
Home     About     Download     Resources     Contact us    
Browse thread
Long-term storage of values
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: -- (:)
From: Berke Durak <berke.durak@e...>
Subject: Re: [Caml-list] Long-term storage of values
Gabriel Kerneis a écrit :
> Hello,
> 
> Le Thu, 28 Feb 2008 20:14:27 -0500 (EST), Brian Hurt <bhurt@spnz.org> a
> écrit :
>> So, mistake number one: either use the data, and structure your data
>> (at that layer) to take advantage of it, or don't use a database.
>> [...]
>> So that's mistake number two: you're communicating between different 
>> versions of the program with an ill-defined (at best) and not 
>> generic protocol/file format.
> 
> Right. But imagine you're communicating with yourself (saving and
> restoring data). And you need to retrieve the data *efficiently*.
> Converting from a generic file format is not efficient - not if you have
> to retrieve the data 100 times per second (imagine a CMS on a popular
> website). It would be faster to use an internal file format. And, of
> course, keeping a backup in a generic file format.
> 
> But now, here is the big deal: when your internal data structure
> changes (and it might not even be under your control, imagine you're
> using a third-party library), you have to convert your generic backup
> to the newer internal format. And if you have, say, an awful lot of
> backups, it might take soooo long... Of course, it's only once in a
> while, but when this happens, how do you deal with it? Remember the
> efficiency is the key point, here.
> 
> I don't think there is a generic solution to this problem. But I'm just
> pointing out the underlying requirements, in case some would have one.
> 
> Regards,

I had exactly those kinds of issues during my work at the EDOS project.
We were basically treating the metadata for every dat of every component
of every architecture of every Debian distribution.

I started using SQL.  I first tried MySQL then PostgreSQL.
Fill performance was bad.  (And didn't get fast enough when Jaap added
prepared statements for postgresql).
Query performance was worse, because we were interested in things like
the transitive dependency closure, and SQL is
well-known to not be suitable for such transitive properties.  Maybe I
should have tried Sqlite but I didn't know it at the time.

I then switched to marshalling.  Boy, that was fast!  Of course I got
bitten very hard by segmentation faults...  sorry, Xavier, for bothering
you about such stupidity.  And yes, I had a version number in my datastructures
but, no, it was not automatically updated.

Also, adding a field was really, really painful.  Marshalling could work when
your data structures are stable, but during development, it is painful,
especially if you can't use a toy data set for development.

I then built an I/O combinator library.  Of course, combinators already
exist for defining parsers and printers, but I thought that it would be
great to combine them both.  (Such an idea has been presented at POPL
under the term of "picklers" if I recall correctly.)

Basically you describe your types using "literates" which can then be used
for reading and writing, as in

   type my_litterate = io_pair (io_list io_int) (io_hasthbl io_int io_string)

Anyway, that led to the "IO" module available here

   http://caml.inria.fr/cgi-bin/hump.en.cgi?contrib=537

and a better version still lives in the EDOS codebase, which is now
maintained by Jaap Boender.  I think Jaap made a GODI package for it.

IO can use multiple backends (binary, ASCII) and that was quite useful.
Performance is reasonably good.  One problem is with records and sum types -
you have to give pattern-matching functions to define readers/writers for them.
However, you can decide how you handle missing values or extra fields.

Martin Jambon's JSON wheel could also be used here, but I'm waiting for
the preprocessor situation to stabilize a little bit...

One major drawback of IO is that it does not handle sharing or recursive
structures.  And I know of no efficient, type-safe way of handling those,
especially if you don't want the serializer to add extra sharing (for instance
if you have distinct mutable records with the same contents)

I am still thinking about these problems.  For instance, I have been recently
working on Wikipedia revision history (only the Turkish (15 GB) and French ones
(200 GB), the English one is too big).  I needed maximal efficiency so I used Marshal, which was pretty
fast.  Of course I added a small version header.

I noticed that when you Marshal a closure, the module puts a MD5 of
presumably the whole program in the output (which costs some bytes but that's
another problem.)

It would be nice to have a mechanism for marshalling a value with an MD5 of its
types, and unmarshalling only then the MD5 matches.  In non-malicious environments,
that is, in environments where no-one fakes MD5s, that would be quite safe.

Of course it won't be possible to marshal polymorphic types.

So, I'm asking the experts: is it possible to have a very small extension that would allow this?
We could have the following restrictions and it still would be very useful:

   - the type t must be defined in a module M, which must live in a separate compilation unit
     (i.e. have an available cmi)
   - the type t must be ground
   - the type t must be named in an interface
   - it must be explicitly named when marshalling/unmarshalling
   - this is an ugly hack that only works in Marshal

Something along the lines of :

   safer_output_to_channel stdout (z : Interface.t) []

Trying

   safer_output_to_channel stdout z []

Would yield

   safer_output_to_channel stdout z []
                                  ^
Error: value must be explicitly annotated with a type

safer_output_to_channel stdout (33 : int) []
Error: Type needs to be defined in an external interface to be Marshallable.

safer_output_to_channel stdout (bar : Foo.t) []
Error: Module Foo.t has no interface

safer_output_to_channel stdout (bar : int Foo.t) []
Error: Type Foo.t is not ground

-- 
Berke DURAK