jackdoe / 0xbeef Goto Github PK

* Install:
perl:
    $ perl Makefile.PL
    $ make && make test && make install
ruby:
    $ git clone https://github.com/jackdoe/0xBEEF
    $ cd 0xBEEF/ruby
    $ gem build beef.gemspec 
    $ gem install beef-0.0.1.gem 

* TLDR - Perl XS/Ruby module that creates interface for exportable radix tree, 
  that can hold moderate amounts of data and can be shared between processess, 
  servers, and saved/loaded from files.

so far the result is not that bad:

perl:
    store native hash ($h{$key} = $value} - 6280418.91/s
    store 0xBEEF                          - 1319293.08/s
    store memcached fast                  - 26129.94/s

    get native hash (my $x = $h{$key})    - 7014893.53/s
    * calling noop xs method              - 2824236.48/s
    get 0xBEEF locally (copy of the pool) - 2518272/s
    get 0xBEEF                            - 1041716.01/s
    get memcached fast                    - 25899.05/s

    * this is literally RETVAL = newSVpv("aaaa",5);
      just to measure the impact of the radix lookup and semaphore locking

ruby:
    hash set  3088253.2 (±3.1%) i/s -   15410647 in   4.994880s
    beef set  1289254.2 (±0.8%) i/s -    6448584 in   5.002095s
    hash get  4010468.1 (±0.7%) i/s -   20083472 in   5.008050s
    beef get   901228.6 (±16.0%) i/s -    4407501 in   5.034593s
    hash mis  4291381.9 (±0.6%) i/s -   21466170 in   5.002366s
    beef mis  1373213.8 (±1.1%) i/s -    6894200 in   5.021121s


the reason I am benchmarking against memcached is because the 0xBEEF pools can
be exported and forcefully overwritten (like reverse memcache pattern). So you 
can have a generator that populates data on several machines and cache it this way.


BEEF can also be used to help memcache like:
my $key = ...
my $value = $BEEF->find($key)    ||
            $memcache->get($key) ||
            $memcache->set($key,slow_function($parameters));
and external sources must decide when to put keys into BEEF, 
since lookup there is only 6-7 times slower then native hash, it is ok
to to failure lookups for a minute or something, while the external tool
populates the cached entries.

Of course if you have only 1 machine it makes sense to use it like memcache and do:
  my $value = $BEEF->find($key) || $BEEF->store($key,slow_function());

At the moment it does not do any kind of serialization. (so it must be wrapped in order
to hold complex data)


* Implementation

I ended up creating a simple shared memory pool protected by binary semaphore.
The radix nodes point to the next node by using offset like:
    pool->tree_blob[ node->branch['a'] ]

data structure looks like this:
    struct item {
        uint32_t branch[26];
        struct data {
            uint32_t off;
            uint32_t len;
        } data;
        uint8_t used;
    } __attribute__((aligned));

    struct pool {
        struct item root;
        uint32_t tree_pos;
        uint32_t data_pos;
        uint8_t tree_blob[TREE_BLOB_SIZE];
        uint8_t data_blob[DATA_BLOB_SIZE];
    } __attribute__((packed));
    
NB: for simplicity the pool id's can be only ODD numbers 
    (i use the even numbers to hold the protecting semaphore's id)

So everything is packed together, the tree's nodes live in the tree_blob
and point to other tree nodes using offsets from 0 (&pool->tree_blob[0])

and they contain data structure which holds offset from &pool->data_blob[0]
about where the data lives, and .len for how big it is.

* Simple usage cases
  - perl
    create new pool:
     my $b = BEEF->new(odd-shared-memory-segment-id)

    store something:
     $b->store("key","value");

    fetch something:
     $b->find("key");
     
    export the pool:
     my $exported = $b->export();
     
    get some info about pool's usage:
     print $b->info();

    import pool:
     $b->overwrite($blob);

    reset:
     $b->reset();


    copy locally:
     $b->copy_locally();
     and then you can $b->find_locally("key")
    
    examples:
    my $b = BEEF->new(0xBEEF); # or any odd int32
    $b->store("key","bzbz");
    my $value = $b->find("key");


    # export the pool into file
    my $exported = $b->export();
    open (my $fh, ">","/tmp/pool.binary") or die $!;
    print $fh $exported;
    close($fh);


    # load the pool form file
    my $b = BEEF->new(0xBEF1); # or any odd number
    open($fh,"<:raw","/tmp/pool.binary") or die $!;
    my $blob = do { local $/; <$fh>; };
    close($fh);
    $b->overwrite($blob);
    $b->find("key"); # bzbz

  - ruby
    x = BEEF.create(0xbeef);
    x.store("key","value")
    result = x.find("key")
    raw = x.export
    x1 = BEEF.create(0xbeef + 2)
    x1.overwrite(raw)
    x1.find("key") # will be equal to "value"

* TODO
   + crc the data to validate exported/imported pools
   + write simple multicast servers (using go.http for example)
   + try to make it from fixed size to dynamic size
 

* Licnese 
This software is copyright (c) 2013 by Borislav Nikolov.
This is free software; you can redistribute it and/or modify it under the same terms as the Perl 5 programming language system itself.