Arkiv för October, 2010

A readonly array is not exacly read-only

Every now and then I come across developers that does not quite get their heads around the meaning of the readonly keyword in C#, and perhaps especially when combined with arrays. Since I like to exemplify with code, let’s start in that end:

class Numbers
{
    public readonly List<int> OneThroughFour = new List<int>{ 1, 2, 3, 4 };
}

class Program
{
    static void Main(string[] args)
    {
        Numbers numbers = new Numbers();
        numbers.OneThroughFour[3] = 42;
        Console.WriteLine(string.Join(", ", numbers.OneThroughFour));
    }
}

This will print "1, 2, 3, 42", which seems confusing for some. If readonly does not make the list read-only, what does it do? The documentation for the readonly keyword says the following:

The readonly keyword is a modifier that you can use on fields. Whena field declaration includes a readonly modifier, assignments to the fields introduced by the declaration can only occur as part of the declaration or in a constructor in the same class.

It clearly says that assignments to the field can only occur during the construction of the class. In our code sample above we assign a value to the list (numbers[3] = 42;). Is that not an assignment to the field? No, it is an assignment to a property in the object that the field holds a reference to, it is not an assignment to the field itself. If we would try to replace the list with another list, the compiler would give us an error:

// the following line gives the compilation error "A readonly
// field cannot be assigned to (except in a static constructor
// or a variable initializer)"
numbers.OneThroughFour = new List<int> { 1, 2, 3, 42 };

OK, but what if the field is an array?

class Numbers
{
    public readonly int[] OneThroughFour = new[] { 1, 2, 3, 4 };
}

class Program
{
    static void Main(string[] args)
    {
        Numbers numbers = new Numbers();
        numbers.OneThroughFour[3] = 42;
        Console.WriteLine(string.Join(",", numbers.OneThroughFour));
    }
}

The result of this code is exactly the same as in the previous example ("1, 2, 3, 42"). Again, we are not assigning a value to the field, but to an element of the array that the field holds a reference to. Now I can hear somebody say “but hey, wait a minute… isn’t int a value type? So the field should hold a copy of the data rather than a reference to it, right?” Yes, int is a value type, but in .NET all arrays are reference types. This means that any code that obtains a reference to the array can also alter its elements. Again, the readonly keyword only prevents the array object itself from being replaced by another array object.

But what if I really want the list read-only?

The first step you should take is to make sure not to expose the field itself outside the type in which it is declared. That way you gain control over what code that can access (and thus modify) the contents of the array directly. The second step is to show intent. Expose the array in a manner that communicates that it should be regarded as being readonly, by returning it as an IEnumerable<int> rather than int[]:

class Numbers
{
    private readonly int[] oneThroughFour = new[] { 1, 2, 3, 4 };

    public IEnumerable<int> GetOneThroughFour()
    {
        return oneThroughFour;
    }
}

This will make any attempt to assign a value to an element (such as numbers.GetOneThroughFour()[3] = 42;) result in a compiler error, since IEnumerable<T> does not support accessing elements by index. This clearly tells developers writing calling code to regard the returned list as a read-only list. However, there is nothing that prevents calling code from manipulating the internal array, using a simple type cast:

((int[])numbers.GetOneThroughFour())[3] = 42;

For most common uses, I would say this is sufficient (unless the type is exposed in some commercial class library or similar); at this point we quite effectively prevent developers from accidentally writing code that modifies the list.

If it is critical that you prevent modification of the list on a technical level, there are some different approaches:

Use a ReadOnlyCollection<T> for storing the list:

class Numbers
{
    private readonly ReadOnlyCollection<int>
    oneThroughFour = new ReadOnlyCollection<int>(new[] { 1, 2, 3, 4 });

    public IEnumerable<int> GetOneThroughFour()
    {
        return oneThroughFour;
    }
}

Store the list as an array, but return a copy of the array:

class Numbers
{
    private readonly int[] oneThroughFour = new[] { 1, 2, 3, 4 };

    public IEnumerable<int> GetOneThroughFour()
    {
        return (IEnumerable<int>)oneThroughFour.Clone();
    }
}

