On April 26th 2007 Steve Souders wrote:

The user’s proximity to your web server has an impact on response times. Deploying your content across multiple, geographically dispersed servers will make your pages load faster from the user’s perspective. [...] Remember that 80-90% of the end-user response time is spent downloading all the components in the page: images, stylesheets, scripts, Flash, etc. [...] A content delivery network (CDN) is a collection of web servers distributed across multiple locations to deliver content more efficiently to users.

Steve posted this approx. e^3.25809654 days after(!) we started to use a CDN for our web sites. Just some days later we noticed the desired effect. Our users started to make more and more traffic. The activity grew. Of course a CDN is some kind of luxury but it’s worth to invest into such a service at a special time. And from our point of view we thought it was time to. We were right.

Actually round about 286.356,421^2 objects will be requested per month by our users. More than the half of that (5,4E10 objects) are photos. Small, medium and big sized ones. So each of all photo files we store will be loaded round(pow(2,4.91)) times in a month. That makes a monthly traffic volume of more ore less 265.334.489.612.288 bytes only for these kind of objects. The total traffic of all delivered objects per month is something about 1,402939962446178 times higher.

At high traffic times there are over 11000011010100000₂ requests per second hitting our CDN and we are happy that our origin servers only get the (5^5)th part of it.

As a side effect we can learn something about the behaviour of our users because the performance graphs can show us for example what they do in the evening. Maybe the Schimanski serials on 26th of July was one of the reasons for the spikes after 8 pm (see graph above) which are nothing else than commercial breaks. Have a break, have a visit at studiVZ.

We wanted to speed up our web-applications by alleviating our database-loads. So we decided to use the distributed memory object caching system, memcached. Due to the many requests of our memcached-systems (about 1.5 million requests per second), we built a tool (called mckoy), which is capable to perform statistics and debugging information about all memcache-requests in our network.

mckoy is a memcache protocol sniffer (based on pcap library) and statistics builder. It automatically detects and parses each key (and its value) and memcache-api methods.  At  the  end of the sniffing session, the results are used to build the statisticis. mckoy was written to analyse our web application and its usage of  memcache-api in PHP. For example: We wanted to know how many set() and get() methods were invoked in a given time. Based on these results,  we had to make changes to improve the usage of memcache-api for PHP. You can run mckoy on any UNIX based systems. It was tested on many *BSD and Linux systems. mckoy is licensed under GPLv3 and completely published as opensource project!

You can run mckoy in various modes (see manpage!). For example, if you want to sniff pattern “foobar” for all memcache-api methods and with live capturing, use:

mckoy -i <interface> -e “port 11211″ -m 5 -k foobar -v

And this is, how it looks like:

Unfortunately, there are some known bugs. :) For example: An SIGSEGV will encounter when ^C is sent from user. Also, we noticed that mckoy isn’t able to handle memcached-1.2.8 <= 1.4.* correctly. These bugs will be fixed in the next version as soon as possible! For the next version I also planned to build in udp and binary support.

You can offcially download mckoy from:
http://www.lamergarten.de/releases.html
or
http://sourceforge.net/projects/mckoy/

cheers.

I attended an awesome talk by Kenneth Lundin about Erlang/OTP at the Erlang Factory in London. The main topic was SMP and it’s improvements it in the latest release(s). That’s exactly one of the main reasons for Erlang, parallelize computations on many cores, without worrying about locks in shared memory.

Some of the issues they’ve been working on:

1. Erlang now detects CPU Topology automatically at startup.
2. Multiple run-queues
3. You can lock schedulers to logical CPU’S
4. Improved message passing – reduced lock time

They improved more things of course but considering SMP these are the most important ones.

1. Erlang now detects the CPU topology of your system automatically at startup. You may still override this automatic setup using:
   erl +sct L0-3c0-3
erlang:system_flag(cpu_topology,CpuTopology).
2. Multiple run queues … what does that mean? We should first take a look at how Erlang does SMP:
   • Erlang without SMP:
     Without SMP support the Erlang VM had one Scheduler for one runqueue. So all the jobs were pushed on one queue and fetched by one scheduler.
   • Erlang SMP / before R13
     They started more schedulers that were pulling jobs from one queue. Sounds more parallel but still not performing as good as desired on many cores.
   • Erlang SMP R13
     Several schedulers like in the former solution but each of them has it’s own runqueue. The problem with this approach is that it can of course happen that you end up with some empty and some full queues because of the different runtime of the processes. So they build something called migration logic that is controlling and balancing the different runqueues.

   They migration logic does:

   • collect statistics about the maxlength of all scheduler’s runqueues
   • setup migration paths
   • Take away jobs from full-load schedulers and pushing jobs on low load scheduler queues

   Running on full load or not! If all schedulers are not fully loaded, jobs will be migrated to schedulers with lower id’s and thus making some schedulers inactive.

   This makes perfectly sense because the more schedulers and runqueues you need the more migrating has to be done. Using SMP support with many schedulers makes only sense if you’re really optimizing for many cores and you will have decreased performance on systems with few cores.

