doc/TwitterAlikeExample.html

   1
   2 <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN">
   3 <html>
   4     <head>
   5         <link type="text/css" rel="stylesheet" href="style.css" />
   6     </head>
   7     <body>
   8         <div id="page">
   9
  10             <div id='header'>
  11             <a href="index.html">
  12             <img style="border:none" alt="Redis Documentation" src="redis.png">
  13             </a>
  14             </div>
  15
  16             <div id="pagecontent">
  17                 <div class="index">
  18 <!-- This is a (PRE) block.  Make sure it's left aligned or your toc title will be off. -->
  19 <b>TwitterAlikeExample: Contents</b><br>&nbsp;&nbsp;<a href="#A case study: Design and implementation of a simple Twitter clone using only the Redis key-value store as database and PHP">A case study: Design and implementation of a simple Twitter clone using only the Redis key-value store as database and PHP</a><br>&nbsp;&nbsp;<a href="#Key-value stores basics">Key-value stores basics</a><br>&nbsp;&nbsp;&nbsp;&nbsp;<a href="#Atomic operations">Atomic operations</a><br>&nbsp;&nbsp;&nbsp;&nbsp;<a href="#Beyond key-value stores">Beyond key-value stores</a><br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<a href="#The set data type">The set data type</a><br>&nbsp;&nbsp;&nbsp;&nbsp;<a href="#Prerequisites">Prerequisites</a><br>&nbsp;&nbsp;&nbsp;&nbsp;<a href="#Data layout">Data layout</a><br>&nbsp;&nbsp;&nbsp;&nbsp;<a href="#Following, followers and updates">Following, followers and updates</a><br>&nbsp;&nbsp;&nbsp;&nbsp;<a href="#Authentication">Authentication</a><br>&nbsp;&nbsp;&nbsp;&nbsp;<a href="#Updates">Updates</a><br>&nbsp;&nbsp;&nbsp;&nbsp;<a href="#Paginating updates">Paginating updates</a><br>&nbsp;&nbsp;&nbsp;&nbsp;<a href="#Following users">Following users</a><br>&nbsp;&nbsp;<a href="#Making it horizontally scalable">Making it horizontally scalable</a><br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<a href="#Hashing the key">Hashing the key</a><br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<a href="#Special keys">Special keys</a>
  20                 </div>
  21
  22                 <h1 class="wikiname">TwitterAlikeExample</h1>
  23
  24                 <div class="summary">
  25
  26                 </div>
  27
  28                 <div class="narrow">
  29                     <h1><a name="A case study: Design and implementation of a simple Twitter clone using only the Redis key-value store as database and PHP">A case study: Design and implementation of a simple Twitter clone using only the Redis key-value store as database and PHP</a></h1>In this article I'll explain the design and the implementation of a <a href="http://retwis.antirez.com" target="_blank">simple clone of Twitter</a> written using PHP and <a href="http://code.google.com/p/redis/" target="_blank">Redis</a> as only database. The programming community uses to look at key-value stores like special databases that can't be used as drop in replacement for a relational database for the development of web applications. This article will try to prove the contrary.<br/><br/>Our Twitter clone, <a href="http://retwis.antirez.com" target="_blank">called Retwis</a>, is structurally simple, has very good performances, and can be distributed among N web servers and M Redis servers with very little efforts. You can find the source code <a href="http://code.google.com/p/redis/downloads/list" target="_blank">here</a>.<br/><br/>We use PHP for the example since it can be read by everybody. The same (or... much better) results can be obtained using Ruby, Python, Erlang, and so on.<br/><br/><b>News! <a href="http://retwisrb.danlucraft.com/" target="_blank">Retwis-rb</a> is a port of Retwis to Ruby and Sinatra written by Daniel Lucraft!</b> With full source code included of course, the git repository is linked at the end of the Retwis-RB page. The rest of this article targets PHP, but Ruby programmers can also check the other source code, it conceptually very similar.<h1><a name="Key-value stores basics">Key-value stores basics</a></h1>
  30 The essence of a key-value store is the ability to store some data, called <i>value</i>, inside a key. This data can later be retrieved only if we know the exact key used to store it. There is no way to search something by value. So for example I can use the command SET to store the value <b>bar</b> at key <b>foo</b>:<br/><br/><pre class="codeblock python" name="code">
  31 SET foo bar
  32 </pre>Redis will store our data permanently, so we can later ask for &quot;<i>What is the value stored at key foo?</i>&quot; and Redis will reply with <b>bar</b>:<br/><br/><pre class="codeblock python python" name="code">
  33 GET foo =&gt; bar
  34 </pre>Other common operations provided by key-value stores are DEL used to delete a given key, and the associated value, SET-if-not-exists (called SETNX on Redis) that sets a key only if it does not already exist, and INCR that is able to atomically increment a number stored at a given key:<br/><br/><pre class="codeblock python python python" name="code">
  35 SET foo 10
  36 INCR foo =&gt; 11
  37 INCR foo =&gt; 12
  38 INCR foo =&gt; 13
  39 </pre><h2><a name="Atomic operations">Atomic operations</a></h2>
  40 So far it should be pretty simple, but there is something special about INCR. Think about this, why to provide such an operation if we can do it ourself with a bit of code? After all it is as simple as:<br/><br/><pre class="codeblock python python python python" name="code">
  41 x = GET foo
  42 x = x + 1
  43 SET foo x
  44 </pre>The problem is that doing the increment this way will work as long as there is only a client working with the value <i>x</i> at a time. See what happens if two computers are accessing this data at the same time:<br/><br/><pre class="codeblock python python python python python" name="code">
  45 x = GET foo (yields 10)
  46 y = GET foo (yields 10)
  47 x = x + 1 (x is now 11)
  48 y = y + 1 (y is now 11)
  49 SET foo x (foo is now 11)
  50 SET foo y (foo is now 11)
  51 </pre>Something is wrong with that! We incremented the value two times, but instead to go from 10 to 12 our key holds 11. This is because the INCR operation done with <code name="code" class="python">GET / increment / SET</code> <b>is not an atomic operation</b>. Instead the INCR provided by Redis, Memcached, ..., are atomic implementations, the server will take care to protect the get-increment-set for all the time needed to complete in order to prevent simultaneous accesses.<br/><br/>What makes Redis different from other key-value stores is that it provides more operations similar to INCR that can be used together to model complex problems. This is why you can use Redis to write whole web applications without using an SQL database and without to get mad.
  52 <h2><a name="Beyond key-value stores">Beyond key-value stores</a></h2>
  53 In this section we will see what Redis features we need to build our Twitter clone. The first thing to know is that Redis values can be more than strings. Redis supports Lists and Sets as values, and there are atomic operations to operate against this more advanced values so we are safe even with multiple accesses against the same key. Let's start from Lists:<br/><br/><pre class="codeblock python python python python python python" name="code">
  54 LPUSH mylist a (now mylist holds one element list 'a')
  55 LPUSH mylist b (now mylist holds 'b,a')
  56 LPUSH mylist c (now mylist holds 'c,b,a')
  57 </pre>LPUSH means <i>Left Push</i>, that is, add an element to the left (or to the head) of the list stored at <i>mylist</i>. If the key <i>mylist</i> does not exist it is automatically created by Redis as an empty list before the PUSH operation. As you can imagine, there is also the RPUSH operation that adds the element on the right of the list (on the tail).<br/><br/>This is very useful for our Twitter clone. Updates of users can be stored into a list stored at <code name="code" class="python">username:updates</code> for instance. There are operations to get data or information from Lists of course. For instance LRANGE returns a range of the list, or the whole list.<br/><br/><pre class="codeblock python python python python python python python" name="code">
  58 LRANGE mylist 0 1 =&gt; c,b
  59 </pre>LRANGE uses zero-based indexes, that is the first element is 0, the second 1, and so on. The command aguments are <code name="code" class="python">LRANGE key first-index last-index</code>. The <i>last index</i> argument can be negative, with a special meaning: -1 is the last element of the list, -2 the penultimate, and so on. So in order to get the whole list we can use:<br/><br/><pre class="codeblock python python python python python python python python" name="code">
  60 LRANGE mylist 0 -1 =&gt; c,b,a
  61 </pre>Other important operations are LLEN that returns the length of the list, and LTRIM that is like LRANGE but instead of returning the specified range <b>trims</b> the list, so it is like <i>Get range from mylist, Set this range as new value</i> but atomic. We will use only this List operations, but make sure to check the <a href="http://code.google.com/p/redis/wiki/README" target="_blank">Redis documentation</a> to discover all the List operations supported by Redis.
  62 <h3><a name="The set data type">The set data type</a></h3>
  63 There is more than Lists, Redis also supports Sets, that are unsorted collection of elements. It is possible to add, remove, and test for existence of members, and perform intersection between different Sets. Of course it is possible to ask for the list or the number of elements of a Set. Some example will make it more clear. Keep in mind that SADD is the <i>add to set</i> operation, SREM is the <i>remove from set</i> operation, <i>sismember</i> is the <i>test if it is a member</i> operation, and SINTER is <i>perform intersection</i> operation. Other operations are SCARD that is used to get the cardinality (the number of elements) of a Set, and SMEMBERS that will return all the members of a Set.<br/><br/><pre class="codeblock python python python python python python python python python" name="code">
  64 SADD myset a
  65 SADD myset b
  66 SADD myset foo
  67 SADD myset bar
  68 SCARD myset =&gt; 4
  69 SMEMBERS myset =&gt; bar,a,foo,b
  70 </pre>Note that SMEMBERS does not return the elements in the same order we added them, since Sets are <b>unsorted</b> collections of elements. When you want to store the order it is better to use Lists instead. Some more operations against Sets:<br/><br/><pre class="codeblock python python python python python python python python python python" name="code">
  71 SADD mynewset b
  72 SADD mynewset foo
  73 SADD mynewset hello
  74 SINTER myset mynewset =&gt; foo,b
  75 </pre>SINTER can return the intersection between Sets but it is not limited to two sets, you may ask for intersection of 4,5 or 10000 Sets. Finally let's check how SISMEMBER works:<br/><br/><pre class="codeblock python python python python python python python python python python python" name="code">
  76 SISMEMBER myset foo =&gt; 1
  77 SISMEMBER myset notamember =&gt; 0
  78 </pre>Ok I think we are ready to start coding!
  79 <h2><a name="Prerequisites">Prerequisites</a></h2>
  80 If you didn't download it already please <a href="http://code.google.com/p/redis/wiki/README" target="_blank">grab the source code of Retwis</a>. It's a simple tar.gz file with a few of .php files inside. The implementation is very simple. You will find the PHP library client inside (redis.php) that is used to talk with the Redis server from PHP. This library was written by <a href="http://qix.it" target="_blank">Ludovico Magnocavallo</a> and you are free to reuse this in your own projects, but for updated version of the library please download the Redis distribution.<br/><br/>Another thing you probably want is a working Redis server. Just get the source, compile with make, and run with ./redis-server and you are done. No configuration is required at all in order to play with it or to run Retwis in your computer.
  81 <h2><a name="Data layout">Data layout</a></h2>
  82 Working with a relational database this is the stage were the database layout should be produced in form of tables, indexes, and so on. We don't have tables, so what should be designed? We need to identify what keys are needed to represent our objects and what kind of values this keys need to hold.<br/><br/>Let's start from Users. We need to represent this users of course, with the username, userid, password, followers and following users, and so on. The first question is, what should identify an user inside our system? The username can be a good idea since it is unique, but it is also too big, and we want to stay low on memory. So like if our DB was a relational one we can associate an unique ID to every user. Every other reference to this user will be done by id. That's very simple to do, because we have our atomic INCR operation! When we create a new user we can do something like this, assuming the user is callled &quot;antirez&quot;:<br/><br/><pre class="codeblock python python python python python python python python python python python python" name="code">
  83 INCR global:nextUserId =&gt; 1000
  84 SET uid:1000:username antirez
  85 SET uid:1000:password p1pp0
  86 </pre>We use the <i>global:nextUserId</i> key in order to always get an unique ID for every new user. Then we use this unique ID to populate all the other keys holding our user data. <b>This is a Design Pattern</b> with key-values stores! Keep it in mind.
  87 Besides the fields already defined, we need some more stuff in order to fully define an User. For example sometimes it can be useful to be able to get the user ID from the username, so we set this key too:<br/><br/><pre class="codeblock python python python python python python python python python python python python python" name="code">
  88 SET username:antirez:uid 1000
  89 </pre>This may appear strange at first, but remember that we are only able to access data by key! It's not possible to tell Redis to return the key that holds a specific value. This is also <b>our strength</b>, this new paradigm is forcing us to organize the data so that everything is accessible by <i>primary key</i>, speaking with relational DBs language.
  90 <h2><a name="Following, followers and updates">Following, followers and updates</a></h2>
  91 There is another central need in our system. Every user has followers users and following users. We have a perfect data structure for this work! That is... Sets. So let's add this two new fields to our schema:<br/><br/><pre class="codeblock python python python python python python python python python python python python python python" name="code">
  92 uid:1000:followers =&gt; Set of uids of all the followers users
  93 uid:1000:following =&gt; Set of uids of all the following users
  94 </pre>Another important thing we need is a place were we can add the updates to display in the user home page. We'll need to access this data in chronological order later, from the most recent update to the older ones, so the perfect kind of Value for this work is a List. Basically every new update will be LPUSHed in the user updates key, and thanks to LRANGE we can implement pagination and so on. Note that we use the words <i>updates</i> and <i>posts</i> interchangeably, since updates are actually &quot;little posts&quot; in some way.<br/><br/><pre class="codeblock python python python python python python python python python python python python python python python" name="code">
  95 uid:1000:posts =&gt; a List of post ids, every new post is LPUSHed here.
  96 </pre>
  97 <h2><a name="Authentication">Authentication</a></h2>
  98 Ok we have more or less everything about the user, but authentication. We'll handle authentication in a simple but robust way: we don't want to use PHP sessions or other things like this, our system must be ready in order to be distributed among different servers, so we'll take the whole state in our Redis database. So all we need is a random string to set as the cookie of an authenticated user, and a key that will tell us what is the user ID of the client holding such a random string. We need two keys in order to make this thing working in a robust way:<br/><br/><pre class="codeblock python python python python python python python python python python python python python python python python" name="code">
  99 SET uid:1000:auth fea5e81ac8ca77622bed1c2132a021f9
 100 SET auth:fea5e81ac8ca77622bed1c2132a021f9 1000
 101 </pre>In order to authenticate an user we'll do this simple work (login.php):
 102 <ul><li> Get the username and password via the login form</li><li> Check if the username:<code name="code" class="python">&lt;username&gt;</code>:uid key actually exists</li><li> If it exists we have the user id, (i.e. 1000)</li><li> Check if uid:1000:password matches, if not, error message</li><li> Ok authenticated! Set &quot;fea5e81ac8ca77622bed1c2132a021f9&quot; (the value of uid:1000:auth) as &quot;auth&quot; cookie</li></ul>
 103 This is the actual code:<br/><br/><pre class="codeblock python python python python python python python python python python python python python python python python python" name="code">
 104 include(&quot;retwis.php&quot;);
 105
 106 # Form sanity checks
 107 if (!gt(&quot;username&quot;) || !gt(&quot;password&quot;))
 108     goback(&quot;You need to enter both username and password to login.&quot;);
 109
 110 # The form is ok, check if the username is available
 111 $username = gt(&quot;username&quot;);
 112 $password = gt(&quot;password&quot;);
 113 $r = redisLink();
 114 $userid = $r-&gt;get(&quot;username:$username:id&quot;);
 115 if (!$userid)
 116     goback(&quot;Wrong username or password&quot;);
 117 $realpassword = $r-&gt;get(&quot;uid:$userid:password&quot;);
 118 if ($realpassword != $password)
 119     goback(&quot;Wrong useranme or password&quot;);
 120
 121 # Username / password OK, set the cookie and redirect to index.php
 122 $authsecret = $r-&gt;get(&quot;uid:$userid:auth&quot;);
 123 setcookie(&quot;auth&quot;,$authsecret,time()+3600*24*365);
 124 header(&quot;Location: index.php&quot;);
 125 </pre>This happens every time the users log in, but we also need a function isLoggedIn in order to check if a given user is already authenticated or not. These are the logical steps preformed by the <code name="code" class="python">isLoggedIn</code> function:
 126 <ul><li> Get the &quot;auth&quot; cookie from the user. If there is no cookie, the user is not logged in, of course. Let's call the value of this cookie <code name="code" class="python">&lt;authcookie&gt;</code></li><li> Check if auth:<code name="code" class="python">&lt;authcookie&gt;</code> exists, and what the value (the user id) is (1000 in the exmple).</li><li> In order to be sure check that uid:1000:auth matches.</li><li> Ok the user is authenticated, and we loaded a bit of information in the $User global variable.</li></ul>
 127 The code is simpler than the description, possibly:<br/><br/><pre class="codeblock python python python python python python python python python python python python python python python python python python" name="code">
 128 function isLoggedIn() {
 129     global $User, $_COOKIE;
 130
 131     if (isset($User)) return true;
 132
 133     if (isset($_COOKIE['auth'])) {
 134         $r = redisLink();
 135         $authcookie = $_COOKIE['auth'];
 136         if ($userid = $r-&gt;get(&quot;auth:$authcookie&quot;)) {
 137             if ($r-&gt;get(&quot;uid:$userid:auth&quot;) != $authcookie) return false;
 138             loadUserInfo($userid);
 139             return true;
 140         }
 141     }
 142     return false;
 143 }
 144
 145 function loadUserInfo($userid) {
 146     global $User;
 147
 148     $r = redisLink();
 149     $User['id'] = $userid;
 150     $User['username'] = $r-&gt;get(&quot;uid:$userid:username&quot;);
 151     return true;
 152 }
 153 </pre><code name="code" class="python">loadUserInfo</code> as separated function is an overkill for our application, but it's a good template for a complex application. The only thing it's missing from all the authentication is the logout. What we do on logout? That's simple, we'll just change the random string in uid:1000:auth, remove the old auth:<code name="code" class="python">&lt;oldauthstring&gt;</code> and add a new auth:<code name="code" class="python">&lt;newauthstring&gt;</code>.<br/><br/><b>Important:</b> the logout procedure explains why we don't just authenticate the user after the lookup of auth:<code name="code" class="python">&lt;randomstring&gt;</code>, but double check it against uid:1000:auth. The true authentication string is the latter, the auth:<code name="code" class="python">&lt;randomstring&gt;</code> is just an authentication key that may even be volatile, or if there are bugs in the program or a script gets interrupted we may even end with multiple auth:<code name="code" class="python">&lt;something&gt;</code> keys pointing to the same user id. The logout code is the following (logout.php):<br/><br/><pre class="codeblock python python python python python python python python python python python python python python python python python python python" name="code">
 154 include(&quot;retwis.php&quot;);
 155
 156 if (!isLoggedIn()) {
 157     header(&quot;Location: index.php&quot;);
 158     exit;
 159 }
 160
 161 $r = redisLink();
 162 $newauthsecret = getrand();
 163 $userid = $User['id'];
 164 $oldauthsecret = $r-&gt;get(&quot;uid:$userid:auth&quot;);
 165
 166 $r-&gt;set(&quot;uid:$userid:auth&quot;,$newauthsecret);
 167 $r-&gt;set(&quot;auth:$newauthsecret&quot;,$userid);
 168 $r-&gt;delete(&quot;auth:$oldauthsecret&quot;);
 169
 170 header(&quot;Location: index.php&quot;);
 171 </pre>That is just what we described and should be simple to undestand.
 172 <h2><a name="Updates">Updates</a></h2>
 173 Updates, also known as posts, are even simpler. In order to create a new post on the database we do something like this:<br/><br/><pre class="codeblock python python python python python python python python python python python python python python python python python python python python" name="code">
 174 INCR global:nextPostId =&gt; 10343
 175 SET post:10343 &quot;$owner_id|$time|I'm having fun with Retwis&quot;
 176 </pre>As you can se the user id and time of the post are stored directly inside the string, we don't need to lookup by time or user id in the example application so it is better to compact everything inside the post string.<br/><br/>After we create a post we obtain the post id. We need to LPUSH this post id in every user that's following the author of the post, and of course in the list of posts of the author. This is the file update.php that shows how this is performed:<br/><br/><pre class="codeblock python python python python python python python python python python python python python python python python python python python python python" name="code">
 177 include(&quot;retwis.php&quot;);
 178
 179 if (!isLoggedIn() || !gt(&quot;status&quot;)) {
 180     header(&quot;Location:index.php&quot;);
 181     exit;
 182 }
 183
 184 $r = redisLink();
 185 $postid = $r-&gt;incr(&quot;global:nextPostId&quot;);
 186 $status = str_replace(&quot;\n&quot;,&quot; &quot;,gt(&quot;status&quot;));
 187 $post = $User['id'].&quot;|&quot;.time().&quot;|&quot;.$status;
 188 $r-&gt;set(&quot;post:$postid&quot;,$post);
 189 $followers = $r-&gt;smembers(&quot;uid:&quot;.$User['id'].&quot;:followers&quot;);
 190 if ($followers === false) $followers = Array();
 191 $followers[] = $User['id']; /* Add the post to our own posts too */
 192
 193 foreach($followers as $fid) {
 194     $r-&gt;push(&quot;uid:$fid:posts&quot;,$postid,false);
 195 }
 196 # Push the post on the timeline, and trim the timeline to the
 197 # newest 1000 elements.
 198 $r-&gt;push(&quot;global:timeline&quot;,$postid,false);
 199 $r-&gt;ltrim(&quot;global:timeline&quot;,0,1000);
 200
 201 header(&quot;Location: index.php&quot;);
 202 </pre>The core of the function is the <code name="code" class="python">foreach</code>. We get using SMEMBERS all the followers of the current user, then the loop will LPUSH the post against the uid:<code name="code" class="python">&lt;userid&gt;</code>:posts of every follower.<br/><br/>Note that we also maintain a timeline with all the posts. In order to do so what is needed is just to LPUSH the post against global:timeline. Let's face it, do you start thinking it was a bit strange to have to sort things added in chronological order using ORDER BY with SQL? I think so indeed.
 203 <h2><a name="Paginating updates">Paginating updates</a></h2>
 204 Now it should be pretty clear how we can user LRANGE in order to get ranges of posts, and render this posts on the screen. The code is simple:<br/><br/><pre class="codeblock python python python python python python python python python python python python python python python python python python python python python python" name="code">
 205 function showPost($id) {
 206     $r = redisLink();
 207     $postdata = $r-&gt;get(&quot;post:$id&quot;);
 208     if (!$postdata) return false;
 209
 210     $aux = explode(&quot;|&quot;,$postdata);
 211     $id = $aux[0];
 212     $time = $aux[1];
 213     $username = $r-&gt;get(&quot;uid:$id:username&quot;);
 214     $post = join(array_splice($aux,2,count($aux)-2),&quot;|&quot;);
 215     $elapsed = strElapsed($time);
 216     $userlink = &quot;&lt;a class=\&quot;username\&quot; href=\&quot;profile.php?u=&quot;.urlencode($username).&quot;\&quot;&gt;&quot;.utf8entities($username).&quot;&lt;/a&gt;&quot;;
 217
 218     echo('&lt;div class=&quot;post&quot;&gt;'.$userlink.' '.utf8entities($post).&quot;&lt;br&gt;&quot;);
 219     echo('&lt;i&gt;posted '.$elapsed.' ago via web&lt;/i&gt;&lt;/div&gt;');
 220     return true;
 221 }
 222
 223 function showUserPosts($userid,$start,$count) {
 224     $r = redisLink();
 225     $key = ($userid == -1) ? &quot;global:timeline&quot; : &quot;uid:$userid:posts&quot;;
 226     $posts = $r-&gt;lrange($key,$start,$start+$count);
 227     $c = 0;
 228     foreach($posts as $p) {
 229         if (showPost($p)) $c++;
 230         if ($c == $count) break;
 231     }
 232     return count($posts) == $count+1;
 233 }
 234 </pre><code name="code" class="python">showPost</code> will simply convert and print a Post in HTML while <code name="code" class="python">showUserPosts</code> get range of posts passing them to <code name="code" class="python">showPosts</code>.<h2><a name="Following users">Following users</a></h2>If user id 1000 (antirez) wants to follow user id 1001 (pippo), we can do this with just two SADD:<br/><br/><pre class="codeblock python python python python python python python python python python python python python python python python python python python python python python python" name="code">
 235 SADD uid:1000:following 1001
 236 SADD uid:1001:followers 1000
 237 </pre>Note the same pattern again and again, in theory with a relational database the list of following and followers is a single table with fields like <code name="code" class="python">following_id</code> and <code name="code" class="python">follower_id</code>. With queries you can extract the followers or following of every user. With a key-value DB that's a bit different as we need to set both the <code name="code" class="python">1000 is following 1001</code> and <code name="code" class="python">1001 is followed by 1000</code> relations. This is the price to pay, but on the other side accessing the data is simpler and ultra-fast. And having this things as separated sets allows us to do interesting stuff, for example using SINTER we can have the intersection of 'following' of two different users, so we may add a feature to our Twitter clone so that it is able to say you at warp speed, when you visit somebody' else profile, &quot;you and foobar have 34 followers in common&quot; and things like that.<br/><br/>You can find the code that sets or removes a following/follower relation at follow.php. It is trivial as you can see.
 238 <h1><a name="Making it horizontally scalable">Making it horizontally scalable</a></h1>
 239 Gentle reader, if you reached this point you are already an hero, thank you. Before to talk about scaling horizontally it is worth to check the performances on a single server. Retwis is <b>amazingly fast</b>, without any kind of cache. On a very slow and loaded server, apache benchmark with 100 parallel clients issuing 100000 requests measured the average pageview to take 5 milliseconds. This means you can serve millions of users every day with just a single Linux box, and this one was monkey asses slow! Go figure with more recent hardware.<br/><br/>So, first of all, probably you will not need more than one server for a lot of applications, even when you have a lot of users. But let's assume we <b>are</b> Twitter and need to handle a huge amount of traffic. What to do?
 240 <h3><a name="Hashing the key">Hashing the key</a></h3>
 241 The first thing to do is to hash the key and issue the request on different servers based on the key hash. There are a lot of well known algorithms to do so, for example check the Redis Ruby library client that implements <i>consistent hashing</i>, but the general idea is that you can turn your key into a number, and than take the reminder of the division of this number by the number of servers you have:<br/><br/><pre class="codeblock python python python python python python python python python python python python python python python python python python python python python python python python" name="code">
 242 server_id = crc32(key) % number_of_servers
 243 </pre>This has a lot of problems since if you add one server you need to move too much keys and so on, but this is the general idea even if you use a better hashing scheme like consistent hashing.<br/><br/>Ok, are key accesses distributed among the key space? Well, all the user data will be partitioned among different servers. There are no inter-keys operations used (like SINTER, otherwise you need to care that things you want to intersect will end in the same server. <b>This is why Redis unlike memcached does not force a specific hashing scheme, it's application specific</b>). Btw there are keys that are accessed more frequently.<h3><a name="Special keys">Special keys</a></h3>For example every time we post a new message, we <b>need</b> to increment the <code name="code" class="python">global:nextPostId</code> key. How to fix this problem? A Single server will get a lot if increments. The simplest way to handle this is to have a dedicated server just for increments. This is probably an overkill btw unless you have really a lot of traffic. There is another trick. The ID does not really need to be an incremental number, but just <b>it needs to be unique</b>. So you can get a random string long enough to be unlikely (almost impossible, if it's md5-size) to collide, and you are done. We successfully eliminated our main problem to make it really horizontally scalable!<br/><br/>There is another one: global:timeline. There is no fix for this, if you need to take something in order you can split among different servers and <b>then merge</b> when you need to get the data back, or take it ordered and use a single key. Again if you really have so much posts per second, you can use a single server just for this. Remember that with commodity hardware Redis is able to handle 100000 writes for second, that's enough even for Twitter, I guess.<br/><br/>Please feel free to use the comments below for questions and feedbacks.
 244                 </div>
 245
 246             </div>
 247         </div>
 248     </body>
 249 </html>
 250