The case for Datastore-Side-Scripting

I have recently posted on predictions that real time web applications are going in the direction of being entirely event driven, from client (WebSockets) to web-server (Node.js) to datastore (Redisql). My current project: Alchemy Database (formerly known as Redisql) hopes to be the final link in this event driven chain. Alchemy Database is taking a new step towards reducing communication between web-server and datastore (thereby increasing thruput), by implementing Datastore-Side-Scripting.

Often, in web applications, the communication between the web-server and the datastore requires 2+ trips involving sequential requests. For example: first the session is validated and then IFF the session is valid, the request’s data is retrieved from the datastore. The web-server must first wait for the “is-session-valid-lookup” to issue the “get-me-data-for-this-request-lookup” (the latter can even be a set of sequential lookups), which implies a good deal of blocking and waiting in the web-server’s backend. Having 2+ sequential steps in web-server datastore communication may seem trivial, but these steps are commonly the cause of SYSTEM bottlenecks. A single frontend request results in webserver threads blocking and waiting multiple times on sequential datastore requests. Each {block, wait, wake-up} in the web-server means 2 context switches, in addition to the latency of 1+ tcp request(s), which are 4-6 orders of magnitude slower than a RAM lookup.

In such cases, if sequential web-server-datastore request-response pairs can be reduced to a single request/response pair, overall system performance will increase substantially and the system will become more predictable/stable (fewer context-switches, less waiting, less requests, less I/O). Datastore-side-scripting can accomplish this, by pushing trivial logic into the datastore itself. In the example above, the only logic being performed is a “if(session_valid)” which has the cost of 2 context switches and a 2+ fold increase in response duration … which is absurd. In this use-case, pushing the “if(session_valid)” into the datastore makes sense on ALL levels.

Some argue, introducing scripting in the datastore is adding logic to the classic bottleneck in 3 tiered architectures, it will exacerbate bottlenecking, it is BAD. This point is valid in theory. In practice, the main bottleneck in ultra-high-performance in-memory-databases is network I/O. Adding NICs, not adding CPUs (or cores) is a better bet to scale vertically (ref: Handlersocket blog). This means, computers running Alchemy Database spend most of their time transporting packets, on request from: NIC->RAM->CPU and then on response from: CPU->RAM->NIC. The operating system’s marshaling of TCP packets takes up far more resources/time than the trivial in-memory lookup to GET/SET the request’s data. Meaning if a few more trivial commands (e.g. an IF block) are packed into the TCP request packet, the request’s duration is not significantly effected, but the overall system is benefited greatly, by taking (very lengthy) blocking/waiting steps in the web-server out of the equation.

Another name for Datastore-side-scripting is “Stored Procedures”, a term w/ lots of baggage. Stored Procedures are flawed on many levels, yet there was and is a need for them. The reality of Stored Procedures is their syntax is ugly in SQL and they open up all sorts of possibilities for developers, which have often been abused. Yet the basic concept of pushing logic into the database was recently mentioned as a future goal for the NOSQL movement. Tokyo Cabinet has embedded Lua deeply into its product (w/ 200 Lua commands), to allow datastore-side-scripting. Voltdb, a next generation SQL server, supports ONLY Stored Procedures and argues that in production they make more sense than ad-hoc SQL.

Stored Procedures are done in a hacked together SQL-like syntax, Datastore-side-scripting is done by embedding Lua. “The Lua programming language is a small scripting language specifically designed to be embedded in other programs. Lua’s C API allows exceptionally clean and simple code both to call Lua from C, and to call C from Lua”.

Lua provides a full (and tested) scripting language and you can define functions in Lua that access your datastore natively in C. I will explain this further, as it confused me at first. Alchemy Database has Lua embedded into it’s server, both Alchemy Database and the Lua engine are written in C. Alchemy Database will pass text given as the 1st argument of the Alchemy Database “LUA” command to the Lua engine. Additionally Alchemy Database has a Lua function called “client()” that can make Alchemy Database SET/GET/INSERT/SELECT/etc.. calls from w/in Lua. The Lua “client” function is written in C via Lua’s C bindings, so calling “client()” in Lua is actually running code natively in C. See its confusing, but the net effect is the following Alchemy Database command:
LUA 'user_id = client("GET", "session:XYZ"); if (user_id) then return client("GET", "data:" .. user_id); else return ""; end'
will perform the use case described above in a single webserver-to-datastore request and the Lua code is pretty easy to understand/write/extend.

Alchemy Database’s datastore-side-scripting was implemented in about 200 lines of C code, and defines a single Lua function “client()” in C, yet it opens up a whole new level of functionality. Performance tests have shown that running Lua has about a 42% performance hit server-side (i.e. 50K req/s) as compared to a single native Alchemy Database call (e.g. SET vs. LUA ‘return client(“SET”);), but packing multiple “client()” calls into a single LUA function does not cause a linear slowdown, meaning use cases that bottleneck on sequential webserver-datastore I/O will see a HUGE performance boost from pushing logic into the datastore.

