技术员博客      html  css  js  c++  java
  • TreapDB is a keyvalue store based on Treap

    treapdb - A fast and stable key-value store based on Treap data structure - Google Project Hosting

    TreapDB is a key-value store based on Treap

    News

    Unit Test

    Features

    • can be a embedded library or a standalone RPC-Server
    • can 'talk' memcache and thrift at the same time
    • master-slave replication
    • random "get" speed: 15000 tps(RPC Server); 32000tps(Embedded)
    • bulkPut speed: 17000 tps, bulkGet speed:30000tps
    • service specification:
    • namespace java fx.sunjoy.server.gen

      struct Pair {
      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

    OperationUsageParameters
    putinsert a new key-value pair, or replace an old key-value pairkey and value
    getget the value of the indicated keykey
    bulkPutinset 2 or more key-value pairs togethermap of key and value
    bulkGetget the value of 2 or more indicated keyslist of keys
    prefixget the value of the keys with the indicated prefix stringprefix and number of result
    bulkPrefixget the value of the keys with the indicated prefix stringslist of prefix, number of result, beginning key, sort the key-value pairs in ascending or descending order
    kmaxget the k maximum key-value pairsk
    kminget the k minimum key-value pairsk
    rangeget the key-value pairs whose key is between the indicated keysbeginning key and ending key
    beforeget the key-value pairs whose key is before the indicated key in alphabetical orderkey and number of result
    afterget the key-value pairs whose key is after the indicated key in alphabetical orderkey and number of result
    lengthget the number of key-value pairsnone
    removedelete the indicated key-value pairkey
    removePrefixdelete value of the keys with indicated prefix stringprefix
    optimizeoptimize the space usage of index filenumber of nodes need to be optimized(1024 is recommended value)

    Sample

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

    RPC Server

    • memcached protocol compatible server for test usage
    • thrift-based server for production usage

    Download & Configure

    • run
      • ./treapdb.sh conf/TreapDBConf.xml(master mode)
      • ./treapdb.sh conf/TreapDBConf_Slave.xml(slave mode)
    • configuration:
    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 = new DiskTreap<String,Serializable>
    (new File("/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?

    • TreapDB server is based on thrift, so you can generate your client in

    any programming language.

    • For example, generate the python client code.
    • thrift --gen py res/service.txt
    • res/service.txt is a service specification:
    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

  • 相关阅读:
    布局管理器(二)
    Android平台Qt开发入门教程 狼人:
    forwarding
    ffmpeg
    basic coder » Hybrid开发手记之聊天窗口的WebKit支持
    Compiler 规格严格
    KeyTool 4096 RSA JDK1.5 1.4 规格严格
    God A Process Monitoring Framework in Ruby
    ThreadLocal 规格严格
    linux munin 服务器监控 安装配置«海底苍鹰(tank)博客
  • 原文地址:https://www.cnblogs.com/lexus/p/2422030.html
Copyright © 2011-2022 技术员博客