Yet another option is to store the list as an array, but use yield return for returning the items. This might be preferable if the list is potentially large:

class Numbers
{
    private readonly int[] oneThroughFour = new[] { 1, 2, 3, 4 };

    public IEnumerable<int> GetOneThroughFour()
    {
        int index = 0;
        while (index < oneThroughFour.Length)
        {
            yield return oneThroughFour[index++];
        }
    }
}

This will throw an InvalidCastException if calling code attempts to cast the return value to int[].

/Fredrik Mörk

Hur löser vi C10K-problemet?

Det så kallade C10K-problemet, ett för många relativt nytt begrepp, beskrivs enligt Wikipedia på följande sätt:

The C10k problem[1] is the numeronym given to a limitation that most web servers currently have which limits the web server’s capabilities to only handle about ten thousand simultaneous connections. This limitation is partly due to operating system constraints and software limitations.

Det här är ett problem som knappt existerade för inte allt för länge sedan, men i takt med Facebook, Twitter och andra tjänster med krav på extremt hög skalbarhet har ökat i popularitet så har även C10K-problemet blivit mer relevant (en annan term man brukar höra i det här sammanhanget är web scale).

Grundproblemet är alltså att de flesta av dagens web-servrar inte är designade för att hantera ett stort antal samtidiga användare (klienter).

För att förstå varför detta blir ett problem tänkte jag börja med att kort beskriva tre olika tekniker som web-servar kan använda sig av för just hanteringen av flera klienter.

1. “En klient i taget”

Den naiva lösningen är att helt enkelt ta hand om en klient åt gången. Om flera klienter anropar servern samtidigt så köar man upp dem och tar dem i turordning.

Med pseudo-kod kan det beskrivas så här:

while(true) {
    waitForClient() {
        handleClient()
    }
}

Anropet waitForClient() läser lämpligen av en kö med väntande klient-anrop. Så fort det finns ett klient-anrop hanterar man det i handleClient(), och därefter tar man nästa klient.

Nackdelarna med det här angreppssättet är ganska uppenbara, om servern har många köande anrop kommer det ta väldigt lång tid innan ett nyinkommet anrop tas om hand. Tex, om varje anrop till handleClient() tar 1 sek, och det finns 9 väntande anrop i kön så kommer man som ny klient behöva vänta runt 10sek innan man får svar från servern. Inte direkt en skalbar lösning, här kommer man stöta på problem långt innan 10.000 anrop.

2. “Trådad server”

För att försöka komma ifrån ovanstående problem kan man tänka sig lösning där hanteringen av ett nytt klient-anrop tas om hand i en egen tråd.

Pseudo-kod:

while(true) {
    waitForClient() {
        Thread t = new Thread()
        t.handleClientRequest()
    }
}

Här skapas alltså en ny tråd upp för varje anrop, och sedan hanteras respektive klient i sin “egen” tråd. Fördelen med detta är att man inte “blockar” för varje klient, och en ny klient behöver inte vänta på att alla tidigare anrop ska bli klara först. Tyvärr finns det andra nackdelar med den här lösningen:

  • För det första är uppskapandet av trådar relativt dyrt/långsamt, och mycket tid kommer gå åt bara till det.
  • Förutom det tillkommer en hel del overhead av att växla mellan de olika trådarna som ska köras (detta brukar kallas “context-switch”). I takt med att antalet trådar blir fler och fler, kommer tiden för “context-switching” öka, tillslut kommer servern i princip vara upptagen med att bara sköta den här växlingen mellan trådar.

Även om det här är en mycket bättre lösning än den som presenterades ovan, så löser den tyvärr inte C10K-problemet.

3. “Trådpoolad server”

En mycket vanlig lösning för att komma bort från problemet ovan är att man redan från start bestämmer sig för hur många klienter man maximalt ska kunna hantera. Man kan då se till att skapa upp alla trådar som behövs direkt, och sedan får servern “hämta” trådar från en tråd-pool istället för att skapa upp nya själv.

Pseudo-kod:

while(true) {
    waitForClient() {
        Thread t = getThreadFromPool()
        t.handleClientRequest()
        returnToPool(t)
    }
}

