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