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>
41 <li><a href="#design">Design</a>
43 <li><a href="#motivation">Motivation</a></li>
44 <li><a href="#web_app_stack">Web App Stack</a></li>
45 <li><a href="#database">Database</a></li>
46 <li><a href="#problems_and_future_work">Problems and Future Work</a></li>
51 <h2><a name="installing">Installing</a></h2>
53 <h3><a name="getting_the_source">Getting the source</a></h3>
55 <p>There's no stable release, yet, but you can get everything currently
56 running on blerg.dominionofawesome.com by cloning the git repository at
57 http://git.bytex64.net/blerg.git.
59 <h3><a name="requirements">Requirements</a></h3>
61 <p>Blërg has varying requirements depending on how you want to run it
62 — as a standalone HTTP server, or as a CGI. You will need:
65 <li><a href="http://lloyd.github.com/yajl/">yajl</a> >= 1.0.0
66 (yajl is a JSON parser/generator written in C which, by some twisted
67 sense of humor, requires ruby to compile)</li>
70 <p>As a standalone HTTP, server, you will also need:
73 <li><a href="http://www.gnu.org/software/libmicrohttpd/">GNU libmicrohttpd</a> >= 0.9.3</li>
76 <p>Or, as a CGI, you will need:
79 <li><a href="http://www.newbreedsoftware.com/cgi-util/download/">cgi-util</a> >= 2.2.1</li>
82 <h3><a name="configuring">Configuring</a></h3>
84 <p>I know I'm gonna get shit for not using an autoconf-based system, but
85 I really didn't want to waste time figuring it out. You should edit
86 libs.mk and put in the paths where you can find headers and libraries
87 for the above requirements.
89 <p>Also, further apologies to BSD folks — I've probably committed
90 several unconscious Linux-isms. It would not surprise me if the
91 makefile refuses to work with BSD make. If you have patches or
92 suggestions on how to make Blërg more portable, I'd be happy to hear
95 <h3><a name="building">Building</a></h3>
97 <p>At this point, it should be gravy. Type 'make' and in a few seconds,
98 you should have <code>http_blerg</code>, <code>cgi_blerg</code>,
99 <code>rss</code>, and <code>blergtool</code>. Each of those can be made
100 individually as well, if you, for example, don't want to install the
101 prerequisites for <code>http_blerg</code> or <code>cgi_blerg</code>.
103 <h3><a name="installing">Installing</a></h3>
105 <p>While it's not required, Blërg will be easier to set up if you
106 configure it to work from the root of your website. For this reason,
107 it's better to use a subdomain (i.e., blerg.yoursite.com is easier than
108 yoursite.com/blerg/). If you do want to put it in a subdirectory, you
109 will have to modify www/js/blerg.js and change baseURL at the top. The
110 CGI version should work fine this way, but the HTTP version will require
111 the request to be rewritten, as it expects to be serving from the root.
113 <h4>For the standalone web server:</h4>
115 <p>Right now, http_blerg doesn't serve any static assets, so you're
116 going to have to put it behind a real webserver like apache, lighttpd,
117 nginx, or similar. Set the document root to the www directory, then
118 proxy /info, /create, /login, /logout, /get, /tag, and /put to
121 <h4>For the CGI version:</h4>
123 <p>Copy the files in www to the root of your web server. Copy cgi_blerg
124 to blerg.cgi somewhere on your web server. Included in www-configs is a
125 .htaccess file for apache that will rewrite the URLs. If you need to
126 call cgi_blerg something other than blerg.cgi, the .htaccess file will
129 <h4>The extra RSS CGI</h4>
131 <p>There is an optional RSS cgi (called simply rss) that will serve RSS
132 feeds for users. Install this like the CGI version above (on my server,
136 <h2><a name="api">API</a></h2>
138 <p>Blërg's API was designed to be as simple as possible. Data sent from
139 the client is POSTed with the application/x-www-form-urlencoded
140 encoding, and a successful response is always JSON. The API endpoints
141 will be described as though the server were serving requests from the
144 <h3><a name="api_definitions">API Definitions</a></h3>
146 <p>On failure, all API calls return either a standard HTTP error
147 response, like 404 Not Found if a record or user doesn't exist, or a 200
148 response with some JSON indicating failure, which will look like this:
150 <p><code>{"status": "failure"}</code>
152 <p>Blërg doesn't currently explain <i>why</i> there is a failure, and
153 I'm not sure it ever will.
155 <p>On success, you'll either get some JSON relating to your request (for
156 /get, /tag, or /info), or a JSON object indicating success (for /create,
157 /put, /login, or /logout), which looks like this:
159 <p><code>{"status": "success"}</code>
161 <p>For the CGI backend, you may get a 500 error if something goes wrong.
162 For the HTTP backend, you'll get nothing (since it will have crashed),
163 or maybe a 502 Bad Gateway if you have it behind another web server.
165 <p>All usernames must be 32 characters or less. Usernames must contain
166 only the ASCII characters 0-9, A-Z, a-z, underscore (_), period (.),
167 hyphen (-), single quote ('), and space ( ). Passwords can be at most
168 64 bytes, and have no limits on characters (but beware: if you have a
169 null in the middle, it will stop checking there because I use
170 <code>strncmp(3)</code> to compare).
172 <p>Tags must be 64 characters or less, and can contain only the ASCII
173 characters 0-9, A-Z, a-z, hyphen (-), and underscore (_).
175 <h3><a name="api_create">/create</a> - create a new user</a></h3>
177 <p>To create a user, POST to /create with <code>username</code> and
178 <code>password</code> parameters for the new user. The server will
179 respond with failure if the user exists, or if the user can't be created
180 for some other reason. The server will respond with success if the user
183 <h3><a name="api_login">/login</a> - log in</a></h3>
185 <p>POST to /login with the <code>username</code> and
186 <code>password</code> parameters for an existing user. The server will
187 respond with failure if the user does not exist or if the password is
188 incorrect. On success, the server will respond with success, and will
189 set a cookie named 'auth' that must be sent by the client when accessing
190 restricted API functions (/put and /logout).
192 <h3><a name="api_logout">/logout</a> - log out</a></h3>
194 <p>POST to /logout with with <code>username</code>, the user to log out,
195 along with the auth cookie in a Cookie header. The server will respond
196 with failure if the user does not exist or if the auth cookie is bad.
197 The server will respond with success after the user is successfully
200 <h3><a name="api_put">/put</a> - add a new record</a></h3>
202 <p>POST to /put with <code>username</code> and <code>data</code>
203 parameters, and an auth cookie. The server will respond with failure
204 if the auth cookie is bad, if the user doesn't exist, or if
205 <code>data</code> contains more than 65535 bytes <i>after</i> URL
206 decoding. The server will respond with success after the record is
209 <h3><a name="api_get">/get/(user), /get/(user)/(start record)-(end record)</a> - get records for a user</a></h3>
211 <p>A GET request to /get/(user), where (user) is the user desired, will
212 return the last 50 records for that user in a list of objects. The
213 record objects look like this:
218 "timestamp":1294309438,
219 "data":"eatin a taco on fifth street"
223 <p><code>record</code> is the record number, <code>timestamp</code> is
224 the UNIX epoch timestamp (i.e., the number of seconds since Jan 1 1970
225 00:00:00 GMT), and <code>data</code> is the content of the record. The
226 record number is sent as a string because while Blërg supports record
227 numbers up to 2<sup>64</sup> - 1, Javascript uses floating point for all
228 its numbers, and can only support integers without truncation up to
229 2<sup>53</sup>. This difference is largely academic, but I didn't want
230 this problem to sneak up on anyone who is more insane than I am. :]
232 <p>The second form, /get/(user)/(start record)-(end record), retrieves a
233 specific range of records, from (start record) to (end record)
234 inclusive. You can retrieve at most 100 records this way. If (end
235 record) - (start record) specifies more than 100 records, the server
236 will respond with JSON failure.
238 <h3><a name="api_info">/info/(user)</a> - Get information about a user</a></h3>
240 <p>A GET request to /info/(user) will return a JSON object with
241 information about the user (currently only the number of records). The
242 info object looks like this:
246 "record_count": "544"
250 <p>Again, the record count is sent as a string for 64-bit safety.
252 <h3><a name="api_tag">/tag/(#|H|@)(tagname)</a> - Retrieve records containing tags</a></h3>
254 <p>A GET request to this endpoint will return the last 50 records
255 associated with the given tag. The first character is either # or H for
256 hashtags, or @ for mentions (I call them ref tags). You should URL
257 encode the # or @, lest some servers complain at you. The H alias for #
258 was created because Apache helpfully strips the fragment of a URL
259 (everything from the # to the end) before handing it off to the CGI,
260 even if the hash is URL encoded. The record objects also contain an
261 extra <code>author</code> field, like so:
266 "timestamp":1294555793,
267 "data":"I'm taking #garfield to the vet."
270 <p>There is currently no support for getting more than 50 tags, but /tag
271 will probably mutate to work like /get.
273 <h2><a name="design">Design</a></h2>
275 <h3><a name="motivation">Motivation</a></h3>
277 <p>Blërg was created as the result of a thought experiment: "What if
278 Twitter didn't need thousands of servers? What if its millions of users
279 could be handled by a single highly efficient server?" This is probably
280 an unreachable goal due to the sheer amount of I/O, but we could
281 certainly do better. Blërg was thus designed as a system with very
285 <li>Store and fetch small chunks of text efficiently</li>
286 <li>Create fast indexes for hash tags and @ mentions</li>
287 <li>Provide a HTTP interface web apps can use</li>
290 <p>And to further simplify, I didn't bother handling deletes, full text
291 search, or more complicated tag searches. Blërg only does the basics.
293 <h3><a name="web_app_stack">Web App Stack</a></h3>
295 <table class="pizzapie">
296 <tr><th>Classical model</th></tr>
298 <td style="background-color: blue; color: white"><b>Client App</b><br>HTML/Javascript</td>
301 <td style="background-color: #9F0000; color: white"><b>Webserver</b><br>Apache, lighttpd, nginx, etc.</td>
304 <td style="background-color: #009F00; color: white"><b>Server App</b><br>Python, Perl, Ruby, etc.</td>
307 <td style="background-color: #404040; color: white"><b>Database</b><br>MySQL, PostgreSQL, MongoDB, CouchDB, etc.</td>
311 <p>Modern web applications have at least a four-layer approach. You
312 have the client-side browser app written in HTML and Javascript, the web
313 server, the server-side application typically written in some scripting
314 language (or, if it's high-performance, ASP/Java/C/C++), and the
315 database (usually SQL, but newer web apps seem to love object-oriented
318 <table class="pizzapie">
319 <tr><th>Blërg model</th></tr>
321 <td style="background-color: blue; color: white"><b>Blërg Client App</b><br>HTML/Javascript</td>
324 <td style="background-color: #404040; color: white"><b>Blërg Database</b><br></td>
328 <p>Blërg compresses the last two or three layers into one application.
329 Blërg can be run as either a standalone web server, or as a CGI (FastCGI
330 support is planned, but I just don't care right now). Less waste, more
331 throughput. As a consequence of this, the entirety of the application
332 logic that the user sees is implemented in the client app in Javascript.
333 That's why all the URLs have #'s — the page is loaded once and
334 switched on the fly to show different views, further reducing load on
335 the server. Even parsing hash tags and URLs are done in client JS.
337 <p>The API is simple and pragmatic. It's not entirely RESTful, but is
338 rather designed to work well with web-based front-ends. Client data is
339 always POSTed with the usual application/x-www-form-urlencoded encoding,
340 and server data is always returned in JSON format.
342 <p>The HTTP interface to the database idea has already been done by <a
343 href="http://couchdb.apache.org/">CouchDB</a>, though I didn't know that
344 until after I wrote Blërg. :)
346 <h3><a name="database">Database</a></h3>
348 <p>Early in the design process, I decided to blatantly copy <a
349 href="http://www.varnish-cache.org/">varnish</a> and rely heavily on
350 mmap for I/O. Each user in Blërg has their own database, which consists
351 of one or more data and index files, and a metadata file. When a
352 database is opened, only the metadata is actually read (currently a
353 single 64-bit integer keeping track of the last record id). The data
354 and index files are memory mapped, which hopefully makes things more
355 efficient by letting the OS handle when to read from disk. The index
356 files are preallocated because I believe it's more efficient than
357 writing to it 40 bytes at a time as records are added. Here's some info
358 on the database's limitations:
360 <table class="statistics">
361 <tr><td>maximum record size</td><td>65535 bytes</td></tr>
362 <tr><td>maximum number of records per database</td><td>2<sup>64</sup> - 1 bytes</td></tr>
363 <tr><td>maximum number of tags per record</td><td>1024</td></tr>
366 <p>To provide support for
367 32-bit machines, and to not create grossly huge and unwieldy data files,
368 the database layer splits data and index files into many "segments"
369 containing at most 64K entries each. Those of you doing some quick math
370 in your heads may note that this could cause a problem on 32-bit
371 machines — if a full segment contains entries of the maximum
372 length, you'll have to mmap 4GB (32-bit Linux gives each process only
373 3GB of virtual memory addressing). Right now, 32-bit users should
374 change <code>RECORDS_PER_SEGMENT</code> in <code>config.h</code> to
375 something lower like 32768. In the future, I might do something smart
376 like not mmaping the whole fracking file.
378 <p>A record is stored by first appending the data to the data file, then
379 writing an index entry containing the offset and length of the data, as
380 well as the timestamp, to the index file. Since each index entry is
381 fixed length, we can find the index entry simply by multiplying the
382 record number we want by the size of the index entry. Upshot:
383 constant-time random-access reads and constant-time writes. As an added
384 bonus, because we're using append-only files, we get lockless reads.
386 <p>Tags are handled by a separate set of indices, one per tag. Each
387 index record simply stores the user and record number. Tags are
388 searched by opening the tag file, reading the last 50 entries or so, and
389 then reading all the records listed. Voila, fast tag lookups.
391 <p>At this point, you're probably thinking, "Is that it?" Yep, that's
392 it. Blërg isn't revolutionary, it's just a system whose requirements
393 were pared down until the implementation could be made dead simple.
395 <p>Also, keeping with the style of modern object databases, I haven't
396 implemented any data safety (har har). Blërg does not sync anything to
397 disk before returning success. This should make Blërg extremely fast,
398 and totally unreliable in a crash. But that's the way you want it,
401 <h3><a name="problems_and_future_work">Problems and Future Work</a></h3>
403 <p>Blërg probably doesn't actually work like Twitter because I've never
404 actually had a Twitter account.
406 <p>I couldn't find a really good fast HTTP server library.
407 Libmicrohttpd is small, but it's focused on embedded applications, so it
408 often eschews speed for small memory footprint. This is especially
409 apparent when you watch it chew through a POST request 300 bytes at a
410 time even though you've specified a buffer size of 256K. Http_blerg is
411 still pretty fast this way (on my 2GHz Opteron 246, <a
412 href="http://www.joedog.org/index/siege-home">siege</a> says it serves a
413 690-byte /get request at about 945 transactions per second, average
414 response time 0.05 seconds, with 100 concurrent accesses), but a
415 high-efficiency HTTP server implementation could knock this out of the
418 <p>Libmicrohttpd is also really difficult to work with. If you look at
419 the code, http_blerg.c is about 70% longer than cgi_blerg.c simply
420 because of all the iterator hoops I had to jump through to process POST
421 requests. And if you can believe it, I wrote http_blerg.c first. If
422 I'd done it the other way around, I probably would have given up on
425 <p>The data structures written to disk are dependent on the size and
426 endianness of the primitive data types on your architecture and OS.
427 This means that the databases are not portable. A dump/import tool is
428 probably the easiest way to handle this.
430 <p>I do want to make a FastCGI version eventually, and this will
431 probably be a rather simple modification of cgi_blerg.
433 <p>Implementing deletes will be... interesting. There is room in the
434 record index for a 'deleted' flag, but the problem is deleting any tags
435 referenced in the data. This requires rescanning the record content and
436 putting a 'deleted' flag in the tag indices. This will not be pretty,
437 so I'm just going to ignore it and hope nobody makes any mistakes. ;]
439 <p>Tag indices can grow arbitrarily large, which will cause problems for
440 32-bit machines around the 3GB mark. Still, that's something like 80
441 million tags, so maybe it's not something to worry about.
443 <p>The API currently requires the client to transmit the user's password
444 in the clear. A digest-based authentication scheme would be better,
445 though for real security, the app should run over HTTPS.