I do want to stress Alchemy Database’s datastore-side-scripting is meant to be used w/ caution. Proper usage (IMO) of Lua in Alchemy Database is to implement very trivial logic datastore-side (e.g. do not do a for loop w/ 10K lookups), especially because Alchemy Database is single threaded and long running queries block other queries during their execution. Recommended usage is to try and pack trivial logical blocks into a single datastore request, effectively avoiding sequential webserver-to-datastore requests. Lua scripting does open up the possibility for map-reduce, Alchemy Database-as-a-RDBMS-proxy/cache, (and for pathological hackers) even usage as a zero-security front-end server … but that was not the intent of embedding Lua; if you use Lua in Alchemy Database in this manner, you are hacking, please know what you are doing.

Datastore-side-scripting is a balancing act that can be exploited for gain by careful/savvy developers or wrongly implemented for loss by sloppy programming/data-modelling … It gives more power to the Developer and consequently the developer needs to wield said power wisely.

Redisql: the lightning fast data polyglot

For about a year, I have been using the NOSQL datastore redis, in various web-serving environments, as a very fast backend to store and retrieve key-value data and data that best fits in lists, sets, and hash-tables. In addition to redis, my backend also employed mysql, because some data fits much better in a relational table. Getting certain types of data to fit into redis data objects would have added to the complexity of the system and in some cases: it’s simply not doable. BUT, I hated having 2 data-stores, especially when one (mysql) is fundamentally slower, this created a misbalance in how my code was architected. The Mysql calls can take orders of magnitude longer to execute, which is exacerbated when traffic surges. So I wrote Redisql which is an extension of redis that also supports a large subset of SQL. The Idea was to have a single roof to house both relational data and redis data and both types of data would exhibit similar lookup/insert latencies under similar concurrency levels, i.e. a balanced backend.

Redisql supports all redis data types and functionality (as it’s an extension of redis) and it also supports SQL SELECT/INSERT/UPDATE/DELETE (including joins, range-queries, multiple indices, etc…) -> lots of SQL, short of stuff like nested joins and Datawarehousing functionality (e.g. FOREIGN KEY CONSTRAINTS). So using a Redisql library (in your environment’s native language), you can either call redis operations on redis data objects or SQL operations on relational tables, its all in one server accessed from one library. Redisql morph commands convert relational tables (including range query and join results) into sets of redis data objects. They can also convert the results of redis commands on redis data objects into relational tables. Denormalization from relation tables to sets of redis hash-tables is possible, as is normalization from sets of redis hash-tables (or sets of redis keys) into relational tables. Data can be reordered and shuffled into the data structure (relational table, list, set, hash-table, OR ordered-set) that best fits your use cases, and the archiving of redis data objects into relational tables is made possible.

Not only is all the data under a single data roof in Redisql, but the lookup/insert speeds are uniform, you can predict the speed of a SET, an INSERT, an LPOP, a SELECT range query … so application code runs w/o kinks (no unexpected bizarro waits due to mysql table locks -> that lock up an apache thread -> that decrease the performance of a single machine -> which creates an imbalance in the cluster).

Uniform data access patterns between front-end and back-end can fundamentally change how application code behaves. On a 3.0Ghz CPU core, Redis SET/GET run at 110K/s and Redisql INSERT/SELECT run at 95K/s, both w/ sub millisecond mean-latencies, so all of a sudden the application server can fetch data from the datastore w/ truly minimal delay. The oh-so-common bottleneck: “I/O between app-server and datastore” is cut to a bare minimum, which can even push the bottleneck back into the app-servers, and that’s great news as app-servers are dead simple (e.g. add server) to scale horizontally. Redisql is an event-driven non-blocking asynchronous-I/O in-memory database, which i have dubbed an Evented Relational Database, for brevity’s sake.

During the development of Redisql, it became evident that optimizing the number of bytes a row occupied was an incredibly important metric, as Redisql is an In-Memory database (w/ disk persistence snapshotting). Unlike redis, Redisql can function if you go into swap space, but this should be done w/ extreme care. Redisql has lots of memory optimisations, it has been written from the ground up to allow you to put as much data as is possible into your machine’s RAM. Relational table per-row overhead is minimal and TEXT columns are stored in compressed form, when possible (using algorithms w/ negligible performance hits). Analogous to providing predictable request latencies at high concurrency levels, Redisql gives predictable memory usage overhead for data storage and provides detailed per-table, per-index memory usage via the SQL DESC command, as well as per row memory usage via the “INSERT … RETURN SIZE” command. The predictability of Redisql, which translates into tweakability for the seasoned programmer, changes the traditional programming landscape where the datastore is slower than the app-server.

Redisql is architected to handle the c10K problem, so it is world class in terms of networking speed AND all of Redisql’s data is in RAM, so there are no hard disk seeks to engineer around, you get all your data in a predictably FAST manner AND you can pack a lot of data into RAM as Redisql aggressively minimizes memory usage AND Redisql combines SQL and NOSQL under one roof, unifying them w/ commands to morph data betwixt them …. the sum of these parts, when integrated correctly w/ a fast app-server architecture is unbeatable as a dynamic web page serving platform with low latency at high concurrency.

