InfoQ: Panel: Multicore, Manycore, and Cloud Computing

InfoQ: Panel: Multicore, Manycore, and Cloud Computing

Note: Biggest challenges are the correctness and performance of parallel execution.
In term of correctness: false sharing, atomicity, consistency model.
In term of performance: locking, synchronization, deadlock.

Understanding CPU caching and performance

Understanding CPU caching and performance:

Block sizes

In the section on spatial locality I mentioned that storing whole blocks is one way that caches take advantage of spatial locality of reference. Now that we know a little more about how caches are organized internally, we can look a bit closer at the issue of block size. You might think that as cache sizes increase you could take even better advantage of spatial locality by making block sizes even bigger. Surely fetching more bytes per block into the cache would decrease the odds that some part of the working set will be evicted because it resides in a different block. This is true, to some extent, but we have to be careful. If we increase the block size while keeping the cache size the same, then we decrease the number of blocks that the cache can hold. Fewer blocks in the cache means fewer sets, and fewer sets means that collisions and therefore misses are more likely. And of course, with fewer blocks in the cache the likelihood that any particular block that the CPU needs will be available in the cache decreases.

The upshot of all this is that smaller block sizes allow us to exercise more fine-grained control of the cache. We can trace out the boundaries of a working set with a higher resolution by using smaller cache blocks. If our cache blocks are too large, we wind up with a lot of wasted cache space because many of the blocks will contain only a few bytes from the working set while the rest is irrelevant junk. If we think of this issue in terms of cache pollution, we can say that large cache blocks are more prone to pollute the cache with non-reusable data than small cache blocks.

The following image shows the memory map we've been using, with large block sizes.

This next image shows the same map, but with the block sizes decreased. Notice how much more control the smaller blocks allow over cache pollution.

The other problems with large block sizes are bandwidth-related. Since the larger the block size the more data is fetched with each LOAD, large block sizes can really eat up memory bus bandwidth, especially if the miss rate is high. So a system has to have plenty of bandwidth if it's going to make good use of large cache blocks. Otherwise, the increase in bus traffic can increase the amount of time it takes to fetch a cache block from memory, thereby adding latency to the cache.

Write Policies: Write through vs. Write back

So far, this entire article has dealt with only one type of memory traffic: loads, or requests for data from memory. I've only talked about loads because they make up the vast majority of memory traffic. The remainder of memory traffic is made up of stores, which in simple uniprocessor systems are much easier to deal with. In this section, we'll cover how to handle stores in single-processor systems with just an L1 cache. When you throw in more caches and multiple processors, things get more complicated than I want to go into, here.??

Once a retrieved piece of data is modified by the CPU, it must be stored or written back out to main memory so that the rest of the system has access to the most up-to-date version of it. There are two ways to deal with such writes to memory. The first way is to immediately update all the copies of the modified data in each level of the hierarchy to reflect the latest changes. So a piece of modified data would be written to the L1 and main memory so that all of its copies are current. Such a policy for handling writes is called write through, since it writes the modified data through to all levels of the hierarchy.?

A write through policy can be nice for multiprocessor and I/O-intensive system designs, since multiple clients are reading from memory at once and all need the most current data available. However, the multiple updates per write required by this policy can greatly increase memory traffic. For each STORE, the system must update multiple copies of the modified data. If there's a large amount of data that has been modified, then that could eat up quite a bit of memory bandwidth that could be used for the more important LOAD traffic.?

The alternative to write through is write back, and it can potentially result in less memory traffic. With a write back policy, changes propagate down to the lower levels of the hierarchy as cache blocks are evicted from the higher levels. So an updated piece of data in an L1 cache block will not be updated in main memory until it's evicted from the L1.?

Conclusions

There is much, much more that can be said about caching, and this article has covered only the basic concepts. In the next article, we'll look in detail at the caching and memory systems of both the P4 and the G4e. This will provide an opportunity note only to fill in the preceding, general discussion with some real-world specifics, but also to introduce some more advanced caching concepts like data prefetching and cache coherency.????

Bibliography

