Virtual Threads

Open letter about Internet radio royalties

2007-04-18T01:39:00.000-06:00

For those that live in the United States, I encourage you to write your representatives in Congress to protest the unfair royalties that are being foised on Internet radio stations. Here is the letter that I am sending to my Congressmen in Utah:

As my representative in Congress, I would like to know what you are doing to prevent the veritable destruction of Internet-based radio stations. As you have undoubtedly heard, the government recently adjusted the sound recording royalty rates for a compulsory license, raising them to a level that will force all small and medium-sized Internet-based radio stations out of business. It concerns me on several levels: as an employee of a local Salt Lake City broadcaster, as a graduate student in Computer Science, and as a citizen that enjoys music.

In my opinion, the problem does not lie with the Copyright Royalty Board's ruling on the new rate structure. Rather, the source of the trouble is Congress and its strange, unfair approach to sound recording royalties. Why do traditional over-the-air stations receive an exemption from having to pay this royalty while digital stations do not? This disparity is unexplainable, and is truly the root cause of the current problem.

Any serious examination will show that the arguments used to justify this discrimination do not stand up to logic. As the argument goes, over-the-air stations encourage CD sales for artists, and thus serve as a form of promotion, while digital stations supposedly transmit "perfect" copies of songs, which could be saved and played back later, thus driving down artists' CD sales. This is wrong for multiple reasons. First, virtually all digital stations transmit songs in a "lossy" format at very low bit-rates, resulting in audio that is noticably worse than a CD or even traditional FM radio. Second, it is no trivial task to save digital radio transmissions -- specialized software is required, and if someone wanted a digital copy of a song they will get it in an easier way (legally via Apple's iTunes or illegally via a peer-to-peer network). Third, digital rights management (DRM) technology can be used to encrypt and protect the transmitted songs from being archived by listeners.

Finally, I am concerned about the long-term consequences of the current situation. The high royalty rates will undoubtedly drive out small and mid-size Internet radio stations; only the largest stations will be able to pay such a royalty structure. This will consolidate more power into the hands of large existing station owners, like Clear Channel. In addition, it will encourage Internet radio stations to negotiate individual licensing deals with record labels so as to obtain cheaper royalty rates, which will be very damaging to the recording industry; it will be too expensive to try to manage hundreds of individual licensing deals with small record labels and independent artists, thus forcing Internet radio stations to only play music from the three or four largest record labels that have given them royalty deals. This will deal a body blow to the small labels and artists, possibly killing one of the most exciting aspects of the modern music industry.

Given the weak argument for treating digital radio differently from traditional radio, I encourage you to undo the mistakes of past Legislators and introduce a bill to grant a sound recording royalty exemption for digital transmissions, just like traditional radio enjoys.

Oh no -- I've become unbalanced!

2007-01-18T00:57:00.000-07:00

I recently discovered an interesting feature of the Linux kernel. It all started when I noticed that some new web servers at work were exhibiting a peculiar behavior -- the two CPU cores didn't seem to have balanced workloads. It seemed that usually the first core would have the majority of the load, while the second core would usually have much less (all witnessed via the mpstat -P ALL 10 command). Given that these servers were Apache web servers, I thought that they should typically be within a few percent of each other, but instead they were separated by anywhere from 5-25%.

After poking around a bit, I decided to try and tweak the server a bit to try and force the kernel to balance better. These servers each had two Ethernet interfaces, one to a 'front channel' across which the HTTP interaction with clients was performed, and one to a 'back channel' across which some database and other calls were made. One of the early thoughts that I had was to dedicate each of the two cores to one of the two Ethernet interfaces: this way, each core would always service the interrupts from the same interface. The default setup on the 2.6 kernel is to have all interrupts serviced by the first core, so I thought that perhaps the data load on the two interfaces was forcing the first core to run a bit hotter than the other.

It was easy enough to make the change. I first checked to find the interrupt numbers for the two interfaces (ifconfig), then forced the second one to always use the second processor core (echo "2" >/proc/irq/177/smp_affinity). This achieved the desired effect of rebalancing the interrupts, but it didn't solve my original problem: the cores were still unbalanced. In fact, the problem became even more interesting -- the two cores had almost flipped their loads, with the second core having the consistently higher usage.

At first I thought that perhaps the second interface might be transferring more data; that was wrong (ifconfig). Next I thought that, even with less total data transferred, perhaps the second interface was triggering more interrupts. That, too, was incorrect (cat /proc/interrupts). Finally, I checked to make sure that both interfaces were using the same driver, which they were (dmesg | grep eth). I had just about given up when I finally decided to put some logging into every web page (using PHP) to see what processor it used. Imagine my surprise when I discovered that nearly every web process started off on the lower-usage core, but then almost immediately migrated to the higher-usage core!

