SDL_Init(SDL_INIT_VIDEO | SDL_INIT_AUDIO);

Python does not have an audio library, which allows to asynchronously play music and control it in close enough to real time. Mainly I need a fast audio start/stop capability, which will be triggered from python code when I press and release different keys on software piano keyboard.

So I will write it in C using SDL and SDL_mixer library in particular:

Mix_OpenAudio(audio_rate, audio_format, audio_channels, audio_buffers);
music = Mix_LoadMUS("music.ogg");
Mix_PlayMusic(music, 0);
Mix_HaltMusic();

The latter two functions can be used to control audio flow and it will be hardware mixed with other system sounds out of the SDL_mixer library box. SDL_mixer supports a wide variety of formats including OGG Vorbis and MP3.

And in a week or so I will publish a nice project I spent a week on. Actually it can be announced right here, but it does not yet work with production servers.
I created a simple enough photo uploader for Shotwell photo management application which uses Yandex.Fotki photohosting, which is the largest on in Russia and I used to use it quite frequently now. I hope my 1000 lines patch will be accepted (some people will even bring me beer for that :)

If I understood correctly Shotwell will replace F-Spot in modern distros.

Shotwell is written in Vala language, which is kind of C#, but its complier is sooo weird, that it is very unlikely I will return to it anytime soon. But java-style memory memory management (i.e. when you do not care about malloc/free) as well as compiler forced exception handling (one has to use try/catch blocks, when some function can throw exceptions) just make me relax during programming...

In a meantime I added stream write support to HTTP elliptics network fronend. WIth this change it is possible to atomically append data to existing records (in backends which support it - currently it is file IO backened).

Thus HTTP interface becomes very useful for stream-like data updates in various projects starting from log saving to auido/video recording.

Another major change includes IO backend update: I finally dropped TokyoCabinet database in favour of libeblob. Main objection against TC was its extremely slow performance when index swaps to disk. I dropped VM cache during test and TokyoCabinet never recovered back even if amount of RAM allows to populate whole database (I used several millions of 10k objects and database size was close to 10 Gb while machine had 24 Gb of RAM).

Also TC version I tested (1.4.44 iirc) was very unstable - I even wrote a test script to restart upload, but to my shame I did not contact author with cores and backtraces. When I tried .23 version year ago it was rock stable, so I expect that in newer version things were fixed.

Another TC issue is related to multi-threading: this database just does not allow multiple users to read and write data simultaneously - it locks the whole database each time we start transaction, which is needed to protect against parallel writes. Although this was not an issue in elliptics network tests.

And now dig back into python and morphological data processing... I tested handful of phrase generation techniques, but neither provided good result for words which were not present in the dictionary. I have to find and answer.

I love languages with rich standard library. Python is just awesome in this regard.

But amount of already written extension is outstanding - I parsed HTML using regexps in Lisp, but in Python with python-lxml it took just couple of hours to parse rather broken html using xpath and small string matching calls.

I spent one day to write a parser of non-structured morphological data (frequently with suddnly unwanted symbols or additional tags within) from aot.ru to create a quite large (300k+ morphems) russian dictionary, and then to store it into prefix array and ouput as XML file.

Yes, default CPython sucks with threads, it is not (yet) suitable for trivial audio processing (play and stop sound when pressing/releasing a key), but it is just bloody ubergood at high-level prototyping.

Returning back to morphological analysis I'm about to start rewriting my experimental knowledge extraction and grammatic generation 'engine' from Lisp to Python. And I expect to have some cool results with it soon.

Python threads suck! They do not have deterministic behaviour from scheduling point of view, i.e. one does not know when thread will run and how long will it run.

And the main problem is that it likely may not give up control when faces syscall and/or lock. So it is not possible to control it using lock acquired in main thread and spawned one. PyQt signal will not be handled with enough priority to interrupt spawned thread which drops into thread.lock.

Eventually spawned thread will give up control, but this non-determinism is not acceptible for piano project I work on - we have to start and stop sound when key is pressed (modulo some short enough timeout, but not failing into extreme like using low-latency jack audio servers).

Legend.

elliptics network - distributed hash table storage
eblob - low-level data storage used as one of IO backends for elliptics network

Hardware: 2 E5530 servers (16 cores, 24 Gb of RAM) each one is connected to SAS shelf (14 disks, ext4, raid10).
Data: 100 millions of objects (total of 1042 Gb) roughly equally spread over above server nodes.
Requests: random IO reads.

Result? We have it:

Reply time (left, in ms) @ number of requests per second (right, red inclined line)



Reply time (in ms) distribution

Net result: 3500 rps within 100 ms, 4000 rps witin 200 ms.
Not that bad I think...

This day has come: I made whole new and shiny elliptics network release. Amount of invasive changes is noticeable but yet a lot more I found should be changed.

We made 30 intermediate releases after 2.9.0 which revealed fair number of bugs and showed a number of different ways of further elliptics storage development.

A short changelog includes:

• Huge log refactoring. Now logs are external entities which are referenced in elliptics core.
• Allow to embed timestamps into data objects, which makes http cache headers processing (namely if-modified-since and last-modified) as fast as data reading. Timestamps are also stored in transaction histories, which previously had to be read from disk, thus making 2 times more disk seeks to handle client request. It is quite easily possible to implement other URI parameters embedding (one can specify object timestamp in URI as well as getting current time, for more details see example config file which comes in a package/archive).
• Added region tag in XML returned by HTTP proxy. Region ID can be obtained using external library calls when properly configured.
• Added EBLOB low-level IO backend. It is an append-only storage system which works with huge blob files and allows to lookup object with O(1) time optionally locking index in memory. I posted a number of its benchmarks here - it outperforms everything, although has a set of constraints, like need to call defragmentation tool. I plan to remove TokyoCabinet database IO backend in next release, since when it starts paging out its performance suffers greatly and elliptics network does not need its rich database API.
• Added spec file for RPM builds. Debian build files were added quite long time ago, and we use deb packages to actually rollout new releases.
• Added C++ and Python bindings. I stumbled upon an interesting user behaviour: when API is exteremely rich library is used noticeably less frequently, since people who are not very familiar with the low-level internals can not decide what exactly they need from this huge exported function set. In C++/Python bindings I implemented rather simple classes with limited API which should solve most of the common problems users face daily. Simplifying API leads to better acceptance of the project.
• Changed library and include filenames from dnet to elliptics. In particular, this solves problem with already existing libdnet found in all popular distros. Now we use libelliptics and include/elliptics.
• Switched server-side code from command-line options to configuration file. Allow low-level IO backends to have their own config options. Split former dnet_ioserv to server code with the same name and dnet_ioclient which is able to read/write/remove objects in the storage as well as requesting VFS/memory/CPU usage statistics.
• Fair number of bug fixes.