• David A. Patterson and John L. Hennessy, Computer Architecture: A Quantitative Approach. Second Edition. Morgan Kaufmann Publishers, Inc.: San Francisco, 1996.?
• Dennis C. Lee, Patrick J. Crowley, Jean-Loup Baer, Thomas E. Anderson, and Brian N. Bershad, "Execution Characteristics of Desktop Applications on Windows NT." 1998.http://citeseer.nj.nec.com/lee98execution.html
• Institute for System-Level Integration, "Chapter 5: The Memory Hierarchy."?
• Manish J. Bhatt, "Locality of Reference." Proceedings of the 4th Pattern Languages of Programming Conference. 1997. http://st-www.cs.uiuc.edu/users/hanmer/PLoP-97/
• James R. Goodman, "Using Cache Memory to Reduce Processor-Memory Traffic." 25 Years ISCA: Retrospectives and Reprints 1998: 255-262
• Luiz Andre Barroso, Kourosh Gharachorloo, and Edouard Bugnion, "Memory System Characterization of Commercial Workloads." Proceedings of the 25th International Symposium on Computer Architecture. June 1998.

Revision History

How to Write High-Performance C# Code

http://dotnet.sys-con.com/node/46342
Writing code that runs quickly is sometimes at odds with writing code quickly. C.A.R. Hoare, computer science luminary and discoverer of the QuickSort algorithm, famously proclaimed, "Premature optimization is the root of all evil." The extreme programming design principle of "You Aren't Gonna Need It" (YAGNI) argues against implementing any features, including performance optimizations, until they're needed.
Writing unnecessary code is undoubtedly bad for work efficiency. However, it's important to realize that different situations have different needs. Code for vehicular real-time control systems has inherent up-front responsibilities for stability and performance that aren't present in, say, a small one-off departmental application. Therefore, it's more important in such code to optimize early and often.
Performance tuning for real-world applications often involves activities geared towards finding bottlenecks: in code, in the network transport layer, and at transaction boundaries. However, these techniques alone cannot solve the dreaded problem of uniformly slow code, which surfaces when large bottlenecks have been resolved but the code still exhibits inadequate performance. This is code that has been written without attention to correct usage, often by junior programmers, in the same style across whole modules or applications. Unfortunately, the best solution for this problem is to make sure that all programmers on a project follow correct coding practice when writing the code the first time; coding guidelines and good shared libraries help enormously.
This article presents helpful tips for writing in-process .NET managed code that performs well. It's assumed that basic programming skills such as factoring control structures, pulling work outside of loops whenever possible, caching variables for reuse, use of the switch statement, and the like are known to the average reader.
All code examples referred to in this article can be downloaded from the .NET Developer's Journal Web site, at www.sys-con.com/dotnet/sourcec.cfm. The code comes with a Windows Forms application that can be used to easily view the code and run all the tests on your own machine. You'll need the .NET Runtime 1.1 to run the code.
Tools
While testing tools such as NUnit and the upcoming VS.NET 2005 Team System can help you find bottlenecks, when tuning small sections of code, there's still no substitute for the micro-benchmark. This is because most generic testing frameworks depend on things like delegates, attributes, and/or interface method calls to do testing, and the code usually is not written with benchmarking primarily in mind. This can be very significant if you're interested in measuring the execution time of a batch of code down to the microsecond or even nanosecond level.
A micro-benchmark consists of a tight loop isolating the code that's being tested for performance, with a time reading before and after. When the test has finished, the start time is subtracted from the end time, and this duration is divided by the number of iterations to get the per-iteration time cost. The following code shows a simple micro-benchmark construct:

int loopCount = 1000000000;
long startTime, endTime;
double nanoseconds;

startTime = DateTime.Now.Ticks * 100;
for(int x = 0; x < loopCount; x++) {
    // put the code to be tested here
}
endTime = DateTime.Now.Ticks * 100;
nanoseconds = ((double)(endTime - startTime)) / ((double)loopCount);
Console.WriteLine(nanoseconds.ToString("F") + " ns per operation");