3. Binding schedulers to CPU’s is really worth looking at it. The more cores your CPU has the more important it’ll be and the more performance improvement you’ll gain. You can force the erlang VM to do scheduler binding by:
   erl +sbt db
erlang:system_flag(scheduler_bind_type,default_bind).1>erlang:system_info(cpu_topology).
[{processor,[{core,{logical,0}},
{core,{logical,3}},
{core,{logical,1}},
{core,{logical,2}}]}]
2> erlang:system_info(scheduler_bindings).
{unbound,unbound,unbound,unbound}
fabrizio@machine:~$ erl +sbt db
1> erlang:system_info(scheduler_bindings).
{0,1,3,2}

Source: presentation Kenneth Lundin – Erlang-Factory

You can test and benchmark SMP using following flags:
fabrizio@machine:~$ erl -smp disable       //default is auto
fabrizio@machine:~$ erl +S 2:4               //Number of Schedulers : Schedulers online

With erlang:system_info/1 you can use the following atoms

# cpu_topology
# multi_scheduling
# scheduler_bind_type
scheduler_bindings
logical_processors
multi_scheduling_blockers
scheduler_id
schedulers
# schedulers_online
smp_support

The ones marked with # can be set using system_flag/2

Buschfunk, die Möglichkeit die Statusnachrichten (”Ist gerade…”) deiner Freunde auf unseren VZ’s anzuzeigen, ist nun/nur der Beginn der VZ Feeds. Letzlich ist der Buschfunk nur die Zusammenführung aller Statusnachrichten deiner Freunde auf der Startseite.

Nach dem Launch der ersten Version des Buschfunks, gab es bereits wenige Minuten später einen riesigen Impakt auf unserer Serverfarm. Dies führte dazu, dass wir bereits nach einem Tag die Statusnachrichtendatenbank auf eigene Server umziehen mussten. Ihr seht hier die absolute Anzahl von Statusaktualisierungen pro Minute (getrennt nach studiVZ/meinVZ = blau/flacher Graph und schuelerVZ = rot/steiler Graph):

Man kann Feeds, also Mitteilungen über Statusaktualisierungen eines Freundes, unterschiedlich implementieren und stellt sich dabei einigen Herausforderungen, gerade wenn es nicht nur um die optimale Speicherung, sondern auch um performante Zugriffe und logisches Zusammenführen von ähnlichen Feedeinträgen geht.

Wir haben uns für erste Tests in Richtung Social-Feeds für eine reine Memcache-Implementierung entschieden. Man hat den Vorteil, dass man die ohnehin nur momentan interessanten Posts von Usern nicht in der Datenbank vorhalten muss und Memcacheoperationen dazu noch um einiges schneller sind. Für einen Feed baut man sich im einfachsten Fall eine Queue pro User mit sortierten Einträgen auf, die man als Entity im Memcache ablegt. Da man nicht unendlich viele Einträge vorhalten muss und ein Memcacheobjekt per default eh nur 1 MB pro Eintrag groß sein darf, limitiert man die Queue auf eine feste Anzahl und wirft bei einem neuen Eintrag einfach alte Einträge weg.

Ok, genug der Einleitung, kommen wir zu ein paar Codeschnippseln. Am besten baut man sich ein Interface, welches sich um das Handling von Feedeinträgen kümmert:

1
2
3
4
5
6
7
8
9
10
11
12
13
14

interface FeedEntry {
 
//referenziertes Memcacheobject, also eigentlicher Inhalt
public function getFeedEntryReference(...);
 
//ist der Eintrag sichtbar -> Privacy
public function isFeedEntryHidden(...);
 
//initialer Aufbau
public function initializeFeedEntry(...);
 
[...]
 
}

Jetzt haben wir einen beliebig erweiterbaren Feed Typen und können mit Implementierungen, wie zum Beispiel Statusänderungen von Nutzerprofilen, Microblogeinträgen etc, beginnen.