With this release I mark 2.9 tree as experimental, since I will break compatibility soon to allow faster fault recovery process.

Milestone TODO list includes:

• Refactor transaction history processing code and move it to elliptics core from low-level IO backends. Transaction logs will be stored in eblobs and will be optimized for performance. IO backends will only store data objects in different formats.
• Remove TokyoCabinet IO backend in favour of EBLOB one.
• Switch to thread-per-client IO processing model.
• POHMELFS port.

Stay tuned!

And now its time to recall about OLOLO-intellect and related lexical and morphological analysis...

I used to believe that reactor (aka state-machine) model is always superior compared to thread-per-client case, since threads are huge, context switch is CPU-pricey and slow.

At least it was 10 years ago when sky was bluer and grass was greener. Now things changed.
When I developed kevent - a kernel dispatching system for file descriptors, process' and other events, I implemented it as a complex enough state machine, which handled different event types and performed scheduled for each event type (like network AIO and so on).

Those days state-machine system did not differ too much from one created on top of thread-per-client model, especially in IO cases where clients frequently sleep waiting for IO completion.
Now, when multi-core systems become commodity hardware we want to utilize all CPUs, which means creating more and more separate state machines each one running on own physical processor. Or we can create a pool of threads where each thread will process its own state machine.

In elliptics network libevent-based state machine handles all network operations. Another state machine handles client commands and third one glues them together (this one is especially visible when we forward data from one socket to another).

System of complex structures is as weak as its weakest member. Thus, when we block in directory reading syscall which takes 10 minutes to populate cold dentry and/or inode cache from directory containing millions of records, that thread is completely uselesss for other operations scheduled. Which means no network transfers or other commands which could be done waiting for blocking operation to complete. In some systems I worked with on top of elliptics it was as much upto 10 thousands of 'clients' per default 128 IO threads.

And in IO-heavy systems amount of such blocking operations prevails number of potentiall non-blocking (like most of writes and all socket events, since it signals only when something can be read/written and sockets are non-blocking). As a proof-of-concept one may consider recent Java NIO vs sync-IO benchmark (shorter and more popular HTML article).

Thus I decided to rewrite event-handling model in elliptics network and use simple thread-per-client approach. It will eliminate possible libevent bugs (and I found some of them in 1.3 versions) as well as greatly simplify processing logic. Also it will be possible to imlpement IO priorities, first by using ionice and then maybe by introducing automatic tools.

We got 2 servers (E5530, 16 cores, 24 Gb of RAM) with 14-disks SAS shelf converted into raid10 in each.
Uploaded 30 millions of records (record size varies from 5 to 20 kb) total of 370 Gb of data.

Fired with random requests and got this graph:

2000 rps within 130-150 ms, according to dynamics we could get more, but stopped test.
Will run longer with additional 60 millions of records (total of about 100 millions objects in the storage).

Eblob index must take all available RAM on such machine, with 15 millions of records on each (30 millions total) we get about 9.9 Gb of virtual memory and 8.7 Gb of 'real' mem.

Should fit 100 millions of records on 2 nodes perfectly :)

In a meantime I cooked up 2.9.1 release, its release candidate will pass final tests and I will make an announcement in a day or so. We got 30 internal releases prior this one already, its time to publish new shiny features in a new package.

Stay tuned!

Using 'threading' module apparently is not a very good idea

$ python /tmp/threads.py
# ... interrupt by Ctrl-C

Traceback (most recent call last):
  File "/tmp/threads.py", line 12, in 
    TestThread().start()
  File "/usr/lib/python2.5/threading.py", line 442, in start
    _sleep(0.000001)    # 1 usec, to let the thread run (Solaris hack)

$  cat /tmp/threads.py 
import threading, sys

test_num = 0
class TestThread(threading.Thread):
	def run (self):
		global test_num
		test_num = test_num + 1

num = 10000;
for x in xrange (num):
	TestThread().start()

print "var: ", test_num, "num: ", num

I created this trivial Python::threading example which spans 10k threads which update global variable to find out whether GIL will protect it and to check how fast is thread creation. It happend that python threads are damn slow to create (and topmost dump confirms that - python sleeps there!). During this test python interpreter ate about 1% of 16 available CPUs and there was only single thread at a time, which means GIL protects thread creation and execution. When I added time.sleep() there, GIL was dropped to enter syscall and procfs confirmed that there were many simultaneous threads created.

But low-level module 'thread' is different. As documentation states:

This module provides low-level primitives for working with multiple threads (also called light-weight processes or tasks) — multiple threads of control sharing their global data space. For synchronization, simple locks (also called mutexes or binary semaphores) are provided.

I do not know what above high-level stuff does, but low-level threads are created very quickly forcing python interpreter to ate gigabytes of virtual memory and then throw unknown exceptions at the end (practice shows that waiting for all threads to complete does not rise those exceptions, maybe this happens only in 2.5.2):

Unhandled exception in thread started by 
Error in sys.excepthook:

$ cat /tmp/low_level_threads.py 
import thread

test_num = 0
def test_thread(smth):
	global test_num
	test_num = test_num + 1

num = 10000
for x in xrange(num):
	thread.start_new_thread(test_thread, ('qwe',))

print "var: ", test_num, "num: ", num

This application ate about 60-100% of CPU so I wonder whether GIL allows multiple threads to run (and not wait in syscall) on different physical processors without hacks (i.e. explicit GIL state drop and acquire).
There are also nice lock classes in that module.

I plan to use separate thread for each key in my piano keyboard emulator, which will be scheduled from key-pressed signal.