When performing a simple micro-benchmark, it's important to remember a couple of things. First, small fluctuations (noise) are normal, so to obtain the most accurate results, each test should be run several times. In particular, the first set of tests executed after program initialization may be skewed due to the lazy acquisition of resources by the .NET runtime. Also, if your results are very inconsistent, you may not have penetrated the "noise floor" of the measurement. The best solution for this is to increase the number of loops and/or tests. Another thing to remember is that looping itself introduces overhead, and for the most accurate readings, you should subtract this from the result. On a P4-M 2-GHz laptop, the per-loop overhead for a for loop with an int counter in release mode is around 1 nanosecond.
I'd never advocate running each code fragment from a long program through micro-benchmarks, but benchmarking is a good way to become familiar with the relative costs of different types of expressions. True knowledge of the performance of your code is built on actual observations. As time goes on, you'll find yourself needing such tests less and less, and you'll keep track in the back of your head of the relative performance of the statements you're writing.
Another important tool is ildasm.exe, the IL disassembler. With it, you can inspect the IL of your release builds to see if your assumptions are correct about what's going on under the covers. IL is not hard to read for a person familiar with the .NET framework; if you're interested in learning more, I suggest starting with Serge Lidin's book on the subject.
A great free tool for decompiling IL to C# or VB source, Reflector, is found at www.aisto.com/roeder/dotnet/; it's incredibly useful for viewing code that ships with the .NET Framework, for those of you less familiar with IL.
The CLR Profiler, available as a free download from Microsoft's Web site, allows you to track memory allocation and garbage collection activity, among other useful features. Also, the MSDN Web site has excellent coverage of performance metrics tools such as WMI and performance counters.
Working with Objects and Value Types
Objects: A Double Whammy
Objects are expensive to use, partly because of the overhead involved in allocating memory from the heap (which is actually well-optimized in .NET) and partly because every created object must eventually be destroyed. The destruction of an object may take longer than its creation and initialization, especially if the class contains a custom finalization routine. Also, the garbage collector runs in an indeterministic way; there's no guarantee that an object's memory will be immediately reclaimed when it goes out of scope, and until it's collected, this wasted memory can adversely affect performance.
The Garbage Collector in a Nutshell
It's necessary to understand garbage collection to appreciate the full impact of using objects. The single most important fact to know about the garbage collector is that it divides objects into three "generations": 0, 1, and 2. Every object starts out in generation 0; if it survives (if at least one reference is maintained) long enough, it goes to 1; much later, it transitions to 2. The cost of collecting an object increases with each generation. For this reason, it's important to avoid creating unnecessary objects, and to destroy each reference as quickly as possible. The objects that are left will often be long-lived and won't be destroyed until application shutdown.
Lazy Instantiation/Initialization
The Singleton design pattern is often used to provide a single global instance of a class. Sometimes it's the case that a particular singleton won't be needed during an application run. It's generally good practice to delay the creation of any object until it's needed, unless there's a specific need to the contrary - for instance, to pre-cache slow-initializing objects such as database connections. The "double-checked locking" pattern is useful in these situations, as a way to avoid synchronization and still ensure that a needed action is only performed once. Lazy initialization is a technique that can enhance the performance of an entire application through object reduction.
Avoiding Use of Class Destructors
Class destructors (implemented as the Finalize() method in VB.NET) cause extra overhead for the garbage collector, because it must track which objects have been finalized before their memory can be reclaimed. I've never had a need for finalizers in a purely managed application.
Casting and Boxing/Unboxing Overhead
Casting is the dynamic conversion of a type at runtime to another, and boxing is the creation of a reference wrapper for a value type (unboxing being the conversion back to the wrapped value type). The overhead of both is most heavily felt in collections classes, as they all - with the exception of certain specialized ones like StringDictionary - store each value as an Object. For instance, when you store an Int32 in an ArrayList, it is first boxed (wrapped in an object) when it is inserted; each time the value is read, it is unboxed before it is returned to the calling code.
This will be fixed in the next version of .NET with the introduction of generics, but for now you can avoid it by creating strongly typed collections and by typing variables and parameters as strongly as possible. If you're unsure about whether or not boxing/unboxing is taking place, you can check the IL of your code for appearances of the box and unbox keywords.
Trusting the Garbage Collector
Programmers new to .NET sometimes worry about memory allocation to the point that they explicitly invoke System.GC.Collect(). Garbage collection is a fairly expensive process, and it usually works best when left to its own devices. The .NET garbage collection scheme can intentionally delay reclamation of objects until memory is available, and in particular longer-lived objects (those that make it to generation 1 or 2) may not be reclaimed for an extended period. Even a simple "Hello, world!" console application may allocate 15 MB or more of memory for its "working set." My advice: don't call GC.Collect() unless you really know what you're doing.
Properties, Methods, and Delegates
Avoiding Overuse of Property Getters and Setters
Most people don't realize that property getters and setters are similar to methods when it comes to overhead; it's mainly syntax that differentiates them. A non-virtual property getter or setter that contains no instructions other than the field access will be inlined by the compiler, but in many other cases, this isn't possible. You should carefully consider your use of properties; from inside a class, access fields directly (if possible), and never blindly call properties repeatedly without storing the value in a variable. All that said, this doesn't mean that you should use public fields! Example 1 demonstrates the performance of properties and field access in several common situations.
About Delegates
Delegates are slower to execute than interface methods. Delegates are often used to introduce a level of indirection in code, but in almost all cases interfaces allow a cleaner design. Of course, it's impossible to completely shun delegates; the entire event-handling paradigm in .NET is based on them. Example 2 compares the performance of delegates and direct method calls.
Minimizing Method Calls
The .NET compiler is capable of performing many optimizations for release builds. One of them is called "method inlining." If method A calls method B and certain other conditions are met, such as the code in method B being small enough, the code from B will be copied into A during compilation. However, .NET won't or can't inline certain types of methods, such as virtual methods or methods over a certain size. Each method invocation/property access entails significant overhead, such as the allocation of a stack frame, etc. Of course, you should never repeatedly call a method for the same result on purpose, but you should also be mindful of the impact of method calls in general.