Was man jetzt noch braucht, ist das eigentliche Aufbauen der Queue, also Füllen des Feeds mit Feed Typen. Man sollte sich überlegen, woraus ein Eintrag innerhalb der Queue aussehen soll. Es sollte die id des Users, einen Zeitstempel, sowie den eigentlichen Inhalt enthalten. Wir haben uns dafür entschieden, den Inhalt des Eintrages nur als Referenz in der Queue zu halten, damit bei Änderungen nicht jedes Queueobjekt, sondern lediglich das referenzierte Memcacheobjekt geändert werden muss. Ausserdem will man die Daten nicht doppelt im Speicher halten.

Beispielhaft könnte eine vereinfachte Queue folgendermaßen aussehen:

1
2
3
4
5

$queue = array(
0 => array ('timestamp' => time(), 'userId' => 123456789, 'contentId' => 1000, 'type' => TYPE_MICROBLOG),
1 => array ('timestamp' => time(), 'userId' => 1234567910, 'contentId' => 1001, 'type'  => TYPE_PHOTOCOMMENT)
[...]
);

Mit Hilfe des Typs und dessen konkreter Implementierung eines Feed Entries kann nun der eigentliche Inhalt aus einem weiteren Memcacheobjekt oder aus der Datenbank geholt werden. Sortiert ist die Queue bereits nach dem Einfügen eines neuen Entries. Wird nun der Content hinter einer solchen Referenz gelöscht, so braucht man die Queues der User, dessen Feeds beeinflusst werden, nicht updaten, da der Feed beim Einlesen automatisch merkt, dass die Referenz nicht mehr gültig ist und diese “überspringt”.

Für’s Aufbauen der Queue noch ein Tipp: Verwendet lieber mehrmaliges array_reverse im Zusammenhang mit array_push, anstatt ein array_shift! Das ist um Welten schneller, wenn man ein Element vorn ranhängt bzw. hinten anfügt.