Spent several hours to write a trivial piano emulator using Python. I do not have a book so just googled whatever did not work: apparently all newbie problems are already solved.
I used PyQt bindings and Qt-designer to create UI. pyuic4 generates a bit ugly Python code: first, python 2.6 does not understand it (namely assignment some value to function, like self.some_func() = something, so I had to manually edit it (I found a post that latest Python snapshots already support it, likely it was about Python3), second, it does not know about loops and just creates a static representation of the form screen.
Also I did not work hard on things like resizing (I just forbid it :)

To play sounds I used PyMedia library, unfortunately it is not available in Ubuntu, and its compilation failed, so I had to edit setup scripts and put proper defines for C code :) Furtunately I quite know C a little.

Probably I will switch out from PyMedia, since it does not allow to control output sound buffer size. I need to 'schedule' audio sample playing so that qt-signal handler returned and next one (like key release) could be processed. PyMedia implements async sound output, but it may be not enough - for example it blocks trying to get and play 100.000 samples.
Or I will try to work with Python threads and assign press/release signals to different threads (if it is possible, I do not know Python enough yet).

This is a very ugly proof of concept code to date. I will polish things and split downloaded scales into separate tones, which will be played when appropriate keys are pressed. I will also try to implement nicer classes for keys and sounds.

And in a meantime my workplace screenshot (full-screen on click):

I found it so simple to program using Python that it is very likely I will switch all prototyping development to Python from Lisp. Lisp is great and I do like its features, but it is way too rare when I used its cool abilities like writing complex macros, most of my macros were rather simple with-something () like with-open-file() and friends.
Lambda and closures for internal states are great, but iirc Python also has them.

But main feature of the Python I like is its incredible standard library as well as zillions of already written extensions. I was not able to find graphical bindings for CLISP or audio processing for example, although its quite unusual to write GUI in Lisp.
I had to write HTTP GET/POST utility myself using low-level sockets; regular-expression in CLISP is rather limited, and although cl-ppcre is great, rich regexp is available in Python out of the box. Python has some multithreading support (and ugly GIL to name), while CLISP does not (at least 2.44.1 version, which comes with Ubuntu Lucid).
And so, and so and on...

Stay tuned, I will play more with this project, after all I want to play some simple music at work :)

We got 2 servers (4 SATA disk raid10, default ext4, 24 Gb of RAM, E5530, 16 cores), uploaded 30 millions of objects into elliptics network on top of libeblob backend. Total of 370 Gb on disks.

And got this with completely random requests:

900 rps within 100-150 ms. Quite a superb result for such hardware.
And we have this SAS shelfs:

md4 : active raid10 sdr[13] sdq[12] sdp[11] sdo[10] sdn[9] sdm[8] sdl[7]
                               sdk[6] sdj[5] sdi[4] sdh[3] sdg[2] sdf[1] sde[0]
      2050780256 blocks super 1.2 16K chunks 2 near-copies [14/14] [UUUUUUUUUUUUUU]

which will be used to host about 200 millions of objects (upload will be finished next week - writing server can not cope with such load :). Will also test the same amount of data on 4-sata-disk raid10 machines as well.

Stay tuned!

A fucking bad musician actually, but I learn...

Yes, there are harminies and scales, accords and arpeggios and so on, which I study every day as well as practicing my trumpet itself. And I have quite good progress I think.

But very frequently I want to play some simple (or complex) motive of the melody I hear. Or 'workaround' it a little... At home I can play piano and try to pick out melody by ears, but in office or anywhere near computer I can not do this.

The reason is simple: Linux does not have a piano synthesizer. Well, it has plenty of them, but each one plays through MIDI. And audio system in Linux is only good for listening. MIDI/alsa/oss/jackd/pulseaudio - thousands of them, and this web only works in some precise setups.

I tried to install plenty of MIDI software on Ubuntu Lucid Lyx - epic fail. Jackd stops, pulseaudio crashes and freezes... It is such a mess.

So I decided to write a trivial application which will look like a piano keyboard and play recorded samples instead of going through MIDI synth when keyboard or mouse keys are pressed. I checked FreshMeat - there are only MIDI synthesizer there.

And I need a simple, fast, nice and non-brain-fucking in setup application, which just plays what I press.

5. Elliptics network implementaion details: data redundancy, fault tolerance, transctions, versions and snapshots, data deduplication and so on.

Elliptics network is a distributed key/value storage. Having more keys associated with the same data being written means that multiple copies of the written block will exist in the storage. Using data hashes to generate keys and having multiple hash functions registered for given block we end up having multiple copies of the data.

Knowing ID distribution among nodes in the storage it is possible to tweak hash generation function the way it will produce hash, which will belong to the interested node. This is a rather complex task to be implemented on client, and instead we introduced virtual datacenters.

Virtual datacenter is a set of nodes combined into some logical group, where nodes may or may not actually be physically groupped together. System modifies hash generated by common function by changing its first 4 bytes to be equal to the datacenter number.

Thus VDC feature allows to specify preconfigured prefix in every transaction ID - the first 4 bytes. Nodes which have their first ID bytes equal to VDC number will receive all transactions indexed by appropriate hash function.

Here is a virtual datacenter example.

Let's suppose we have two transformation functions setup on client: dc1_sha1 and dc2_sha1. They will produce sha1 hash of the data with the first bytes set to 1 and 2 accordingly.

Now let's suppose we add two nodes with IDs being equal to 0x01000000 and 0x01000080 and then two nodes with 0x02000000 and 0x02800000 IDs. Now there will be two transactions made with above transformation functions with its first 4 bytes set either to 1 or 2, so there will be a guaranteed copy in each virtual datacenter.

Now we can implement multiple VDCs with different ID's first bytes for every datacenter we want to work with. If we only need to have 2 copies, but there are more than 2 datacenters, nodes can be spread between those VDCs. '2' is arbitrary here of course.

This feature also allows to implement geographical linking of the requests. Let's suppose some application receives data read request from Moscow, it can check whether its set of transformation functions contains the one with the ID assigned to Moscow. If there is such a function, it can be used first to obtain object ID and to fetch it from Moscow-local servers instead of going to New York, where main datacenter lives. If Moscow storage does not contain our requested object, we will use second transformation function(s), which will 'point' to main storage cluster.

5.1. Fault tolerance in elliptics network.

In a meantime I was told that there will be a special man who will teach me how to make presentations...
They got me. And I did not yet read what I wrote several days ago :)