Using the 'Sealed' Keyword
Wherever extensibility is not required, you should use the sealed keyword. This makes your design easier to understand, as someone can tell at a glance if a certain class or method isn't meant to be extended or overridden. It also increases the chances that the compiler will inline code.
Working with Collections
Avoid Overuse of Collections
This might sound strange, but I'm not advocating working without data structures. The fact is, I've seen collections used many times when they don't actually simplify the code or provide any benefit at all. The single biggest avoidable use of collections is the use of an ArrayList when a simple array would suffice. It should be obvious that there's no way that calling a collection method - which may do significant work under the covers - can compare to something as simple as an array access for performance. See Example 3 for more information.
for vs foreach
The rumor abounds that the foreach loop is bad for performance. The truth is actually a little more complicated. Basically, foreach involves no performance penalty when used against arrays. However, when used against lists it involves the same overhead as creating an enumerator and using it within a try/catch block! Ildasm.exe may come in handy here to see what's going on. This isn't a complete killer, but if you do enough list access you may want to avoid it. Example 4 compares the two statements for access against an array and an ArrayList.
Enumerators: Don't Go Overboard
Just because the possibility exists for the enumerating of a collection doesn't mean you have to do it. For instance, the ArrayList class is useful as an array replacement; one of its best features is indexed element access. By using an enumerator with ArrayList, you hide its most useful features and introduce needless overhead. Example 5 shows the performance difference between indexed access and the use of an enumerator.
Avoid Overuse of Collection Wrappers
A peek at the code in classes such as ArrayList shows that, to implement synchronized, fixed-size, and read-only versions of these, methods such as Synchronized() actually create a new wrapper list around the original one (this scheme was copied from Java). While this is nice from certain design standpoints, it degrades performance; the method-call overhead for each operation is multiplied. For a fixed-size, synchronized ArrayList, this overhead is tripled! Chances are, if you're working with a collection and need synchronization, the code using the collection is already synchronized. In any case, simply locking on the collection itself around every access turns out to be faster than using a synchronized wrapper. Example 6 compares the use of a synchronized ArrayList with synchronizing access to an ArrayList.
Working With Strings
Don't Use String.Format() to Concatenate Strings
While string-formatting routines built into .NET are very useful for globalization and other tasks, they're not meant to be used for appending strings to each other. Example 7 tests the performance difference between String.Format() and string concatenation.
Use StringBuilder to Build Strings Inside Loops
The StringBuilder class is basically an array list for string fragments; the StringBuilder takes care of expanding its internal char array, hiding this from the user. The use of this class is also specially optimized by the .NET compiler, making it impossible to duplicate this functionality with equivalent performance (for instance, by manipulating char arrays directly and converting to a string afterwards). Example 8 shows the performance benefit of building a large string using StringBuilder instead of string concatenation.
Don't Use StringBuilder to Concatenate Small Numbers of Strings
Many .NET developers who consider themselves well-versed in performance matters advocate the use of the StringBuilder class whenever possible. However, it's not the fastest approach for concatenating small numbers of strings. Actually, any number can be combined in a single statement, although the performance benefit tends to dwindle above five or six substrings. This is due to instantiation and destruction overhead for the StringBuilder instance, as well as method-call overhead involved in calling Append() once for every added substring and ToString() once the string is built. What are the alternatives? Plus-sign concatenation and the String.Concat() method are equivalent; I prefer plus signs for readability. Note that this cannot be used across loops because the entire concatenation must occur within a single statement. Example 9 tests String.Concat() vs. StringBuilder for various numbers of substrings.
Don't Be Afraid to Use String Literals
Many developers incorrectly assume that a new object is created for every string literal, and, therefore, avoid their use. In some cases, using string literals directly in your code is a better approach than using string constants! It can make the code easier to understand and has no adverse impact on performance. This is due to the use of the .NET interned string table; this table maintains a String instance for every known string and reuses this instance whenever the same character sequence is used as a literal. See the documentation of the String.Intern() method for more details. Example 10 compares string literals to the use of string constants.
Threading
In itself, this is a huge topic. Most easy-to-apply, synchronization-related optimizations focus on minimizing the amount of code executing inside synchronized blocks, which may involve moving some code from inside to outside such blocks. In some cases, thoughtful programming may allow elimination of synchronization entirely from a class (see "Immutable Objects").
Performing a multithreaded micro-benchmark is more complicated than running a simple loop. In the simplest method, multiple threads are spawned, each looping over the benchmarked code; the reading is not started until all threads are successfully executing the code, and is terminated before the threads are shut down.
Thread Reuse
Newbie programmers make the common mistake of spawning a new thread for every request or other action. This can result in worse performance than using a single-threaded approach; the relative performance degradation is worse the quicker the individual requests can be serviced.
Writing Your Own Threading Code
Even better than the .NET thread pool, with its dependence on delegates, is to write your own threading code. Instead of using QueueUserWorkItem(), you typically write your own queueing code to coordinate work items. This also allows other benefits such as priority-based queueing.
Immutable Objects
Immutable objects are objects in which the data cannot be changed. In most cases, this is achieved by setting all fields in constructor methods and providing only property getters and/or methods that retrieve data from the object, without any mutator logic whatsoever. Many classes in the .NET Common Type System are immutable: System.String, System. Drawing.Font, etc. In addition, care should be taken that any values returned from property accessors, etc. are immutable as well. Otherwise, this data may be copied to insure the integrity of the object itself. Example 11 shows the performance benefit of immutable objects over synchronization.
Data Copying
This flies in the face of the advice given earlier, to minimize the use of objects. However, it's really the other side of the coin from immutable objects. Object copying allows you to use the data in a non-immutable object, but in a way that still completely avoids synchronization. The more highly multithreaded the environment, the more strategies like this make sense.
Read-Write Locks
Synchronization issues in managed code mirror those in databases. In some situations, optimistic concurrency strategies can be used; in some dirty reads are acceptable, etc. For situations in which a structure is seldom updated and often read, the ReaderWriterLock class can give significant performance benefits over simple synchronization. It allows either multiple read access or single write access at once. Example 12 compares ReaderWriterLock to simple synchronization in a read-heavy scenario.
Minimizing Synchronized Blocks
The use of the [MethodImpl Attribute(MethodImplOptions.Synchronized)]attribute should be avoided, as it always locks an entire method and is also non-standard C# usage. Instead, the lock keyword or one of the System.Threading classes should be used. Wherever possible, adjust the start of a synchronized section forward and the end backward. Do whatever you can to decrease the number of synchronized operations.
Suggested Reading

