4 <title>Blërg Documentation</title>
5 <link rel="stylesheet" href="/css/doc.css">
11 Blërg is a minimalistic tagged text document database engine that also
12 pretends to be a <a href="/">microblogging system</a>. It is designed
13 to efficiently store small (< 64K) pieces of text in a way that they
14 can be quickly retrieved by record number or by querying for tags
15 embedded in the text. Its native interface is HTTP — Blërg comes
16 as either a standalone HTTP server, or a CGI. Blërg is written in pure
20 <li><a href="#installing">Installing</a>
22 <li><a href="#getting_the_source">Getting the source</a></li>
23 <li><a href="#requirements">Requirements</a></li>
24 <li><a href="#configuring">Configuring</a></li>
25 <li><a href="#building">Building</a></li>
26 <li><a href="#installing">Installing</a></li>
29 <li><a href="#api">API</a>
31 <li><a href="#api_definitions">API Definitions</a></li>
32 <li><a href="#api_create">/create - create a new user</a></li>
33 <li><a href="#api_login">/login - log in</a></li>
34 <li><a href="#api_logout">/logout - log out</a></li>
35 <li><a href="#api_put">/put - add a new record</a></li>
36 <li><a href="#api_get">/get/(user), /get/(user)/(start record)-(end record) - get records for a user</a></li>
37 <li><a href="#api_info">/info/(user) - Get information about a user</a></li>
38 <li><a href="#api_tag">/tag/(#|H|@)(tagname) - Retrieve records containing tags</a></li>
39 <li><a href="#api_subscribe">/subscribe/(user) - Subscribe to a user's updates</a></li>
40 <li><a href="#api_unsubscribe">/unsubscribe/(user) - Unsubscribe from a user's updates</a></li>
41 <li><a href="#api_feed">/feed - Get updates for subscribed users</a></li>
42 <li><a href="#api_feedinfo">/feedinfo, /feedinfo/(user) - Get subscription status</a></li>
45 <li><a href="#design">Design</a>
47 <li><a href="#motivation">Motivation</a></li>
48 <li><a href="#web_app_stack">Web App Stack</a></li>
49 <li><a href="#database">Database</a></li>
50 <li><a href="#subscriptions">Subscriptions</a></li>
51 <li><a href="#problems">Problems and Future Work</a></li>
56 <h2><a name="installing">Installing</a></h2>
58 <h3><a name="getting_the_source">Getting the source</a></h3>
60 <p>There's no stable release yet, but you can get everything currently
61 running on blerg.dominionofawesome.com by cloning the git repository at
62 http://git.bytex64.net/blerg.git.
64 <h3><a name="requirements">Requirements</a></h3>
66 <p>Blërg has varying requirements depending on how you want to run it
67 — as a standalone HTTP server, or as a CGI. You will need:
70 <li><a href="http://lloyd.github.com/yajl/">yajl</a> >= 1.0.0
71 (yajl is a JSON parser/generator written in C which, by some twisted
72 sense of humor, requires ruby to compile)</li>
75 <p>As a standalone HTTP, server, you will also need:
78 <li><a href="http://www.gnu.org/software/libmicrohttpd/">GNU libmicrohttpd</a> >= 0.9.3</li>
81 <p>Or, as a CGI, you will need:
84 <li><a href="http://www.newbreedsoftware.com/cgi-util/download/">cgi-util</a> >= 2.2.1</li>
87 <h3><a name="configuring">Configuring</a></h3>
89 <p>There is now an experimental autoconf build system. If you run
90 <code>add-autoconf</code>, it'll do the magic and create a
91 <code>configure</code> script that'll do the familiar things. If I ever
92 get around to distributing source packages, you should find that this
93 has already been done.
95 <p>If you'd rather stick with the manual system, you should edit libs.mk
96 and put in the paths where you can find headers and libraries for the
99 <p>Also, further apologies to BSD folks — I've probably committed
100 several unconscious Linux-isms. It would not surprise me if the
101 makefile refuses to work with BSD make, or if it fails to compile even
102 with gmake. If you have patches or suggestions on how to make Blërg
103 more portable, I'd be happy to hear them.
105 <h3><a name="building">Building</a></h3>
107 <p>At this point, it should be gravy. Type 'make' and in a few seconds,
108 you should have <code>blerg.httpd</code>, <code>blerg.cgi</code>,
109 <code>rss.cgi</code>, and <code>blergtool</code>. Each of those can be
110 made individually as well, if you, for example, don't want to install
111 the prerequisites for <code>blerg.httpd</code> or
112 <code>blerg.cgi</code>.
114 <h3><a name="installing">Installing</a></h3>
116 <p>While it's not strictly required, Blërg will be easier to set up if
117 you configure it to work from the root of your website. For this
118 reason, it's better to use a subdomain (i.e., blerg.yoursite.com is
119 easier than yoursite.com/blerg/). If you do want to put it in a
120 subdirectory, you will have to modify <code>www/js/blerg.js</code> and
121 change baseURL at the top as well as a number of other self-references
122 in that file and <code>www/index.html</code>. The CGI version should
123 work fine this way, but the HTTP version will require the request to be
124 rewritten, as it expects to be serving from the root.
126 <p>You cannot serve the database and client from different domains
127 (i.e., yoursite.com vs othersite.net, or even foo.yoursite.com and
128 bar.yoursite.com). This is a requirement of the web browser — the
129 same origin policy will not allow an AJAX request to travel across
132 <h4>For the standalone web server:</h4>
134 <p>Right now, <code>blerg.httpd</code> doesn't serve any static assets,
135 so you're going to have to put it behind a real webserver like apache,
136 lighttpd, nginx, or similar. Set the document root to the www
137 directory, then proxy /info, /create, /login, /logout, /get, /tag, and
138 /put to blerg.httpd. You can change the port <code>blerg.httpd</code>
139 listens on in <code>config.h</code>.
141 <h4>For the CGI version:</h4>
143 <p>Copy the files in www/ to the root of your web server. Copy
144 <code>blerg.cgi</code> to your web server. Included in www-configs/ is
145 a .htaccess file for Apache that will rewrite the URLs. If you need to
146 call the CGI something other than <code>blerg.cgi</code>, the .htaccess
147 file will need to be modified.
149 <h4>The extra RSS CGI</h4>
151 <p>There is an optional RSS cgi (<code>rss.cgi</code>) that will serve
152 RSS feeds for users. Install this like <code>blerg.cgi</code> above.
155 <h2><a name="api">API</a></h2>
157 <p>Blërg's API was designed to be as simple as possible. Data sent from
158 the client is POSTed with the application/x-www-form-urlencoded
159 encoding, and a successful response is always JSON. The API endpoints
160 will be described as though the server were serving requests from the
163 <h3><a name="api_definitions">API Definitions</a></h3>
165 <p>On failure, all API calls return either a standard HTTP error
166 response, like 404 Not Found if a record or user doesn't exist, or a 200
167 response with a 'JSON failure', which will look like this:
169 <p><code>{"status": "failure"}</code>
171 <p>Blërg doesn't currently explain <i>why</i> there is a failure, and
172 I'm not sure it ever will.
174 <p>On success, you'll either get some JSON relating to your request (for
175 /get, /tag, or /info), or a 'JSON success' response (for /create, /put,
176 /login, or /logout), which looks like this:
178 <p><code>{"status": "success"}</code>
180 <p>For the CGI backend, you may get a 500 error if something goes wrong.
181 For the HTTP backend, you'll get nothing (since it will have crashed),
182 or maybe a 502 Bad Gateway if you have it behind another web server.
184 <p>All usernames must be 32 characters or less. Usernames must contain
185 only the ASCII characters 0-9, A-Z, a-z, underscore (_), and hyphen (-).
186 Passwords can be at most 64 bytes, and have no limits on characters (but
187 beware: if you have a null in the middle, it will stop checking there
188 because I use <code>strncmp(3)</code> to compare).
190 <p>Tags must be 64 characters or less, and can contain only the ASCII
191 characters 0-9, A-Z, a-z, underscore (_), and hyphen (-).
193 <h3><a name="api_create">/create</a> - create a new user</a></h3>
195 <p>To create a user, POST to /create with <code>username</code> and
196 <code>password</code> parameters for the new user. The server will
197 respond with JSON failure if the user exists, or if the user can't be
198 created for some other reason. The server will respond with JSON
199 success if the user is created.
201 <h3><a name="api_login">/login</a> - log in</a></h3>
203 <p>POST to /login with the <code>username</code> and
204 <code>password</code> parameters for an existing user. The server will
205 respond with JSON failure if the user does not exist or if the password
206 is incorrect. On success, the server will respond with JSON success,
207 and will set a cookie named 'auth' that must be sent by the client when
208 accessing restricted API functions (/put and /logout).
210 <h3><a name="api_logout">/logout</a> - log out</a></h3>
212 <p>POST to /logout with with <code>username</code>, the user to log out,
213 along with the auth cookie in a Cookie header. The server will respond
214 with JSON failure if the user does not exist or if the auth cookie is
215 bad. The server will respond with JSON success after the user is
216 successfully logged out.
218 <h3><a name="api_put">/put</a> - add a new record</a></h3>
220 <p>POST to /put with <code>username</code> and <code>data</code>
221 parameters, and an auth cookie. The server will respond with JSON
222 failure if the auth cookie is bad, if the user doesn't exist, or if
223 <code>data</code> contains more than 65535 bytes <i>after</i> URL
224 decoding. The server will respond with JSON success after the record is
227 <h3><a name="api_get">/get/(user), /get/(user)/(start record)-(end record)</a> - get records for a user</a></h3>
229 <p>A GET request to /get/(user), where (user) is the user desired, will
230 return the last 50 records for that user in a list of objects. The
231 record objects look like this:
236 "timestamp":1294309438,
237 "data":"eatin a taco on fifth street"
241 <p><code>record</code> is the record number, <code>timestamp</code> is
242 the UNIX epoch timestamp (i.e., the number of seconds since Jan 1 1970
243 00:00:00 GMT), and <code>data</code> is the content of the record. The
244 record number is sent as a string because while Blërg supports record
245 numbers up to 2<sup>64</sup> - 1, Javascript uses floating point for all
246 its numbers, and can only support integers without truncation up to
247 2<sup>53</sup>. This difference is largely academic, but I didn't want
248 this problem to sneak up on anyone who is more insane than I am. :]
250 <p>The second form, /get/(user)/(start record)-(end record), retrieves a
251 specific range of records, from (start record) to (end record)
252 inclusive. You can retrieve at most 100 records this way. If (end
253 record) - (start record) specifies more than 100 records, or if the
254 range specifies invalid records, or if the end record is before the
255 start record, the server will respond with JSON failure.
257 <h3><a name="api_info">/info/(user)</a> - Get information about a user</a></h3>
259 <p>A GET request to /info/(user) will return a JSON object with
260 information about the user (currently only the number of records). The
261 info object looks like this:
265 "record_count": "544"
269 <p>Again, the record count is sent as a string for 64-bit safety.
271 <h3><a name="api_tag">/tag/(#|H|@)(tagname)</a> - Retrieve records containing tags</a></h3>
273 <p>A GET request to this endpoint will return the last 50 records
274 associated with the given tag. The first character is either # or H for
275 hashtags, or @ for mentions (I call them ref tags). You should URL
276 encode the # or @, lest some servers complain at you. The H alias for #
277 was created because Apache helpfully strips the fragment of a URL
278 (everything from the # to the end) before handing it off to the CGI,
279 even if the hash is URL encoded. The record objects also contain an
280 extra <code>author</code> field, like so:
286 "timestamp":1294555793,
287 "data":"I'm taking #garfield to the vet."
291 <p>There is currently no support for getting more than 50 tags, but /tag
292 will probably mutate to work like /get.
294 <h3><a name="api_subscribe">/subscribe/(user)</a> - Subscribe to a
295 user's updates</a></h3>
297 <p>POST to /subscribe/(user) with a <code>username</code> parameter and
298 an auth cookie, where (user) is the user whose updates you wish to
299 subscribe to. The server will respond with JSON failure if the auth
300 cookie is bad or if the user doesn't exist. The server will respond
301 with JSON success after the subscription is successfully registered.
303 <h3><a name="api_unsubscribe">/unsubscribe/(user)</a> - Unsubscribe from
304 a user's updates</h3>
306 <p>Identical to /subscribe, but removes the subscription.
308 <h3><a name="api_feed">/feed</a> - Get updates for subscribed users</h3>
310 <p>POST to /feed, with a <code>username</code> parameter and an auth
311 cookie. The server will respond with a JSON list of the last 50 updates
312 from all subscribed users, in reverse chronological order. Fetching
313 /feed resets the new message count returned from /feedinfo.
315 <p>NOTE: subscription notifications are only stored while subscriptions
316 are active. Any records inserted before or after a subscription is
317 active will not show up in /feed.
319 <h3><a name="api_feedinfo">/feedinfo, /feedinfo/(user)</a> - Get subscription
320 status for a user</a></h3>
322 <p>POST to /feedinfo with a <code>username</code> parameter and an auth
323 cookie to get general information about your subscribed feeds.
324 Currently, this only tells you how many new records there are since the
325 last time /feed was fetched. The server will respond with a JSON
332 <p>POST to /feedinfo/(user) with a <code>username</code> parameter and
333 an auth cookie, where (user) is a user whose subscription status you are
334 interested in. The server will respond with a simple JSON object:
340 <p>The value of "subscribed" will be either true or false depending on
341 the subscription status.
343 <h2><a name="design">Design</a></h2>
345 <h3><a name="motivation">Motivation</a></h3>
347 <p>Blërg was created as the result of a thought experiment: "What if
348 Twitter didn't need thousands of servers? What if its millions of users
349 could be handled by a single highly efficient server?" This is probably
350 an unreachable goal due to the sheer amount of I/O, but we can certainly
351 try to do better. Blërg was thus designed as a system with very simple
355 <li>Store and fetch small chunks of text efficiently</li>
356 <li>Create fast indexes for hash tags and @ mentions</li>
357 <li>Provide a HTTP interface web apps can use</li>
360 <p>And to further simplify, I didn't bother handling deletes, full text
361 search, or more complicated tag searches. Blërg only does the basics.
363 <h3><a name="web_app_stack">Web App Stack</a></h3>
365 <table class="pizzapie">
366 <tr><th>Classical model</th></tr>
368 <td style="background-color: blue; color: white"><b>Client App</b><br>HTML/Javascript</td>
371 <td style="background-color: #9F0000; color: white"><b>Webserver</b><br>Apache, lighttpd, nginx, etc.</td>
374 <td style="background-color: #009F00; color: white"><b>Server App</b><br>Python, Perl, Ruby, etc.</td>
377 <td style="background-color: #404040; color: white"><b>Database</b><br>MySQL, PostgreSQL, MongoDB, CouchDB, etc.</td>
381 <p>Modern web applications have at least a four-layer approach. You
382 have the client-side browser app, the web server, the server-side
383 application, and the database. Your data goes through a lot of layers
384 before it actually resides on disk somewhere (or, as they're calling it
385 these days, "The Cloud" *waves hands*). Each of those layers requires
386 some amount of computing resources, so to increase throughput, we must
387 make the layers more efficient, or reduce the number of layers.
389 <table class="pizzapie">
390 <tr><th>Blërg model</th></tr>
392 <td style="background-color: blue; color: white"><b>Blërg Client App</b><br>HTML/Javascript</td>
395 <td style="background-color: #404040; color: white"><b>Blërg Database</b><br>Fuckin' hardcore C and shit</td>
399 <p>Blërg does both by smashing the last two or three layers into one
400 application. Blërg can be run as either a standalone web server, or as
401 a CGI (FastCGI support is planned, but I just don't care right now).
402 Less waste, more throughput. As a consequence of this, the entirety of
403 the application logic that the user sees is implemented in the client
404 app in Javascript. That's why all the URLs have #'s — the page is
405 loaded once and switched on the fly to show different views, further
406 reducing load on the server. Even parsing hash tags and URLs are done
409 <p>The API is simple and pragmatic. It's not entirely RESTful, but is
410 rather designed to work well with web-based front-ends. Client data is
411 always POSTed with the usual application/x-www-form-urlencoded encoding,
412 and server data is always returned in JSON format.
414 <p>The HTTP interface to the database idea has already been done by <a
415 href="http://couchdb.apache.org/">CouchDB</a>, though I didn't know that
416 until after I wrote Blërg. :)
418 <h3><a name="database">Database</a></h3>
420 <p>I was impressed by <a
421 href="http://www.varnish-cache.org/">varnish</a>'s design, so I decided
422 early in the design process that I'd try out mmaped I/O. Each user in
423 Blërg has their own database, which consists of a metdata file, and one
424 or more data and index files. The data and index files are memory
425 mapped, which hopefully makes things more efficient by letting the OS
426 handle when to read from disk (or maybe not &mdash I haven't benchmarked
427 it). The index files are preallocated because I believe it's more
428 efficient than writing to it 40 bytes at a time as records are added.
429 The database's limits are reasonable:
431 <table class="statistics">
432 <tr><td>maximum record size</td><td>65535 bytes</td></tr>
433 <tr><td>maximum number of records per database</td><td>2<sup>64</sup> - 1 bytes</td></tr>
434 <tr><td>maximum number of tags per record</td><td>1024</td></tr>
437 <p>So as not to create grossly huge and unwieldy data files, the
438 database layer splits data and index files into many "segments"
439 containing at most 64K entries each. Those of you doing some quick math
440 in your heads may note that this could cause a problem on 32-bit
441 machines — if a full segment contains entries of the maximum
442 length, you'll have to mmap 4GB (32-bit Linux gives each process only
443 3GB of virtual address space). Right now, 32-bit users should change
444 <code>RECORDS_PER_SEGMENT</code> in <code>config.h</code> to something
445 lower like 32768. In the future, I might do something smart like not
446 mmaping the whole fracking file.
448 <table class="bitstructure">
449 <tr><th>Record Index Structure</th></tr>
450 <tr><td class="B4">offset (32-bit integer)</td></tr>
451 <tr><td class="B2">length (16-bit integer)</td></tr>
452 <tr><td class="B2">flags (16-bit integer)</td></tr>
453 <tr><td class="B4">timestamp (32-bit integer)</td></tr>
456 <p>A record is stored by first appending the data to the data file, then
457 writing an entry in the index file containing the offset and length of
458 the data, as well as the timestamp. Since each index entry is fixed
459 length, we can find the index entry simply by multiplying the record
460 number we want by the size of the index entry. Upshot: constant-time
461 random-access reads and constant-time writes. As an added bonus,
462 because we're using append-only files, we get lockless reads.
464 <table class="bitstructure">
465 <tr><th>Tag Structure</th></tr>
466 <tr><td class="B32">username (32 bytes)</td></tr>
467 <tr><td class="B8">record number (64-bit integer)</td></tr>
470 <p>Tags are handled by a separate set of indices, one per tag. When a
471 record is added, it is scanned for tags, then entries are appended to
472 each tag index for the tags found. Each index record simply stores the
473 user and record number. Tags are searched by opening the tag file,
474 reading the last 50 entries or so, and then reading all the records
475 listed. Voila, fast tag lookups.
477 <p>At this point, you're probably thinking, "Is that it?" Yep, that's
478 it. Blërg isn't revolutionary, it's just a system whose requirements
479 were pared down until the implementation could be made dead simple.
481 <p>Also, keeping with the style of modern object databases, I haven't
482 implemented any data safety (har har). Blërg does not sync anything to
483 disk before returning success. This should make Blërg extremely fast,
484 and totally unreliable in a crash. But that's the way you want it,
487 <h3><a name="subscriptions">Subscriptions</a></h3>
489 <p>When I first started thinking about the idea of subscriptions, I
490 immediately came up with the naïve solution: keep a list of users to
491 which users are subscribed, then when you want to get updates, iterate
492 over the list and find the last entries for each user. And that would
493 work, but it's kind of costly in terms of disk I/O. I have to visit
494 each user in the list, retrieve their last few entries, and store them
495 somewhere else to be sorted later. And worse, that computation has to
496 be done every time a user checks their feed. As the number of users and
497 subscriptions grows, that will become a problem.
499 <p>So instead, I thought about it the other way around. Instead of doing
500 all the work when the request is received, Blërg tries to do as much as
501 possible by "pushing" updates to subscribed users. You can think of it
502 kind of like a mail system. When a user posts new content, a
503 notification is "sent" out to each of that user's subscribers. Later,
504 when the subscribers want to see what's new, they simply check their
505 mailbox. Checking your mailbox is usually a lot more efficient than
506 going around and checking everyone's records yourself, even with the
507 overhead of the "mailman."
509 <p>The "mailbox" is a subscription index, which is identical to a tag
510 index, but is a per-user construct. When a user posts a new record, a
511 subscription index record is written for every subscriber. It's a
512 similar amount of I/O as the naïve version above, but the important
513 difference is that it's only done once. Retrieving records for accounts
514 you're subscribed to is then as simple as reading your subscription
515 index and reading the associated records. This is hopefully less I/O
516 than the naïve version, since you're reading, at most, as many accounts
517 as you have records in the last N entries of your subscription index,
518 instead of all of them. And as an added bonus, since subscription index
519 records are added as posts are created, the subscription index is
520 automatically sorted by time! To support this "mail" architecture, we
521 also keep a list of subscribers and subscrib...ees in each account.
523 <h3><a name="problems">Problems, Caveats, and Future Work</a></h3>
525 <p>Blërg probably doesn't actually work like Twitter because I've never
526 actually had a Twitter account.
528 <p>I couldn't find a really good fast HTTP server library.
529 Libmicrohttpd is small, but it's focused on embedded applications, so it
530 often eschews speed for small memory footprint. This is especially
531 apparent when you watch it chew through a POST request 300 bytes at a
532 time even though you've specified a buffer size of 256K.
533 <code>blerg.httpd</code> is still pretty fast this way — on my
535 href="http://www.joedog.org/index/siege-home">siege</a> says it serves a
536 690-byte /get request at about 945 transactions per second, average
537 response time 0.05 seconds, with 100 concurrent accesses — but a
538 fast HTTP server implementation could knock this out of the park.
540 <p>Libmicrohttpd is also really difficult to work with. If you look at
541 the code, <code>http_blerg.c</code> is about 70% longer than
542 <code>cgi_blerg.c</code> simply because of all the iterator hoops I had
543 to jump through to process POST requests. And if you can believe it, I
544 wrote <code>http_blerg.c</code> first. If I'd done it the other way
545 around, I probably would have given up on libmicrohttpd. :-/
547 <p>The data structures written to disk are dependent on the size and
548 endianness of the primitive data types on your architecture and OS.
549 This means that the databases are not portable. A dump/import tool is
550 probably the easiest way to handle this.
552 <p>I do want to make a FastCGI version eventually, and this will
553 probably be a rather simple modification of cgi_blerg.
555 <p>Implementing deletes will be... interesting. There is room in the
556 record index for a 'deleted' flag, but the problem is deleting any tags
557 referenced in the data. This requires rescanning the record content and
558 putting a 'deleted' flag in the tag indices. This will not be pretty,
559 so I'm just going to ignore it and hope nobody makes any mistakes. ;]
561 <p>Tag indices can grow arbitrarily large, which will cause problems for
562 32-bit machines around the 3GB mark. Still, that's something like 80
563 million tags, so maybe it's not something to worry about.
565 <p>The API currently requires the client to transmit the user's password
566 in the clear. A digest-based authentication scheme would be better,
567 though for real security, the app should run over HTTPS.
projects / blerg.git / blob