I had uncovered the superficial culprit: when a user requested a web page, one of the first things that the server would do is get a copy of their current session data from another server through the second interface. The moment that the second interface was used, the web process would flip over to the second core (or whatever core was assigned to service that interface's interrupts).

A little more research into the kernel code revealed it even further (caveat: I'm not a kernel hacker, so the details are still a bit fuzzy). When a network interface receives some data, Linux will find the process that is sleeping while waiting for that data and wake it up. When waking up the process, Linux will try to keep it on the same processor core that received the interrupt. I imagine that it does this in an effort to better utilize the core's memory cache, which should speed things up. However, it also appears to have a slight unbalancing effect on the other cores, which is exactly what I was seeing on my servers.

Of course, there are ways to fix this "problem". The easiest is to simply remove the flags in the kernel code that trigger this behavior (you'll find them in include/linux/topology.h; just remove any lines that say SD_WAKE_AFFINE), and then recompile the kernel. I've discovered, though, that this change doesn't seem to improve things like I thought it might. It did seem to balance out the load between the two cores, but the average load across the cores is actually slightly higher (1-2%, usually). This would make some sense; like I said before, the kernel is probably trying to make more efficient use of each core's cache, which apparently has a greater positive effect than having a more equal load distribution.

In the end, I suppose I can live with unbalanced CPU cores. I just wish that this behavior had been a bit better documented -- it was a rather painful process to have to figure it out myself. I suppose it could have been worse, though: I could be using closed-source Windows. ;)

Web serving on the cheap

2007-01-16T23:35:00.000-07:00

Have you ever wanted to set up a small web server at home that can handle a small but reasonable amount of traffic? Perhaps you have a pet project or a home business and can't justify the cost of professional hosting. Maybe you have a fetish for low powered servers on small internet connections. Or possibly you just want to see if a Slashdotting of your home DSL line will trigger a call from your ISP. In any case, here are some tips on how to get the most out of a small setup.

Understand your limitations

If you don't have a large budget, then you obviously are going to have two big problems:

A lack of CPU power

A lack of bandwidth

Any effort to improve the performance of your small web site should be directly aimed at alleviating one of these two problems. I'll discuss each of these two issues below. There are other issues, such as a lack of RAM or disk space or disk performance, but usually your CPU and bandwidth will dominate the situation. I'll also ignore the most obvious solution to these problems, which is simply to buy a better processor and a bigger tube.

Bandwidth

More often than not, bandwidth will be your biggest hurdle, especially if you're running your server on your home internet connection; most home connections have terrible upstream speeds, which really hurts you when you're a content producer and not a consumer. In addition, some connections, like DSL, will have high latencies.

To mitigate your lack of speed, you're simply going to need to push fewer bytes down the pipe. Look at your web pages and appreciate all of those pretty pictures while you can, because they're the first thing to go. A typical image can be anywhere from 10 to 200 kilobytes, which is simply too large for a small connection, especially if you have 20 of them on the front page. If you can stand it, remove every single GIF, JPEG, and PNG from your site. You may need to redesign your site around the new image-less paradigm, but you won't regret it in a few weeks when you get your bandwidth bill.

Next, move to a CSS-based design instead of a pure HTML one. You should be able to slim down your HTML this way, which will make it that much faster for a user to download. For an added bonus, you should put all of the CSS commands into a separate file. This will slow things down a tiny bit for the user's first visit to the site, but it also means that the same CSS file will be cached on every subsequent page view.

Finally, you should go for the biggest savings of all: compressed web pages. The idea is simple: the web server compress any text files before sending them to a user and the user's web browser will automatically decompress them before reading them. Every modern web browser supports compressed web pages, and you can see immense space savings from using it. Page compression can be a tricky thing to get right, especially if you're short on CPU power, because it obviously takes some effort by the web server to compress things. There are a few ways to get around this, one of which is to pre-render compressed versions of frequently accessed pages and then dish those out to users. You need to experiment with compression to see how much it affects your server's CPU.

CPU

If you're on a budget, then you most likely have an old computer with an outdated processor. This isn't necessarily a problem -- even very old computers can saturate a small internet connection -- but you're going to need to code your site correctly if you want to prevent it from being your big bottleneck.

The very first thing to go is the database. Sure, a database like MySQL is nice to have and does provide some convenience, but it can totally kill your web server's performance. Obviously, not everyone can do this, but many people can; it's usually a waste to store every page of a small web site in a full-fledged database system. Many small web sites could eliminate MySQL completely if they just stored data directly in files instead. For those that absolutely must have a database, you will need to at least remove any direct database query on your front page. Sometimes you can even just keep a copy of a MySQL query in a file and have a program update that file every so often.

Another way to avoid making database calls or any other expensive operation is to pre-render entire pages. If you know that your home page is only updated a few times a day, then why dynamically generate it every time someone views it? Just take the rendered page's HTML and save it in a file; the next time a user requests that page, just throw the rendered copy at them. You need to be careful to not give users stale pages, but it usually isn't too hard to figure it out on a small site. This concept ties in well with the previously mentioned tactic of saving pre-compressed copies of pages.

Finally, try to avoid web scripting in general. It is usually hard to avoid, given how much power it provides, but a poorly coded PHP or Perl page can chew through your CPU and RAM; it is best to use it only when it is truly needed. If you manage to free yourself of scripting on all but a few pages, you can even take advantage of a new class of lighter and faster web servers like lighttpd or tux; you'll still need to run a heavier web server process for those few scripted pages, but most of your traffic will hopefully run through the fast and light web server process.

Faith-based Computing

2006-08-30T23:17:00.000-06:00

Anyone has ever worked in a computer-related job should recognize the affliction I'm about to describe. It is a terrible scourge, and despite the best efforts of educators and gurus across the planet, it seems to be growing. Few things are so vile, so noxious, so... irritating. I am referring, of course, to faith-based computing, or "voodoo computing" as it is sometimes called.

Allow me to briefly describe faith-based computing for the uninformed; perhaps even an example is in order. Imagine yourself being the Joe (or Jane) in charge of the company's network. You receive a phone call from an irrate user who says that his download speeds from the Internet are very slow. Of course, this isn't the run-of-the-mill user who knows how to use Microsoft Word and Excel only. No, as luck would have it, this is the user whose knowledge of all things networked is vast, by virtue of their addiction on online games at home. He is the one who shelled out an extra $50 for a 1000Mbps switch instead of a 100Mbps switch, just so his ping time to game servers would somehow be faster. He is the one who bought a $300 network card, thinking that something so expensive and with such a "killer" name must be faster. Yes, he is the user with whom you don't want to discuss networking at all.

After dragging yourself to his desk, you test things out for a minute and then declare that the problem is simply the site from which he is downloading; the server or its connection must be overloaded. You determine this using some simple yet clear procedures, such as trying a different download from another web site and testing the same site using your account through a different ISP. Despite your best efforts to explain the situation, he refuses to believe you. "I download stuff from this site at home all the time and they've never had a problem before. It must be your network!" You can explain it to him as many times as you like, but he always has the same response, "If you guys would just buy a gigabit-capable switch, everyone's downloads would be so much faster." In the end, you must simply walk away and allow him to persist in his fantasies; he has become so blinded by the glare of his ego that he cannot see anything else.

This strange disease is manifested in a couple of different ways. First, there are the people who are simply too tired, disinterested, or stupid to spend the time learning about how things really work. A good example of this kind of person is the IT manager who buys Celeron processors instead of Pentiums because they believe that the Pentium is only useful if you are "doing a lot of math equations". Or the poor guy in the accounting department who reboots his computer five times a day because it "makes it run fast again" after he does it. This group of people has little interest in actually learning about how things work or debugging problems; they completely rely on rumors and heresay, with circumstantial evidence reinforcing their beliefs.

Another type of faith-based computing is the person who gets one thing stuck in their head and just can't let it go. "Your so-called evidence be damned," is their commonly thought phrase. Unlike the previous class of people, this group isn't lazy or dumb but instead very proud. They have their tried-and-true rules and solutions, most of which have actually been useful at some point, and they will stick to those rules and solutions no matter what the situation may be. You can logically build a waterproof case that a user's overheating CPU is causing intermittent shutdowns, but they will ignore you and insist that "it's the motherboard -- we need to replace it." This is the kind of person that will never trust any piece of network equipment that doesn't carry the Cisco logo. They are typically more aggrevating than other types of faithers, mostly because of their tendancy to show up in managerial positions.

So what can be done about this problem? It is not an easy puzzle to solve, but I believe a massive reeducation program is necessary. We need to begin a missionary effort to spread the gospel of logical thinking to these heathens. Once you have made sure that you yourself have cleansed yourself of all voodoo computing beliefs, you are prepared to begin your ministry. Spend extra time with your friends, family, and coworkers, teaching them the paths of logical computing. Those places where conversion efforts are successful should proudly display their achievement with signs that declare their new alliance with logical computing. Companies should note in their mission statements and job postings that they refuse to practice faith-based computing and will not hire those who adhere to it.

With a strong and steady effort, we will eventually eradicate its evil vestiges from every corner of the transistor-based world. I call on everyone to join the battle to dismiss one of the last remnants of the Dark Ages from our hallowed halls of computing.

Under the covers of a memory access

2006-04-23T23:24:00.000-06:00

When someone writes a computer program, they use many statements that look something like A=B+1. This simple operataion retrieves a piece of data from memory location B, adds one to it, and then stores the result in memory location B. Statements of this form are incredibly common in computer programs; they probably make up the majority of the operations performed by programs. With something so simple and common, you would think that it would be a trivial matter for the computer to carry it out. This is not the case at all. In this posting, I will give a very high-level introduction to some of the steps involved in just retrieving a single piece of data from memory. I have made a number of simplifications (such as placing the memory address translation before any of the caches), but hopefully it is detailed enough to give people a taste of the complexities involved.

The first step is to translate the memory address used by the program into a different address, called a physical address. Most modern computers use a special thing called a memory-management unit (MMU) to allow each process on a system to pretend that it is the only thing running. It does this by having the process use a large set of virtual ("fake") addresses which are then translated by the MMU into physical ("real") addresses on demand. Of course, this can be a slow process; the computer must have a set of translation tables for each process that map from virtual to physcical memory addresses, and it must consult this table for every single memory access. These tables are stored in the computer's memory, and thus each memory access potentially turns into TWO memory accesses. Fortunately, a high-speed caching mechanism called the TLB is used to speed up translation table lookups, which makes the virtual-to-physical translation process fast enough to be feasible.

Once the computer has the physical address of the desired item in memory, it then proceeds to look in a set of high-speed caches for it. Although the RAM in a computer is incredibly fast when compared to something like a hard drive, it is actually somewhat slow when compared to the speed of a CPU. Thus, memory caches exist between the processor and memory that are small but fast. Whenever a piece of data is retrieved from RAM, it is subsequently placed into one or more of these caches so that future references to it are much quicker. A lot of effort has been put into making these various caches as fast and efficient as possible, as they can have a dramatic effect on the performance of a computer. In many modern computers, there are two levels of caches: L1, which is very small but also very fast, and L2, which is somewhat larger but also somewhat slower. Some processors even have a third cache (L3) that is even larger than the previous two. Each of these caches must be checked in turn to see if one of them contains the requested data.

If the requested data is not in any of the caches, then the computer is forced to actually retrieve it from main memory. This is a somewhat lengthy process and is one of the big obstacles in speeding up computers; in the time that it takes to retrieve a piece of data from memory, a processor could possibly execute hundreds or thousands of instructions. Unfortunately, the processor many times must simply sit and twiddle its thumbs while the memory system services the request.

There is another complication, though. Sometimes the operating system on the computer will tell a little white lie to the running processes by letting them believe that something is in RAM when it really is on the hard drive. This can happen in a few different circumstances, the most well-known of which is when the operating system "swaps" something out from memory to the drive. This works rather well when a block of data doesn't need to be used soon, but it does complicate memory accesses because the operating system needs to dynamically and transparently move things in and out of memory. Thus, if the requested piece of data has been swapped out to the hard drive, the memory system will essentially wake up the operating system and tell it to put it back into memory. This process is incredibly time consuming and involves thousands and thousands of additional memory accesses, as the operating system must determine where the data is located on the hard drive and communicate with the disk to load it in.

Once the requested piece of data has been found, the memory system returns the data to the processor (placing it into one or more of the caches along the way). After all is said and done, that single memory access has potentially cause numerous additional memory accesses, instruction executions, and even hard disk accesses. It is easy to see why computer and operating system designers work very hard to mitigate the costs associated with memory accesses by taking full advantage of high-speed caching mechanisms and advanced algorithms to predict program behavior. Even compilers use special tricks to try and ameliorate the situation, by doing things like reordering instructions and making the most efficient use of low-level processor resources.

This overview of a computer's memory system has been very brief, and thus is somewhat incorrect int its details. For further information, I would recommend that people read a good computer architecture book (such as Computer Organization and Design) as well as an introductory operating systems book (Operating System Concepts covers many of these details). The Wikipedia also has extensive coverage of many low-level computer architecture details like this.

Why a "Clean Internet Channel" won't work

2006-03-19T00:01:00.000-07:00

I received a message on my answering machine tonight from a group that is advocating the creation of a "Clean Internet Channel". Although the web site is rather short on details, it sounds very similar to another recent proposal in Utah called "CP80" that proposed the use of a separate TCP port for pornographic content on the Internet, thus allowing people to easily choose whether or not to allow said content on their Internet connections. Although their end goal is a good one, their logical skills seem to be a bit lacking.

To be fair, I must admit that an Internet port, or "channel" as they like to call it, could be used in this fashion. People use different Internet ports all the time for different things, although it is usually for more technical reasons (e.g. requesting an encrypted version of a web site as opposed to the regular, unencrypted version). It would be rather simple to get a bunch of lawyers-turned-politicians together and create a law that forced all pornographic content to use a special Internet port. It would take a monumental effort to get all of the software in the world to work correctly, but we'll conveniently ignore that fact. Thus far, we'll assume that the Clean Channel idea will technically work. The devil is in the details, though.

Problem #1: How do you avoid cheaters?
The first question that they need to ask themselves is how they will prevent people from cheating. That is, how do you prevent web sites from offering inappropriate content using the Clean Internet Channel? We'll consider the legal aspects of this in a moment, but for now, let's simply talk about the technical hurdles involved. The most common way to block "bad" Internet ports is to use a firewall; companies often use firewalls to prevent access to things like file sharing programs (which use their own specific Internet ports).

A firewall simply looks at the relevant Internet port of your Internet traffic and allows or denies it based on that port. Unfortunately, a firewall becomes useless junk if a pornographic website decides to maliciously use the "clean port"; the traffic will look good to the firewall because it is coming from a port number that is considered to be clean. More advanced firewalls can do more than this -- they can scan the data being passed through them and look for keywords that are considered bad (e.g. "sex", "drugs", "rock and roll"), and then allow or deny the data based on those key words -- but if that's the real solution, then why even bother with the Clean Internet Channel? We already have the technology to do the deeper keyword-based blocking, so why create a port-based law that would basically be ineffective?

Problem #2: How do you internationally enforce a US law?
Now let's address the political issues involved. How do you legally stop a web site from cheating? "Well, we'll just sue companies that don't comply!" is undoubtedly the answer. This will work for companies like Playboy, but it's tough to sue companies that are based outside of the United States. Do they really think that Europe cares about a US Clean Internet Channel? Even if Europe did agree to implement a similar law, I know that their standards for pornography are quite different than what we have here; just watch Europen television for a while and you'll see the difference. And if we can't get Europe to comply, then what are the chances of getting even more dissimilar countries to comply, like Nigeria or Venezuela?

Problem #3: How do you find the cheaters?
Even if the entire world adopted the same law and the same standards for pornography, you still wouldn't be able to shut them all down; you simply couldn't find and sue them fast enough. The Clean Internet Channel web site refers to a wonderful technology that "will instantly track down and report to law enforcement any sending of pornographic material through the Clean Channel", but it won't work. Why not? Because if it did work, then the problem would already be solved; you could just buy it and use it as a filter for your Internet connection, as it would be able to recognize indecent content regardless of the associated Internet port. Obviously, their wonderful porn-recognition techology won't work as well as they are claiming.

Let's face it, everyone: porn is here to stay. You're not going to find an easy way to prevent people from finding it. In fact, if you put a determined 14-year-old up against any porn-filtering mechanism, I guarantee that the porn filter is going to lose every time. A Clean Internet Channel law is simply a feel-good measure for parents, not a real solution to the problem. I can only hope that legislators realize this and begin to place more emphasis on education instead of technological placebos.

Beware Ethernet flow control

2006-02-21T02:56:00.000-07:00

After having been recently bitten by Ethernet's flow control mechanism, I decided to learn about this somewhat obscure but commonly used facet of modern networks. This post is a summary of what I discovered about it and its associated benefits and dangers.

What is flow control?
Ethernet flow control, or 802.3x, is a way for a network device to tell its immediate neighbor that it is overloaded with data, such as when a device is receiving data faster than it can process it. It allows for an overloaded device to send out a special Ethernet frame, called a pause frame, that asks the device on the other end of the wire to stop sending data temporarily. If the receiving device honors the pause frame then the sending device has time to catch up on the stack of received data that it hasn't had time to process yet.

There also exists an older method for flow control called "back pressure" that is used in half-duplex environments (i.e. non-switched Ethernet). It consists of the overloaded device "jamming" the medium temporarily until it has the ability to accept more data. I don't know much about half-duplex flow control, and thus I won't mention it again; everything here applies solely to full-duplex flow control via 802.3x. Also, TCP has a mechanism for performing its own flow control that is entirely different from Ethernet's flow control; I will not be fully explaining TCP's flow control method here, as it would merit a lengthy discussion itself.

Rules of the game
When thinking about Ethernet flow control, it is important to keep several things in mind:

Flow control operates at a lower layer than TCP or IP, and thus is independent of them. Put another way, flow control is capable of being used regardless of what higher-level protocols are put on top of it. An important side-effect of this is that neither TCP nor IP know what Ethernet's flow control is doing; they operate under the assumption that there is no flow control other than what they may or may not provide themselves.
Flow control functions between two directly connected network devices, and flow control frames are never forwarded between links. Thus, two computers that are connected via a switch will never send pause frames to each other, but could send pause frames to the switch itself (and vice versa: the switch can send pause frames to the two computers).
Pause frames have a limited duration; they will automatically "expire" after a certain amount of time. The expiration time is set by the device that transmits the pause frame.
A paused link is not a discriminator of protocols; it will prevent any data from being passed across the link other than more pause frames.

Perhaps you have begun to see some issues with flow control in light of some of the above points. Let's start looking at them.

TCP breakage
Okay, it isn't true, TCP doesn't stop working when flow control is enabled. However, an important part of it does stop working correctly: its own flow control mechanism. TCP flow control uses a more complex mechanism of timeouts and acknowledgement segments to determine when a remote device is overloaded. It basically sends at a faster and faster pace until it sees that some of its sent data isn't getting to the remote device and then slows down. This allows TCP to utilize network links in a somewhat intelligent manner, as an overloaded network or device will cause some TCP segments to be lost and thus cause the sender to send data at a slower rate.

Now consider what happens when Ethernet flow control is mixed with TCP flow control. Let's assume that we have two directly connected computers, one of which is much slower than the other. The faster sending computer starts sending lots of data to the slower receiving computer. The receiver eventually notices that it is getting overloaded with data and sends a pause frame to the sender. The sender sees the pause frame and stops sending temporarily. Once the pause frame expires, the sender will resume sending its flood of data to the other computer. Unfortunately, the TCP engine on the sender will not recognize that the receiver is overloaded, as there was no lost data -- the receiver will typically stop the sender before it loses any data. Thus, the sender will continue to speed up at an exponential rate; because it didn't see any lost data, it will send data twice as fast as before! Because the receiver has a permanent speed disadvantage, this will require the receiver to send out pause frames twice as often. Things start snowballing until the receiver pauses the sender so often that the sender starts dropping its own data before it sends it, and thus finally sees some data being lost and slows down.

Is this a problem? In some ways it isn't. Because TCP is a reliable protocol, nothing is ever really "lost"; it is simply retransmitted and life goes on. Ethernet flow control accomplishes the same thing as TCP flow control in this situation, as they both slow down the data transmission to the speed that the slower device can handle. There are some arguments to be made for there being an awkward overlap between the two flow control mechanisms, but it could be worse.

Unfortunately, it does get worse.

Head-of-line blocking
In the last example, I considered the case where two computers were directly connected to each other. This example is too simplistic to be of much use -- when was the last time you saw two directly connected computers? It is a bit of a rarity. Let's now look at what happens when you introduce a switch into the mix. For our purposes, let us assume that the switch fully supports Ethernet flow control and that it is willing to use it. Our new setup will consist of two desktop computers and one file server, all of which are attached to the switch. It isn't any fun to make everything perfect, so let's also say that one of the desktops has a 10 Mbps connection to the switch while the other desktop and the server have 100 Mbps connections.

This setup is usually fine -- the 10 Mbps connection will be slower than the others, but it doesn't cause too many problems, just slower service to the one desktop. Things could get ugly, though, if Ethernet flow control is enabled on the switch. Imagine that the 10 Mbps desktop requests a large file from the file server. The file server begins to send the file to the desktop initially at a slow rate, but quickly picks up steam. Eventually, the file server will start to send data to the desktop at 11 Mbps, which is more than the poor 10 Mbps connection can handle. Without flow control enabled on the switch, the switch would start to simply drop data segments destined to the desktop, which the file server would notice and start to throttle back its sending rate.

With flow control enabled on the switch, though, the switch takes a very different approach; it will send out its own pause frames to any port that is sending data to the now-overloaded 10 Mbps port. This means that the file server will receive a pause frame from the switch, requesting it to cease all transmissions for a certain amount of time. Is this a problem? Yes! Because pause frames cease all transmissions on the link, any other data that the file server is sending will be paused as well, including data that may be destined to the 100 Mbps desktop computer. Eventually the pause will expire and the file server will continue sending out data. Unfortunately, the TCP mechanism on the file server will not know that anything is wrong and will continue sending out data at faster and faster speeds, thus overloading the 10 Mbps desktop again. As before, the cycle will keep repeating itself until the file server starts dropping its own data. Unlike the previous situation, the innocent 100 Mbps desktop bystander is penalized and will see its transfers from the file server drop to 10 Mbps speeds.

This situation is called head-of-line blocking, and it is the major reason why Ethernet flow control is somewhat dangerous to use. When enabled on network switches, it can create situations where one slow link in a network can bring the rest of the network to a crawl. It gets especially bad if the backbones in your network have flow control enabled; it should be obvious by this point just how bad that could get.

When to enable flow control
So what should you do? Should you completely disable flow control on all computers and switches? Not necessarily. It is generally safe to leave flow control enabled on computers. Switches, though, should either have flow control disabled or configured such that they will honor received pause frames but will never send out new pause frames. Some Cisco switches are even permanently configured this way -- they can receive pause frames but never emit them. To be honest, the complete answer to flow control is somewhat more complicated than this (e.g. you could probably enable pause frame emission if a switch port is connected to a slow backplane), but the safest bet is to disable flow control when given the option.

Great computer books

2006-02-09T00:14:00.000-07:00

There was a very good comment on my Understanding memory usage on Linux post a couple of days ago. Besides having some insightful points about memory usage, the poster made mention of Linux Kernel Development, a book by Robert Love on the Linux 2.6 kernel. I own this book and love it; I'm not really a kernel hacker, but I have found the information in the book invaluable when it comes to understanding how Linux ticks. I highly recommend it to anyone that wants to delve into the kernel.

Although Linux Kernel Development can be read without having too much theoretical operating systems background, I would still recommend that people also pick up a good general OS book. My preference is Operating System Concepts by Silberschatz, Galvin, and Gagne, but that may be because it's the one that I used for my college OS class. I've wanted to try out Andrew Tanenbaum's Modern Operating Systems, but it's a little too spendy for me. Plus, I'd feel like I couldn't read it around other Linux geeks, what with Tanenbaum's addiction to microkernels...

My other favorite topic, besides operating systems, is networking. In this field I have two all-time favorites, one of which is Tanenbaum's Computer Networks. Not only does he cover a huge range of networking topics, but he does it in the classic hacker way -- with humor. The other favorite of mine is Computer Networking: A Top-Down Approach by Kurose and Ross. It's more accessible than Tanenbaum's book and has a nice solid, professional feel to it. Both of these books are on the high side in terms of price, but are well worth it.

Disclaimer: Greg Gagne of Operating System Concepts was my advisor in college (although, interestingly enough, I didn't know about his book until I went to graduate school). Other than that, I do not have any personal or financial ties to any of these books.

Hello world!

2006-02-06T21:36:00.000-07:00

After my recent Understanding memory usage on Linux post was linked from some large web sites (Slashdot, Digg, and del.icio.us so far), I thought it would be fun to create a map that showed where the resulting ~60,000 hits came from.

The map displays a dot for each hit that I received over the last few days. This isn't an exact science, as I can only determine where everyone's ISPs are located, but I figure it is a pretty close estimate. I would love to create an hour-by-hour slideshow, but that will have to wait for another day.

So here's a "hello world" to all of my fellow geeks in Russia, Nigeria, Egypt, Bermuda, the middle of the Caspian Sea, Sydney, Sri Lanka, Argentina, Iceland, Italia, and everywhere else.

Re: memory usage on Linux

2006-02-06T14:42:00.000-07:00

A lot of people made good points in the comments section of my last posting (Understanding memory usage on Linux). Here are some of the general ideas that were mentioned:

(1) Several comments noted that non-x86 hardware has a different approach to shared memory between processes. This is true; some architectures do not handle shared memory in the same way as x86. To be honest, I don't know which platforms those are, so I'm not going to even try to list them. Thus, my previous post should be taken with a big grain of salt if you're working on a non-x86 platform.

(2) Many people also noted that this shared library feature of Linux isn't some fancy new thing, which is completely true. Microsoft Windows platforms undoubtedly have the same basic sharing feature, just like any full-featured modern operating system. My post only addressed Linux because, to be honest, I'm a Linux-centric kind of person.

(3) Yes, I did commit the sin of using "it's" instead of "its". To all of the English majors in the audience, I offer my most sincere apology.

(4) A few comments mentioned the memory size of Firefox. I must admit that I began this article with Firefox instead of KEdit as the primary example, but I was forced to switch to KEdit when I saw how big Firefox's private/writeable size was; KEdit illustrated my point much better. :)

(5) If the word "marginal" that I used confused anyone, then feel free to just mentally replace it with the word "incremental".

Thanks to everyone that commented on the posting; part of my reason for writing it was to see what other people thought, as other people usually know more than I do about any given subject.

Understanding memory usage on Linux

2006-02-04T15:36:00.000-07:00

This entry is for those people who have ever wondered, "Why the hell is a simple KDE text editor taking up 25 megabytes of memory?" Many people are led to believe that many Linux applications, especially KDE or Gnome programs, are "bloated" based solely upon what tools like ps report. While this may or may not be true, depending on the program, it is not generally true -- many programs are much more memory efficient than they seem.

What ps reports
The ps tool can output various pieces of information about a process, such as its process id, current running state, and resource utilization. Two of the possible outputs are VSZ and RSS, which stand for "virtual set size" and "resident set size", which are commonly used by geeks around the world to see how much memory processes are taking up.

For example, here is the output of ps aux for KEdit on my computer:


USER       PID %CPU %MEM    VSZ   RSS TTY      STAT START   TIME COMMAND
dbunker   3468  0.0  2.7  25400 14452 ?        S    20:19   0:00 kdeinit: kedit

According to ps, KEdit has a virtual size of about 25 megabytes and a resident size of about 14 megabytes (both numbers above are reported in kilobytes). It seems that most people like to randomly choose to accept one number or the other as representing the real memory usage of a process. I'm not going to explain the difference between VSZ and RSS right now but, needless to say, this is the wrong approach; neither number is an accurate picture of what the memory cost of running KEdit is.

Why ps is "wrong"
Depending on how you look at it, ps is not reporting the real memory usage of processes. What it is really doing is showing how much real memory each process would take up if it were the only process running. Of course, a typical Linux machine has several dozen processes running at any given time, which means that the VSZ and RSS numbers reported by ps are almost definitely "wrong". In order to understand why, it is necessary to learn how Linux handles shared libraries in programs.

Most major programs on Linux use shared libraries to facilitate certain functionality. For example, a KDE text editing program will use several KDE shared libraries (to allow for interaction with other KDE components), several X libraries (to allow it to display images and copy and pasting), and several general system libraries (to allow it to perform basic operations). Many of these shared libraries, especially commonly used ones like libc, are used by many of the programs running on a Linux system. Due to this sharing, Linux is able to use a great trick: it will load a single copy of the shared libraries into memory and use that one copy for every program that references it.

For better or worse, many tools don't care very much about this very common trick; they simply report how much memory a process uses, regardless of whether that memory is shared with other processes as well. Two programs could therefore use a large shared library and yet have its size count towards both of their memory usage totals; the library is being double-counted, which can be very misleading if you don't know what is going on.

Unfortunately, a perfect representation of process memory usage isn't easy to obtain. Not only do you need to understand how the system really works, but you need to decide how you want to deal with some hard questions. Should a shared library that is only needed for one process be counted in that process's memory usage? If a shared library is used my multiple processes, should its memory usage be evenly distributed among the different processes, or just ignored? There isn't a hard and fast rule here; you might have different answers depending on the situation you're facing. It's easy to see why ps doesn't try harder to report "correct" memory usage totals, given the ambiguity.

Seeing a process's memory map
Enough talk; let's see what the situation is with that "huge" KEdit process. To see what KEdit's memory looks like, we'll use the pmap program (with the -d flag):


Address   Kbytes Mode  Offset           Device    Mapping
08048000      40 r-x-- 0000000000000000 0fe:00000 kdeinit
08052000       4 rw--- 0000000000009000 0fe:00000 kdeinit
08053000    1164 rw--- 0000000008053000 000:00000   [ anon ]
40000000      84 r-x-- 0000000000000000 0fe:00000 ld-2.3.5.so
40015000       8 rw--- 0000000000014000 0fe:00000 ld-2.3.5.so
40017000       4 rw--- 0000000040017000 000:00000   [ anon ]
40018000       4 r-x-- 0000000000000000 0fe:00000 kedit.so
40019000       4 rw--- 0000000000000000 0fe:00000 kedit.so
40027000     252 r-x-- 0000000000000000 0fe:00000 libkparts.so.2.1.0
40066000      20 rw--- 000000000003e000 0fe:00000 libkparts.so.2.1.0
4006b000    3108 r-x-- 0000000000000000 0fe:00000 libkio.so.4.2.0
40374000     116 rw--- 0000000000309000 0fe:00000 libkio.so.4.2.0
40391000       8 rw--- 0000000040391000 000:00000   [ anon ]
40393000    2644 r-x-- 0000000000000000 0fe:00000 libkdeui.so.4.2.0
40628000     164 rw--- 0000000000295000 0fe:00000 libkdeui.so.4.2.0
40651000       4 rw--- 0000000040651000 000:00000   [ anon ]
40652000     100 r-x-- 0000000000000000 0fe:00000 libkdesu.so.4.2.0
4066b000       4 rw--- 0000000000019000 0fe:00000 libkdesu.so.4.2.0
4066c000      68 r-x-- 0000000000000000 0fe:00000 libkwalletclient.so.1.0.0
4067d000       4 rw--- 0000000000011000 0fe:00000 libkwalletclient.so.1.0.0
4067e000       4 rw--- 000000004067e000 000:00000   [ anon ]
4067f000    2148 r-x-- 0000000000000000 0fe:00000 libkdecore.so.4.2.0
40898000      64 rw--- 0000000000219000 0fe:00000 libkdecore.so.4.2.0
408a8000       8 rw--- 00000000408a8000 000:00000   [ anon ]
... (trimmed) ...
mapped: 25404K    writeable/private: 2432K    shared: 0K

I cut out a lot of the output; the rest is similar to what is shown. Even without the complete output, we can see some very interesting things. One important thing to note about the output is that each shared library is listed twice; once for its code segment and once for its data segment. The code segments have a mode of "r-x--", while the data is set to "rw---". The Kbytes, Mode, and Mapping columns are the only ones we will care about, as the rest are unimportant to the discussion.

If you go through the output, you will find that the lines with the largest Kbytes number are usually the code segments of the included shared libraries (the ones that start with "lib" are the shared libraries). What is great about that is that they are the ones that can be shared between processes. If you factor out all of the parts that are shared between processes, you end up with the "writeable/private" total, which is shown at the bottom of the output. This is what can be considered the incremental cost of this process, factoring out the shared libraries. Therefore, the cost to run this instance of KEdit (assuming that all of the shared libraries were already loaded) is around 2 megabytes. That is quite a different story from the 14 or 25 megabytes that ps reported.

What does it all mean?
The moral of this story is that process memory usage on Linux is a complex matter; you can't just run ps and know what is going on. This is especially true when you deal with programs that create a lot of identical children processes, like Apache. ps might report that each Apache process uses 10 megabytes of memory, when the reality might be that the marginal cost of each Apache process is 1 megabyte of memory. This information becomes critial when tuning Apache's MaxClients setting, which determines how many simultaneous requests your server can handle (although see one of my past postings for another way of increasing Apache's performance).

It also shows that it pays to stick with one desktop's software as much as possible. If you run KDE for your desktop, but mostly use Gnome applications, then you are paying a large price for a lot of redundant (but different) shared libraries. By sticking to just KDE or just Gnome apps as much as possible, you reduce your overall memory usage due to the reduced marginal memory cost of running new KDE or Gnome applications, which allows Linux to use more memory for other interesting things (like the file cache, which speeds up file accesses immensely).

Lack of monitoring tools for Linux

2006-02-04T14:52:00.000-07:00

I've been looking for a way to monitor a few dozen Linux servers lately, and there just doesn't seem to be a nice integrated tool to do it. In particular, I am looking for something that:

Pulls various SNMP data from a list of Linux server
Stores said data for a user-specifiable amount of time
Generates useful graphs of said data
Sends emails out when said data exceeds certain thresholds
Provides a decent web interface for controlling everything
Runs under Linux

Maybe I'm just blind, but there doesn't seem to be anything that can do all of the above. I can accomplish some of it using mon, for example, but then I don't have a decent web interface, data retrieval/storage, or graphing. I can use Cacti, but then I don't have good alerting or data storage (RRD files are "lossy"). I would write my own, but then I lose the nice user interface.

Undoubtedly, someone will eventually come out with the complete package that satisfies my every desire. Once that happens, I'll just be one step away from having everything I ever wanted from Linux, with better cluster administration tools being my last hurdle.

User comments on news sites

2006-02-02T18:19:00.000-07:00

Yesterday, ksl.com unveiled its new comment system. I must say that I love being able to see what other people think about news stories, especially local ones; comments are the feature of Slashdot that I love the most.

This is quite the contrast to the Washington Post which recently turned off user comments on their blog postings. Although I can understand why they are nervous about some of the user-supplied content, I cannot help but think that they are shooting themselves in the foot. What's strange is that it seems they weren't even allowing people to comment on the main news stories, but just on the blog.

For me, half of the value of news stories on places like Slashdot and now ksl.com is seeing how everyone else is reacting. There is a sense of community there that is sorely missing in much of today's media.

Tuning Apache, part 1

2006-01-31T22:30:00.000-07:00

There was a link on Digg a couple of days ago to an article about how to tune Apache so as to survive a Slashdotting. After reading it through, I came to the conclusion that the author had no idea what he was talking about. Not only did he admit that he had never experienced the "Slashdot Effect", but his advice was just plain wrong. I offered a few comments there, but I figured that I should elaborate on a few of them here. I'll post each major configuration topic as a new blog entry, and today's entry is about HTTP's Keep-Alive feature.

A brief history of Keep-Alives
The original HTTP protocol did not allow keep-alives, which meant that a connection was made to the server for each file that needed to be downloaded. This was a very inefficient method of doing things, especially since web pages typically had several files that needed to be downloaded in order to be properly displayed. Why was it inefficient? For two reasons:

Each connection requires an overhead of at least 3 packets to be initiated (SYN, SYN-ACK, and ACK packets). This means that at least three round-trips are required to open a connection, which obviously slowed things down.
Due to the nature of TCP, which underlies HTTP, a connection gets "faster" the longer it is open. By continously opening and closing new connections, HTTP would never be able to fully utilize its available bandwidth.

The designers of HTTP realized this weakness in the protocol, and took steps to correct it in the next version of HTTP. This new version of HTTP incorporated the concepts of keep-alives, where a client could keep a connection to the web server open indefinitely, or at least as long as the server permitted. Although this somewhat went against HTTP's original design goal of being "stateless", it allowed for it to overcome its speed and overhead problems.

A brief introduction to Apache
Now let's examine how Apache works. When you start Apache, a main "coordinator" process is created. This main process is responsible for accepting incoming connections and passing them off to "worker" processes that it creates. These workers then read users' requests and send back responses. Once a worker is done servicing a user's requests, it reports back to the main process and then waits for a new connection to be handed to it.

Apache and Keep-Alives
So, in theory, keep-alives are a great thing. They allow web clients and servers to fully utilize their available bandwidth, and reduces latency by eliminating the overhead of frequently opening new connections. In a perfect world, you would want Apache's KeepAliveTimeout setting to be "infinity", so that web clients maintain a connection to the web server for as long as possible and thus everything on your web site pulls up as fast as possible.

Apache allows you to configure its behavior in regard to keep-alives through a few options in its configuration file:

KeepAlive: either On or Off, depending on whether Apache should allow connections to be used for multiple requests
KeepAliveTimeout: how long, in seconds, Apache will wait after a request has been answered for another request before closing the connection
MaxKeepAliveRequests: how many total requests a client can issue across a single connection
MaxClients: the total number of worker processes that Apache will allow at any given time

The default Apache configuration file sets KeepAlive to be on, with a KeepAliveTimeout of 15 seconds and MaxKeepAliveRequests of 100. The MaxClients setting is set to 150.

Apache meets its match
Unfortunately, nothing in life is free, not even keep-alives. Each client connection requires Apache to create (or use a waiting) worker process to service its requests. These worker processes can only handle one connection at a time, and each connection will last at least 15 seconds. Apache will create a new worker process for each new connection until it hits its limit of MaxClients at 150. Thus, the cost of a keep-alive is one worker process for the KeepAliveTimeout.

Now imagine what happens when 1,000 web clients try to access your web site at the same moment (e.g. when it first shows up on Slashdot). The first 150 clients will successfully connect to your web server, because Apache will create workers to service their requests. However, those web clients do not immediately leave; after they've downloaded your page, they will hold open their connections for 15 seconds until your server forces their connection to close. The next 850 clients will be unable to access the web server, as all of the available Apache worker processes will be used up, waiting for 15 seconds on the unused connections to the first 150 clients. Some of those 850 clients will queue up and wait for an available Apache process to service their request, but most will give up.

Perhaps some readers are wondering why you wouldn't just increase the MaxClients setting to something high enough to handle your peak load, like 2000 or something. This is a very bad idea; you can increase Apache's MaxClients, but only at your own peril. Because each Apache process consumes a bit of memory, you can only fit a certain number in memory before the web server begins to violently thrash, swapping things between RAM and the hard drive in a futile attempt to make it work. The result is a totally unresponsive server; by increasing MaxClients too high, you will have caused your own demise. I will talk about how to figure out a good value for MaxClients in a future post, but a good rule of thumb might be to divide your total RAM by 5 megabytes. Thus, a server with 512 megabytes of RAM could probably handle a MaxClients setting of 100. This is probably a somewhat conservative estimate, but it should give you a starting point.

A partial solution
So how do you fix the problem, other than by adding many gigabytes of RAM to the server? One easy way to get around this limitation is to either reduce the KeepAliveTimeout to a mere second or two, or else to simply turn KeepAlive off completely. I have found that turning it down to 2 seconds seems to give the client enough time to request all of the files needed for a page without having to open multiple connections, yet allows Apache to terminate the connection soon enough to be able to handle many more clients than usual.

One interesting thing of which to take note is what the major Apache-based web sites allow, in terms of keep-alive timeouts. In my (very brief) experiments, it seems that CNN, Yahoo, craigslist, and Slashdot don't permit keep-alives at all, while the BBC has a very short keep-alive timeout of under 5 seconds. On the other hand, there are several other major Apache-based sites that do use a large keep-alive timeout (Apple, CNET, etc...), but they may have decided that they would prefer to take the performance hit so that they can have the "fastest" web sites as possible.

Of course, this isn't a perfect solution. It would be nice to be able to have both high-performance as well as long-lived client connections. Apache 2.2, from what I understand, includes an experimental module that allows keep-alives to be handled very efficiently. If it turns out to work well, then it could be a near-perfect solution to the problem. It does have its problems (i.e. it seems to require a threaded MPM, which is not recommended if you use PHP), but it could be incredibly useful in some situations.