Lidin, Serge. (2002). Inside Microsoft .NET IL Assembler: Microsoft Press.

Archer, Tom, and Whitechapel, Andrew. (2002). Inside C#, Second Edition. Microsoft Press.

Rico Mariani's Weblog: http://blogs.msdn.com/ricom

Garbage Collector Basics and Performance Hints: dotnetgcbasics.asp

Improving .NET Application Performance and Scalability: scalenet.asp

An Introduction to C# Generics: csharp_generics.asp

WikiWikiWeb: http://c2.com/cgi/wiki?UniformlySlowCode

The Full Stack, Part I

The Full Stack, Part I: "

One of my most vivid memories from school was the day our chemistry teacher let us in on the Big Secret: every chemical reaction is a joining or separating of links between atoms. Which links form or break is completely governed by the energy involved and the number of electrons each atom has. The principle stuck with me long after I'd forgotten the details. There existed a simple reason for all of the strange rules of chemistry, and that reason lived at a lower level of reality. Maybe other things in the world were like that too.

 

xkcd.com/435

 

A 'full-stack programmer" is a generalist, someone who can create a non-trivial application by themselves. People who develop broad skills also tend to develop a good mental model of how different layers of a system behave. This turns out to be especially valuable for performance & optimization work. No one can know everything about everything, but you should be able to visualize what happens up and down the stack as an application does its thing. An application is shaped by the requirements of its data, and performance is shaped by how quickly hardware can throw data around.

 

