Saturday, October 29, 2011

Snappy and the compressed format


Google snappy: A fast compressor/decompressor

1. Optimized for:
64-bit platforms
x86 little-endian

2. Block compression
Snappy compressor works in 32KB blocks and does not do matching across blocks, it will never produce a bitstream with offsets larger than about 32768. However, the decompressor should not rely on this, as it may change in the future.

3. Snappy is a LZ77-type compressor with a fixed, byte-oriented encoding.
The format of snappy compressed data like the left figure.



Sunday, June 12, 2011

Cassandra Compression and the Performance Evaluation

Even though we had put the Cassandra away in all our products, we would like to share our works here.



Why we put away the Cassandra in our products? Because:
(1) It is a big wrong in Cassandra’s implementation, especially on it’s local storage engine layer, i.e. SSTable and Indexing.
(2) It is a big wrong to combine Bigtable and Dynamo. Dynamo’s hash ring architecture is a obsolete technolohy for scale, it’s consistency and replication policy is also unusable in big data storage.

Saturday, July 10, 2010

My comments to "Cassandra at Twitter Today"

Someone said the twitter blog post "Cassandra at Twitter Today" is a big blow to the reputation of Cassandra.


Here are my comments:

1. Cassandra is very young! Especially, the design and implementation of local storage and local indexing are junior and not good.

2. Pool read-performance is also due to the poor local storage implementation.

3. The local storage, indexing and persistence structures are not stable. They need to be re-designed /re-implemented. If Twitter move data to current Cassandra, they should do another move later for a new local storage, indexing and persistence structure.

4. There are many good techniques in Cassandra and other open-sourced projects (such as Hadoop, HBase ...), etc. But, they are not ready for production. Understand the detail of these techniques and implement them in your projects/products.

Monday, April 19, 2010

Cassandra Insert Throughput

** 0.5.1

Test Cluster:
DELL 2950 1*CPU Intel Xeon 5310 (4 cores)
5 nodes
1 node: 2GB heap for Cassandra JVM
4 nodes: 4GB heap for Cassandra JVM

Commit-log and Data stored on same disks.
25 client threads run on 5 nodes.

Data Model:
Keyspace Name = “Test”
Column Family Name = “ABC”
CompareWith for Column = LongType
Column Name = Timestamp (LongType), Value = 400 bytes binary
Billions of keys, thousands of columns.

Partitioner = dht.RandomPartitioner
MemtableSizeInMB = 64MB
ReplicationFactor = 3

Use Thrift Client Interface
Client.insert(..)
Consistency Level (write) = 1

Total inserted 1,076,333,461 columns.
Disk Use: 302GB+283GB+335GB+186GB+276GB=1,382GB (~~400B*1G=400GB *3= 1200GB)

On inserting: 1000 SSTables on each node. The latency of a query is about 1~3 seconds.
Quiet for long time: 10 SSTables (very big files, such as there is one 144GB SSTable data file)
The latency of a query is in ms.

Result: 18,000 columns/second


** 0.6.0
Only 4 nodes.

JVM GC for big heap.
Memory, GC..., always to be the bottleneck and big issue of java-based infrastructure software!
https://issues.apache.org/jira/browse/CASSANDRA-896 (LinkedBlockingQueue issue, fixed in jdk-6u19)

Seems 0.5.1 performed better.
0.6.0 eat more memory.

Tuesday, March 30, 2010

Please don't puzzle on Column-Stores

Daniel Abadi have a blog post here:
http://dbmsmusings.blogspot.com/2010/03/distinguishing-two-major-types-of_29.html

I want to leave a comment and to correct it here:

It is meaningless to compare the two groups, they target to different applications. I think the post just make more confusion. And what Mr. Stonebraker said is also not right.

I think the only thing which make these confusions is the term "column" in Group A. In fact, it is not traditional "column" of RDBMS area. And your example of a traditional spreadsheet table is also not the real target of Group A. The "column" name in Group A is in fact data (not schema).

