TreapDB is a keyvalue store based on Treap

发布时间：2022-08-09 文章分类：编程知识 投稿人：李佳 字号： 默认 | 大 | 超大 打印

TreapDB is a key-value store based on Treap

News

Unit Test

Features

namespace java fx.sunjoy.server.gen

structPair{
 1:string key,
 2: binary value,
}

service TreapDBService{
    void put(1:string key,2:binary value);
    binary get(1:string key),
    void bulkPut(1:map<string,binary> kvMap);
    list<Pair> bulkGet(1:list<string> keyList);
    list<Pair> prefix(1:string prefixStr,2:i32 limit,3:string startK,4:bool asc),
    list<Pair> bulkPrefix(1:list<string> prefixList,2:i32 limit,3:string startK,4:bool asc),
    list<Pair> kmax(1:i32 k),
    list<Pair> kmin(1:i32 k),
    list<Pair> range(1:string kStart,2:string kEnd,3:i32 limit),
    list<Pair> before(1:string key,2:i32 limit),
    list<Pair> after(1:string key,2:i32 limit),
    i32 length(),
    bool remove(1:string key),
    bool removePrefix(1:string key),
    void optimize(1:i32 amount)
}

Operations of TreapDB

Operation Usage Parameters
put insert a new key-value pair, or replace an old key-value pair key and value
get get the value of the indicated key key
bulkPut inset 2 or more key-value pairs together map of key and value
bulkGet get the value of 2 or more indicated keys list of keys
prefix get the value of the keys with the indicated prefix string prefix and number of result
bulkPrefix get the value of the keys with the indicated prefix strings list of prefix, number of result, beginning key, sort the key-value pairs in ascending or descending order
kmax get the k maximum key-value pairs k
kmin get the k minimum key-value pairs k
range get the key-value pairs whose key is between the indicated keys beginning key and ending key
before get the key-value pairs whose key is before the indicated key in alphabetical order key and number of result
after get the key-value pairs whose key is after the indicated key in alphabetical order key and number of result
length get the number of key-value pairs none
remove delete the indicated key-value pair key
removePrefix delete value of the keys with indicated prefix string prefix
optimize optimize the space usage of index file number of nodes need to be optimized(1024 is recommended value)

Sample

http://code.google.com/p/treapdb/wiki/SomeBenchmark

RPC Server

Download & Configure

TreapDBConf.xml

  
   <?xml version="1.0" encoding="UTF-8"?>
   <TreapDB>
    <Params>
        <Port>
            <Memcache>11811</Memcache> 
            //Listening port of memcache protocol
            <Thrift>11812</Thrift>   
            //Listening port of thrift protocol
        </Port>
        <Index>
            <FilePath>/var/log/treapdb/master</FilePath> 
             //Index file name
            <BlockSize>64</BlockSize> 
             //size of index-block-item;
             //default key length is 26(=64-38),38 is the node-overhead, 
             //TreapDB supports max key-length: 127 bytes)

        </Index>
        <MMapSize>128</MMapSize> //the more the better, 128MB is enough for 2 Million keys
        <Replication>
            <Role>Master</Role>
        </Replication>
    </Params>
   </TreapDB>

TreapDBConf_Slave.xml

   <?xml version="1.0" encoding="UTF-8"?>
   <TreapDB>
    <Params>
        <Port>
            <Memcache>11911</Memcache>
            <Thrift>11912</Thrift>
        </Port>
        <Index>
            <FilePath>/var/log/treapdb/slave</FilePath>
            <BlockSize>64</BlockSize>
        </Index>
        <MMapSize>128</MMapSize>
        <Replication>
            <Role>Slave</Role>
            <Source>10.61.1.170:11811</Source>
           //Set master address and port here!
        </Replication>
    </Params>
   </TreapDB>

How to build from source

  1. svn checkout http://treapdb.googlecode.com/svn/trunk/
  2. ant dist
  3. use the jars generated in build/dist

How to write client code

Java:

  String host ="localhost";
  Integer port =11812;//thrift port
  TreapDBClient client =TreapDBClientFactory.getClient(host, port);
  client.put(...)
  client.get(...)
  client.prefix(...)
  ...

Python:

  import pytreap
  client = pytreap.connect('localhost',11812)//thrift port
  client.get(...)
  client.put(...)
  client.remove(...)

Can TreapDB be used in an embedded way?

Yes,put libtreap-xx.jar in your app's classpath.

  DiskTreap<String,Serializable> treap =newDiskTreap<String,Serializable>
(newFile("/usr/local/indexpath")); 

  treap.put(...)
  treap.get(...)
  ...

  /* key can be any type which implements Comparable;
  value can be any type which implements Serializable*/

Only Java?

any programming language.

Python client: http://code.google.com/p/treapdb/wiki/PythonClientExample

What is treap?

In computer science, the treap and the randomized binary search tree are two closely-related forms of binary search tree data structures that maintain a dynamic set of ordered keys and allow binary searches among the keys. After any sequence of insertions and deletions of keys, the shape of the tree is a random variable with the same probability distribution as a random binary tree; in particular, with high probability its height is proportional to the logarithm of the number of keys, so that each search, insertion, or deletion operation takes logarithmic time to perform.

http://en.wikipedia.org/wiki/Treap

Contact the author

All Operationshttp://code.google.com/p/treapdb/wiki/SomeBenchmarkTreapDBConf.xmlTreapDBConf_Slave.xmlJava:

  String host ="localhost";
  Integer port =11812;//thrift port
  TreapDBClient client =TreapDBClientFactory.getClient(host, port);
  client.put(...)
  client.get(...)
  client.prefix(...)
  ...

Python:

  import pytreap
  client = pytreap.connect('localhost',11812)//thrift port
  client.get(...)
  client.put(...)
  client.remove(...)

Yes,put libtreap-xx.jar in your app's classpath.

  DiskTreap<String,Serializable> treap =newDiskTreap<String,Serializable>
(newFile("/usr/local/indexpath")); 

  treap.put(...)
  treap.get(...)
  ...

  /* key can be any type which implements Comparable;
  value can be any type which implements Serializable*/

thrift --gen py res/service.txtPython client: http://code.google.com/p/treapdb/wiki/PythonClientExampleIn computer science, the treap and the randomized binary search tree are two closely-related forms of binary search tree data structures that maintain a dynamic set of ordered keys and allow binary searches among the keys. After any sequence of insertions and deletions of keys, the shape of the tree is a random variable with the same probability distribution as a random binary tree; in particular, with high probability its height is proportional to the logarithm of the number of keys, so that each search, insertion, or deletion operation takes logarithmic time to perform.

标签 , ,