Consider this harmless-looking SQL query:

 

DELETE FROM some_table WHERE id = 1234;

 

If the id column is not indexed, this code will usually result in a table scan: all of the records in some_table will be examined one-by-one to see if id equals 1234. Let's assume id is the indexed primary key. That's a good as it gets, right? Well, if the table is in InnoDB format it will result in one disk-seek, because the data is stored next to the primary key and can be deleted in one operation. If the table is MyISAM it will result in at least two seeks, because indexes and data are stored in different files. A hard drive can only do one seek at a time, so this detail can make the difference between 1X or 2X transactions per second. Digging deeper into how these storage engines work, you can find ways to trade safety for even more speed.

 

The shape of the data

One way to visualize a system is how its data is shaped and how it flows. Here are a some useful factors to think about:

• Working data size: This is the amount of data a system has to deal with during normal operation. Often it is identical to the total data size minus things like old logs, backups, inactive accounts, etc. In time-based applications such as email or a news feed the working set can be much smaller than the total set. People rarely access messages more than a few weeks old.

 

• Average request size: How much data does one user transaction have to send over the network? How much data does the system have to touch in order to serve that request? A site with 1 million small pictures will behave differently from a site with 1,000 huge files, even if they have the same data size and number of users. Downloading a photo and running a web search involve similar-sized answers, but the amounts of data touched are very different.

 

• Request rate: How many transactions are expected per user per minute? How many concurrent users are there at peak (your busiest period)? In a search engine you may have 5 to 10 queries per user session. An online ebook reader might see constant but low volumes of traffic. A game may require multiple transactions per second per user.

 

• Mutation rate: This is a measure of how often data is added, deleted, and edited. A webmail system has a high add rate, a lower deletion rate, and an almost-zero edit rate. An auction system has ridiculously high rates for all three.

 

• Consistency: How quickly does a mutation have to spread through the system? For a keyword advertising bid, a few minutes might be acceptable. Trading systems have to reconcile in milliseconds. A comments system is generally expected to show new comments within a second or two.

 

• Locality: This has to do with the probability that a user will read item B if they read item A. Or to put it another way, what portion of the working set does one user session need access to? On one extreme you have search engines. A user might want to query bits from anywhere in the data set. In an email application, the user is guaranteed to only access their inbox. Knowing that a user session is restricted to a well-defined subset of the data allows you to shard it: users from India can be directed to servers in India.

 

• Computation: what kinds of math do you need to run on the data before it goes out? Can it be precomputed and cached? Are you doing intersections of large arrays? The classic flight search problem requires lots of computation over lots of data. A blog does not.

 

• Latency: How quickly are transactions supposed to return success or failure? Users seem to be ok with a flight search or a credit card transaction taking their time. A web search has to return within a few hundred milliseconds. A widget or API that outside systems depend on should return in 100 milliseconds or less. More important is to maintain application latency within a narrow band. It is worse to answer 90% of queries in 0.1 seconds and the rest in 2 seconds, rather than all requests in 0.2 seconds.

 

• Contention: What are the fundamental bottlenecks? A pizza shop's fundamental bottleneck is the size of its oven. An application that serves random numbers will be limited by how many random-number generators it can employ. An application with strict consistency requirements and a high mutation rate might be limited by lock contention. Needless to say, the more parallelizability and the less contention, the better.

 