(Quelle: http://www.ingo-schramm.de/blog/archives/9-PHP-array_shift-does-not-scale.html)

Da der Memcache, wenn der ihm zugewiesene Speicher vollläuft, wenig frequentierte Bereiche freigibt, muss man sich zwangsweise überlegen, wie man mit Datenverlusten innerhalb der Queue umgeht. Dazu könnte man zyklische Backups der Queueeinträge oder ein initiales Befüllen der Feedeinträge implementieren (im Interface bereits vorgesehen). Die eigentlichen Daten (bsp. das konkrete Statusupdate) bleiben natürlich erhalten und liegen in der Datenbank persistent vor, es geht hierbei nur um die Referenzen auf diese Einträge.

I made a little benchmark to check out the new Erlang Release R13A and the behavior of the multiple run queues. The benchmarking program was the same I used in another benchmark you may find here. You may also find the sources at that location. As already noted there the slope from 1 CPU to 2 CPUs is due to the “bad” implementation made to challange the Erlang SMP features. The mashine was an 8 core Intel Xeon 3 GHz with a 64bit 2.6.9 Linux, Erlang kernel polling active.

Data structures and collections are one of the most wanted features for the Standard PHP Library SPL over the last few years. With PHP 5.3 we’ll finally get a little of what we want and this is good news. With data structures like stack,  queue, heap or priority queue implemented in C we expect PHP programming to become somewhat more efficient.

Inspired by this post http://blueparabola.com/blog/spl-deserves-some-reiteration we decided to run our own benchmarks to either verify or disapprove the results posted. Our benchmarks were executed on a 64bit RHEL with PHP 5.3.0beta1. As you may expect, we carefully excluded startup or compilation time and measured only the code blocks in question. We used getrusage() to determine CPU time consumption. A huge number of iterations guaranteed smooth results.

The first structure under consideration was the SplFixedArray. If you only need numerical indices you now can create an array of fixed size that does not have to grow while more and more items are inserted. Dealing with an SplFixedArray saves you about 10 percent of runtime compared to a plain old PHP array.

Next we tried the SplStack and SplQueue. It is usually easy to implement a stack and a queue with plain arrays. Using array_push(), array_pop() and array_shift() is straightforward. It may be a surprise to the average PHP programmer to learn about the runtime behaviour of these functions. Worst is array_shift() because of the internal rehashing and the experienced PHP programmer may – for critical code at least – try to access arrays by indices maintaining counters, for example. This is much more efficient. Compared to the functions, at least SplQueue is something like an upset, but it is possible to find comparable solutions with plain PHP.

There is a little danger to compare apples and pears when turning towards SplHeap and SplPriorityQueue. What is the proper representation of a heap implemented using plain old arrays only? It’s a sorted array, ok. But a heap is sorted for each insert, so, do we really have to sort the array for each insert? Who will do this in real life?

It’s the use case that decides about the sorting strategy. If you are supposed to carefully separate writing the heap and reading from it, it is sufficient to sort it once. That way you beat SPL. But if you have to mix reading and writing arbitrarily the SPL will beat plain arrays by far. This is shown in the pictures below. For the mixed strategy we read once for 5 inserts and the SplMinHeap scales very well. The same holds for SplMaxHeap and SplPriorityQueue.

Lessons learned:

• SPL rules
• use SPL data structures where appropriate for a particular use case, they are efficient and comfortable
• benchmarking is error prone
• anyway, always benchmark performance critical code blocks

Als MySQL Datenbankadministrator ist man täglich damit beschäftigt, unzählige Datenbank-Server am Laufen zu halten. Hier eine Auswahl an Werkzeugen, die man unbedingt in der täglichen Arbeit braucht:

• myTop
• show innodb status
• DSH (Distributed SSH Shell)
• Maatkit (http://www.maatkit.org/)

Aus Maatkit eignet sich mk-query-digest besonders gut, um ein System nach einem Neustart der Datenbank “aufzuwärmen”.

mk-query-digest --processlist h=d-mm-05-1-svz --execute h=d-mm-05-2-svz \
   --filter '$event->{fingerprint} =~ m/^select/

Außerdem kann man damit sehr elegant an einem Zweitsystem verschiedene Dinge testen und die Auswirkungen direkt beobachten.
Es bietet sich dazu an, dass man sein System damit immer genau im Blick hat:

• Ganglia (Distributiertes Grid Monitoring)

Ganglia ist eine Allzweckwaffe, um ein Gefühl dafür zu bekommen, wie eine Datenbank “lebt”. Es visualisiert quasi den Herzschlag des Systems. Durch gmetric bekommt man zudem die Möglichkeit mit wenig Aufwand alle möglichen Parameter vom System oder der Datenbank an Ganglia zu übergeben und damit zu visualisieren. Basics dabei sind die Queries per Second, Slave Lag und Slow Queries per Second.

• iostat -x

Was ist auf meinen Platten los? Wie verteilt sich das await auf die einzelnen Devices? Viel sieht man damit leider nicht, aber es gibt deswegen Erweiterungen für MySQL, die das IO bis auf Tabellen und Indizes runterbrechen können.

• Nagios – damit man den Fehler auch mitbekommt

Kristian Köhntopp hat dafür was Nettes gebaut. Man braucht an der Stelle also nicht mehr ganz so viel tun.

Nicht zu vergessen der Kommandozeilenclient mysql mit einem ordentlichen Prompt, damit man nicht bei mehreren Maschinen durcheinander kommt:

[mysql]
prompt = \u@hostname[\d]>\_

Percona ist ein Consultingunternehmen für MySQL und hilft als remote DBA, bei Architekturplanungen, Trouble Shooting und Database Recovery. Percona wurde 2006 von Peter Zaitsev und Vadim Tkachenko gegründet.

Seit einiger Zeit nutzen wir auf unserer Plattform die MySQL-Version von Percona, weil es unheimlich praktische Patches gibt, die uns als DBA das Leben erleichtern.

• Session status to check fragmentation of the last InnoDB scan
• SHOW USER/TABLE/INDEX statistics
• SHOW PATCHES
• Adds additional information of InnoDB internal hash table memories in SHOW INNODB STATUS
• Information schema table of InnoDB IO counts for each datafile pages
• Adds INFOMATION_SCHEMA.PROCESSLIST with TIME_MS column
• Add locks held, remove locked records in SHOW INNODB STATUS
• Extended statistics in slow.log
• Patch allows redirect output of error.log to syslog-ng
• Information of fsync callers in InnoDB
• Show innodb buffer pool content

Mit show index_statistics sieht man z.B. sehr gut, wieviele Rows durch welchen Index gelesen wurden. Ideal, um nicht benutzte Indizes aufzuspüren.
Natürlich will man auch wissen, wie sich die IO auf einzelne Tabellen und Indizes verteilt. Dafür gibt es dann im Information-Schema die Tabelle INNODB_IO_PATTERN:

$ describe INNODB_IO_PATTERN;
+------------+-------------+------+-----+---------+-------+
| Field      | Type        | Null | Key | Default | Extra |
+------------+-------------+------+-----+---------+-------+
| SPACE      | bigint(11)  | NO   |     | 0       |       |
| OFFSET     | bigint(11)  | NO   |     | 0       |       |
| INDEX_ID   | bigint(11)  | NO   |     | 0       |       |
| TABLE_NAME | varchar(32) | NO   |     | NULL    |       |
| INDEX_NAME | varchar(32) | NO   |     | NULL    |       |
| N_READ     | bigint(11)  | NO   |     | 0       |       |
| N_WRITE    | bigint(11)  | NO   |     | 0       |       |
+------------+-------------+------+-----+---------+-------+
7 rows in set (0.01 sec)
 

Bevor man Auswertungen starten kann, muss MySQL erstmal Daten sammeln:

$ set global innodb_io_pattern_trace = 1;
$ set global innodb_io_pattern_trace_running = 1;
$ set global innodb_io_pattern_trace_size_limit = 1;
-- Anzahl der Pages die gesammelt werden sollen

Man muss auch unbedingt darauf achten, dass man genug freien Hauptspeicher hat, bevor man das Tracing startet.
Auswertung des IO für jeden Index, getrennt nach Read und Write:

$ select sum(i.n_read) n_read, sum(i.n_write) n_write, index_name, table_name from information_schema.innodb_io_pattern i group by index_id

Dokumenation, Sourcen und Binaries finden sich im Wiki von Percona. Großes Lob also an die verschiedenen Entwickler, die dafür sorgen, dass auch die Datenbanken bei studiVZ unheimlich gut performen. Hier aus unserem Grid Monitoring die aggregierte Datenbanklast in Queries pro Sekunden:

Morgen früh (Dienstag, den 10.02.09) gehen wir mit meinVZ, studiVZ und schülerVZ von 01.00 bis ca. 08.00 Uhr offline aufgrund von Wartungsarbeiten an den Datenbanken.

Unter anderem sind wir dabei die Datensätze der Gruppenmitgliedschaften zu partitionieren, die vorher zusammen gespeichert waren. Es gibt von Flickr eine Präsentation über das Data Sharding die ziemlich gut beschreibt, was wir machen werden. Außerdem geht nach tagelanger Arbeit unser neuer LVS/ Heartbeat 2-Cluster mit einer neuen Version online. Mit dem LVS läuft im Backend die komplette Lastverteilung auf die Systeme, dank Direct Server Routing hält sich der Durchsatz auch in Grenzen, da nur die eingehenden Frames durch das System müssen.

Mehr dazu demnächst in einem anderem Blog-Post.

P.S. Der/das Blog bleibt online.

Everybody knows Apache and Tomcat but when I try to talk about such strange things like Yaws or Mochiweb nobody knows what I actually want. These two are HTTP server implementations written in the old fashioned functional language Erlang and running on the famous Open Telecom Platform or OTP. Erlang/OTP was developed in the late 80s as a fault tolerant and highly scalable system for telecom applications. Nowadays in the social networking community it is daily business to serve some 10.000s of PHP requests per second. So we are facing problems telcos have for a long time.

Apache is the canonical web server to serve PHP to the world. Thinking about technological alternatives in the backend domain we have a look at both Java and Erlang. A rather quick and easy test to compare the scalability of the technologies was to setup web servers delivering the same static document. The image below shows the results.

Apache and Tomcat scale nearly linearly up to a concurrency of 1000. We find that Mochiweb has a breakdown when concurrency reaches 300 but afterwards still scales linearly as Yaws does at a lower level. Absolute performance is less interesting here. What counts is the scaling behavior. Mochiweb for example is not designed first hand to deliver static content but to act as a HTTP endpoint for arbitrary OTP applications. Neither Yaws nor Mochiweb seem to cache documents in the default setup. Also, we did not use HiPE.

Unfortunally we had not yet the chance to verify the measurements given in this post: http://www.sics.se/~joe/apachevsyaws.html where Yaws still scales linearly (in the average) when Apache has long gone away, at concurrency of 50.000 or even 80.000 and clearly seems to survive DDoS attacks.

In this picture Erlang/OTP may not be a recommendation for classical web delivery but to build reliable services either to provide internal or external API endpoints. An interesing alternative at least.