Jedi/Sector One's random thoughts

Here's a big picture of what data structures you can get of some NoSQL data stores, in a JSON representation.

Before picking a data store, try to model your data to these constraints and see what the best fit is.

SQL

{
    "table 1": {
        "key 1": {
            "property 1": "string",
            "property 2": "numerical value"
        },
        "key 2": {
            "property 1": "string",
            "property 2": "numerical value"
        }, ...
    },
    "table 2": {
        "key 3": {
            "property 3": "date"
        },
        "key 4": {
            "property 3": "date"
        }, ...
    }, ...
}

• The set of properties is fixed for every record of a table.
• Any key and/or property can be indexed.

Cassandra

Columns:

{
    "column family 1": {
        "key 1": {
            "property 1": "value",
            "property 2": "value"
        },
        "key 2": {
            "property 1": "value",
            "property 4": "value",
            "property 5": "value"
        }
    }, ...
}

and supercolumns:

{
    "column family 2": {
        "super key 1": {
            "key 1": {
                "property 1": "value",
                "property 2": "value"               
            },
            "key 2": {
                "property 1": "value",
                "property 4": "value",
                "property 5": "value"           
            }, ...
        }, ...
        "super key 2": {
            "key 1": {
                "property 4": "value",
                "property 5": "value"               
            },
            "key 2": {
                "property 1": "value",
                "property 6": "value",
                "property 7": "value"           
            }, ...
        }, ...
    }, ...
}

• Columns families are constrained by a schema. You need to predefine their names, their types (simple columns or supercolumns), and how the keys and properties will be sorted. Changing the schema requires a server restart in < 0.7 versions.
• A database ("keyspace") can mix simple columns and supercolumns.
• Range queries are supported.
• Support for expiration times in >= 0.7
• Distributed, fault-tolerant.
• Never locks, even for writes. Efficiently uses multiple cores.
• Runs on a lot of operating systems (wherever a JVM exists).
• No REST client interface. Uses Thrift serialization.
• Can run Hadoop map/reduce jobs.

MongoDB

{
    "namespace 1": any json object,
    "namespace 2": any json object,
    ...
}

To elaborate, here's an example:

{
    "namespace 1": [
        {
            "_id": "key 1",
            "property 1": "value",
            "property 2": {
                "property 3": "value",
                "property 4": [ "value", "value", "value" ]
            }, ...
        },
        {
            "_id": "key 2",
            "property5": {
                "property3": "value",
                "property7": { "question": "6x9", "answer": 42, "list": [ 3, 5 ] }
            }, ...      
        }, ...
    ]
}

• No schema, the model is totally flexible. Any property can be added to any object any time.
• Any property can be indexed, at any depth (for example, "property3" could be indexed).
• A wide range of operations can be performed.
• Collections can be capped to a fixed number of bytes or elements.
• Will be distributed and fault-tolerant through a proxy, but this one is still in early stage.
• Write operations lock the whole database. Efficiently uses multiple cores.
• Written in C++ but currently runs on a limited number of operating systems.
• Uses its own protocol, but basic REST proxies do exist (in Python and NodeJS).

Riak

{
    "bucket 1": {
        "key 1": document + content-type,
        "key 2": document + content-type,
        "link to another object 1": URI of other bucket/key,
        "link to another object 2": URI of other bucket/key,        
    },
    "bucket 2": {
        "key 3": document + content-type,
        "key 4": document + content-type,
        "key 5": document + content-type
        ...
    }, ...
}

• Keys are indexed.
• Range queries are not supported.
• Retrieving multiple keys in a single query isn't supported (must use map/reduce).
• Never locks, even for writes. Efficiently uses multiple cores.
• Distributed and fault tolerant.
• Records can be traversed through links.
• Runs on any platform Erlang runs on.
• REST client interface.

Pincaster

{
    "layer 1": {
        "key 1": {
            {
                "property 1": "value",
                "property 2": "value",
                "property 3": "value", ...
            }
        },
        "key 2": {
            {
                "property 1": "value",
                "property 4": "value",
                "geographic location": "latitude, longitude"
            }
        }, ...
    }, ...
}

• Keys and geographic locations are indexed.
• Keys are lexically ordered and prefix matching queries are supported.
• Efficient storage of a lot of small entries.
• Support for expiration times on stored keys.
• High throughput with a single host.
• Writes can block reads, but efficiently uses multiple cores.
• Written in portable C, works on most operating systems.
• No distribution nor fault tolerance.
• REST client interface.

Redis