The goal of Redisql is to be the complete datastore solution for applications that require the fastest data lookups/inserts possible. Pairing Redisql w/ an event driven language like Node.js, Ruby Eventmachine, or Twisted Python, should yield a dynamic web page serving platform capable of unheard of low latency at high concurrency, which when paired w/ intelligent client side programming, could process user events in the browser quickly enough to finally realize the browser as an applications platform.

Redisql: the polyglot that speaks SQL and redis, was written to be the Evented Relational Database, the missing piece in the 100% event driven architecture spanning from browser to app-server to database-server and back.

Next Generation Web Server Pole: Low Latency at High Concurrency

Web pages are quickly becoming instantly reactive. Typing into an HTML form does more than simply display the typed characters, under the covers the browser sends an Ajax request to a server that replies w/ instructions to modify the current webpage … the web page reacts to the keystroke “instantly”. When the client-server I/O follow this model, web pages served via a browser can yield a user experience akin to that of a desktop application.

The best prevalent example is Google’s Instant Search. The results of your search are shown AS you type them. If you search for “taco bell”, Google will display a different result set for each new letter typed. In the “taco bell” example, Google receives requests for “t”, “ta”, “tac”, “taco”, “taco “, “taco b”, “taco be”, “taco bel”, and “taco bell” (a total of 9 requests instead of one). Google goes on to state: it takes 300 milliseconds to type a letter and (one tenth of that) 30 milliseconds to glance at another part of the page. So the 9 result sets need to be returned and rendered quickly to be “Instant”. This represents an increase in request concurrency (9 in the time span where one used to be made) and a decrease in latency (“instant” as opposed to the time needed to load a new web page).

History has shown that once Google adds something to its search engine, everyone follows suit and extends the concept beyond the search engine. It is very probably that in the near future any button or any form on any web page will need to be “instant” to yield a competitive user experience.

Recent client side advances to give “instant” results include HTML5 Websockets and Google’s
v8 JavaScript engine (the latter has been optimized to render Ajax requests VERY quickly).

Server-side serving “instant” requests means serving more requests (which are usually pretty small) and serving them QUICKLY. Each user will be making loads of smallish requests and need them returned ASAP. The server-side challenge boils down to achieving Low Latency at High Concurrency, which is something of an engineering paradox. Recent advances to tackle what is often referred to as the c10K problem (web servers able to handle ten thousand clients simultaneously) include nginx and node.js.

Both nginx and node.js differ from traditional web servers by being single threaded, event driven, non-blocking, and asynchronous. They are coded to the reality that the network interface is the bottleneck in serving web pages. Under highly concurrent load they greatly out perform any web server built on a multi-threaded architecture. The multi-threaded architecture stress tested under high concurrency will bottleneck on context switches whereas the single threaded event driven architecture cannot context switch, so it bottlenecks on other things under MUCH (100x) higher concurrency.

A common mistake in web server benchmarking is to test the server under low concurrency. In the real world, this tests the case where a small set of users is pounding your web server w/ requests. The only users that match these benchmarks’ characteristics are web-spiders and denial-of-service attacks. Consequently such benchmarks’ results are not that meaningful. In the real world, web traffic comes from many concurrent users and likes to come in bursts. So concurrency (even in the non-“Instant” case) is vital in any web server benchmark.

Nginx serves only static webpages, but Node.js is capable of building dynamic web pages employing JavaScript SERVER side. Node.js is non blocking by nature and if it matures properly could be the platform of choice for “Instant” dynamic web pages.

There is, unfortunately, one piece missing in the full chain to build a “instant” dynamic web page platform: the database. All relational databases to date are multi-threaded. In the use case where many smallish requests are made from the browser (to provide the “Instant” experience), even if the web server is capable of delivering low latency web pages at high concurrency, the database will bottleneck, and the flow through the chain will develops kink and no progress over the multi threaded web server architecture will be evident.

The NOSQL movement has developed some event driven data stores. Of note is Redis, an event driven data store providing list, set, and hash table primitives. It is VERY fast. Pairing Redis w/ Node.js to serve dynamic web pages and using nginx to serve static web pages is an optimal platform for bleeding edge “Instant” web serving platforms as the entire chain has the same event driven architecture … i.e. no kinks.

But NOSQL is new and foreign to most, so the switch towards “Instant” web serving platforms is currently reserved only for the gutsy early adapter. What is missing is an event driven relational database that speaks SQL. When an Evented Relational Database is created, anyone w/ JavaScript and SQL knowledge will be able to create “Instant” web serving platforms (JavaScript on the server-side also provides a single language for client side and server side development).

Users demanding an “Instant” web experience will be the catalyst to move the event driven programming style into the mainstream. The means to accomplish the “Instant” web experience on the large scale can only be realised by simplifying the process of writing event driven programs. Javascript and SQL employed as an end to end solution accomplishes this: both are widely known and have low barriers to entry.

The “Instant” web requires Low Latency at High Concurrency and the tools to realize this are Ajax/Websockets, an Evented Web Server (Nginx, Node.js), and an Evented Relational Database … I will write a later post on the Evented Relational Database.