www/doc/index.html

   1 <!DOCTYPE html>
   2 <html>
   3 <head>
   4 <title>Blërg Documentation</title>
   5 <link rel="stylesheet" href="/css/doc.css">
   6 <meta http-equiv="content-type" content="text/html; charset=utf8">
   7 </head>
   8 <body>
   9
  10 <h1>Blërg</h1>
  11
  12 Blërg is a minimalistic tagged text document database engine that also
  13 pretends to be a <a href="/">microblogging system</a>.  It is designed
  14 to efficiently store small (&lt; 64K) pieces of text in a way that they
  15 can be quickly retrieved by record number or by querying for tags
  16 embedded in the text.  Its native interface is HTTP &mdash; Blërg comes
  17 as either a standalone HTTP server, or a CGI.  Blërg is written in pure
  18 C.
  19
  20 <ul class="toc">
  21   <li><a href="#running">Running Blërg</a>
  22     <ul>
  23       <li><a href="#getting_the_source">Getting the source</a></li>
  24       <li><a href="#requirements">Requirements</a></li>
  25       <li><a href="#configuring">Configuring</a></li>
  26       <li><a href="#building">Building</a></li>
  27       <li><a href="#installing">Installing</a></li>
  28     </ul>
  29   </li>
  30   <li><a href="#api">API</a>
  31     <ul>
  32       <li><a href="#api_definitions">API Definitions</a></li>
  33       <li><a href="#api_create">/create - create a new user</a></li>
  34       <li><a href="#api_login">/login - log in</a></li>
  35       <li><a href="#api_logout">/logout - log out</a></li>
  36       <li><a href="#api_put">/put - add a new record</a></li>
  37       <li><a href="#api_get">/get/(user), /get/(user)/(start record)-(end record) - get records for a user</a></li>
  38       <li><a href="#api_info">/info/(user) - Get information about a user</a></li>
  39       <li><a href="#api_tag">/tag/(#|H|@)(tagname) - Retrieve records containing tags</a></li>
  40       <li><a href="#api_subscribe">/subscribe/(user) - Subscribe to a user's updates</a></li>
  41       <li><a href="#api_unsubscribe">/unsubscribe/(user) - Unsubscribe from a user's updates</a></li>
  42       <li><a href="#api_feed">/feed - Get updates for subscribed users</a></li>
  43       <li><a href="#api_feedinfo">/feedinfo, /feedinfo/(user) - Get subscription status</a></li>
  44       <li><a href="#api_passwd">/passwd - Change a user's password</a></li>
  45     </ul>
  46   </li>
  47   <li><a href="#libraries">Libraries</a>
  48     <ul>
  49       <li><a href="#lib_c">C</a></li>
  50       <li><a href="#lib_perl">Perl</a></li>
  51     </ul>
  52   </li>
  53   <li><a href="#design">Design</a>
  54     <ul>
  55       <li><a href="#motivation">Motivation</a></li>
  56       <li><a href="#web_app_stack">Web App Stack</a></li>
  57       <li><a href="#database">Database</a></li>
  58       <li><a href="#subscriptions">Subscriptions</a></li>
  59       <li><a href="#problems">Problems and Future Work</a></li>
  60     </ul>
  61   </li>
  62 </ul>
  63
  64 <h2><a name="running">Running Blërg</a></h2>
  65
  66 <h3><a name="getting_the_source">Getting the source</a></h3>
  67
  68 <p>There's no stable release yet, but you can get everything currently
  69 running on blerg.dominionofawesome.com by cloning the git repository at
  70 http://git.bytex64.net/blerg.git.
  71
  72 <h3><a name="requirements">Requirements</a></h3>
  73
  74 <p>Blërg has varying requirements depending on how you want to run it
  75 &mdash; as a standalone HTTP server, or as a CGI.  You will need:
  76
  77 <ul>
  78 <li><a href="http://lloyd.github.com/yajl/">yajl</a> &gt;= 1.0.0
  79 (yajl is a JSON parser/generator written in C which, by some twisted
  80 sense of humor, requires ruby to compile)</li>
  81 </ul>
  82
  83 <p>As a standalone HTTP, server, you will also need:
  84
  85 <ul>
  86 <li><a href="http://www.gnu.org/software/libmicrohttpd/">GNU libmicrohttpd</a> &gt;= 0.9.3</li>
  87 </ul>
  88
  89 <p>Or, as a CGI, you will need:
  90
  91 <ul>
  92 <li><a href="http://www.newbreedsoftware.com/cgi-util/download/">cgi-util</a> &gt;= 2.2.1</li>
  93 </ul>
  94
  95 <h3><a name="configuring">Configuring</a></h3>
  96
  97 <p>There is now an experimental autoconf build system.  If you run
  98 <code>add-autoconf</code>, it'll do the magic and create a
  99 <code>configure</code> script that'll do the familiar things.  If I ever
 100 get around to distributing source packages, you should find that this
 101 has already been done.
 102
 103 <p>If you'd rather stick with the manual system, you should edit libs.mk
 104 and put in the paths where you can find headers and libraries for the
 105 above requirements.
 106
 107 <p>Also, further apologies to BSD folks &mdash; I've probably committed
 108 several unconscious Linux-isms.  It would not surprise me if the
 109 makefile refuses to work with BSD make, or if it fails to compile even
 110 with gmake.  If you have patches or suggestions on how to make Blërg
 111 more portable, I'd be happy to hear them.
 112
 113 <h3><a name="building">Building</a></h3>
 114
 115 <p>At this point, it should be gravy.  Type 'make' and in a few seconds,
 116 you should have <code>blerg.httpd</code>, <code>blerg.cgi</code>,
 117 <code>rss.cgi</code>, and <code>blergtool</code>.  Each of those can be
 118 made individually as well, if you, for example, don't want to install
 119 the prerequisites for <code>blerg.httpd</code> or
 120 <code>blerg.cgi</code>.
 121
 122 <p><strong>NOTE</strong>: blerg.httpd is deprecated and will not be
 123 updated with new features.
 124
 125 <h3><a name="installing">Installing</a></h3>
 126
 127 <p>While it's not strictly required, Blërg will be easier to set up if
 128 you configure it to work from the root of your website.  For this
 129 reason, it's better to use a subdomain (i.e., blerg.yoursite.com is
 130 easier than yoursite.com/blerg/).  If you do want to put it in a
 131 subdirectory, you will have to modify <code>www/js/blerg.js</code> and
 132 change baseURL at the top as well as a number of other self-references
 133 in that file and <code>www/index.html</code>.
 134
 135 <p>You cannot serve the database and client from different domains
 136 (i.e., yoursite.com vs othersite.net, or even foo.yoursite.com and
 137 bar.yoursite.com).  This is a requirement of the web browser &mdash; the
 138 same origin policy will not allow an AJAX request to travel across
 139 domains (though you can probably get around it these days with <a
 140   href="http://en.wikipedia.org/wiki/Cross-origin_resource_sharing">Cross-origin
 141   resource sharing</a>).
 142
 143 <h4>For straight CGI with Apache</h4>
 144
 145 <p>Copy the files in www/ to the root of your web server.  Copy
 146 <code>blerg.cgi</code> to your web server.  Included in www-configs/ is
 147 a .htaccess file for Apache that will rewrite the URLs.  If you need to
 148 call the CGI something other than <code>blerg.cgi</code>, the .htaccess
 149 file will need to be modified.
 150
 151 <h4>For nginx</h4>
 152
 153 <p>Nginx can't run CGI directly, and there's currently no FastCGI
 154 version of Blërg, so you will have to run it under some kind of CGI to
 155 FastCGI gateway, like the one described <a
 156 href="http://wiki.nginx.org/SimpleCGI">here on the nginx wiki</a>.  This
 157 pretty much destroys the performance of Blërg, but it's all we've got
 158 right now.
 159
 160 <h4>The extra RSS CGI</h4>
 161
 162 <p>There is an optional RSS cgi (<code>rss.cgi</code>) that will serve
 163 RSS feeds for users.  Install this like <code>blerg.cgi</code> above.
 164 As of 1.9.0, this is a perl FastCGI script, so you will have to make
 165 sure the perl libraries are available to it.  A good way of doing that
 166 is to install to an environment directory, as described below.
 167
 168 <h4>Installing to an environment directory</h4>
 169
 170 <p>The Makefile has support for installing Blërg into a directory that
 171 includes tools, libraries, and configuration snippets for shell and web
 172 servers.  Use it as <code>make install-environment
 173   ENV_DIR=&lt;directory&gt;</code>.  Under &lt;directory&gt;/etc will be
 174 a shell script that sets environment variables, and configuration
 175 snippets for nginx and apache to do the same.  This should make it
 176 somewhat easier to use Blërg in a self-contained way.
 177
 178 <p>For example, this will install Blërg to an environment directory
 179 inside your home directory:
 180
 181 <pre>user@devhost:~/blerg$ make install-environment ENV_DIR=$HOME/blerg-env
 182 ...
 183 user@devhost:~/blerg$ . ~/blerg-env/etc/env.sh
 184 </pre>
 185
 186 <p>Then, you will be able to run tools like <code>blergtool</code>, and
 187 it will operate on data inside <code>~/blerg-env/data</code>.  Likewise,
 188 you can include
 189 <code>/home/user/blerg-env/etc/nginx-fastcgi-vars.conf</code> or
 190 <code>/home/user/blerg-env/etc/apache-setenv.conf</code> in your
 191 webserver to make the CGI/FastCGI scripts to the same thing.
 192
 193
 194 <h2><a name="api">API</a></h2>
 195
 196 <p>Blërg's API was designed to be as simple as possible.  Data sent from
 197 the client is POSTed with the application/x-www-form-urlencoded
 198 encoding, and a successful response is always JSON.  The API endpoints
 199 will be described as though the server were serving requests from the
 200 root of the wesite.
 201
 202 <h3><a name="api_definitions">API Definitions</a></h3>
 203
 204 <p>On failure, all API calls return either a standard HTTP error
 205 response, like 404 Not Found if a record or user doesn't exist, or a 200
 206 response with a 'JSON failure', which will look like this:
 207
 208 <p><code>{"status": "failure"}</code>
 209
 210 <p>Blërg doesn't currently explain <i>why</i> there is a failure, and
 211 I'm not sure it ever will.
 212
 213 <p>On success, you'll either get some JSON relating to your request (for
 214 /get, /tag, or /info), or a 'JSON success' response (for /create, /put,
 215 /login, or /logout), which looks like this:
 216
 217 <p><code>{"status": "success"}</code>
 218
 219 <p>For the CGI backend, you may get a 500 error if something goes wrong.
 220 For the HTTP backend, you'll get nothing (since it will have crashed),
 221 or maybe a 502 Bad Gateway if you have it behind another web server.
 222
 223 <p>All usernames must be 32 characters or less.  Usernames must contain
 224 only the ASCII characters 0-9, A-Z, a-z, underscore (_), and hyphen (-).
 225 Passwords can be at most 64 bytes, and have no limits on characters (but
 226 beware: if you have a null in the middle, it will stop checking there
 227 because I use <code>strncmp(3)</code> to compare).
 228
 229 <p>Tags must be 64 characters or less, and can contain only the ASCII
 230 characters 0-9, A-Z, a-z, underscore (_), and hyphen (-).
 231
 232 <h3><a name="api_create">/create</a> - create a new user</a></h3>
 233
 234 <p>To create a user, POST to /create with <code>username</code> and
 235 <code>password</code> parameters for the new user.  The server will
 236 respond with JSON failure if the user exists, or if the user can't be
 237 created for some other reason.  The server will respond with JSON
 238 success if the user is created.
 239
 240 <h3><a name="api_login">/login</a> - log in</a></h3>
 241
 242 <p>POST to /login with the <code>username</code> and
 243 <code>password</code> parameters for an existing user.  The server will
 244 respond with JSON failure if the user does not exist or if the password
 245 is incorrect.  On success, the server will respond with JSON success,
 246 and will set a cookie named 'auth' that must be sent by the client when
 247 accessing restricted API functions (/put and /logout).
 248
 249 <h3><a name="api_logout">/logout</a> - log out</a></h3>
 250
 251 <p>POST to /logout with with <code>username</code>, the user to log out,
 252 along with the auth cookie in a Cookie header.  The server will respond
 253 with JSON failure if the user does not exist or if the auth cookie is
 254 bad.  The server will respond with JSON success after the user is
 255 successfully logged out.
 256
 257 <h3><a name="api_put">/put</a> - add a new record</a></h3>
 258
 259 <p>POST to /put with <code>username</code> and <code>data</code>
 260 parameters, and an auth cookie.  The server will respond with JSON
 261 failure if the auth cookie is bad, if the user doesn't exist, or if
 262 <code>data</code> contains more than 65535 bytes <i>after</i> URL
 263 decoding.  The server will respond with JSON success after the record is
 264 successfully added.
 265
 266 <h3><a name="api_get">/get/(user), /get/(user)/(start record)-(end record)</a> - get records for a user</a></h3>
 267
 268 <p>A GET request to /get/(user), where (user) is the user desired, will
 269 return the last 50 records for that user in a list of objects.  The
 270 record objects look like this:
 271
 272 <pre>
 273 {
 274   "record":"0",
 275   "timestamp":1294309438,
 276   "data":"eatin a taco on fifth street"
 277 }
 278 </pre>
 279
 280 <p><code>record</code> is the record number, <code>timestamp</code> is
 281 the UNIX epoch timestamp (i.e., the number of seconds since Jan 1 1970
 282 00:00:00 GMT), and <code>data</code> is the content of the record.  The
 283 record number is sent as a string because while Blërg supports record
 284 numbers up to 2<sup>64</sup> - 1, Javascript uses floating point for all
 285 its numbers, and can only support integers without truncation up to
 286 2<sup>53</sup>.  This difference is largely academic, but I didn't want
 287 this problem to sneak up on anyone who is more insane than I am. :]
 288
 289 <p>The second form, /get/(user)/(start record)-(end record), retrieves a
 290 specific range of records, from (start record) to (end record)
 291 inclusive.  You can retrieve at most 100 records this way.  If (end
 292 record) - (start record) specifies more than 100 records, or if the
 293 range specifies invalid records, or if the end record is before the
 294 start record, the server will respond with JSON failure.
 295
 296 <h3><a name="api_info">/info/(user)</a> - Get information about a user</a></h3>
 297
 298 <p>A GET request to /info/(user) will return a JSON object with
 299 information about the user (currently only the number of records).  The
 300 info object looks like this:
 301
 302 <pre>
 303 {
 304   "record_count": "544"
 305 }
 306 </pre>
 307
 308 <p>Again, the record count is sent as a string for 64-bit safety.
 309
 310 <h3><a name="api_tag">/tag/(#|H|@)(tagname)</a> - Retrieve records containing tags</a></h3>
 311
 312 <p>A GET request to this endpoint will return the last 50 records
 313 associated with the given tag.  The first character is either # or H for
 314 hashtags, or @ for mentions (I call them ref tags).  You should URL
 315 encode the # or @, lest some servers complain at you.  The H alias for #
 316 was created because Apache helpfully strips the fragment of a URL
 317 (everything from the # to the end) before handing it off to the CGI,
 318 even if the hash is URL encoded.  The record objects also contain an
 319 extra <code>author</code> field, like so:
 320
 321 <pre>
 322 {
 323   "author":"Jon",
 324   "record":"57",
 325   "timestamp":1294555793,
 326   "data":"I'm taking #garfield to the vet."
 327 }
 328 </pre>
 329
 330 <p>There is currently no support for getting more than 50 tags, but /tag
 331 will probably mutate to work like /get.
 332
 333 <h3><a name="api_subscribe">/subscribe/(user)</a> - Subscribe to a
 334 user's updates</a></h3>
 335
 336 <p>POST to /subscribe/(user) with a <code>username</code> parameter and
 337 an auth cookie, where (user) is the user whose updates you wish to
 338 subscribe to.  The server will respond with JSON failure if the auth
 339 cookie is bad or if the user doesn't exist.  The server will respond
 340 with JSON success after the subscription is successfully registered.
 341
 342 <h3><a name="api_unsubscribe">/unsubscribe/(user)</a> - Unsubscribe from
 343 a user's updates</h3>
 344
 345 <p>Identical to /subscribe, but removes the subscription.
 346
 347 <h3><a name="api_feed">/feed</a> - Get updates for subscribed users</h3>
 348
 349 <p>POST to /feed, with a <code>username</code> parameter and an auth
 350 cookie.  The server will respond with a JSON list of the last 50 updates
 351 from all subscribed users, in reverse chronological order.  Fetching
 352 /feed resets the new message count returned from /feedinfo.
 353
 354 <p>NOTE: subscription notifications are only stored while subscriptions
 355 are active.  Any records inserted before or after a subscription is
 356 active will not show up in /feed.
 357
 358 <h3><a name="api_feedinfo">/feedinfo, /feedinfo/(user)</a> - Get subscription
 359 status for a user</a></h3>
 360
 361 <p>POST to /feedinfo with a <code>username</code> parameter and an auth
 362 cookie to get general information about your subscribed feeds.
 363 Currently, this only tells you how many new records there are since the
 364 last time /feed was fetched.  The server will respond with a JSON
 365 object:
 366
 367 <pre>
 368 {"new":3}
 369 </pre>
 370
 371 <p>POST to /feedinfo/(user) with a <code>username</code> parameter and
 372 an auth cookie, where (user) is a user whose subscription status you are
 373 interested in.  The server will respond with a simple JSON object:
 374
 375 <pre>
 376 {"subscribed":true}
 377 </pre>
 378
 379 <p>The value of "subscribed" will be either true or false depending on
 380 the subscription status.
 381
 382 <h3><a name="api_passwd">/passwd</a> - Change a user's password</a></h3>
 383
 384 <p>POST to /passwd with a <code>username</code> parameter and an auth
 385 cookie, plus <code>password</code> and <code>new_password</code>
 386 parameters to change the user's password.  For extra protection,
 387 changing a password requires sending the user's current password in the
 388 <code>password</code> parameter.  If authentication is successful and
 389 the password matches, the user's password is set to
 390 <code>new_password</code> and the server responds with JSON success.
 391
 392 If the password doesn't match, or one of <code>password</code> or
 393 <code>new_password</code> are missing, the server returns JSON failure.
 394
 395 <h2><a name="libraries">Libraries</a></h2>
 396
 397 <h3><a name="lib_c">C</a></h3>
 398
 399 <p>Most of Blërg's core functionality is packaged in a static library
 400 called <code>blerg.a</code>.  It's not designed to be public or
 401 installed with `make install-environment`, but it should be relatively
 402 straightforward to use it in C programs.  Look at the headers under the
 403 <code>databse</code> directory.
 404
 405 <p>A secondary library called <code>blerg_auth.a</code> handles the
 406 authentication layer of Blërg.  To use it, look at
 407 <code>common/auth.h</code>.
 408
 409 <h3><a name="lib_perl">Perl</a></h3>
 410
 411 <p>As of 1.9.0, Blërg includes a perl library called
 412 <code>Blerg::Database</code>.  It wraps the core and authentication
 413 functionality in a perlish interface.  The module has its own POD
 414 documentation, which you can read with your favorite POD reader, from
 415 the manual installed in an environment directory, or in HTML <a
 416 href="perl/Blerg-Database.html">here</a>.
 417
 418 <h2><a name="design">Design</a></h2>
 419
 420 <h3><a name="motivation">Motivation</a></h3>
 421
 422 <p>Blërg was created as the result of a thought experiment: "What if
 423 Twitter didn't need thousands of servers? What if its millions of users
 424 could be handled by a single highly efficient server?"  This is probably
 425 an unreachable goal due to the sheer amount of I/O, but we can certainly
 426 try to do better.  Blërg was thus designed as a system with very simple
 427 requirements:
 428
 429 <ol>
 430 <li>Store and fetch small chunks of text efficiently</li>
 431 <li>Create fast indexes for hash tags and @ mentions</li>
 432 <li>Provide a HTTP interface web apps can use</li>
 433 </ol>
 434
 435 <p>And to further simplify, I didn't bother handling deletes, full text
 436 search, or more complicated tag searches.  Blërg only does the basics.
 437
 438 <h3><a name="web_app_stack">Web App Stack</a></h3>
 439
 440 <table class="pizzapie">
 441 <tr><th>Classical model</th></tr>
 442 <tr>
 443   <td style="background-color: blue; color: white"><b>Client App</b><br>HTML/Javascript</td>
 444 </tr>
 445 <tr>
 446   <td style="background-color: #9F0000; color: white"><b>Webserver</b><br>Apache, lighttpd, nginx, etc.</td>
 447 </tr>
 448 <tr>
 449   <td style="background-color: #009F00; color: white"><b>Server App</b><br>Python, Perl, Ruby, etc.</td>
 450 </tr>
 451 <tr>
 452   <td style="background-color: #404040; color: white"><b>Database</b><br>MySQL, PostgreSQL, MongoDB, CouchDB, etc.</td>
 453 </tr>
 454 </table>
 455
 456 <p>Modern web applications have at least a four-layer approach.  You
 457 have the client-side browser app, the web server, the server-side
 458 application, and the database.  Your data goes through a lot of layers
 459 before it actually resides on disk somewhere (or, as they're calling it
 460 these days, "The Cloud" *waves hands*).  Each of those layers requires
 461 some amount of computing resources, so to increase throughput, we must
 462 make the layers more efficient, or reduce the number of layers.
 463
 464 <table class="pizzapie">
 465 <tr><th>Blërg model</th></tr>
 466 <tr>
 467   <td style="background-color: blue; color: white"><b>Blërg Client App</b><br>HTML/Javascript</td>
 468 </tr>
 469 <tr>
 470   <td style="background-color: #404040; color: white"><b>Blërg Database</b><br>Fuckin' hardcore C and shit</td>
 471 </tr>
 472 </table>
 473
 474 <p>Blërg does both by smashing the last two or three layers into one
 475 application.  Blërg can be run as either a standalone web server
 476 (currently deprecated because maintaining two versions is hard), or as a
 477 CGI (FastCGI support is planned, but I just don't care right now).  Less
 478 waste, more throughput.  As a consequence of this, the entirety of the
 479 application logic that the user sees is implemented in the client app in
 480 Javascript.  That's why all the URLs have #'s &mdash; the page is loaded
 481 once and switched on the fly to show different views, further reducing
 482 load on the server.  Even parsing hash tags and URLs are done in client
 483 JS.
 484
 485 <p>The API is simple and pragmatic.  It's not entirely RESTful, but is
 486 rather designed to work well with web-based front-ends.  Client data is
 487 always POSTed with the usual application/x-www-form-urlencoded encoding,
 488 and server data is always returned in JSON format.
 489
 490 <p>The HTTP interface to the database idea has already been done by <a
 491 href="http://couchdb.apache.org/">CouchDB</a>, though I didn't know that
 492 until after I wrote Blërg. :)
 493
 494 <h3><a name="database">Database</a></h3>
 495
 496 <p>I was impressed by <a
 497 href="http://www.varnish-cache.org/">varnish</a>'s design, so I decided
 498 early in the design process that I'd try out mmaped I/O.  Each user in
 499 Blërg has their own database, which consists of a metdata file, and one
 500 or more data and index files.  The data and index files are memory
 501 mapped, which hopefully makes things more efficient by letting the OS
 502 handle when to read from disk (or maybe not &mdash; I haven't
 503 benchmarked it).  The index files are preallocated because I believe
 504 it's more efficient than writing to it 40 bytes at a time as records are
 505 added.  The database's limits are reasonable:
 506
 507 <table class="statistics">
 508 <tr><td>maximum record size</td><td>65535 bytes</td></tr>
 509 <tr><td>maximum number of records per database</td><td>2<sup>64</sup> - 1</td></tr>
 510 <tr><td>maximum number of tags per record</td><td>1024</td></tr>
 511 <table>
 512
 513 <p>So as not to create grossly huge and unwieldy data files, the
 514 database layer splits data and index files into many "segments"
 515 containing at most 64K entries each.  Those of you doing some quick
 516 mental math may note that this could cause a problem on 32-bit machines
 517 &mdash; if a full segment contains entries of the maximum length, you'll
 518 have to mmap 4GB (32-bit Linux gives each process only 3GB of virtual
 519 address space).  Right now, 32-bit users should change
 520 <code>RECORDS_PER_SEGMENT</code> in <code>config.h</code> to something
 521 lower like 32768.  In the future, I might do something smart like not
 522 mmaping the whole fracking file.
 523
 524 <table class="bitstructure">
 525 <tr><th>Record Index Structure</th></tr>
 526 <tr><td class="B4">offset (32-bit integer)</td></tr>
 527 <tr><td class="B2">length (16-bit integer)</td></tr>
 528 <tr><td class="B2">flags (16-bit integer)</td></tr>
 529 <tr><td class="B4">timestamp (32-bit integer)</td></tr>
 530 </table>
 531
 532 <p>A record is stored by first appending the data to the data file, then
 533 writing an entry in the index file containing the offset and length of
 534 the data, as well as the timestamp.  Since each index entry is fixed
 535 length, we can find the index entry simply by multiplying the record
 536 number we want by the size of the index entry.  Upshot: constant-time
 537 random-access reads and constant-time writes.  As an added bonus,
 538 because we're using append-only files, we get lockless reads.
 539
 540 <table class="bitstructure">
 541 <tr><th>Tag Structure</th></tr>
 542 <tr><td class="B32">username (32 bytes)</td></tr>
 543 <tr><td class="B8">record number (64-bit integer)</td></tr>
 544 </table>
 545
 546 <p>Tags are handled by a separate set of indices, one per tag.  When a
 547 record is added, it is scanned for tags, then entries are appended to
 548 each tag index for the tags found.  Each index record simply stores the
 549 user and record number.  Tags are searched by opening the tag file,
 550 reading the last 50 entries or so, and then reading all the records
 551 listed.  Voila, fast tag lookups.
 552
 553 <p>At this point, you're probably thinking, "Is that it?"  Yep, that's
 554 it.  Blërg isn't revolutionary, it's just a system whose requirements
 555 were pared down until the implementation could be made dead simple.
 556
 557 <p>Also, keeping with the style of modern object databases, I haven't
 558 implemented any data safety (har har).  Blërg does not sync anything to
 559 disk before returning success.  This should make Blërg extremely fast,
 560 and totally unreliable in a crash.  But that's the way you want it,
 561 right? :]
 562
 563 <h3><a name="subscriptions">Subscriptions</a></h3>
 564
 565 <p>When I first started thinking about the idea of subscriptions, I
 566 immediately came up with the naïve solution: keep a list of users to
 567 which users are subscribed, then when you want to get updates, iterate
 568 over the list and find the last entries for each user.  And that would
 569 work, but it's kind of costly in terms of disk I/O.  I have to visit
 570 each user in the list, retrieve their last few entries, and store them
 571 somewhere else to be sorted later.  And worse, that computation has to
 572 be done every time a user checks their feed. As the number of users and
 573 subscriptions grows, that will become a problem.
 574
 575 <p>So instead, I thought about it the other way around. Instead of doing
 576 all the work when the request is received, Blërg tries to do as much as
 577 possible by "pushing" updates to subscribed users.  You can think of it
 578 kind of like a mail system.  When a user posts new content, a
 579 notification is "sent" out to each of that user's subscribers.  Later,
 580 when the subscribers want to see what's new, they simply check their
 581 mailbox.  Checking your mailbox is usually a lot more efficient than
 582 going around and checking everyone's records yourself, even with the
 583 overhead of the "mailman."
 584
 585 <p>The "mailbox" is a subscription index, which is identical to a tag
 586 index, but is a per-user construct.  When a user posts a new record, a
 587 subscription index record is written for every subscriber.  It's a
 588 similar amount of I/O as the naïve version above, but the important
 589 difference is that it's only done once.  Retrieving records for accounts
 590 you're subscribed to is then as simple as reading your subscription
 591 index and reading the associated records.  This is hopefully less I/O
 592 than the naïve version, since you're reading, at most, as many accounts
 593 as you have records in the last N entries of your subscription index,
 594 instead of all of them.  And as an added bonus, since subscription index
 595 records are added as posts are created, the subscription index is
 596 automatically sorted by time!  To support this "mail" architecture, we
 597 also keep a list of subscribers and subscrib...ees in each account.
 598
 599 <h3><a name="problems">Problems, Caveats, and Future Work</a></h3>
 600
 601 <p>Blërg probably doesn't actually work like Twitter because I've never
 602 actually had a Twitter account.
 603
 604 <p>I couldn't find a really good fast HTTP server library.
 605 Libmicrohttpd is small, but it's focused on embedded applications, so it
 606 often eschews speed for small memory footprint.  This is especially
 607 apparent when you watch it chew through a POST request 300 bytes at a
 608 time even though you've specified a buffer size of 256K.
 609 <code>blerg.httpd</code> is still pretty fast this way &mdash; on my
 610 2GHz Opteron 246, <a
 611 href="http://www.joedog.org/index/siege-home">siege</a> says it serves a
 612 690-byte /get request at about 945 transactions per second, average
 613 response time 0.05 seconds, with 100 concurrent accesses &mdash; but a
 614 fast HTTP server implementation could knock this out of the park.
 615
 616 <p>Libmicrohttpd is also really difficult to work with.  If you look at
 617 the code, <code>http_blerg.c</code> is about 70% longer than
 618 <code>cgi_blerg.c</code> simply because of all the iterator hoops I had
 619 to jump through to process POST requests.  And if you can believe it, I
 620 wrote <code>http_blerg.c</code> first. If I'd done it the other way
 621 around, I probably would have given up on libmicrohttpd. :-/
 622
 623 <p>The data structures written to disk are dependent on the size and
 624 endianness of the primitive data types on your architecture and OS.
 625 This means that the databases are not portable.  A dump/import tool is
 626 probably the easiest way to handle this.
 627
 628 <p>I do want to make a FastCGI version eventually, and this will
 629 probably be a rather simple modification of cgi_blerg.
 630
 631 <p>Implementing deletes will be... interesting.  There is room in the
 632 record index for a 'deleted' flag, but the problem is deleting any tags
 633 referenced in the data.  This requires rescanning the record content and
 634 putting a 'deleted' flag in the tag indices.  This will not be pretty,
 635 so I'm just going to ignore it and hope nobody makes any mistakes. ;]
 636
 637 <p>Tag indices can grow arbitrarily large, which will cause problems for
 638 32-bit machines around the 3GB mark.  Still, that's something like 80
 639 million tags, so maybe it's not something to worry about.
 640
 641 <p>The API currently requires the client to transmit the user's password
 642 in the clear.  A digest-based authentication scheme would be better,
 643 though for real security, the app should run over HTTPS.
 644
 645 </body>
 646 </html>