{
    database number: {
        "key 1": "value",
        "key 2": [ "value", "value", "value" ],
        "key 3": [
            { "value": "value", "score": score },
            { "value": "value", "score": score },
            ...         
        ],
        "key 4": {
            "property 1": "value",
            "property 2": "value",
            "property 3": "value", ...
        }, ...
    }
}

• A database can mix different types of keys.
• Keys and scores are indexed.
• Efficient storage of a lot of small entries.
• High throughput with a single host.
• Support for expiration times on stored keys.
• Collections can be lists or hold distinct elements (sets).
• Rich set of atomic operations.
• No distribution (but through some client libraries) nor fault tolerance.
• Only takes advantage of a single CPU core (but you can run multiple instances on the same host)
• Written in portable C. Runs on most operating systems.
• Uses its own protocol.

Elliptics Network

KumoFS

Flare

{
    "key 1": "value",
    "key 2": "value",
    ...
}

• No range queries.
• Keys are indexed.
• Efficient storage of a lot of small entries.
• KumoFS supports the CAS operation.
• High throughput with a single host.
• Uses Tokyo Cabinet for on-disk storage. Writes can block reads.
• Distributed and fault tolerant.
• Written in portable C and C++, works on most operating systems.
• Memcache (KumoFS, Flare) or REST (Elliptics Network) client interface.

CompeGPS Twonav is an awesome piece of GPS navigation software, featuring both onroad and offroad navigation.

The iPhone version is now available on the AppStore and it definitely looks like the best GPS navigation app for iPhone ever.

Oh and it features a well-known FTP server :)

Get it while it's hot, it's really worth the price.

In order to reduce latency and improve the user experience, using client caching is the web development 101.

Setting correct HTTP server-side headers in order to instruct the web browser to keep the content in its local cache, has become straightforward with modern web servers (for static content), frameworks and middleware layers (Rack!).

However, this is only a hint. The actual caching policy remains up to the web browser. Setting HTTP headers doesn't give applications any control nor feedback about what's really going on client-side.

Specifically:

• You can't tell whether a resource is already in the client cache or not (ok, you can, but by making extra requests, which is, outside the scope of a demonstration, exactly what you're trying to avoid),
• You can't tell whether what you asked the browser to cache was actually cached or not
• You can't invalidate a cached resource
• You have no way to prioritize cached content. A huge Javascript should probably stay in the client cache as long as possible, while a 20 bytes-long transparent GIF image is no biggie if it has to eventually get reloaded. The only knob you have on the browser cache is a deadline (which is almost always, and should be, "immediately" or "never"), and it doesn't allow any kind of real prioritization.
• Some web browsers, like Safari (and UIWebView components) on the iPhone have a ridiculously small cache.
• Watching your web server delivering so many 304 replies is driving you nuts.

Fortunately, the HTML5 specs bring an exciting feature: client-side storage. Thanks to localStorage et al., web browsers now provide a convenient way to permanently store big chunks of data, giving applications full control of the data store. While the primary target was offline web applications, client-side storage can also be extremely helpful in a bunch of other situations.

When you think about it, what's the difference between local storage and cached resources? Not much, except that local storage is fully application-controlled, and can solve every issue listed above!

A good example might be a huge Javascript that you really would love to keep cached. It doesn't mean that additional content like pictures shouldn't get cached as well, but you know that this specific script is critical and that users won't be able to see anything but a blank page till this one isn't ready for action.

Here's the trick. Instead of using a script element, this very script can be loaded using XHR, then eval()'d. Since the script is available as a regular string, storing it as an entry in the browser data store is a piece of cake. Checking whether the script is already in the cache is also as easy as checking a key for existence. Invalidation is as easy as deleting the entry. This way, we get a totally user-controlled browser cache.

Here's a real-life example: Geobar

Geobar was specifically designed for iPhone and Android devices. It relies on the OpenLayers scripts + some custom Geoportail scripts. All packed together, we get 1 Mb worth of data that are absolutely mandatory for the page to display. And this is where local storage works wonders.

    function load_scripts() {
        if (window.localStorage["geoapi_js"]) {
            window.eval(window.localStorage["geoapi_js"]);
        } else {
            var xhr = new XMLHttpRequest;
            xhr.onreadystatechange = function() {
                if (this.readyState != 4) {
                    return;
                }
                if (this.status != 200 && this.status != 0) {
                    alert("Error: " + this.status);
                    return;
                }
                try {
                    window.localStorage["geoapi_js"] = this.responseText;
                } catch (e) { }
                window.eval(this.responseText);            
            };
            xhr.open("GET", "geoapi.js", true);
            xhr.send();
        }
    }