If have got to change the term, I think we can change the term "column" in Group A to "end-key". In fact, in Bigtable, there is no column, it is "qualifier".

In short:
(1) Group A's "column" is in data, not schema.
(2) Group B's "column" is in schema.
They are different in conception and application target.

Wednesday, January 6, 2010

Jeff Dean and Sanjay Ghemawat's good advices on MapReduce


I'd like to put a copy here, since this paper[1] matchs my opinions so much on MapReduce model and the pratices about large-dataset management/processing implementations.

In the paper, Jeffrey Dean and Sanjay Ghemawat reply Stonebrake and DeWitt's misconceptions about MapReduce. In fact, these misconceptions are so obvious and easy to understand for us.

It is also a good guide to improve the implementation of Hadoop and other members in the family. Suggest you reading it carefully.

Dean and other scientists from Google always bring us clear and reasonable explains about their technologies and pratices. But sometimes, someones from other organizations bring use puzzles.

Except for the five witchcrafts which Google exposed in following papers:
GFS: http://labs.google.com/papers/gfs.html
MapReduce: http://labs.google.com/papers/mapreduce.html
Bigtable: http://labs.google.com/papers/bigtable.html
Chubby: http://labs.google.com/papers/chubby.html
幻灯片 6 Google Cluster and WorkQueue Cluster Management

Following papers/articles/keynotes are very worthy of careful reading:
Jeff Dean Keynotes on LADIS09 (Designs, Lessons and Advice from Building Large
Distributed Systems): http://www.cs.cornell.edu/projects/ladis2009/talks/dean-keynote-ladis2009.pdf
Jeff Dean Keynotes on WSDM09(Challenges in Building Large-Scale Information Retrieval Systems): http://research.google.com/people/jeff/WSDM09-keynote.pdf
Jeff Dean Stanford-295-talk (Software Engineering Advice from Building Large-Scale Distributed Systems): http://research.google.com/people/jeff/stanford-295-talk.pdf
Jeff Dean "Handling Large Datasets at Google": http://hepix.caspur.it/storage/hep_pdf/2008/Spring/handling-large-datasets-20080507.pdf
Jeff Dean "A Behind the ScenesTour": http://www.slideshare.net/rawwell/googleabehindthescenestourjeffdean