The purpose of Elliptics network storage is to allow users to access a set of physically distributed servers through flat addressing model in decentralized network environment. Key/value distributed storage provides an efficient method of accessing data with limited set of constraints. As a proof that such functionality is useful in a real life scenarios we present practical implementation of the DHT storage server with modular IO backends on top of common filesystems or database and various frontends varying from POSIX interface to HTTP access mode. We will discuss limitations faced with distributed hash table approach and compare them to functionality provided by centralized storage systems, namely high-performance data access and its high-availability in the fault-prone environment. Based on the practical results and flexibility of the implemented storage model we will highlight possible new functionality and the ways it could be made in the discussed system.

This is an abstract, I will post some blocks here, but whole article will be available when LK is over.

libeblob is a low-level IO library which stores data in huge blob files appending records one after another.

I implemented all missing functionality, added comments and README, and rolled out the first version: 0.0.1

Here is a short changelog:

• defragmentation tool: entries to be deleted are only marked as removed, eblob_check will iterate over specified blob files and actually remove those blocks
• off-line blob consistency checker: eblob_check can verify checksums for all records which have them
• run-time sync support - dedicated thread runs fsync on all files on timed base
• added documentation and comments

libeblob can be downloaded from git tree ($ git clone http://www.ioremap.net/git/eblob.git/) or archive.

Elliptics network is a very modular key/value (distributed hash table) storage. Among others it allows to build pluggable low-level IO backends - those entities which store data.

Currently elliptics network supports following IO backends:

• file IO backend, where each transaction is stored as a separate file
• TokyoCabinet database backend - each transaction is stored as a record in appropriate table. I dropped BerkelyDB support because of its low performance, even though TC does not provide ACID contrary to BDB

And now I added append-only blob storage - libeblob.

Following features are already supported:

• fast append-only updates which do not require disk seeks
• compact index to populate lookup information from disk
• multi-threaded index reading during starup
• O(1) data location lookup time
• ability to lock in-memory lookup index (hash table) to eliminate memory swap
• readahead games with data and index blobs for maximum performance
• multiple blob files support (tested with blob-file-as-block-device too)
• optional sha256 on-disk checksumming
• 2-stage write: prepare (which reserves the space) and commit (which calculates checksum and update in-memory and on-disk indexes). One can (re)write data using pwrite() in between without locks
• usuall 1-stage write interface
• flexible configuration of hash table size, flags, alignment

TODO list includes:

• defragmentation tool: entries to be deleted are only marked as removed, we need to have a tool (or embed it into library) to actually remove those blocks from blob files
• proper off-line blob consistency checker: we put a checksum into data blob, someone may want to check if read data matches
• run-time sync support - we should have a dedicate thread to call syncs on timed base

Elliptics network uses it as one of its low-level IO backends. Numbers I posted (1, 2, 3) also highlight its advantages.

But during elliptics network integration with libeblob I found how unoptimal transaction history log was implemented in the storage (and maybe found an answer why monsters like Cassandra do not support it at all). Maybe its time to rethink and reinvent it though...

Anyway, there is a set of features I will create to complete this implementation as well as new elliptics network release (with C++ and Python bindings and new IO backend).
Stay tuned!

I extended C++ and Python bindings for elliptics library, although python part was a little bit messy at first.

Python is massively ... single-threaded language: GIL is a tricky global lock monster, which does not easily allow to implement not only threads but also async communications. Of course python has threads, but they are internal entities which can not be worked with from the outside system threads.

Contrary elliptics network library is a multi-threaded application, and the main problem related to python was its async completion notifications. When transaction is finished or being processed, remote side can send multiple replies about its state (like chunks of data being read for exampl), which are processed in different thread than original sending one.

Python does not expect itself to be interrupted by those callbacks (even if we properly wrap them into python classes). But still we can (or it can be called a hack) invoke async python callbacks from C/C++ code and external threads.

Python may have multiple execution threads, or states, and at startup we have to select the one, which will be used to invoke our C++ callbacks. In older python versions it took quite a bit of efforts: stack selection, saving it somewhere in private data, then switch to/from it and so on. In newer python versions it is just as simple as calling PyEval_InitThreads(). Python thread which called it first will be selected as the one to dispatch exernal callbacks. Then just doing

PyGILState_STATE st = PyGILState_Ensure();
this->get_override("some_virtual_callback_invoked_from_cpp")(its, data);
PyGILState_Release(st);

will schedule C++ callback invocation. It will take care about thread state and GIL.

And when I managed to finally implement all wrappers and helpers for async bidirectional C++-to-Python communication, I dropped its support. Just because it is much simpler to read/write data using blocking calls, which is I believe the most common Python programming model.

That's how this works in python now:

#!/usr/bin/python

from libelliptics_python import *
from array import *
import sys

id = array('B')
for x in xrange(0, 20) :
	id.append(x + 1)

trans = array('B')
for x in xrange(0, 20) :
	trans.append(1)

try:
	log = elliptics_log_file("/dev/stderr", 15)
	n = elliptics_node_python(id.buffer_info()[0], log)

	t = elliptics_transform_openssl("sha1")

	n.add_transform(t)
	# weird thing happens if I write n.add_transform(elliptics_transform_openssl("sha1"))
	# we crash somewhere inside c++ binding, probably because I implemented lazy
	# reference counting model (i.e. not at all :)
	# thus object MUST live after this function is completed
	# this should be fixed of course with proper copy constructors
	# the same applies to logger actually

	n.add_remote("devfs8", 1025)

	#n.write_file(trans.buffer_info()[0], "/tmp/test_file", 0, 0, 0)
	#n.read_file(trans.buffer_info()[0], "/tmp/test_file.read", 0, 0)

	data = array('B', "1234567890")
	n.write_data(trans.buffer_info()[0], data.buffer_info()[0], 0, data.buffer_info()[1])

	read = array('B')
	for x in xrange(0, len(data)) : read.append(0)

	n.read_data(trans.buffer_info()[0], read.buffer_info()[0], 0, read.buffer_info()[1])

	for x in xrange(0, len(data)) :
		print data[x], " ", read[x]
except:
	print "Ooops, error:", sys.exc_info()[0]

$ ./test.py  # written and read data from example above
49   49
50   50
51   51
52   52
53   53
54   54
55   55
56   56
57   57
48   48

Also finished proper object copy for logger, it will clone logger and when proper methods are implemented one can create own private python-made loggers. But that's details.

To date I consider python bindings as well as C++ ones fully finished. C++ has async callbacks as well as blocking sync IO operations.

After several bottles of cold beer with this killing heat in Moscow... And brain suddenly starts 'thinking' in the right or better say - alternative direction.

[zbr@baccara lib]$ ./test.py 
010203040506: successfully initialized notify hash table (256 entries).
Server is now listening at 0.0.0.0:0.
010203040506: new node has been created at 0.0.0.0:0, id_size: 20.
connected to 127.0.0.1:1025.
123abc000000 reverse lookup -> 127.0.0.1:1025.
123abc000000: node list dump:
      id: 123abc000000 [12], addr: 127.0.0.1:1025.
do_transform: transform
calling openssl::transform
transform
000000000000: created trans: 1, cmd: 4, size: 575, offset: 0, local_offset: 0 -> 127.0.0.1:1025.
010101010101: created trans: 2, cmd: 4, size: 64, offset: 0, local_offset: 0 -> 127.0.0.1:1025.
000000000000: transactions sent: 2, error: 0.
010203040506: started resending thread. Timeout: 60 seconds.
000000000000: object write completed: trans: 1, status: 0.
010101010101: object write completed: trans: 2, status: 0.
Successfully wrote file: '/tmp/test_file' into the storage, size: 575.
010101010101: created trans: 3, cmd: 5, size: 0, offset: 0, local_offset: 0 -> 127.0.0.1:1025.
010101010101: read completed: file: '/tmp/test_file.read.history', offset: 0, size: 96, status: 0.
010101010101: read completed: file: '/tmp/test_file.read.history', status: 0, freeing: 1.
/tmp/test_file.read.history: objects: 1, range: 0-18446744073709551615, counting from the most recent.
a13677c93a73: created trans: 4, cmd: 5, size: 575, offset: 0, local_offset: 0 -> 127.0.0.1:1025.
a13677c93a73: reading chunk into file '/tmp/test_file.read', direct: 0, offset: 0/0, size: 575, err: 0.
a13677c93a73: flags: 00000080, offset:        0, size:      575: match: -2, rest: 18446744073709551615
a13677c93a73: read completed: file: '/tmp/test_file.read', offset: 0, size: 575, status: 0.
a13677c93a73: read completed: file: '/tmp/test_file.read', status: 0, freeing: 1.
010203040506: destroying node at 0.0.0.0:0, st: 0x8609f50.


[zbr@baccara lib]$ md5sum /tmp/test_file /tmp/test_file.read
d712a7ccfe66a45bef31892befa250f8  /tmp/test_file
d712a7ccfe66a45bef31892befa250f8  /tmp/test_file.read
[zbr@baccara lib]$

Sort of completed - there are couple of other functions (read/write data via pointer and not file) to test, but overall it is done. Although I can not say I understand how boost::python works, and why it may crash or did not compile if I change A to B.

But what do you want, I started to write c++ bindings 2 days ago and wrote first python program today.
After all: program crashes - its time to make alpha release!

To solve 'unsigned char *' and other non-existing types in Python I use this hack:

class elliptics_node_python : public elliptics_node {
	public:
		elliptics_node_python(unsigned long lptr, elliptics_log &l) :
			elliptics_node((unsigned char *)lptr, &l) {};

		void read_file_by_id(unsigned long lid, const char *file, uint64_t offset, uint64_t size) {
			elliptics_node::read_file((unsigned char *)lid, const_cast(file), offset, size);
		}

I.e. transform 'unsigned long' into pointer in C++ code. I wonder why Python calls it 'int' no matter what :)

[zbr@baccara lib]$ cat test.py 
#!/usr/bin/python

from libelliptics_python import *
from array import *

id = array('B')
for x in xrange(0, 20) :
	id.append(x + 1)

trans = array('B')
for x in xrange(0, 20) :
	trans.append(1)

log = elliptics_log_file("/dev/stderr", 10)
n = elliptics_node_python(id.buffer_info()[0], log)

t = elliptics_transform_openssl("sha1")

n.add_transform(t)
# weird thing happens if I write n.add_transform(elliptics_transform_openssl("sha1"))
# we crash somewhere inside c++ binding, probably because I implemented lazy
# reference counting model (i.e. not at all :)
# thus object MUST live after this function is completed
# this should be fixed of course with proper copy constructors
# the same applies to logger actually

n.add_remote("localhost", 1025)

n.write_file(trans.buffer_info()[0], "/tmp/test_file", 0, 0, 0)
n.read_file(trans.buffer_info()[0], "/tmp/test_file.read", 0, 0)

My study of this language was started today. And while my knowledge base is somewhere between zero and void I already can ask stupid qustions, which were not answered on #python / irc.freenode.net

What python type to use when c++ to python boost::python binding requires 'unsigned char *' parameter?
Code snippet will tell much more:

class test_class : public test_class_base {
	public:
		test_class(const char *path);
		virtual ~test_class();

		virtual void log(const char *msg);
		unsigned char test(unsigned char *ptr) { return *ptr; };
	private:
		std::ofstream *stream;
};

....

	class_ >("test_class", init())
		.def("log", &test_class::log, &test_class_wrap::default_log)
		.def("test", &test_class::test)
	;

I ommitted wrapper class definition, since it is not critical. It works for python-string to c++ 'const char *' transform, but unsigned char pointer fires up an error. I tried both struct.unpack_from("P", array) and array.buffer_info()[0], but python says that they both return 'int' while c++ code expects 'unsigned char *':

id = array('B')
for x in xrange(0, 20) :
	id.append(x)

s = struct.unpack_from("P", id);
print hex(s[0])

t = test_class("/dev/stderr")
print hex(t.test(s[0]))

error:
[zbr@baccara python]$ ./test.py
0x3020100
Traceback (most recent call last):
  File "./test.py", line 19, in 
    print hex(t.test(s[0]))
Boost.Python.ArgumentError: Python argument types in
    test_class.test(test_class, int)
did not match C++ signature:
    test(test_class {lvalue}, unsigned char*)

Code snippets can be also found at http://paste.pocoo.org/show/239085/.

If no solution will be found, I will refactor elliptics python binding to support new classes for missing types like 'elliptics_id' for 'unsigned char *'.

I study C++ effectively for last two days. Well, about 15 years ago I knew it to some degree (without STL, although with templates), but I would not count it now.

That's why my first sexual experience with C++, STL and boost::python pushed me into deep depression.
Any single error and you will get 7-10 pages of compiler errors, which are completely non-understandible for newbie like me. Googling them for 30 minutes I found, for example, that stl::iostream and its children are non-copyable streams. No need to tell that this was not obvious from things like (5 pages of):

class test_class {
  public:
    test_class(const char *path) : stream(path) {};
    std::ofstream stream;
};

In file included from /usr/lib/gcc/i686-redhat-linux/4.4.4/../../../../include/c++/4.4.4/bits/localefwd.h:43,
                 from /usr/lib/gcc/i686-redhat-linux/4.4.4/../../../../include/c++/4.4.4/string:45,
                 from /usr/lib/gcc/i686-redhat-linux/4.4.4/../../../../include/c++/4.4.4/stdexcept:39,
                 from /usr/include/boost/function/function_base.hpp:14,
                 from /usr/include/boost/function/detail/prologue.hpp:17,
                 from /usr/include/boost/function/function_template.hpp:13,
                 from /usr/include/boost/function/detail/maybe_include.hpp:13,
                 from /usr/include/boost/function/function0.hpp:11,
                 from /usr/include/boost/python/errors.hpp:13,
                 from /usr/include/boost/python/handle.hpp:11,
                 from /usr/include/boost/python/args_fwd.hpp:10,
                 from /usr/include/boost/python/args.hpp:10,
                 from /usr/include/boost/python.hpp:11,
                 from eee_python.cpp:16:
/usr/lib/gcc/i686-redhat-linux/4.4.4/../../../../include/c++/4.4.4/bits/ios_base.h: In copy constructor
‘std::basic_ios<char, std::char_traits<char> >::basic_ios(const std::basic_ios<char, std::char_traits<char> >&)’:
/usr/lib/gcc/i686-redhat-linux/4.4.4/../../../../include/c++/4.4.4/iosfwd:47:   instantiated from
‘boost::python::objects::value_holder::value_holder(PyObject*, A0)
[with A0 = boost::reference_wrapper<const test_class>, Value = test_class]’

I stopped to count such shit error-reporting pages when I tried to export virtual functions via multi-level inheritance through boost::python. ALthough it was quite simple in tutorial...

And yet after 5 A.M. I fucking won:

[zbr@baccara lib]$ python
Python 2.6.2 (r262:71600, Jun  4 2010, 18:28:04)
[GCC 4.4.3 20100127 (Red Hat 4.4.3-4)] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> from libelliptics_python import elliptics_log_file
>>> w = elliptics_log_file("/dev/stderr", 31)
>>> w.log(31, "qweqweqe\n")
qweqweqe

Tomorrow I will complete Python bindings and happily hopefully forget C++ for another 15 years.

Our generic system contains just 4 sata disks combined into software RAID10. Putting BLOB IO backend to ext4 fs and installing two nodes, we got quite surprising skyrocketed results:

2 sata storages, each contains 4-disks software RAID10

There are 10 millions of records, total of 87 Gb. Each node contains about 44 Gb of data, and it has 24 Gb of RAM. Although we flush caches prior each test run, readahead games quickly suck blob files back into ram, which I believe explains such results: 700 rps (of completely random IO) within 200 ms, 1000 rps within 300 ms.

I wonder why 4-disks SATA setup is close to 16-disks SAS storage. Looks like raid10 requires a serious tuning for larger storages, otherwise I can not explain such major hardware difference and quite similar performance numbers.

It took a little bit more time than we expected: it tends that people suddenly get some other tasks and of course with higher priority.

So, I decided to write thinkgs up myself. To implement python bindings I will use boost::python, but first I have to wrap common elliptics network operations into proper classes.
That's what I ended up with today:

int main()
{
	unsigned char id[DNET_ID_SIZE];
	elliptics_transform_openssl t("sha1");
	elliptics_log_file log("/dev/stderr", 15);

	memset(id, 1, DNET_ID_SIZE);

	elliptics_node n(id, &log);

	n.add_remote("devfs8", 1025, AF_INET);
	n.add_transform(t);
#if 1
	elliptics_callback_io callback(&log);

	memset(id, 0xff, DNET_ID_SIZE);
	n.read_data(id, 0, 0, callback);
#endif
	n.write_file(id, const_cast<char *>("/tmp/some_file.txt.bak"), 0, 0, 0);
	n.read_file(id, const_cast<char *>("/tmp/some_file.txt"), 0, 0);

	n.read_file(reinterpret_cast<void *>(const_cast<char *>("1.xml")), 5,
			const_cast<char *>("/tmp/1.xml.cpp"), 0, 0);

	/* cool, yeah? we have to wait for read_data() to complete actually */
	sleep(10);
}

Most of them can throw numeric exceptions. There are less than a dozen of classes, which I will put into proper boost::python wrappers.

And in a meantime it is of course possible to use them in c++ code. Current version can be found in git.

DHT is virtually the same hash table spread over multiple nodes. Thus it shares its advantages, like O(1) access when properly configured, and its weak parts, like full absence of scalability.

Yes, hash table does not scale. Because to change its size one has to perform lots of tricks which are generally end up in a full table content rehash. With millions of entries on disks this may take a while...

Thus we can not easily extend hash table storage - each node addition will require table rebuild. Depending on DHT configuration and routing protocol used, it can be full or partial content copying.

Contrary to hash table, classical distributed storage with dedicated master server is able to scale without need to copy data each time new server is added. Master server will return this new node's address for each new write, then next node and so on.

This looks shine and well in theory. Let's face the practice.

Data tends to wear down with time - we do not lok at old photos and do not read old mails as frequently as access recently written information. Thus servers which host old data will not be loaded compared to the new nodes in the described master server example.
To fix this issue master server has to start data copying - old servers move their old unaccesible data to some new nodes, and new writes can go to old nodes too. This task is full of non-trivial heuristics about what data to move and what server to use. With time it ends up with data copy for each new write (or usually sufficiently large chunk write).

In distributed hash table this copy is not needed, since by design writes are balanced across the whole storage (when cryptographically strong hash function and storage size are configured of course).
In DHT there is no problem of data wearing, since each write goes to (kind of) random node, thus all nodes will contain roughly the same amount of old and new data.

Drawing the line, in DHT we have to copy data when new node is added to take some load from the neighbours, while in master-server scenario we have to copy each time new data is added (this can be limited to large chunks of course). In theory master-server scenario will copy data to the distribution DHT provides out of the box, and still will have to copy again when new nodes added.

In some cases this is not an issue - we may want not to start data redistribution in master-server storage because of some reasons, or may not foresee that this demand will appear though, while need for data copy in DHT when new node is added is a must - otherwise data will not be accessible because of changed hash distribution over nodes.

This two cases frequently (if not all the time :) becomes the most significant corner cases when DHT is not selected to be used for distributed storage.

Previous elliptics test showed how good (or bad) is append-only BLOB backend, when HTTP proxy issued two reads to handle single client's request.
Namely it fetched transaction history log to find out which stored transaction has the same version as client asks.

Now let's see how well we behave when single client request results in single data read from the blob.

700 rps witin 100 ms, 900 rps within 300 ms

Surprisingly absolute numbers did not change - we still fit 1000 rps within 300 ms, which is rather unacceptible for single client. But at the beginning we are about 2 times faster than described 2-reads case: we handle 700 rps within 100 ms range.

Testing etup is the same as in previus test: 2 SAS storages attached, each has 16 disks in it. Ext4 over software RAID10. 2.6.34 kernel. Random requests. 10 millions of records (about 87 Gb total, 44 on each SAS storage).

We also ran the same test but moved storage blob to single SAS storage. Also moved it to block device directly instead of using usual file on ext4 filesystem. Results were 2 times degraded as expected: like about 600 rps within 200 ms.

There was no difference whether block device or ext4 was used as low-level storage.

In a meantime blob IO backend got loading index support to speedup its startup. The only missing feature is index truncation aka ability to compact and remove deleted entries. When this is done, I will start POHMELFS - POSIX frontend to elliptics network.
Its initial implementation will not be performance centered as well as feature-rich, instead I will create a rather simple client, which will allow trivial deployment procedure.

And I have to start writing elliptics network paper for Linux Kongress. This may take a while though...
Stay tuned!

Elliptics network is a quite modular distributed hash table, which allows to implement and build-in different IO backends, enabled via config. IO backend is a quite simple entity which just stores data to media and allows to read it back using provided tranaction ID.

BLOB IO backend is a yet trivial append-only array of variable-sized elements, which are stored one after another on disk. Each entry's offset is stored in hash table in RAM, indexed by transaction IDs. Currently we do not even support ID index - to create this hash table in memory initialization code runs over whole file and jumps from entry to entry. With 10 millions of entries stored on single node (about 44 Gb of data) this takes about 8-9 minutes to initialize, so it is likely a good idea to implement external index.
Hash table is neven swapped to disk if configured to be locked in RAM.

Thus to get an object we ask hash table about object offset and read it directly from the storage (send it via sendfile() actually). In theory it should be noticebly faster than filesystem IO backend, where each object is stored in separate file.

Let's see raw results for 2 sas storages (each one contains 16 disks), about 10 millions of data objects (total of about 30 millions, since we have 2 additional history objects for each data one). To handle single request we have to read two objects from disk: one history (parse it and get ID for selected version) and data (with the ID read previously). It is possible to disable versioning and get data via single disk read of course.

Filesystem is default ext4 on 2.6.34 kernel. Machine has about 24 Gb of RAM. Random requests.

600 rps witin 200 ms, 1000 rps within 300 ms

And compare BLOB to filesystem IO backends.

Clearly blob is about 2 times faster than filesystem at the beginning (green one is blob, violet is file-per-object aka filesystem backend), but with time they become equal, likely because of filled hardware queues.

Although I play some simple tricks with read-ahead in blob backend, I still want to test with data stored in raw block device, thus eliminating potential FS overhead, although ext4 has extents it still may require multuple seeks to read different blocks in single file. Also direct-io case can be useful too.

Main problem with blobs is object removal support. While in common web scenarios we can just mark object as removed and drop it from index not even trying to 'squeeze' blob file, in a real life some external application (or IO backend itself triggered by timeout or whatever else) should be able to compact blobs.
Back to drawing board...

This is a rather small release (actually it was made several days ago, but I postponed announcement to allow binding poll to stick on top) - it does not even break library or API at all.

Instead it changes IO server and its backends to use config file insted of zillions command line options.
Main purpose of this step was not to simplify deployment life actually, but instead to make a ground for the further extensions: namely automatic network topology configuration and new single-seek backend.

Currently elliptics network servers are required to be properly configured prior cloud join - they have to have unique IDs, which split address space according to administration policy. But all the time it is just as simple as spread IDs according to node's disk space (the bigger disk space is the larger ID set it covers). And in the common case of the same nodes IDs should be equally spread over covered address space.

This will be made automatic to reduce configuration only to network address selection. It should also alow to reconfigure storage on demand, for example when new nodes added or removed.

As of new IO backend, I plan to implement a rather trivial low-level storage, which will operate with huge blobs of data. With some (common) usage cases it is supposed to perform only single seek to get data by its index. Main users will be storages with lots (tens of millions) of rather small objects. Classical databases like TokyoCabinet IO backend do not work here, since even for several millions of objects it starts paging out which drops it down to floor immediately, which is unacceptible.

File IO backend is much worse in this scenario. For example having about 30 millions of objects (about tens of KB each) with versions (i.e. to get single object we have to read two times from disk) loaded into SAS and SATA 16-disk raid10 machines, we got following numbers (random objects are fetched):

SAS raid10 array (2 storages of 16 disks each)
Got 800 rps within 300 ms

SATA raid10 array (2 storages of 16 disks each)
Got 200 rps within 200 ms

Which in SATA case roughly corresponds to 20ms per seek and we make 2 seeks to get an object (4 seeks, which 2 times decreases performance, since we have to read two files from the disk when versions are used). With its uber-large NCQ depth of 32 this is the end of the story: 400 rps from such setup.

SAS was a little bit (3-4 times) faster - 800 rps within 300 ms and 600 rps within 200 ms.
Again, to handle a single request we have to read two times from the storage (each one in turn resulted in multiple seeks) - one to get version information, and another one to get object with some version itself.

With the new IO backend I believe we can suddenly increase performance. By the factor of 2.
But so far it is a speculation only, let's first implement the idea...

Dear Evgeniy,
Congratulations! The program committee has finished their work and is glad to tell you that your submission for a /Refereed Paper/ with the title

"Elliptics network - a distributed hash table, design and implementation"

was accepted!

Wanna chat? I will show up a small presentation for Linux Kongress this year. Back to writing table now... its time to write some bits.

The former is actually quite religious question, but still it has a fair amount of technical background to talk about.

Main pros of the dedicated metadata server is its incredible flexibility and control. To determine where given object lives we ask special server which can perform whatever we want to make the answer: system can check permissions, locate the least loaded server, update centralized statistics or contact oracle and notify external entities.
Thus metadata server becomes a complex database which is too hard to replicate and generally maintain in consistent state with its copies. And we do need another copies, since every server fails and dedicated metadata one fails too. In some practical scenarious they fail even more frequently than storage ones, although quite contrary I have example where they never fail during several years of maintenance and everyday access.

But no matter what, generally we want to replicate metadata server and preferably to implement master-master operation mode to unload single entry of failure. To date I do not know production-quality master-master replication solution neither in free nor in proprietary world. And by production I mean hundreds of millions of records with millions of records updated/created per day with physically separated datacenters with flaky link between.

A very elegant solution for metadata servers is ... full absence of them. Distributed hash storage is one of them. But it only solves access problem - client can determine needed server itself, but we still have to implement control access, statistics and notifications somewhere. If we put more complex logic into the storage, unflexibility of the central control point absence becomes even more visible.

One such problem is caching. When some object is popular we want to put it to faster media to satisfy increased access rate. For example we can create multiple copies and distribute clients between them.
With metadata server this is a trivial case - we just update appropriate database record, so that connected client could get random (or preferable, doesn't matter) path to the data object. The more popular content is the more copies we put into the storage and update metadata database.

With the distributed storage without central metadata server we have to perform a full lookup to determine whether given object is present in the storage or not. Which means we have to contact remote server and try to read some data from its media. This slows things down noticebly, especially for non-popular content which does not have hundred of cached copies.

A simple solution is to move a control entity from the storage to higher levels. In case of cache it means some external storage, which will contact low-level one only when requested objects are not in the cache. Depending on the cache implementation this can be very cheap price for the access problems.

Thus we build a layerd system where DHT is a low-level storage.

Actually this solution will also work for metadata server too, except that for some workloads classical LRU caches do not work. Thus squid or page cache should not be used for them, and metadata server solution wins again.

But what wins and especially what is needed not only for distributed metadata-free storages is cache with content weights - the more frequently given object is requested the more time it will live in cache even if currently it is not requested. Last access time does not work in this case.

To my shame I do not know such cache systems - very popular memcached and squid do not support this iirc. And they do not allow to distribute cache content among multiple nodes. Memcached actually has quite nice frontends, which can form DHT, but still pure memcached lacks some features.

Plan has been plotted by itself...

This is a rather small update which brings together various recovery tools bug fixes as well as debug cleanups.
I believe this will be the last 2.8 elliptics network release, since I plan to change server code to drop command line arguments in favour of config file, since this breaks backward compatibility I believe we will change version to 2.9 cycle.

Actually main reason I want to introduce config files (besides zillion command line options mess) is to move further in autoconfiguration land. This will require some options which are not quite fit into command-line interface, or actually into its getopt() parser.

And the main goal is to implement full server node autoconfiguration. Basically we need some simple enough protocol to gather node usage statistics (we have this already via stat command) and a policy engine, which will run over all nodes in the cloud, collect their statistical data and determine ID of the joining node according to loaded heuristics. The main (and to date the only) one is to select joining node ID, that it could get half of the load from the neighbour node. Extension of this mode is to change IDs of all nodes so that data could be spread equally over all nodes.

So according to config options joining node will connect to all nodes, get their storage statistics and IDs and calculate its own ID.

WIth this changes completed we can simplify and automate storage reconfiguration, which basically will not require administrators to perform any steps to add or remove server nodes to/from the cloud.
Automation will not be full though - elliptics network maintains eventual consistency model, thus after new node has been added or removed whole storage does not start reconfiguration/recovery process. This is external step which is not started by the storage itself. Thus when node is removed some data will not be accesible until recovery tools completed its work. And in some cases we want to postpone recovery... This will be administration step, but at least knowledge of very low-level configuration will be taken off admin shoulders.

This is not a trivial task though - we support so called virtual datacenters, when storage nodes are groupped into smaller clouds, usually physically separated, to guarantee that different data copies live in different storage node groups. Dumb storage check can determine that node being added should live in some other virtual datacenter than that admins wanted it to be added, but it is a technical details of the process, which I believe can be easily fixed.

Dear fcking Ubuntu Lucid, I'm writing you from the tank in fire, and you know, I want you to be here.

$ clisp 
  i i i i i i i       ooooo    o        ooooooo   ooooo   ooooo
  I I I I I I I      8     8   8           8     8     o  8    8
  I  \ `+' /  I      8         8           8     8        8    8
   \  `-+-'  /       8         8           8      ooooo   8oooo
    `-__|__-'        8         8           8           8  8
        |            8     o   8           8     o     8  8
  ------+------       ooooo    8oooooo  ooo8ooo   ooooo   8

Welcome to GNU CLISP 2.44.1 (2008-02-23) 

Copyright (c) Bruno Haible, Michael Stoll 1992, 1993
Copyright (c) Bruno Haible, Marcus Daniels 1994-1997
Copyright (c) Bruno Haible, Pierpaolo Bernardi, Sam Steingold 1998
Copyright (c) Bruno Haible, Sam Steingold 1999-2000
Copyright (c) Sam Steingold, Bruno Haible 2001-2008

Type :h and hit Enter for context help.

[1]> (asdf:operate 'asdf:load-op :cl-ppcre)
; loading system definition from /usr/share/common-lisp/systems/cl-ppcre.asd into #
;; Loading file /usr/share/common-lisp/systems/cl-ppcre.asd ...
; registering # as CL-PPCRE
; registering # as CL-PPCRE-TEST

*** - Program stack overflow. RESET
[2]>