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 </head>
   7 <body>
   8
   9 <h1>Blërg Documentation</h1>
  10
  11 <h2>Installing</h2>
  12
  13 <h3>Getting the source</h3>
  14
  15 <p>There's no stable release, yet, but you can get everything currently
  16 running on blerg.dominionofawesome.com by cloning the git repository at
  17 http://git.bytex64.net/blerg.git.
  18
  19 <h3>Requirements</h3>
  20
  21 <p>Blërg has varying requirements depending on how you want to run it
  22 &mdash; as a standalone HTTP server, or as a CGI.  You will need:
  23
  24 <ul>
  25 <li><a href="http://lloyd.github.com/yajl/">yajl</a> &gt;= 1.0.0
  26 (yajl is a JSON parser/generator written in C which, by some twisted
  27 sense of humor, requires ruby to compile)</li>
  28 </ul>
  29
  30 <p>As a standalone HTTP, server, you will also need:
  31
  32 <ul>
  33 <li><a href="http://www.gnu.org/software/libmicrohttpd/">GNU libmicrohttpd</a> &gt;= 0.9.3</li>
  34 </ul>
  35
  36 <p>Or, as a CGI, you will need:
  37
  38 <ul>
  39 <li><a href="http://www.newbreedsoftware.com/cgi-util/download/">cgi-util</a> &gt;= 2.2.1</li>
  40 </ul>
  41
  42 <h3>Configuring</h3>
  43
  44 <p>I know I'm gonna get shit for not using an autoconf-based system, but
  45 I really didn't want to waste time figuring it out.  You should edit
  46 libs.mk and put in the paths where you can find headers and libraries
  47 for the above requirements.
  48
  49 <p>Also, further apologies to BSD folks &mdash; I've probably committed
  50 several unconscious Linux-isms.  It would not surprise me if the
  51 makefile refuses to work with BSD make.  If you have patches or
  52 suggestions on how to make Blërg more portable, I'd be happy to hear
  53 them.
  54
  55 <h3>Building</h3>
  56
  57 <p>At this point, it should be gravy.  Type 'make' and in a few seconds,
  58 you should have <code>http_blerg</code>, <code>cgi_blerg</code>,
  59 <code>rss</code>, and <code>blergtool</code>.  Each of those can be made
  60 individually as well, if you, for example, don't want to install the
  61 prerequisites for <code>http_blerg</code> or <code>cgi_blerg</code>.
  62
  63 <h3>Installing</h3>
  64
  65 <p>While it's not required, Blërg will be easier to set up if you
  66 configure it to work from the root of your website.  For this reason,
  67 it's better to use a subdomain (i.e., blerg.yoursite.com is easier than
  68 yoursite.com/blerg/).  If you do want to put it in a subdirectory, you
  69 will have to modify www/js/blerg.js and change baseURL at the top.  The
  70 CGI version should work fine this way, but the HTTP version will require
  71 the request to be rewritten, as it expects to be serving from the root.
  72
  73 <h4>For the standalone web server:</h4>
  74
  75 <p>Right now, http_blerg doesn't serve any static assets, so you're
  76 going to have to put it behind a real webserver like apache, lighttpd,
  77 nginx, or similar.  Set the document root to the www directory, then
  78 proxy /info, /create, /login, /logout, /get, /tag, and /put to
  79 http_blerg.
  80
  81 <h4>For the CGI version:</h4>
  82
  83 <p>Copy the files in www to the root of your web server.  Copy cgi_blerg
  84 to blerg.cgi somewhere on your web server.  Included in www-configs is a
  85 .htaccess file for apache that will rewrite the URLs.  If you need to
  86 call cgi_blerg something other than blerg.cgi, the .htaccess file will
  87 need to be modified.
  88
  89 <h4>The extra RSS CGI</h4>
  90
  91 <p>There is an optional RSS cgi (called simply rss) that will serve RSS
  92 feeds for users.  Install this like the CGI version above (on my server,
  93 it's at /rss.cgi).
  94
  95
  96 <h2>Design</h2>
  97
  98 <h3>Motivation</h3>
  99
 100 <p>Blërg was created as the result of a thought experiment: "What if
 101 Twitter didn't need thousands of servers? What if its millions of users
 102 could be handled by a single highly efficient server?"  This is probably
 103 an unreachable goal due to the sheer amount of I/O, but we could
 104 certainly do better.  Blërg was designed with very simple requirements:
 105
 106 <ol>
 107 <li>Store and fetch small chunks of text efficiently</li>
 108 <li>Create fast indexes for hash tags and @ mentions</li>
 109 <li>Provide a HTTP interface web apps can use</li>
 110 </ol>
 111
 112 <p>And to further simplify, I didn't bother handling deletes, full text
 113 search, or more complicated tag searches.  Blërg only does the basics.
 114
 115 <h3>Web App Stack</h3>
 116
 117 <table class="pizzapie">
 118 <tr><th>Classical model</th></tr>
 119 <tr>
 120   <td style="background-color: blue; color: white"><b>Client App</b><br>HTML/Javascript</td>
 121 </tr>
 122 <tr>
 123   <td style="background-color: #9F0000; color: white"><b>Webserver</b><br>Apache, lighttpd, nginx, etc.</td>
 124 </tr>
 125 <tr>
 126   <td style="background-color: #009F00; color: white"><b>Server App</b><br>Python, Perl, Ruby, etc.</td>
 127 </tr>
 128 <tr>
 129   <td style="background-color: #404040; color: white"><b>Database</b><br>MySQL, PostgreSQL, MongoDB, CouchDB, etc.</td>
 130 </tr>
 131 </table>
 132
 133 <p>Modern web applications have at least a four-layer approach.  You
 134 have the client-side browser app written in HTML and Javascript, the web
 135 server, the server-side application typically written in some scripting
 136 language (or, if it's high-performance, ASP/Java/C/C++), and the
 137 database (usually SQL, but newer web apps seem to love object-oriented
 138 DBs).
 139
 140 <table class="pizzapie">
 141 <tr><th>Blërg model</th></tr>
 142 <tr>
 143   <td style="background-color: blue; color: white"><b>Blërg Client App</b><br>HTML/Javascript</td>
 144 </tr>
 145 <tr>
 146   <td style="background-color: #404040; color: white"><b>Blërg Database</b><br></td>
 147 </tr>
 148 </table>
 149
 150 <p>Blërg compresses the last two or three layers into one application.
 151 Blërg can be run as either a standalone web server, or as a CGI (FastCGI
 152 support is planned, but I just don't care right now).  Less waste, more
 153 throughput.  As a consequence of this, the entirety of the application
 154 logic that the user sees is implemented in the client app in Javascript.
 155 That's why all the URLs have #'s &mdash; the page is loaded once and
 156 switched on the fly to show different views, further reducing load on
 157 the server.  Even parsing hash tags and URLs are done in client JS.
 158
 159 <p>The API is simple and pragmatic.  It's not entirely RESTful, but is
 160 rather designed to work well with web-based front-ends.  Client data is
 161 always POSTed with the usual application/x-www-form-urlencoded encoding,
 162 and server data is always returned in JSON format.
 163
 164 <p>The HTTP interface to the database idea has already been done by <a
 165 href="http://couchdb.apache.org/">CouchDB</a>, though I didn't know that
 166 until after I wrote Blërg. :)
 167
 168 <h3>Database</h3>
 169
 170 <p>Early in the design process, I decided to blatantly copy <a
 171 href="http://www.varnish-cache.org/">varnish</a> and rely heavily on
 172 mmap for I/O.  Each user in Blërg has their own database, which consists
 173 of one or more data and index files, and a metadata file.  When a
 174 database is opened, only the metadata is actually read (currently a
 175 single 64-bit integer keeping track of the last record id).  The data
 176 and index files are memory mapped, which hopefully makes things more
 177 efficient by letting the OS handle when to read from disk.  The index
 178 files are preallocated because I believe it's more efficient than
 179 writing to it 40 bytes at a time as records are added.  Here's some info
 180 on the database's limitations:
 181
 182 <table class="statistics">
 183 <tr><td>maximum record size</td><td>65535 bytes</td></tr>
 184 <tr><td>maximum number of records per database</td><td>2<sup>64</sup> - 1 bytes</td></tr>
 185 <tr><td>maximum number of tags per record</td><td>1024</td></tr>
 186 <table>
 187
 188 <p>To provide support for
 189 32-bit machines, and to not create grossly huge and unwieldy data files,
 190 the database layer splits data and index files into many "segments"
 191 containing at most 64K entries each.  Those of you doing some quick math
 192 in your heads may note that this could cause a problem on 32-bit
 193 machines &mdash; if a full segment contains entries of the maximum
 194 length, you'll have to mmap 4GB (32-bit Linux gives each process only
 195 3GB of virtual memory addressing).  Right now, 32-bit users should
 196 change <code>RECORDS_PER_SEGMENT</code> in <code>config.h</code> to
 197 something lower like 32768.  In the future, I might do something smart
 198 like not mmaping the whole fracking file.
 199
 200 <p>A record is stored by first appending the data to the data file, then
 201 writing an index entry containing the offset and length of the data, as
 202 well as the timestamp, to the index file.  Since each index entry is
 203 fixed length, we can find the index entry simply by multiplying the
 204 record number we want by the size of the index entry.  Upshot:
 205 constant-time random-access reads and constant-time writes.  As an added
 206 bonus, because we're using append-only files, we get lockless reads.
 207
 208 <p>Tags are handled by a separate set of indices, one per tag.  Each
 209 index record simply stores the user and record number.  Tags are
 210 searched by opening the tag file, reading the last 50 entries or so, and
 211 then reading all the records listed.  Voila, fast tag lookups.
 212
 213 <p>Also, keeping with the style of modern object databases, I haven't
 214 implemented any data safety (har har).  Blërg does not sync anything to
 215 disk before returning success.  This should make Blërg extremely fast,
 216 and totally unreliable in a crash.  But that's the way you want it,
 217 right? :]
 218
 219 <h3>Problems and Future Work</h3>
 220
 221 <p>I couldn't find a really good fast HTTP server library.
 222 Libmicrohttpd is small, but it's focused on embedded applications, so it
 223 often eschews speed for small memory footprint.  This is especially
 224 apparent when you watch it chew through a POST request 300 bytes at a
 225 time even though you've specified a buffer size of 256K.  Http_blerg is
 226 still pretty fast this way (on my 2GHz Opteron 246, <a
 227 href="http://www.joedog.org/index/siege-home">siege</a> says it serves a
 228 690-byte /get request at about 945 transactions per second, average
 229 response time 0.05 seconds, with 100 concurrent accesses), but a
 230 high-efficiency HTTP server implementation could knock this out of the
 231 park.
 232
 233 <p>Libmicrohttpd is also really difficult to work with.  If you look at
 234 the code, http_blerg.c is about 70% longer than cgi_blerg.c simply
 235 because of all the iterator hoops I had to jump through to process POST
 236 requests.  And if you can believe it, I wrote http_blerg.c first. If
 237 I'd done it the other way around, I probably would have given up on
 238 libmicrohttpd. :-/
 239
 240 <p>The data structures written to disk are dependent on the size and
 241 endianness of the primitive data types on your architecture and OS.
 242 This means that the databases are not portable.  A dump/import tool is
 243 probably the easiest way to handle this.
 244
 245 <p>I do want to make a FastCGI version eventually, and this will
 246 probably be a rather simple modification of cgi_blerg.
 247
 248 <p>Implementing deletes will be... interesting.  There is room in the
 249 record index for a 'deleted' flag, but the problem is deleting any tags
 250 referenced in the data.  This requires rescanning the record content and
 251 putting a 'deleted' flag in the tag indices.  This will not be pretty,
 252 so I'm just going to ignore it and hope nobody makes any mistakes. ;]
 253
 254 <p>Tag indices can grow arbitrarily large, which will cause problems for
 255 32-bit machines around the 3GB mark.  Still, that's something like 80
 256 million tags, so maybe it's not something to worry about.
 257
 258 <p>The API currently requires the client to transmit the user's password
 259 in the clear.  A digest-based authentication scheme would be better,
 260 though for real security, the app should run over HTTPS.
 261
 262 </body>
 263 </html>