And following so called GFS-II articals:
Sean Quinlan: GFS: Evolution on Fast-forward (http://queue.acm.org/detail.cfm?id=1594206)

Monday, December 21, 2009

Google Basic Building Block - Protocol Buffers

“Protocol Buffers” is an important one of Google’s basic building blocks. It’s is a way of encoding structured data in an efficient yet extensible format, and a compiler that generates convenient wrappers for manipulating the objects in a variety of languages. Protocol Buffers are used extensively at Google for almost all RPC protocols, and for storing structured information in a variety of persistent storage systems.

When to use Protocol Buffers:
- RPC Protocols/Messages
- Persistent Storage of structured information
- As Client/Server Framework

According to Jeff Dean’s keynote at LADIS2009 http://www.cs.cornell.edu/projects/ladis2009/talks/dean-keynote-ladis2009.pdf

Serialization/Deserialization
- high performance (200+ MB/s encode/decode)
- fairly compact (uses variable length encodings)
- format used to store data persistently (not just for RPCs)

Low-level MapReduce interfaces are in terms of byte arrays
- Hardly ever use textual formats, though: slow, hard to parse
- Most input & output is in encoded Protocol Buffer format

Language Support:
- C++
- Java
- Python

Optimization for different use cases: (e.g.: option optimize_for = SPEED)

- SPEED (default): The protocol buffer compiler will generate code for serializing, parsing, and performing other common operations on your message types. This code is extremely highly optimized.

- CODE_SIZE: The protocol buffer compiler will generate minimal classes and will rely on shared, reflection-based code to implement serialialization, parsing, and various other operations. The generated code will thus be much smaller than with SPEED, but operations will be slower. Classes will still implement exactly the same public API as they do in SPEED mode. This mode is most useful in apps that contain a very large number .proto files and do not need all of them to be blindingly fast.

- LITE_RUNTIME: The protocol buffer compiler will generate classes that depend only on the "lite" runtime library (libprotobuf-lite instead of libprotobuf). The lite runtime is much smaller than the full library (around an order of magnitude smaller) but omits certain features like descriptors and reflection. This is particularly useful for apps running on constrained platforms like mobile phones. The compiler will still generate fast implementations of all methods as it does in SPEED mode. Generated classes will only implement the MessageLite interface in each language, which provides only a subset of the methods of the full Message interface.

The detail of Protocol Buffers, please refer http://code.google.com/apis/protocolbuffers/.

We may select one between Protocol Buffers and Thrift as our building block. After have a brief read of the Protocol Buffers’ code, and compare to our experiences of using Thrift, I like Thrift, which provide better RPC implementation and coding interfaces.

There are also some performance compares of Thrift and Protocol Buffers:
http://timyang.net/programming/thrift-protocol-buffers-performance-java/
http://timyang.net/programming/thrift-protocol-buffers-performance-2/
http://rapd.wordpress.com/2009/04/18/json-vs-thrift-vs-pbuffer/

How to install protobuf (an example):

1. Download protobuf-2.2.0a.tar.gz
$ cd /usr/local/src
$ tar -zxvf /root/pkgs/protobuf-2.2.0a.tar.gz

Read README.TXT and INSTALL.TXT for detail.

2. Build and install the C++ Protocol Buffer runtime and the Protocol Buffer compiler (protoc)
$./configure --prefix=/usr/local/protobuf
$ make
$ make check
$ make install

Set linux lib path, then application can find protobuf.so.
$ echo “/usr/local/protobuf/lib” > /etc/ld.so.conf.d/protobuf.conf
$ ldconfig

3. /etc/profile.d/local.sh
This local.sh is added by me. It add some system level environment variables for the convenience of applications.
# apache-ant
ANT_HOME=/usr/local/apache-ant
PATH=$PATH:$ANT_HOME/bin
export ANT_HOME

# google protocol buffer
GOOGLE_PROTOBUF_HOME=/usr/local/protobuf
PATH=$PATH:$GOOGLE_PROTOBUF_HOME/bin
export GOOGLE_PROTOBUF_HOME
# apps use pkg-config to compile and link protobuf (eg. pkg-config --cflags --libs protobuf)
export PKG_CONFIG_PATH=$PKG_CONFIG_PATH:$GOOGLE_PROTOBUF_HOME/lib/pkgconfig/

export PATH
4. Install protobuf Java
$ cd /usr/local/src/protobuf-2.2.0a/java
Read README.TXT (Installation - Without Maven)

Generate DescriptorProtos.java
$ protoc --java_out=src/main/java -I../src ../src/google/protobuf/descriptor.proto

Write a new build.xml:
-------------------
<?xml version="1.0" encoding="UTF-8" standalone="no"?>

<project basedir="." default="jar-libprotobuf" name="libprotobuf">
<property environment="env"/>

<!-- javac options -->
<property name="javac.version" value="1.6"/>
<property name="javac.source" value="${javac.version}"/>
<property name="javac.target" value="${javac.version}"/>
<property name="javac.deprecation" value="off"/>
<property name="javac.debug" value="off"/>
<property name="javac.debuglevel" value="source,lines,vars"/>
<property name="javac.optimize" value="on"/>
<property name="javac.args" value=""/>
<property name="javac.args.warnings" value="-Xlint:unchecked"/>

<!-- jar options -->
<property name="jar.index" value="true"/>

<!-- protobuf names -->
<property name="version" value="2.2.0a"/>
<property name="Name" value="libprotobuf"/>
<property name="final.name" value="${Name}-java-${version}"/>

<!-- dir locations -->
<property name="src.dir" value="${basedir}/src"/>
<property name="src.main.dir" value="${src.dir}/main"/>
<property name="src.test.dir" value="${src.dir}/test"/>
<property name="build.dir" value="${basedir}/build"/>
<property name="build.classes.dir" value="${build.dir}/classes"/>

<!-- TARGET init -->
<target name="init">
<mkdir dir="${build.dir}"/>
</target>

<!-- TARGET clean -->
<target name="clean">
<delete dir="${build.dir}"/>
</target>

<!-- TARGET cleanall -->
<target name="cleanall" depends="clean">
<delete>
<fileset dir="." includes="*.jar"/>
</delete>
</target>

<!-- TARGET compile-libprotobuf -->
<target name="compile-libprotobuf" depends="init" >
<echo message="${ant.project.name}: ${ant.file}"/>
<mkdir dir="${build.classes.dir}"/>
<javac source="${javac.source}" target="${javac.target}"
destdir="${build.classes.dir}"
srcdir="${src.main.dir}"
debug="${javac.debug}"
debuglevel="${javac.debuglevel}"
optimize="${javac.optimize}"
deprecation="${javac.deprecation}">
<compilerarg line="${javac.args} ${javac.args.warnings}" />
</javac>
</target>

<!-- TARGET jar-libprotobuf -->
<target name="jar-libprotobuf" depends="compile-libprotobuf">
<jar basedir="${build.classes.dir}" destfile="${build.dir}/${final.name}.jar" index="${jar.index}">
</jar>
<copy todir="${basedir}">
<fileset file="${build.dir}/${final.name}.jar"/>
</copy>
</target>


<!-- for libprotobuf-lite -->

<property name="build.lite.dir" value="${build.dir}/lite"/>
<property name="build.lite.classes.dir" value="${build.lite.dir}/classes"/>
<property name="final.lite.name" value="${Name}-lite-java-${version}"/>

<!-- TARGET compile-libprotobuf-lite -->
<target name="compile-libprotobuf-lite" depends="init" >
<echo message="${ant.project.name}: ${ant.file}"/>
<mkdir dir="${build.lite.dir}"/>
<mkdir dir="${build.lite.classes.dir}"/>
<javac source="${javac.source}" target="${javac.target}"
destdir="${build.lite.classes.dir}"
srcdir="${src.main.dir}"
includes="**/AbstractMessageLite.java
**/ByteString.java
**/CodedInputStream.java
**/CodedOutputStream.java
**/ExtensionRegistryLite.java
**/FieldSet.java
**/GeneratedMessageLite.java
**/InvalidProtocolBufferException.java
**/Internal.java
**/MessageLite.java
**/UninitializedMessageException.java
**/WireFormat.java"
debug="${javac.debug}"
debuglevel="${javac.debuglevel}"
optimize="${javac.optimize}"
deprecation="${javac.deprecation}">
<compilerarg line="${javac.args} ${javac.args.warnings}" />
</javac>
</target>

<!-- TARGET jar-libprotobuf-lite -->
<target name="jar-libprotobuf-lite" depends="compile-libprotobuf-lite">
<jar basedir="${build.lite.classes.dir}" destfile="${build.lite.dir}/${final.lite.name}.jar" index="${jar.index}">
</jar>
<copy todir="${basedir}">
<fileset file="${build.lite.dir}/${final.lite.name}.jar"/>
</copy>
</target>

</project>
-------------------

$ ant
$ cp libprotobuf-java-2.2.0a.jar /usr/local/protobuf/lib/

$ ant libprotobuf-lite-java
$ cp libprotobuf-lite-java-2.2.0a.jar /usr/local/protobuf/lib/

5. Build examples
$ cd /usr/local/src/protobuf-2.2.0a/examples
Read detail of README.txt

JAVA:
$ export CLASSPATH=.:$CLASSPATH:/usr/local/protobuf/lib/libprotobuf-java-2.2.0a.jar
$ make java

CPP:
$ make cpp

Python:
$ make python

Then we can read the example code (AddPersion and ListPeople) and run them.