This model can be applied to a system as a whole or to a particular feature like a search page or home page. It's rare that all of the factors stand out for a particular application; usually it's 2 or 3. A good example is ReCAPTCHA. It generates a random pair of images, presents them to the user, and verifies whether the user spelled the words in the images correctly. The working set of data is small enough to fit in RAM, there is minimal computation, a low mutation rate, low per-user request rate, great locality, but very strict latency requirements. I'm told that ReCAPTCHA's request latency (minus network latency) is less than a millisecond.

 

A horribly oversimplified model of computation

aturingmachine.com

How an application is implemented depends on how real computers handle data. A computer really does only two things: read data and write data. Now that CPU cycles are so fast and cheap, performance is a function of how fast it can read or write, and how much data it must move around to accomplish a given task. For historical reasons we draw a line at operations over data on the CPU or in memory and call that 'CPU time'. Operations that deal with storage or network are lumped under 'I/O wait'. This is terrible because it doesn't distinguish between a CPU that's doing a lot of work, and a CPU that's waiting for data to be fetched into its cache.[0] A modern server works with five kinds of input/output, each one slower but with more capacity than the next:

• Registers & CPU cache (1 nanosecond): These are small, expensive and very fast memory slots. Memory controllers try mightily to keep this space populated with the data the CPU needs. A cache miss means a 100X speed penalty. Even with a 95% hit rate, CPU cache misses waste half the time.

 

• Main memory (10^2 nanoseconds): If your computer was an office, RAM would be the desk scattered with manuals and scraps of paper. The kernel is there, reserving Papal land-grant-sized chunks of memory for its own mysterious purposes. So are the programs that are either running or waiting to run, network packets you are receiving, data the kernel thinks it's going to need, and (if you want your program to run fast) your working set. RAM is hundreds of times slower than a register but still orders of magnitude faster than anything else. That's why server people go to such lengths to jam more and more RAM in.

 

• Solid-state drive (10^5 nanoseconds): SSDs can greatly improve the performance of systems with working sets too large to fit into main memory. Being 'only' one thousand times slower than RAM, solid-state devices can be used as ersatz memory. It will take a few more years for SSDs to replace  magnetic disks. And then we'll have to rewrite software tuned for the RAM / magnetic gap and not for the new reality.

 

• Magnetic disk (10^7 nanoseconds): Magnetic storage can handle large, contiguous streams of data very well. Random disk access is what kills performance. The latency gap between RAM and magnetic disks is so great that it's hard to overstate its importance. It's like the difference between having a dollar in your wallet and having your mom send you a dollar in the mail. The other important fact is that access time varies wildly. You can get at any part of RAM or SSD in about the same time, but a hard disk has a physical metal arm that swings around to reach the right part of the magnetic platter.

 

• Network (10^6 to 10^9 nanoseconds): Other computers. Unless you control that computer too, and it's less than a hundred feet away, network calls should be a last resort.

Trust, but verify

The software stack your application runs on is well aware of the memory/disk speed gap, and does its best to juggle things around such that the most-used data stays in RAM. Unfortunately, different layers of the stack can disagree about how best to do that, and often fight each other pointlessly. My advice is to trust the kernel and keep things simple. If you must trust something else, trust the database and tell the kernel to get out of the way.

 

Thumbs and envelopes

I'm using approximate powers-of-ten here to make the mental arithmetic easier. The actual numbers are less neat. When dealing with very large or very small numbers it's important to get the number of zeros right quickly, and only then sweat the details. Precise, unwieldy numbers usually don't help in the early stages of analysis. [1]

 

Suppose you have ten million (10^7) users, each with 10MB (10^7) bytes of data, and your network uplink can handle 100 megabits (10^7 bytes) per second. How long will it take to copy that data to another location over the internet? Hmm, that would be 10^7 seconds, or about 4 months: not great, but close to reasonable. You could use compression and multiple uplinks to bring the transfer time down to, say, a week. If the approximate answer had been not 4 but 400 months, you'd quickly drop the copy-over-the-internet idea and look for another answer.

 

movies.example.com

