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