[gambit-list] A couple of random questions

mikel evins mevins at me.com
Mon Jul 25 14:52:00 EDT 2011


On Jul 25, 2011, at 6:23 AM, Marc Feeley wrote:

> 
> On 2011-07-22, at 4:41 AM, mikel evins wrote:
> 
>> Question 2:
>> (I asked this one before, but didn't see an answer.)
>> 
>> Suppose I have a file containing data serialized by calling object->u8vector and then written to a file. Suppose, further, that I happen to know that an object of interest to me starts at a specific byte offset within the file.
>> 
>> What's the right way to read that object from the file?
>> 
>> An additional constraint is that I don't want to have to read the entire contents of the file in order to read the object; I want to be able to read just enough bytes to reconstitute the object whose serialized representation starts at the given offset.
> 
> The object encoding used by object->u8vector (and u8vector->object) does not contain a length.  The stream of bytes has to be parsed to know how long the object encoding is.  To facilitate I/O, I usually prefix the encoding with a 32 bit integer which indicates the length of the encoding.
> 
> A second problem is that the object encoding supports shared structures.  This means that the object created with
> 
>    (let ((shared (cons 1 2))) (cons shared (cons 3 shared)))
> 
> will be encoded with something like this:
> 
>    OBJ0=[pair
>          OBJ1=[pair 1 2]
>          OBJ2=[pair 3 OBJ1]
>         ]
> 
> or if you want all the details:
> 
>> (object->u8vector
>     (let ((shared (cons 1 2))) (cons shared (cons 3 shared))))
>  #u8(100 100 81 82 100 83 129 0)
>      ^   ^   ^  ^  ^   ^  ^
>      |   |   |  |  |   |  |
>      |   |   1  2  |   3  reference to shared object 0
>      |   |         |
>      |   |         "pair" (index 2)
>      |   |
>      |   "pair" (index 1)
>      |
>      "pair" (index 0)
> 
> So you can't just start parsing an object from an arbitrary point inside the encoding.  Some context will be missing.
> 
> The approach I would take is to dump each object independently in the file and keep a separate index of where each object starts, and its length (then use input-port-byte-position to seek to the right place).  Even better, store the serialized objects in a database and let it do the indexing for you (it also simplifies deleting objects).

Thanks very much, Marc; this is very helpful.

We're using Gambit serialization to implement an embedded database engine of our own. For this project, we can guarantee that we won't need to store shared references to objects, which simplifies things a bit.

Here's a sketch of the solution we're using: The database file is log structured, with a header that includes an offset field. The offset field points to the location of an object table, and is the only mutable field in the file. 

Scheme objects are stored in the file as bytevectors produced by object->u8vector, with a length field prepended. Given an offset and a promise that it's the start of an object record, we can reconstitute the object simply by reading the length, then reading that many bytes and passing the resulting bytevector to u8vector->object.

Data, once written, is never mutated, though new data are appended. New data are not written directly to the database file; instead transaction records are appended to a transaction log as updates in RAM occur. At suitable intervals, the database subsystem consolidates ranges of transaction records and writes new objects to the database file, appending an updated object table and updating the offset field at the top of the file. (In this way, a crash can result in a database file with a range of inaccessible garbage objects near the end, but cannot result in accessible garbage values, because the object table is written only after all new values have been written, and the offset field is updated only after the new object table is written.)

The on-disk object table is simply a serialized Scheme object that maps oids to offsets.





More information about the Gambit-list mailing list