This is enough to keep the script in the data store instead of relying on the traditional HTTP cache.

Why not use an HTML5 manifest instead, you may ask? To start with, the manifest still doesn't give you much control about the cached content. And further HTTP requests made from a resource loaded this way have no Referer, which might be a showstopper, as it was the case here.

Of course, the same trick can be used in order to store other kind of resources like stylesheets, and, why not, hex-encoded images.

While HTML5 makes local storage easy and powerful, almost every major web browser out there has some kind of support for local storage for ages: userData (since IE 5.0), globalStorage (since Firefox 2), and for those running behind, Flash comes to the rescue with its Shared Objects.

From igvita.com:

"With all the recent buzz about real-time web, surely this is the year XMPP/AMQP Publish-Subscribe (PubSub) makes it to the big leagues! Or maybe not. Ejabberd (XMPP), RabbitMQ (AMQP) and other pubsub server implementations have come a long way but they remain cumbersome to setup and maintain, and perhaps more importantly, the clients require special libraries and a steep learning curve. That is not to say that either XMPP or AMQP are doomed for failure, in fact, they will continue to thrive, but there is a great case for a simplified PubSub implementation to cover the ad-hoc cases where a dedicated TCP channel might be an overkill: enter Webhooks.

The best part about Webhooks is that most of us are already familiar with them: callbacks over HTTP. Pioneered by PayPal and Subversion as a way to send real-time notifications to the client, they have found their way into many dozens of products we all use every day. Need pre or post commit hooks for your SVN or Git repository? Both GitHub and SVN support HTTP callbacks. Need a payment alert from PayPal, or an alert when a wiki page is modified? There are webhooks for that too. This simple mechanism allows us to build web services that work together via a simple and ubiquitous protocol we can all understand: HTTP!"

Read more

[Elliptics Network 2.5.0] has just been released.

"This is a major milestone in the elliptics network roadmap. System got full support of all essential operations needed for the fully self-contained distributed hash table storage creation.

Elliptics network is an object based distributed storage which supports different kinds of object replication, data deduplication, high-level file-based API and low-level object-based one. All logically complex parts are hidden behind provided API including failover connection processing, routing table maintenance, joining and synchronization protocols, merge strategies and IO itself.

Example applications contain a full-featured IO server and client capable of data replication and parallel reading and failover processing, system statistics gathering tool, notification receiver and history dump utility."

I'm dying to give it a try.

Just released: Bayon, a simple and fast hard-clustering tool, with support for repeated bisection clustering and K-means clustering.

Feed him a list of documents, optionally with weighted terms, ask for any number of groups you want it to output, and Bayon will do its best to assign documents to groups.

That kind of tool can bring a lot of benefits to Ning-like web sites, forums, etc.

And it seems to work just as advertised.

Yet another gem by Mixi.

A new release of UCARP is now available for download.

As a workaround for some OS / setups, that new version adds an option (--nomcast) to use broadcast advertisements instead of multicast.

Thanks a lot to Steve Kehlet and Juan Antonio for bringing in and testing that new feature.

Elliptics Network is a a fault tolerant distributed hash table object storage, made by the genius who already brang POHMELFS.

A new benchmark of Elliptics Network has been published, and it demonstrates its parallel scalability.

Pretty good. Elliptics Network is yet another project to keep an eye on.

Rados, from the Ceph project is also moving on, btw, but it's still not production-ready yet.

The slides and videos of the MountainWest event are now available.

Some very interesting stuff in here.

Even if you don't have any Ruby skill, I'd really suggest you to have a look at these presentations. Some of the technologies described here can be very helpful to build modern applications, regardless of the language they are built in. And these technologies are for sure people with swear by in a few years.

Here are some picks:

• Modern SQL-free databases: Redis and its competitor, MongoDB - two excellent presentations.
• Vertebra - Practical cloud computing. That presentation really wowed me. Vertebra makes traditional architectures really look like dinosaurs.
• Improving the usability, ie. improving the user experience of web sites and applications with intuitive interfaces.
• In a World of Middleware, Who Needs Monolithic Applications? - Rack
• Machine learning - We can learn from that one, too.
• Rhodes - a great framework for building mobile applications on iPhone, BlackBerry, Symbian, Android, and Windows Mobile devices
• Behavior driven development
• Event Machine - some advanced tricks
• FFI - libffi is a really cool way of writing extensions.