So can we use this model to identify the performance gotchas of an application? Let's say we want to build a movies-on-demand service like Netflix or Hulu. Videos are professionally produced and 20 and 200 minutes long. You want to support a library of 100,000 (10^5) films and 10^5 concurrent users. For simplicity's sake we'll consider only the actual watching of movies and disregard browsing the website, video encoding, user comments & ratings, logs analysis, etc.

• Working data size: The average video is 40 minutes long, and the bitrate is 300kbps. 40 * 60 * 300,000 / 8 is about 10^8 bytes. Times 10^5 videos means that your total working set is 10^13 bytes, or 10TB.

 

• Average request size: A video stream session will transfer somewhere between 10^7 and 10^9 bytes. In Part One we won't be discussing networking issues, but if we were this would be cause for alarm.

 

• Request rate: Fairly low, though the concurrent requests will be high. Users should have short bursts of browsing and long periods of streaming.

 

• Mutation rate: Nearly nil.

 

• Consistency: Unimportant except for user data. It would be nice to keep track of what place they were in a movie and zip back to that, but that can be handled lazily (eg in a client-side cookie).

 

• Locality: Any user can view any movie. You will have the opposite problem of many users accessing the same movie.

 

• Computation: If you do it right, computation should be minimal. DRM or on-the-fly encoding might eat up cycles.

 

• Latency: This is an interesting one. The worst case is channel surfing. In real-world movie services you may have noticed that switching streams or skipping around within one video takes a second or two in the average case. That's at the edge of user acceptability.

 

• Contention: How many CPU threads do you need to serve 100,000 video streams? How much data can one server push out? Why do real-world services seem to have this large skipping delay? When multiple highly successful implementations seem to have the same limitation, that's a strong sign of a fundamental bottleneck.

 

It's possible to build a single server that holds 10TB of data, but what about throughput? A hundred thousand streams at 300kbps (10^5 * 3 * 10^5) is 30 gigabits per second (3 * 10^10). Let's say that one server can push out 500mbps in the happy case. You'll need at least 60 servers to support 30gbps. That implies about 2,000 concurrent streams per server, which sounds almost reasonable. These guesses may be off by a factor or 2 or 4 but we're in the ballpark.

 

You could store a copy of the entire 10TB library on each server, but that's kind of expensive. You probably want either:

  
• A set of origin servers and a set of streaming servers. The origins are loaded with disks. The streamers are loaded with RAM. When a request comes in for a video, the streamer first checks to see if it has a local cache. If not, it contacts the origins and reads it from there.
  
• A system where each video is copied to only a few servers and requests are routed to them. This might have problems with unbalanced traffic.

 

An important detail is the distribution of popularity of your video data. If everyone watches the same 2GB video, you could just load the whole file into the RAM of each video server. On the other extreme, if 100,000 users each view 100,000 different videos, you'd need a lot of independent spindles or SSDs to keep up with the concurrent reads. In practice, your traffic will probably follow some kind of power-law distribution in which the most popular video has X users, the second-most has 0.5X users, the third-most 0.33X users, and so on. On one hand that's good; the bulk of your throughput will be served hot from RAM. On the other hand that's bad, because the rest of the requests will be served from cold storage.

 

Whatever architecture you use, it looks as though the performance of movies.example.com will depend almost completely on the random seek time of your storage devices. If I were building this today I would give both SSDs and non-standard data prefetching strategies a serious look.

 

It's been fun

This subject is way too large for a short writeup to do it justice. But absurd simplifications can be useful as long as you have an understanding of the big picture: an application's requirements are shaped by the data, and implementations are shaped by the hardware's ability to move data. Underneath every simple abstraction is a world of details and cleverness. The purpose of the big fuzzy picture is to point you where to start digging.

 

Carlos Bueno, an engineer at Facebook, thinks it's turtles all the way down.

 

 

Notes

[*] This article is part of Perf Planet's 2010 Performance Calendar.

 

[0] Fortunately there is a newish tool for Linux called 'perf counters'.

 

[1] Jeff Dean of Google deserves a lot of credit for popularizing the 'numbers you should know' approach to performance and systems work. As my colleague Keith Adams put it, 'The ability to quickly discard bad solutions, without actually building them, is a lot of what good systems programming is. Some of that is instinct, some experience, but a lot of it is algebra.'

"