Den här approachen är den som används av de flesta web-servrar. Man slipper overheaden med att skapa upp nya trådar, dock kommer man stöta på samma problem med context/thread switching om man satt ett för högt maximalt antal klienter (trådar).

Det här kommer alltså fungera bra så länge vi inte har krav på för många samtidiga klienter. Tyvärr är alltså inte heller detta tillräckligt bra för att lösa C10K-problemet, som var vår utgångspunkt.

“Lösningen”

För att verkligen lösa detta finns en fjärde approach, nämligen vad man kan kalla “Single-trådad asynkron / non-blocking server”.

Grundtanken här är att man precis som i punkt 1 låter servern köra på bara en tråd, men att själva hanteringen av klienter sker icke-blockande / asynkront. På så vis kommer man ifrån det första problemet att varje klient-anrop låser upp servern en viss tid och eftersom man bara använder en tråd så slipper man även undan problemet med tråd-swtichning.

Pseudokod:

while(true) {
    waitForClient() {
        handleClientAsyncronous()
    }
}

Vid första anblick är det väldigt likt lösningen som presenterades i 1. Den stora skillnaden är att hanteringen av varje klient sker asynkront, på så vis kan servern direkt ta hand om nästa anrop. Detta skalar även väldigt bra för fall när man behöver hantera “long-lived connections”, t ex en chat-tjänst, där klienterna hela tiden behöver vara uppkopplade mot chat-servern för att kunna ta emot meddelanden. En server som då använder sig av en tråd-pool kommer begränsa det maximala antalet klienter till tråd-poolens storlek. Ökar man storleken kommer fler klienter kunna vara uppkopplade, men samtidigt kommer overheaden (context-switch) öka.

Men en single-trådad server har man inget max-tak (ingen tråd-pool), och man slipper även undan problemet med ökad overhead för ökat antal klienter.

Deft web server

Det finns sedan tidigare ett antal servrar som använder sig av just en single-trådad lösning, t.ex. Tornado och node.js. Tornado är skriven i Python, och node.js är skriven i C++.

Med det här som bakgrund började jag och en person till (Roger Schildmeijer) undersöka möjligheterna att implementera en motsvarande web-server helt baserad på Java. Detta ledde så småningom fram till open source projektet “Deft“.

Deft är skriven helt i Java och använder sig av java.nio för alla underliggande I/O operationer.
För att kommunicera med servern används HTTP, och hanteringen av HTTP-request bestäms av något som vi kallar RequestHandlers. Deft implementerar en RequestHandler för att leverera statiska filer, t.ex. ett HTTP GET anrop för att hämta en bild.

Användare av Deft kan sedan skriva egna RequestHandlers där de implementerar den logik de själva vill ha.
Se gärna http://deftserver.org för exempel på hur en “HelloWorld”-RequestHandler kan se ut.

Performance

Något som är intressant i sammanhanget är så klart performance, hur många request servern faktiskt klarar av.

Detta avgörs givetvis till stor del av hur tung “logik” som varje request kräver, men för att kunna göra en jämförelse av hur Deft står sig mot Tornado och node.js, har vi implementerat “HelloWorld”-exemplet för de olika tre servarna.

För själva testandet har vi använt Apache HTTP Benchmarking “ab”.

Kommandot som kördes för testet var:

ab -k -c[5, 10, 15, 20, 25] -n800000 http://127.0.0.1:8080/

Grafen nedan visar hur många request per sekund de tre olika servarna klarar.

Deft klarar alltså nästan tre ggr fler req/sek är node.js, och runt nio ggr så mycket som Tornado! Detta var klart bättre siffror än vi vågat hoppas på när vi började utvecklingen av Deft.

Nästa steg i utvecklingen av Deft är bland annat bättre stöd av HTTP 1.1-specen och web socket support.

Utveckling och källkoden kan nås på http://github.com/rschildmeijer/deft.

En “getting-started-guide” finns på http://deftserver.org.

Ladda gärna ner och testa själva, och är det någon som har förslag på en bra logo så mottages tips tacksamt :)

//Jim Petersson

Tillbaka