Yes, this post comes late, but in case you missed it: Austin Appleby has released a new version of MurmurHash 2, optimized for 64-bits CPUs.

MurmurHash is nothing but the fastest hash function ever designed so far. It's a non-cryptographic function, but it has excellent distribution, excellent avalanche behavior and excellent collision resistance. Plus, it is public domain.

Speedwise, MurmurHash beats Bob Jenkin's lookup3 hash and Hesieh's Superfasthash hands down.

MurmurHash home page - MurmurHash on Wikipedia

and of course, there's already a Ruby extension: Ruby extension for MurmurHash 2

Might make a PHP one if I ever have time to waste.

Release 1.0.22 of pure-ftpd is now available.

There have been a bunch of changes, but this release also shows that the projects starts moving forward again.

So, what's new, what's cool, what sucks?

First, thanks to Taik0, a Catalan translation has been added. Don't hesitate to provide new translations if you can, although the current scheme lacks flexibility in order to provide accurate translations in some languages. A move to gettext() might happen in the future.

The bogus LDAP schema has of course been fixed. Thanks for packagers that fixed it in their packages meanwhile. Using LDAP over TLS should also work now, thanks to Marc Balmer. A last one about LDAP: FTPStatus should also properly work with the new schema. Pure-FTPd should also compile with recent versions of OpenLDAP without any tweak.

Some overdue updates to the MySQL backend are in: multiple statements, stored procedures and the new hashing scheme are finally supported.

A bunch of compatibility and reliability fixes have been merged in. They should prevent unwanted disconnections during transfers, and improve compatibility with most clients.

Time zones, time zones, time zones... Yes, bogus time zones in log messages is an old one, and while simple workarounds exists, having that fixed in the first place would have been way more convenient. It should be the case now. For good.

An important change: on-demand creation of home directories now applies permissions 0777, combined with the umask. It used to be 0755. It shouldn't change anything in the default configuration. By the way, on-demand creation of directories with a chroot mark should now work properly.

TLS encryption on the data channel. Yes, this one finally went in, without the GSSAPI part, though. Transfers can now be completely encrypted, both for commands and for data. Of course it requires more CPU power on both sides, compared to plain unencrypted transfers.

For conveniency, you can keep using --tls=1 (or -Y 1), so that clients can pick whatever they want to use. But --tls=2 is still available (enforce encryption on the control channel) and you can now also use --tls=3 to refuse any connection that is not encrypted both on the command and the data channels.

Credits for that feature mainly go to Rajat Upadhyaya from Novell and Christian Cier-Zniewski.

As suggested by Koczka Ferenc, external authentication handlers should know about the encryption status. This has been added, through a new environment variable called AUTHD_ENCRYPTED.

Changes from Arkadiusz Miskiewicz/PLD Linux have been merged in (fix error reporting when TLS is compiled in, but not used, log full path on deletion, sleep before not after password failure).

--with-privsep is now included in --with-everything. It's also enabled by default in the dialog-based installer.

Per popular request: symbolic links can now be shown as their real targets. Ie. you don't see symbolic links any more, you see real files and directories instead. This is convenient for crappy FTP clients that don't know about symbolic links. But it's not for other things like mirroring. So, it only happens if the compatibility mode (--brokenclientscompatibility or -b) is enabled.

It's fun to see that Ubuntu's design has actually been made on MacOSX with Photoshop. This applies to the default theme, but it looks like the CD cover and label artwork have also been made with Photoshop on OSX.

Here's how the background was "fixed" after the discovery: the Photoshop signature has been wiped off the file. Amazing.

It looks like Ubuntu is all so a replacement for Windows or OSX that using Photoshop and Illustrator remains a common way to draw Ubuntu backgrounds.

Kahuho's work has already been covered on that blog, but he explained the big picture at the Percona's conference.

Running a Realtime Stats Service on MySQL is worth a read in order to know about clever ways to compute stats in real-time using MySQL.

Queue 4 MySQL (Q4M) is not a new project and it was already covered a while back on that blog.

But the project keeps growing and its author made a neat presentation for the MySQL Conference (who said that all interesting presentations took place at Percona's?)

Here's is an overview of Q4M that covers most of its features and some of its typical uses.

Natural Docs is an open-source documentation generator for multiple programming languages. You document your code in a natural syntax that reads like plain English. Natural Docs then scans your code and builds high-quality HTML documentation from it.

It has built-in support for 19 programming languages.

Have a look at the Natural Docs walkthrough to discover how it is way more natural than Javadoc / PHPdoc.