Cacheboy Development

Where's cacheboy been hiding?

2011-07-15T19:04:00.001-07:00

I've had a few people ask where Cacheboy has been hiding since late 2009.

In short - I had a lack of reliable traffic nodes and my bachelor's degree to finish off.

Now, the long version.

The university reason is easy - I've been working on and off on a Bachelor of Arts for a few years, and decided late 2009 that I should just buckle down and get it all done. So I spent 2010 and the first part of 2011 studying (and working!) full-time. It was pretty intense. I had to put a few things on hold, and working on cacheboy was one of them.

The traffic node problem is more difficult. I had plenty of interest in running edge nodes in places like Australia, Italy and South Africa - where local connectivity is great, but international transit is not. But in order to run any useful amount of traffic from those nodes, I'll have to serve a lot of content to the network as a whole. This means "US" and "Western Europe".

I found myself in a catch-22 situation. I'd like to serve content across local IXes, but in order to do so, I first need to serve a lot more content to the US/Europe.

In order to do this, I'll need a few reliable nodes pushing at least a gigabit each. The last time I ran the numbers, more than 70% of traffic was destined to the US, UK and Germany.

So to properly push proper CDN of open source content, I'm going to need some donated nodes in the US that can source at least a gigabit. If I can't get that, the amount of traffic served to other destinations which could benefit from local traffic is .. well, it's really quite small.

So far, noone's stepped up to help with that.

More issues with Lighttpd

2009-11-10T19:14:00.000-08:00

So occasionally Lighttpd on FreeBSD-7.x+ZFS gets all upset. I -think- there's something weird going on where I hit mbuf exhaustion somehow when ZFS starts taking a long time to complete IO requests; then all socket IO fails in Lighttpd until it is restarted.

More investigation is required. Well, more statistics are needed so I can make better judgements. Well, actually, more functional backends are needed so I can take one out of production when something like this occurs, properly debug what is going on and try to fix it.

Cacheboy Update / October/November 2009

2009-11-10T18:53:00.000-08:00

Howdy,

Just a few updates this time around!

Cacheboy was pushing around 800-1200mbit during the Firefox 3.5.4 release cycle. I started to hit issues with the backend server not keeping up with revalidating requests and so I'll have to improve the edge caching logic a little more.
Lusca seems quite happy serving up 300-400mbit from a single node though; which is a big plus.
I've found some quite horrible memory leaks in Quagga on only one of the edge nodes. I'll have to find some time to login and debug this a little more.
The second backend server is now offically toast. I need to acquire another 1ru server with 2 SATA slots to magically appear in downtown Manhattan, NY.

Cacheboy downtime - hardware failures

2009-10-08T18:38:00.001-07:00

Howdy,

I've had both backend servers fail today. One is throwing undervolt errors on one PSU line and is having disk issues (most likely related to an undervoltage); the other is just crashed.

I'm waiting for remote hands to prod the other box into life.

This is why I'd like some more donated equipment and hosting - I can make things much more fault tolerant. Hint hint.

Lusca updates - September 2009

2009-09-30T23:31:00.000-07:00

Just a few Lusca related updates!

All of the Cacheboy CDN nodes are running Lusca-HEAD now and are nice and stable.
I've deployed Lusca at a few customer sites and again, it is nice and stable.
The rebuild logic changes are, for the most part, nice and stable. There seems to be some weirdness with 32 vs 64 bit compilation options which I need to suss out but everything "just works" if you compile Lusca with large file/large cache file support regardless of the platform you're using. I may make that the default option.
I've got a couple of small coding projects to introduce a couple of small new features to Lusca - more on those when they're done!
Finally, I'm going to be migrating some more of the internal code over to use the sqinet_t type in preparation for IPv4/IPv6 agnostic support.

Stay Tuned!

My current wishlist

2009-09-21T22:05:00.000-07:00

I'm going to put this on the website at some point, but I'm currently chasing a few things for Cacheboy:

More US nodes. I'll take anything from 50mbit to 5gbit at this point. I need more US nodes to be able to handle enough aggregate traffic to make optimising the CDN content selection methods worthwhile.
Some donations to cover my upcoming APNIC membership for ASN and IPv4/IPv6 space. This will run to about AUD $3500 this year and then around AUD $2500 a year after that.
Some 1ru/2ru server hardware in the San Francisco area
Another site or two willing to run a relatively low bandwidth "master" mirror site. I have one site in New York but I'd prefer to run a couple of others spread around Europe and the United States.

I'm sure more will come to mind as I build things out a little more.

New project - sugar labs!

2009-09-21T22:03:00.001-07:00

I've just put the finishing touches on the basic sugar labs software repository. I'll hopefully be serving part or all of their software downloads shortly.

Sugar is the software behind the OLPC environment. It works on normal intel based PCs as far as I can tell. More information can be found at http://www.sugarlabs.org/

Cacheboy presentation at AUSNOG

2009-08-31T22:50:00.001-07:00

I've just presented on Cacheboy at AUSNOG in Sydney. The feedback so far has been reasonably positive.

There's more information available at http://www.creative.net.au/talks/.

Cacheboy status update

2009-08-17T19:32:00.001-07:00

So by and large, the pushing of bits is working quite well. I have a bunch of things to tidy up and a DNS backend to rewrite in C or C++ but that won't stop the bits from being pushed.

Unfortunately what I'm now lacking is US hosts to send traffic from. I still have more Europe and Asian connectivity than North American - and North America is absolutely where I need connectivity the most. Right now I'm only able to push 350-450 megabits of content from North America - and this puts a big, big limit on how much content I can serve overall.

Please contact me as soon as possible if you're interested in hosting a node in North America. I ideally need enough nodes to push between a gigabit and ten gigabits of traffic.

I will be able to start pushing noticable amounts of content out of regional areas once I've sorted out North America. This includes places like Australia, Africa, South America and Eastern Europe. I'd love to be pushing more open source bits out of those locations to keep the transit use low but I just can't do so at the moment.

Canada node online and pushing bits!

2009-08-17T19:30:00.000-07:00

The Canada/TORIX node is online thanks to John Nistor at prioritycolo in Toronto, Canada.

Thanks John!

Cacheboy is on WAIX!

2009-08-17T18:55:00.001-07:00

Yesterday's traffic from mirror1.au into WAIX:

ASN	MBytes	Requests	% of overall
AS7545	17946.77	7437	29.85	TPG-INTERNET-AP TPG Internet Pty Ltd
AS4802	12973.47	4476	21.58	ASN-IINET iiNet Limited
AS4739	8497.92	2947	14.13	CIX-ADELAIDE-AS Internode Systems Pty Ltd
AS9543	2524.57	1241	4.20	WESTNET-AS-AP Westnet Internet Services
AS4854	2097.32	941	3.49	NETSPACE-AS-AP Netspace Online Systems
AS17746	1881.17	1050	3.13	ORCONINTERNET-NZ-AP Orcon Internet
AS9822	1425.44	456	2.37	AMNET-AU-AP Amnet IT Services Pty Ltd
AS17435	1161.01	411	1.93	WXC-AS-NZ WorldxChange Communications LTD
AS9443	1140.62	701	1.90	INTERNETPRIMUS-AS-AP Primus Telecommunications
AS7657	891.93	1187	1.48	VODAFONE-NZ-NGN-AS Vodafone NZ Ltd.
AS7718	740.74	272	1.23	TRANSACT-SDN-AS TransACT IP Service Provider
AS7543	732.11	423	1.22	PI-AU Pacific Internet (Australia) Pty Ltd
AS24313	527.38	252	0.88	NSW-DET-AS NSW Department of Education and Training
AS9790	436.80	389	0.73	CALLPLUS-NZ-AP CallPlus Services Limited
AS17412	365.13	228	0.61	WOOSHWIRELESSNZ Woosh Wireless
AS17486	349.27	116	0.58	SWIFTEL1-AP People Telecom Pty. Ltd.
AS17808	311.65	248	0.52	VODAFONE-NZ-AP AS number for Vodafone NZ IP Networks
AS24093	303.40	114	0.50	BIGAIR-AP BIGAIR. Multihoming ASN
AS9889	288.85	197	0.48	MAXNET-NZ-AP Auckland
AS17705	282.49	84	0.47	INSPIRENET-AS-AP InSPire Net Ltd

Query content served: 54878.07 mbytes; 23170 requests.
Total content served: 60123.25 mbytes; 28037 requests.

BGP aware DNS

2009-08-17T18:33:00.000-07:00

I've just written up the first "test" hack of BGP aware DNS.

The basic logic is simple but evil. I'm simply mapping BGP next-hop to a set of weighted servers. A server is then randomly chosen from this pool.

I'm not doing this for -all- prefixes and POPs - it is only being used for two specific POPs where there is a lot of peering and almost no transit. There are a few issues regarding split horizon BGP/DNS and request routing which I'd like to fully sort out before I enable it for everything. I don't want a quirk to temporarily redirect -all- requests to -one- server cluster!

In any case, the test is working well. I'm serving ~10mbit to WAIX (Western Australia) and ~ 30mbit to TORIX (Toronto, Canada.)

All of the DNS based redirection caveats apply - most certainly that not all client requests to the caches will also be over peering. I'll have to craft some method(s) of tracking this.

Updates - or why I've not been doing very much

2009-08-09T11:28:00.001-07:00

G'day! Cacheboy has been running on autopilot for the last couple of months whilst I've been focusing on paid work and growing my little company. So far (mostly) so good there.

The main issue scaling traffic has been the range request handling in Squid/Lusca, so I've been working on fixing things up "just enough" to make it work in the firefox update environment. I think I've finally figured it out - and figured out the bugs in the range request handling in Squid too! - so I'll push out some updates to the network next week and throw it some more traffic.

I really am hoping to ramp traffic up past the gigabit mark once this is done. We'll just have to see!

VLC 1.0 released

2009-07-08T09:53:00.000-07:00

VLC-1.0 has been released. The CDN is pushing out between 550 and 700mbit of VLC downloads. I'm sure it can do more but as I'm busy working elsewhere, I'm going to be overly conservative and leave the mirror weighting where it is.

Graphs to follow!

Current Downtime/issues

2009-06-29T01:36:00.000-07:00

There's a current issue with content not being served correctly. It stemmed from a ZFS related panic on one of the backend servers (note to self - update to the very latest FreeBSD-7-stable code; these are all fixed!) which then came up with lighttpd but no ZFS mounts. Lighttpd then started returning 404's.

I'm now watching the backend(s) throw random connection failures and the Lusca caches then cache an error rather than the object.

I've fixed the backend giving trouble so it won't start up in that failed mode again and I've set the negative caching in the Lusca cache nodes to 30 seconds instead of the default 5 minutes. Hopefully the traffic levels now pick up to where its supposed to be.

EDIT: The problem is again related to the Firefox range requests and Squid/Lusca's inability to cache range request fragments.

The backend failure(s) removed the objects from the cache. The problem now is that the objects aren't re-entering the cache because they are all range requests.

I'm going to wind down the Firefox content serving for now until I get some time to hack up Lusca "enough" to cache the range request objects. I may just do something dodgy with the URL rewriter to force a full object request to occur in the background. Hm, actually..

New mirror node - italy

2009-06-27T10:03:00.000-07:00

I've just turned on a new mirror node in Italy thanks to New Media Labs. They've provided some transit services and (I believe) 100mbit access to the local internet exchange.

Thanks guys!

And the GeoIP summary..

2009-06-17T07:26:00.000-07:00

And the geoip summary:

From Sun Jun 7 00:00:00 2009 to Sun Jun 14 00:00:00 2009

Country	MBytes	Requests
us	5163783.09	6533162
de	1514664.22	2307222
ca	1152095.00	917777
fr	948433.27	1451105
uk	945640.71	1136455
it	818161.03	770164
br	542497.79	1426306
se	482932.15	229559
es	445444.34	647321
pl	397755.30	1021083
nl	373185.13	306023
ru	368124.64	749924
tr	293627.27	484965
mx	276775.12	463252
be	249088.62	213460
ch	201782.33	209530
ro	190059.45	274216
fi	172399.75	204630
ar	170421.77	374071
no	169351.46	155258

A quick snapshot of Cacheboy destinations..

2009-06-16T18:17:00.000-07:00

The following is a snapshot of the per destination AS traffic information I'm keeping.

If you're peering with any of these ASes and are willing to sponsor a cacheboy node or two then please let me know. How well I can scale things at this point is rapidly becoming limited to where I can push traffic from, rather than anything intrinsic to the software.

From Sun Jun 7 00:00:00 2009 to Sun Jun 14 00:00:00 2009

ASN	MBytes	Requests	% of overall
AS3320	602465.01	1021975	3.26	DTAG Deutsche Telekom AG
AS7132	583164.05	778259	3.16	SBIS-AS - AT&T Internet Services
AS19262	459322.30	603127	2.49	VZGNI-TRANSIT - Verizon Internet Services Inc.
AS3215	330962.95	553299	1.79	AS3215 France Telecom - Orange
AS3269	317534.06	333114	1.72	ASN-IBSNAZ TELECOM ITALIA
AS9121	259768.32	434932	1.41	TTNET TTnet Autonomous System
AS22773	244573.65	283427	1.32	ASN-CXA-ALL-CCI-22773-RDC - Cox Communications Inc.
AS12322	224708.25	343686	1.22	PROXAD AS for Proxad/Free ISP
AS3352	206093.84	305183	1.12	TELEFONICADATA-ESPANA Internet Access Network of TDE
AS812	204120.74	166633	1.10	ROGERS-CABLE - Rogers Cable Communications Inc.
AS8151	198918.22	328632	1.08	Uninet S.A. de C.V.
AS6327	197906.53	152861	1.07	SHAW - Shaw Communications Inc.
AS3209	191429.18	303787	1.04	ARCOR-AS Arcor IP-Network
AS20115	182407.09	225151	0.99	CHARTER-NET-HKY-NC - Charter Communications
AS2119	181719.20	117656	0.98	TELENOR-NEXTEL T.net
AS577	181167.02	152383	0.98	BACOM - Bell Canada
AS12874	172973.42	108429	0.94	FASTWEB Fastweb Autonomous System
AS6389	165445.73	236133	0.90	BELLSOUTH-NET-BLK - BellSouth.net Inc.
AS6128	165183.07	210300	0.89	CABLE-NET-1 - Cablevision Systems Corp.
AS2856	164332.96	219267	0.89	BT-UK-AS BTnet UK Regional network

Query content served: 5234195.61 mbytes; 6878234 requests (ie, what was displayed in the table.)

Total content served: 18473721.25 mbytes; 26272660 requests (ie, the total amount of content served over the time period.)

Seeking a few more US / Canada hosts

2009-06-13T03:27:00.001-07:00

G'day everyone!

I'm now actively looking for some more Cacheboy CDN nodes in the United States and Canada. I've got around 3gbit of available bandwidth in Europe, 1gbit of available bandwidth in Japan but only 300mbit of available bandwidth in North America.

I'd really, really appreciate a couple of well-connected North American nodes so I can properly test the platform and software that I'm building. The majority of traffic is still North American in destination; I'm having to serve a fraction of it from Sweden and the United Kingdom at the moment. Erk.

Please drop me a line if you're interested. The node requirements are at http://www.cacheboy.net/node_requirements.html . Thankyou!

Another day, another firefox release done..

2009-06-12T21:41:00.000-07:00

The June Firefox 3.0.11 release rush is all but over and Cacheboy worked without much of a problem.

The changes I've made to the Lusca load shedding code (ie, being able to disable it :) works well for this workload. Migrating the backend to lighttpd (and fixing up the ETag generation to be properly consistent between 32 bit and 64 bit platforms) fixed the initial issues I was seeing.

The network pushed out around 850mbit at peak. Not a lot (heck, I can do that on one CPU of a mid-range server without a problem!) but it was a good enough test to show that things are working.

I need to teach Lusca a couple of new tricks, namely:

It needs to be taught to download at the fastest client speed, not the slowest; and
Some better range request caching needs to be added.

The former isn't too difficult - that is a weekend 5 line patch. The latter is more difficult. I don't really want to shoehorn in range request caching into the current storage layer. It would look a lot like how Vary and Etag is currently handled (ie, with "magical" store entries acting as indexes to the real backend objects.) I'd rather put in a dirtier hack that is easy to undo now and use the opportunity to tidy up the whole storage layer a whole lot. But the "tidying up" rant is not for this blog entry, its for the Lusca development blog.

The hack will most likely be a little logic to start downloading full objects that aren't in the cache when their first range request comes in - so subsequent range requests for those objects will be "glued" to the current request. It means that subsequent requests will "stall" until enough of the object is transferred to start satisfying their range request. The alternative is to pass through each range request to a backend until the full object is transferred and this would improve initial performance but there's a point where the backend could be overloaded with too many range requests for highly popular objects and that starts affecting how fast full objects are transferred.

As a side note, I should probably do up some math on a whiteboard here and see if I can model some of the potential behaviour(s). It would certainly be a good excuse to brush up on higher math clue. Hm..!

Migrating to Lighttpd on the backend, and why aren't my files being cached..

2009-06-11T22:31:00.001-07:00

I migrated away from apache-1.3 to Lighttpd-1.4.19 to handle the load better. Apache-1.3 handles lots of concurrent disk IO on large files fine but it bites for lots of concurrent network connections.

In theory, once all of the caching stuff is fixed, the backends will spend most of their time revalidating objects.

But for some weird reason I'm seeing TCP_REFRESH_MISS on my Lusca edge nodes and generally poor performance during this release. I look at the logs and find this:


[Host: mozilla.cdn.cacheboy.net\r\n
User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.9.0.10) Gecko/2009042316 Firefox/3.0.10\r\n
Accept: text/html,application/xhtml+xml,application/xml;q=0.9,*/*;q=0.8\r\n
Accept-Language: en-us,en;q=0.5\r\n
Accept-Charset: ISO-8859-1,utf-8;q=0.7,*;q=0.7\r\n
If-Modified-Since: Wed, 03 Jun 2009 15:09:39 GMT\r\n
If-None-Match: "1721454571"\r\n
Cache-Control: max-stale=0\r\n
Connection: Keep-Alive\r\n
Pragma: no-cache\r\n
X-BlueCoat-Via: 24C3C50D45B23509\r\n]

[HTTP/1.0 200 OK\r\n
Content-Type: application/octet-stream\r\n
Accept-Ranges: bytes\r\n
ETag: "1687308715"\r\n
Last-Modified: Wed, 03 Jun 2009 15:09:39 GMT\r\n
Content-Length: 2178196\r\n
Date: Fri, 12 Jun 2009 04:25:40 GMT\r\n
Server: lighttpd/1.4.19\r\n
X-Cache: MISS from mirror1.jp.cacheboy.net\r\n
Via: 1.0 mirror1.jp.cacheboy.net:80 (Lusca/LUSCA_HEAD)\r\n
Connection: keep-alive\r\n\r]

Notice the different ETags? Hm! I wonder whats going on. On a hunch I checked the Etags from both backends. master1 for that object gives "1721454571"; master2 gives "1687308715". They both have the same size and same timestamp. I wonder what is different?

Time to go digging into the depths of the lighttpd code.

EDIT: the etag generation is configurable. By default it uses the mtime, inode and filesize. Disabling inode and inode/mtime didn't help. I then found that earlier lighttpd versions have different etag generation behaviour based on 32 or 64 bit platforms. I'll build a local lighttpd package and see if I can replicate the behaviour on my 32/64 bit systems. Grr.

Meanwhile, Cacheboy isn't really serving any of the mozilla updates. :(

EDIT: so it turns out the bug is in the ETag generation code. They create an unsigned 32-bit integer hash value from the etag contents, then shovel it into a signed long for the ETag header. Unfortunately for FreeBSD-i386, "long" is a signed 32 bit type, and thus things go airy from time to time. Grrrrrr.

EDIT: fixed in a newly-built local lighttpd package; both backend servers are now doing the right thing. I'm going back to serving content.

New mirrors - mirror2.uk and mirror3.uk

2009-06-02T22:49:00.000-07:00

I've just had two new sponsors show up with a pair of UK mirrors.

mirror2.uk is thanks to UK Broadband, who have graciously given me access to a few hundred megabits of traffic and space on an ESX server.

mirror3.uk (due to be turned up today!) is thanks to a private donor named Alex who has given me a server in his colocation space and up to a gigabit of traffic.

Shiny! Thanks to you both.

More traffic!

2009-04-22T06:14:00.001-07:00

970mbit and rising...!

mirror1.jp.cacheboy.net - mozilla!

2009-04-22T05:36:00.000-07:00

The nice folk at mozilla.org have provided me with a .jp CDN node. I'm now serving a good stack of bits from it into Australia, Malaysia, India, Japan, China, Korea and the Phillipines.

Thanks guys!

Mozilla 3.0.9 release..

2009-04-22T05:34:00.000-07:00

The mozilla release (3.0.9) is currently going on. The traffic levels are ramping up now to the release peak.

880mbit/sec and counting..

Lusca and Cacheboy improvements in the pipeline..

2009-04-06T01:10:00.000-07:00

After profiling Lusca-HEAD rather extensively on the CDN nodes, I've discovered that the largest CPU "use" on the core 2 duo class boxes is memcpy(). On the ia64-2 node memcpy() shows up much lower down in the list. I'm sure this has to do with the differing FSB and general memory bus bandwidth available on the two architectures.

I'm planning out the changes to the store client needed to support fully copy-free async read and write. This should reduce the CPU overhead on core 2 duo class machines to the point where Lusca should break GigE throughput on this workload without too much CPU use. (I'm sure it could break GigE throughput right now on this workload though.)

I'll code this all up during the week and build a simulated testing rig at home "pretending" to be a whole lot of clients downloading partial bits of mozilla/firefox updates, complete with a random packetloss, latency and abort probability.

I also plan on finally releasing the bulk of the Cacheboy CDN software (hackish as it is!) during the week, right after I finally remove the last few bits of hard-coded configuration locations. :) I still haven't finished merging in the bits of code which do the health check, calculate the current probabilities to assign each host and then write out the geoip map files. I'll try to sort that out over the next few days and get a public subversion repository with the software online.

By the way, I plan on releasing the Cacheboy CDN software under the Affero GPL (AGPL) licence.

Lusca snapshot released

2009-03-31T22:11:00.000-07:00

I've just put up a snapshot of the version of lusca-head which is running on the cacheboy cdn. Head to http://code.google.com/p/lusca-cache/downloads/list .

Mirroring a new project - Cyberduck!

2009-03-30T14:33:00.000-07:00

I've just started providing mirror download services for Cyberduck - a file manager for a wide variety of platforms including the traditional (SFTP, FTP) and the new (Amazon/S3, WebDAV.) Cacheboy is listed as the primary download site on the main page.

Woo!

Mozilla 3.0.8 release!

2009-03-30T14:26:00.000-07:00

The CDN handled the load with oodles to spare. The aggregate client traffic peak was about 650mbit across 5 major boxes. The boxes themselves peaked at about 160mbit each, depending upon the time of day (ie, whether Europe or the US was active.) None of the nodes were anywhere near maximum CPU utilisation.

About 2 and a half TB of mozilla updates a day are being shuffled out.

I'd like to try pushing a couple of the nodes up to 600mbit -each- but I don't have enough CDN nodes to guarantee the bits will keep flowing if said node fails. I'll just have to be patient and wait for a few more sponsors to step up and provide some hardware and bandwidth to the project.

So far so good - the bits are flowing, I'm able to use this to benchmark Lusca development and fix performance bottlenecks before they become serious (in this environment, at least) and things are growing at about the right rate for me to not need to panic. :)

My next major goal will be to finish off the BGP library and lookup daemon; flesh out some BGP related redirection map logic; and start investigating reporting for "services" on the box. Hm, I may have to write some nagios plugins after all..

shortcomings in the async io code

2009-03-28T16:05:00.000-07:00

Profiling the busy(ish) Lusca nodes during the Mozilla 3.0.8 release cycle has shown significant CPU wastage in memset() (ie, 0'ing memory) - via the aioRead and aioCheckCallbacks code paths.

The problem stems from the disk IO interface inherited from Squid. With Squid, there's no explicit cancel-and-wait-for-cancel to occur with both the network and disk IO code, so the async disk IO read code would actually allocate its own read buffer, read into that, and then provide said read buffer to the completion callback to copy said read data out of. If the request is cancelled but the worker thread is currently read()'ing data, it'll read into its own buffer and not a potentially free()'d buffer from the owner. Its a bit inefficient but in the grand scheme of Squid CPU use, its not that big a waste on modern hardware.

In the short term, I'm going to re-jig the async IO code to not zero buffers that are involved in the aioRead() path. In the longer term, I'm not sure. I prefer cancels which may fail - ie, if an operation is in progress, let it complete, if not then return immediately. I'd like this for the network code too, so I can use async network IO threads for less copy network IO (eg FreeBSD and aio_read() / aio_write()); but there's significant amounts of existing code which assumes things can be cancelled immediately and assumes temporary copies of data are made everywhere. Sigh.

Anyway - grr'ing aside, fixing the pointless zero'ing of buffers should drop the CPU use for large file operations reasonably noticably - by at least 10% to 15%. I'm sure that'll be a benefit to someone.

Googletalk: "Getting C++ threads to work right"

2009-03-28T15:14:00.000-07:00

I've been watching a few Google dev talks on Youtube. I thought I'd write up a summary of this one:

http://www.youtube.com/watch?v=mrvAqvtWYb4

In summary:

Writing "correct" thread code using the pthreads and CPU instructions (fencing, for example) requires the code to know whats going on under the hood;
Gluing concurrency to the "side" of a language which was specified without concurrency has shown to be a bit of a problem - eg, concurrent access to different variables in a structure and how various compilers have implemented this (eg, changing a byte in a struct becoming a 32 bit load, 8 bit modify, 32 bit store);
Most programmers should really use higher level constructs, like what C++0x and what the Java specification groups have been doing.

If you write threaded code or you're curious about it, you should watch this talk. It provides a very good overview of the problems and should open your mind up a little to what may go wrong..

Another open cdn project - mirrorbrain

2009-03-27T14:21:00.000-07:00

I've been made aware of Mirrorbrain (http://mirrorbrain.org), another project working towards an open CDN framework. Mirrorbrain uses Apache as the web server and some apache module smarts to redirect users between mirrors.

I like it - I'm going to read through their released source and papers to see what clue can be crimed from them - but they still base the CDN on an untrusted, third-party mirror network out of their control. I still think the path forward to an "open CDN" involves complete control right out to the mirror nodes and, in some places, the network which the mirror nodes live on.

There's a couple of shortcomings - most notably, their ASN implementation currently uses snapshots of the BGP network topology table rather than a live BGP feed distributed out to each mirror and DNS node. They also store central indexes of files and attempt to maintain maps of which mirror nodes have which updated versions of files, rather than building on top of perfectly good HTTP/1.1 caching semantics. I wonder why..

Example CDN stats!

2009-03-23T14:57:00.000-07:00

Here's a snapshot of the global aggregate traffic level:

.. and top 10 AS stats from last Sunday (UTC) :

wiki.cacheboy.net

2009-03-22T17:13:00.000-07:00

I've setup http://wiki.cacheboy.net/, a simple mediawiki install which will serve as a place for me to braindump stuff into.

More "Content Delivery" done open

2009-03-19T14:30:00.000-07:00

Another network-savvy guy in Europe is doing something content-delivery related: http://www.as250.net/ .

AS250 is building a BGP anycast based platform for various 'open' content delivery and other applications. I plan on doing something similar (or maybe just partner with him, I'm not sure!) but anycast is only part of my over-all solution space.

He's put up some slides from a presentation he did earlier in the year:

http://www.trex.fi/2009/as250-anycast-bgp.pdf

Filesystem Specifications, or EXT4 "Losing Data"

2009-03-19T12:24:00.001-07:00

This is a bit off-topic for this blog, but the particular issue at hand bugs the heck out of me.

EXT4 "meets" the POSIX specifications for filesystems. The specification does not make any requirements for data to be written out in any order - and for very good reason. If the application developer -requires- data to be written out in order, they should serialise their operations through use of fsync(). If they do -not- require it, then the operating system should be free to optimise away the physical IO operations.

As a clueful(!) application developer, -I- appreciate being given the opportunity to provide this kind of feedback to the operating system. I don't want one or the other. I'd like to be able to use both where and when I choose.

Application developers - stop being stupid. Fix your applications. Read and understand the specification and what it provides -everyone- rather than just you.

Breaking 200mbit..

2009-03-16T16:29:00.001-07:00

The CDN broke 200mbit at peak today - roughly half mozilla and half videolan.

200mbit is still tiny in the grand scheme of things, but it proves that things are working fine.

The next goal is to handle 500mbit average traffic during the the day, and keep a very close eye on the overheads in doing so (specifically - making sure that things don't blow up when the number of concurrent clients grows.)

GeoIP backend, or "reinventing the wheel"

2009-03-16T15:27:00.001-07:00

The first incantation of the Cacheboy CDN uses 100% GeoIP to redirect users. This is roughly how it goes:

Take a GeoIP map to break up IPs into "country" regions (thanks nerd.dk!) ;
Take the list of "up" CDN nodes;
For each country in my redirection table, find the CDN node that is up with the highest weight;
Generate a "geo-map" file consisting of the highest-weight "up" CDN node for each country in "3";
Feed that to the PowerDNS geoip module (thanks Mark @ Wikipedia!)

This really is a good place to start - its simple, its tested and it provides me with some basic abilities for distributing traffic across multiple sites to both speed up transfer times to end-users and better use the bandwidth available. The trouble is that it knows very little about the current state of the "internet" at any point in time. But, as I said, as a first (coarse!) step to get the CDN delivering bits, it worked out.

My next step is to build a much easier "hackable" backend which I can start adding functionality to. I've reimplemented the geoip backend in Perl and glued it to the "pipe-backend" module in PowerDNS. This simply passes DNS requests to an external process which spits back DNS replies. The trouble is that multiple backend processes will be invoked regardless of whether you want to or not. This means that I can't simply load in large databases into the backend process as it'll take time to load, waste RAM, and generally make things scale (less) well.

So I broke out the first memory hungry bit - the "geoip" lookup - and stuffed it into a small C daemon. All the daemon does is take a client IP and answer the geoip information for that IP. It will periodically check and reload the GeoIP database file in the background if its changed - maintaining whatever request rate I'm throwing at it rather than pausing for a few seconds whilst things are loaded in.

I can then use the "geoip daemon" (lets call it "geoipd") by the PowerDNS pipe-backend process I'm writing. All this process has to do at the moment is load in the geo maps (which are small) and reload them as required. It sends all geoip requests to the geoipd and uses the reply. If there is a problem talking to the geoipd, the backend process will simply use a weighted round robin of well-connected servers as a last resort.

The aim is to build a flexible backend framework for processing redirection requests which can be used by a variety of applications. For example, when its time for the CDN proxy nodes to also do 302 redirections to "closer" nodes, I can simply reuse a large part of the modular libraries written. When I integrate BGP information into the DNS infrastructure, I can reuse all of those libraries in the CDN proxy redirection logic, or the webserver URL rewriting logic, or anywhere else where its needed.

The next step? Figuring out how to load balance traffic destined to the same AS / GeoIP region across multiple CDN end nodes. This should let me scale the CDN up to a gigabit of aggregate traffic given the kind of sponsored boxes I'm currently receiving. More to come..

Downtime!

2009-03-13T22:09:00.001-07:00

The CDN had a bit of downtime tonight. It went like this:

The first mirror threw a disk;
For some reason, gmirror became unhappy, rather than running on the second mirror (I'm guessing the controller went unhappy; there wasn't anything logged to indicate the other disk in the mirror set was failing);
The second mirror started taking load;
For some weird reason, the second mirror hung hard without any logging to explain why.

I've replaced the disks in mirror1 and its slowly rebuilding the content. It probably won't be finished resync'ing the (new) mirror set until tomorrow. Hopefully mirror-2 will stay just as stable as it currently is.

The CDN ended up still serving content whilst the masters were down - they just couldn't download uncached content. So it wasn't a -total- loss.

This just highlights that I really do require another mirror master or two located elsewhere. :)

minimising traffic to the backends..

2009-03-09T22:11:00.000-07:00

Squid/Cacheboy/Lusca has a nifty feature where it'll "piggyback" a client connection on an existing backend connection if the backend response is cachable AND said response is valid for the client (ie, its the right variant, doesn't require revalidation at that point, etc.)

I've been using this for the videolan and mozilla downloads. Basically, one client will suck down the whole object, and any other clients which want the same object (say, the 3.0.7 US english win32 update!) will share the same connection.

There's a few problems which have crept up.

Firstly - the "collapsed forwarding" support is not working in this instance. I think the logic is broken with large objects (it was only written for small objects, delaying forwarding the request until the forwarded response was known cachable) where it denies cachability of the response (well, it forces it to be RELEASEd after it finishes transferring) because of all of the concurrent range requests going on.

Secondly - Squid/Cacheboy/Lusca doesn't handle range request caching. It'll -serve- range responses for objects it has the data for, but it won't cache partial responses nor will it reassemble them into one chunk. I've been thinking about how to possibly fix that, but for now I'm hacking around the problems with some scripts.

Finally - the forwarding logic uses the speed of the -slowest- client to determine how quickly to download the file. This needs to be changed to use the speed of the -fastest- client to determine how quickly to download said file.

I need to get these fixed before the next mozilla release cycle if I'm to have a chance of increasing the traffic levels to a gigabit and beyond.

More to come..

Cacheboy Outage

2009-03-09T22:08:00.001-07:00

There was a brief outage earlier tonight due to some troubles with the transit provider of one of my sponsors. They're sponsoring the (only) pair of mirror master servers at the moment.

This will be (somewhat) mitigated when I bring up another set of mirror master servers elsewhere.

Cacheboy is pushing bits..

2009-03-08T23:19:00.001-07:00

The Cacheboy CDN is currently pushing about 1.2 TB a day (~ 100mbit average) of mozilla and videolan downloads out of 5 seperate CDN locations. A couple of the servers are running LUSCA_HEAD and they seem to handle the traffic just fine.

The server assignment is currently being done through GeoIP mapping via DNS. I've brought up BGP sessions to each of the sites to eventually use in the request forwarding process.

All in all, things are going reasonably successfully so far. There's been a few hiccups which I'll blog about over the next few days but the bits are flowing, and noone is complaining. :)

Cacheboy CDN is online!

2009-02-27T23:04:00.000-08:00

There's been a few changes!

* The "Cacheboy proxy" development has become Lusca; thats spun off into a little separate project of its own.
* The "Cacheboy" project is now focusing on providing an open source platform for content delivery. I've organised some donated hardware (some donated by me), some donated bandwidth (again, some donated by me) and a couple of test projects to serve content for.

More details to come!

(As a side note, I've got too many blogs; I think its time to rationalise them down to one or two and use labels to correctly identify which is which.)

Lusca and BGP, take 2.

2009-02-23T23:10:00.001-08:00

I've ironed out the crash kinks (the rest of the "kinks" are in the BGP FSM implementation); thus I'm left with:

1235459412.856 17063 118.92.109.x TCP_REFRESH_HIT/206 33405 GET http://videolan.cdn.cacheboy.net/vlc/0.9.8a/win32/vlc-0.9.8a-win32.exe - NONE/- application/x-msdownload AS7657
1235459417.194 1113 202.150.98.x TCP_HIT/200 45637 GET http://videolan.cdn.cacheboy.net/vlc/0.9.8a/win32/vlc-0.9.8a-win32.exe - NONE/- application/x-msdownload AS17746

Notice how the Squid logs have AS numbers in them? :)

Lusca and BGP

2009-02-23T08:46:00.001-08:00

I've been fleshing out some very, very basic BGP support in a lusca-head branch. I'm only using the BGP information right now for logging but I'll eventually use it as part of the request and reply processing.

It *cough* mostly works. I need to figure out why there's occasional radix tree corruption (which probably means running it under valgrind to find when the radix code goes off the map..) and un-dirty some of the BGP code (ie, implement a real FSM; proper separation of the protocol handling, FSM, network and RIB code) and add in the AS path/community/attribute stuff before I commit it to LUSCA_HEAD.

It is kind of cool though having a live BGP feed in your application. :) All 280,000 odd routes of it. :)

Lusca development, and changes to string handling

2009-02-01T21:36:00.001-08:00

I've just renamed Cacheboy to "Lusca". I've had a few potential users comment that "Cacheboy" isn't uhm, "management compatible", so the project has been renamed to try and bring some of these users on board. I'm also hoping to make Lusca less Adrian-focused and involve more of the community. We'll see how that goes.

In terms of development, I've shifted the code to http://code.google.com/p/lusca-cache/ and I'm continuing my work in /branches/LUSCA_HEAD.

I've been working on src/http.c (the server-side HTTP code) in preparation for introducing reference counted buffer/string handling. I removed one copy (of the socket read buffer into another memory buffer, to assemble a buffer containing the HTTP reply, in preparation for parsing) and have just migrated that bit of the codebase over to use my reference counted buffer (buf_t; found in libmem/buf.[ch].) It's entirely possible that I've horribly broken the server-side code so I'm reluctant to do much else until I've finished restructuring and testing the server-side HTTP code.

I've also been tidying up a few more places where the current String API is used "incorrectly", at least incorrectly for reference counted strings/buffers. I have ~ 61 code chunks to rewrite, mostly in the logging code. I've done it twice already in other branches, so this won't be terribly difficult. Its just boring. :)

Oh, and I've also just removed the "caching" bits of the MemPools code. MemPools in LUSCA_HEAD is now just a small wrapper around malloc/calloc/free, mainly to preserve the "block allocator" style API and keep some statistics. At the end of the day, Squid uses memory very very poorly and the caching code in MemPools is purely to avoid said poor memory use. I'm going to just fix the memory use (mostly revolving around String buffers, HTTP headers and the TLV code, amazing that!) so the number of calls through the allocator is much, much reduced. I'm guessing once I've finished, the number of calls through the system allocator will be about 2 or 3% of what they are now. That should drop the CPU use quite a bit.

Ah, now to find testers..

Where the CPU is going

2009-01-20T15:31:00.000-08:00

Oprofile is fun.

So, lets find out all of the time spent in cacheboy-head, per-symbol, with accumulative time, but only showing symbols taking 1% or more of CPU:


root@jennifer:/home/adrian/work/cacheboy/branches/CACHEBOY_HEAD/src# opreport -la -t 1 ./squid
CPU: PIII, speed 634.485 MHz (estimated)
Counted CPU_CLK_UNHALTED events (clocks processor is not halted) with a unit mask of 0x00 (No unit mask) count 90000
samples  cum. samples  %        cum. %     image name               symbol name
2100394  2100394        6.9315   6.9315    libc-2.3.6.so            memcpy
674036   2774430        2.2244   9.1558    libc-2.3.6.so            vfprintf
657729   3432159        2.1706  11.3264    squid                    memPoolAlloc
463901   3896060        1.5309  12.8573    libc-2.3.6.so            _int_malloc
453978   4350038        1.4982  14.3555    libc-2.3.6.so            strncasecmp
442439   4792477        1.4601  15.8156    libc-2.3.6.so            re_search_internal
438752   5231229        1.4479  17.2635    squid                    comm_select
423196   5654425        1.3966  18.6601    squid                    memPoolFree
418949   6073374        1.3826  20.0426    squid                    stackPop
412394   6485768        1.3609  21.4036    squid                    httpHeaderIdByName
402709   6888477        1.3290  22.7325    libc-2.3.6.so            strtok
364201   7252678        1.2019  23.9344    squid                    httpHeaderClean
359257   7611935        1.1856  25.1200    squid                    statHistBin
343628   7955563        1.1340  26.2540    squid                    SQUID_MD5Transform
330128   8285691        1.0894  27.3434    libc-2.3.6.so            memset
323962   8609653        1.0691  28.4125    libc-2.3.6.so            memchr

Ok, thats sort of useful. Whats unfortunate is that there's uhm, a lot more symbols than that:


root@jennifer:/home/adrian/work/cacheboy/branches/CACHEBOY_HEAD/src# opreport -la ./squid | wc -l
595

Ok, so thats a bit annoying. 16 symbols take ~ 28% of the CPU time, but the other 569 odd take the ~ 72% remaining CPU. This sort of makes traditional optimisation techniques a bit pointless now. I've optimised almost all of the "stupid" bits - double/triple copying of data, over-allocating and freeing pointlessly, multiple parsing attempts, etc.

How many samples in total?


root@jennifer:/home/adrian/work/cacheboy/branches/CACHEBOY_HEAD/src# opreport -l ./squid | cut -f1 -d' ' | awk '{ s+= $1; } END { print s }'
30302294

Lets look now at what memcpy() is doing, just to get an idea of what needs to be changed


root@jennifer:/home/adrian/work/cacheboy/branches/CACHEBOY_HEAD/src# opreport -lc -t 1 -i memcpy ./squid
CPU: PIII, speed 634.485 MHz (estimated)
Counted CPU_CLK_UNHALTED events (clocks processor is not halted) with a unit mask of 0x00 (No unit mask) count 90000
samples  %        image name               symbol name
-------------------------------------------------------------------------------
 28133     1.3394  squid                    storeSwapOut
 31515     1.5004  squid                    stringInit
 32619     1.5530  squid                    httpBuildRequestPrefix
 54237     2.5822  squid                    strListAddStr
 54322     2.5863  squid                    storeSwapMetaBuild
 80047     3.8110  squid                    clientKeepaliveNextRequest
 171738    8.1765  squid                    httpHeaderEntryParseCreate
 211091   10.0501  squid                    httpHeaderEntryPackInto
 318793   15.1778  squid                    stringDup
 1022812  48.6962  squid                    storeAppend
2100394  100.000  libc-2.3.6.so            memcpy
 2100394  100.000  libc-2.3.6.so            memcpy [self]
------------------------------------------------------------------------------

So hm, half the memcpy() CPU time is spent in storeAppend, followed by storeDup, and httpHeaderEntryPackInto. Ok, those are what I'm going to be working on eliminating next anyway, so its not a big deal. This means I'll eliminate ~ 73% of the memcpy() CPU time, which is 73% of 7%, so around 5% of CPU time. Not too shabby. There'll be some overheads introduced by how its done (referenced buffer management) but one of the side-effects of that should be a drop in the number of calls to the memory allocator functions, so they should drop off a bit.

But this stuff is still just micro-optimisation. What I need is an idea of what code -paths- are taking up precious CPU time and thus what I should consider first to reimplement. Lets use the "-t" on non-top-level symbols. To start with, lets look at the two top-level "read" functions, which generally lead to some kind of other processing.

root@jennifer:/home/adrian/work/cacheboy/branches/CACHEBOY_HEAD/src# opreport -lc -t 1 -i clientReadRequest ./squid
CPU: PIII, speed 634.485 MHz (estimated)
Counted CPU_CLK_UNHALTED events (clocks processor is not halted) with a unit mask of 0x00 (No unit mask) count 90000
samples  %        symbol name
-------------------------------------------------------------------------------
  87536     4.7189  clientKeepaliveNextRequest
  1758418  94.7925  comm_select
88441    100.000  clientReadRequest
  2121926  86.3731  clientTryParseRequest
  88441     3.6000  clientReadRequest [self]
  52951     2.1554  commSetSelect
-------------------------------------------------------------------------------


root@jennifer:/home/adrian/work/cacheboy/branches/CACHEBOY_HEAD/src# opreport -lc -t 1 -i httpReadReply ./squid
CPU: PIII, speed 634.485 MHz (estimated)
Counted CPU_CLK_UNHALTED events (clocks processor is not halted) with a unit mask of 0x00 (No unit mask) count 90000
samples  %        symbol name
-------------------------------------------------------------------------------
  3962448  99.7463  comm_select
163081   100.000  httpReadReply
  2781096  53.2193  httpAppendBody
  1857597  35.5471  httpProcessReplyHeader
  163081    3.1207  httpReadReply [self]
  57084     1.0924  memBufGrow
------------------------------------------------------------------------------

Here we're not interested in who is -calling- these functions (since its just the comm routine :) but which functions this routine is calling. The next trick, of course, is to try and figure out which of these paths are taking a noticable amount of CPU time. Obviously httpAppendBody() and httpProcessReplyHeader() are; they're doing both a lot of copying and a lot of parsing.

I'll look into things a little more in-depth in a few days; I need to get back to paid work. :)

Eliminating copies, or "god this code is horrible"

2009-01-19T20:09:00.002-08:00

I've been (slowlyish!) unwinding some of the evil horridness that exists in the src/http.c code which handles reading data from upstream servers/caches, parsing it, and throwing it into the store.

There's two annoying memory copies as I've said before - one was a copy of the incoming data into a MemBuf, used -just- to assemble the full response headers for parsing, and the other (well, other two) are for appending the data coming in from the network into the memory store, on its way to the client-side code to be sent back to the client.

Now, as I've said before, the src/http.c code isn't all that long and complicated (by far most of the logic actually happens in the forward and client-side routines; the http.c routines do very little besides pump data back into the memory store) but unfortunately enough various layers of logic are mashed together to make things uhm, "very difficult" to work on separately.

Anyway, back on track. I've mostly pulled apart the code which handles reading the reply and parsing the response headers, and I've eliminated the first copy. The data is now read directly into a MemBuf, which serves as both the incoming buffer (which gets appended to) for the reply status line + headers, _AND_ the incoming buffer for HTTP body data (which never gets appended to - it is written out to the memory store and then reset back to empty.)

So the good news now is the number one place for L2 loads, L2 stores and CPU cycles spent unhalted (as measured on my P3 667mhz celeron test box, nice and slow, to expose all those stupid inefficiencies modern CPUs try to cover up :) comes from the memcpy() from src/http.c -> { header parsing (12%), http body appending (84%) } -> storeAppend().

This means one main thing - if I can eliminate the copying from into the store, and instead read directly into variable-sized pages (which is unfortunately the bloody tricky part), which are then handed to their entirety to the memory store, that last memcpy() will be eliminated, along with hopefully a good 10 + % of CPU time on this P3.

After that, its fixing the various uses of *printf() functions in the critical path, which absolutely should be avoided. I've got some basic patches to begin replacing some of the really STUPID uses of those. I'll begin committing the really obviously easy ones to Cacheboy HEAD once I've verified they don't break anything (in particular, SNMP indexes of all things..)

Once the two above are done, which accounts for a good 15 - 20% of the current CPU use in Cacheboy (at least in my small objects, memory-cache-only test load on the above hardware), I'll absolutely stop adding any and all new changes, features, optimisations, etc, and go -straight- to "make everything stable" mode again.

There's still so much that needs doing (proper refcounted buffers and strings, comm library functions which properly implement readv() and writev() so I can do things like write out the entire request/reply using vector operations and avoid the other bits of copying which go on, lessening the load on the memory allocator by actually efficiently packing structures, rewriting the http request/reply handling in preparation for replacement HTTP client/server modules, oh and IPv6/threading!) but that will come later.

Eliminating copies, or "god this code is horrible"

2009-01-19T20:09:00.001-08:00

Tidying up the http reply handling code..

2009-01-18T12:28:00.001-08:00

One of the unfortunate parts of the Squid codebase is that the HTTP request and reply handling code is messed up with the client and server code, and contains both stuff specific to a Cache (eg, looking for headers to control cache behaviour) as well as connection stuff (eg Transfer Encoding stuff, Keepalive, etc.)

My long-term goal is to finally separate all of this mess out so there's "generic" routines to be a HTTP client and server, create requests/replies and parse responses. But for now, tidying up some of the messy code to improve performance (and thus give people motivation to migrate their busy sites to Cacheboy) is on my short-term TODO list.

I spent some time ~ 18 months ago tidying up all of the client-side code so the request line and request header parsing didn't require half a dozen copies of various things just to complete. That was quite successful. The code structure is still horrible, but it works, and that for now is absolutely the most important part.

Now I'm doing something similar to the server-side code. The HTTP server code (src/http.c) combines both reply buffer appending, parsing, 100-continue response handling (well, "handling") and the various header checks for caching and connection in one enormous puddle of code. I'm trying to tease these apart so each part is done separately and the reply data isn't double-copied - once into the reply buffer, then once via storeAppend() into the memory store.

The CPU time spent doing this copying isn't all that high on current systems but it is definitely noticable (~30% of all CPU time spent in memcpy()) for slower systems talking to LAN-connected servers. So I'm going to do it - primarily to fix performance on slower hardware, but it also forces me to tidy up the existing code somewhat.

The next step is avoiding the copy into the memory store entirely, removing another 65% or so of memcpy() CPU time.

Refcounted string buffers!

2009-01-16T10:41:00.000-08:00

Those of you who have been watching may have noticed a few String tidyups going into CACHEBOY_HEAD recently (one of which caused a bug in the first cacheboy-1.6 stable release that made it very non-stable!)

This is all in preparation for more sensible string and buffer handling. Unfortunately the Cacheboy codebase inherited a lot of dirty string handling and it needed some house cleaning before I could look towards the future.

Well, the future is here now (well, in /svn/branches/CACHEBOY_HEAD_strref ...) - I brought in my refcounted buffer routines from my previous attempts at all of this and converted String.[ch] over to use it.

For now, the refcounted string implementation doubles the malloc overhead for new strings (since it has to create a small buf_t and a string buffer) but stringDup() becomes essentially free. Since in a lot of cases, the stringDup() occurs when copying string headers and basically leaving them alone, this saves on a bunch of memory copying.

Decent performance benefits will only come with a whole lot of work:

Remove all of the current assumptions in code which uses String that the actual backing buffer (accessible via strBuf()) is NUL-terminated;
Rewrite sections of the code which go between String and C string buffers (with copying, etc) to use String where applicable. Unfortunately a whole lot of the original client_side.c code which handles parsing the request involves a fair bit of crap - so..
.. writing replacement request and reply HTTP parsers is probably the next thing to do;
Shuffling around the client-side code and the http code to use a buf_t as a incoming socket buffer, instead of how they currently do things (in an ugly way..)
Propagate down the incoming socket buffer to the request/reply parsing code, so said code can simply create references to the original socket buffer, bypassing any and all requirement for copying the request/reply data seperately.

I'm reasonably excited about the future benefits this code holds, but for now I'm going to remain reasonably conservative and leave the current String improvements where they are. I don't mind if these and the next round of changes to the MemBuf code reduce performance but improve the code; I know that the medium-term goal is going to provide some pretty decent benefits and I want to keep things stable and usable in production whilst I get there.

Next on my list though; looking at removing the places where *printf() is used in critical sections..

More profiling!

2009-01-09T07:08:00.000-08:00

The following info is for a 10,000 concurrent connections, keep-alived, of just a fetch of an internal icon object from Squid. This is using my apachebench-adrian package which can handle such traffic loads.

The below accounts for roughly 60% of total CPU time (ie, 60% of the CPU is spent in userspace) on one core.
With oprofile, it hits around 12,300 transactions a second.

I have much, much hatred for how Squid uses *printf() everywhere. Sigh.



CPU: AMD64 processors, speed 2613.4 MHz (estimated)
Counted CPU_CLK_UNHALTED events (Cycles outside of halt state) with a unit mask of 0x00 (No unit mask) count 100000
samples  cum. samples  %        cum. %     image name               symbol name
5383709  5383709        4.5316   4.5316    libc-2.6.1.so            vfprintf
4025991  9409700        3.3888   7.9203    libc-2.6.1.so            memcpy
3673722  13083422       3.0922  11.0126    libc-2.6.1.so            _int_malloc
3428362  16511784       2.8857  13.8983    libc-2.6.1.so            memset
3306571  19818355       2.7832  16.6815    libc-2.6.1.so            malloc_consolidate
2847887  22666242       2.3971  19.0787    squid                    memPoolFree
2634120  25300362       2.2172  21.2958    libm-2.6.1.so            floor
2609922  27910284       2.1968  23.4927    squid                    memPoolAlloc
2408836  30319120       2.0276  25.5202    libc-2.6.1.so            re_search_internal
2296612  32615732       1.9331  27.4534    libc-2.6.1.so            strlen
2265816  34881548       1.9072  29.3605    libc-2.6.1.so            _int_free
1826493  36708041       1.5374  30.8979    libc-2.6.1.so            _IO_default_xsputn
1641986  38350027       1.3821  32.2800    libc-2.6.1.so            free
1601997  39952024       1.3484  33.6285    squid                    httpHeaderGetEntry
1575919  41527943       1.3265  34.9549    libc-2.6.1.so            memchr
1466114  42994057       1.2341  36.1890    libc-2.6.1.so            re_string_reconstruct
1275377  44269434       1.0735  37.2625    squid                    clientTryParseRequest
1214714  45484148       1.0225  38.2850    squid                    httpMsgFindHeadersEnd
1185932  46670080       0.9982  39.2832    squid                    statHistBin
1170361  47840441       0.9851  40.2683    squid                    urlCanonicalClean
1169694  49010135       0.9846  41.2529    libc-2.6.1.so            strtok
1145933  50156068       0.9646  42.2174    squid                    comm_select
1128595  51284663       0.9500  43.1674    libc-2.6.1.so            __GI_____strtoll_l_internal
1116573  52401236       0.9398  44.1072    squid                    httpHeaderIdByName
956209   53357445       0.8049  44.9121    squid                    SQUID_MD5Transform
915844   54273289       0.7709  45.6830    squid                    memBufAppend
907609   55180898       0.7640  46.4469    squid                    stringLimitInit
898666   56079564       0.7564  47.2034    libc-2.6.1.so            strspn
883282   56962846       0.7435  47.9468    squid                    urlParse
852875   57815721       0.7179  48.6647    libc-2.6.1.so            calloc
819613   58635334       0.6899  49.3546    squid                    clientWriteComplete
800196   59435530       0.6735  50.0281    squid                    httpMsgParseRequestLine

FreeBSD TPROXY works!

2009-01-08T15:53:00.000-08:00

The FreeBSD TPROXY support (with a patched FreeBSD kernel for now) works just fine in testing.

I'm going to commit the changes to FreeBSD in the next couple of days. I'll then bring in the TPROXY4 support from Squid-3, and hopefully get functioning TPROXY2, TPROXY4 and FreeBSD TPROXY support into the upcoming Cacheboy-1.6 release.

TPROXY support

2009-01-07T14:43:00.000-08:00

G'day,

I've done a bit of shuffling in the communication code to include a more modular approach to IP source address spoofing.

There's (currently) untested support for some FreeBSD source IP address spoofing that I'm bringing over courtesy of Julian Elischer; and there's a Linux TPROXY2 module.

I'll look at porting over the TPROXY4 support from Squid-3 in a few days.

I think this release is about as close to "stable" as Cacheboy-1.6 is going to get, so look forward to a "stable" release as soon as the FreeBSD port has been setup.

I already have a list of things to do for Cacheboy-1.7 which should prove to be interesting. Stay tuned..

next steps..

2009-01-04T18:54:00.000-08:00

I've been slowly fixing whatever bugs creep up in my local testing. The few people publicly testing Cacheboy-1.6 have reported that all the bugs have been fixed. I'd appreciate some further testing but I'll get what I can for now. :)

I'll be doing a few things to the CACHEBOY_HEAD branch after the 1.6 release which will hopefully lead towards a mostly thread-safe core. I'm also busy documenting various things in the core libraries which I haven't yet gotten around to. I also really should sort out some changes to the apple HeaderDoc software to support generating slightly better looking documents from C source.

I've almost finished the first round of code reorganisation. The stuff that I would have liked to have done this round includes shuffling out the threaded async operations from the AUFS code and building a proper disk library, sort of like what Squid-2.2 "had" and what Squid-3.0 almost did; but instead use them to implement general disk IO versus specialised modules just for storage. I'd like to take advantage of threaded/non-blocking disk IO in a variety of situations, including logfile writing.

Cacheboy-HEAD updates

2008-12-28T12:04:00.000-08:00

I've finished cleaning up the bits of the IPv6 work from CACHEBOY_HEAD - it should be just a slightly better structured Squid-2.HEAD / Cacheboy-1.5.

Right now I'm pulling out as much of the HTTP related code from src/ into libhttp/ before the 1.6 release. I'm hoping to glue together bits and pieces of the HTTP code into a very lightweight (for Squid) HTTP server implementation which can be used to test out various things like thread safe-ness. Of course, properly testing thread-safeness in production relies on a lot of the other code being thread-safe, like the comm code, the event registration code, the memory allocation code, the debugging and logging code ... aiee, etc. Oh well, I said I wanted to..

I'm also going through and adding some headerDoc comments to various library files. headerDoc (from apple) is actually rather nice. It lacks -one- function - the ability to merge multiple files together (say, libsqinet/sqinet.[ch]) into one "module" for documentation. I may look at doing that in some of my spare time.

Reverting IPv6 for now; moving forward with structural changes

2008-12-27T15:28:00.000-08:00

I've been working on the IPv6 support in Cacheboy for a couple months now and I've come to the conclusion that I'm not getting anywhere near as far along the development path as I wanted to be.

So I've taken a rather drastic step - I've branched off CACHEBOY_HEAD from the last point along the main codebase where the non-intrusive IPv6 changes had occured and I'm going to pursue Cacheboy-1.6 development from that.

The primary short-term goal with Cacheboy was to restructure the codebase in such a way as to make further development much, much simpler. I sort of lost track with the IPv6 development stuff and I rushed it in when the codebase obviously wasn't ready.

So, the IPv6 changes will stay in the CACHEBOY_PRE branch for now; development will continue in CACHEBOY_HEAD. I'll continue the restructuring work and stability work towards a Cacheboy-1.6 release come January 1. I'll then look at merging over the IPv6 infrastructure work into CACHEBOY_HEAD far before I merge in the client and server related code - specifically, completing the DNS updates, the ipcache/fqdncache updates, port over the IPv6 SNMP changes from Squid-3, and look at modularising the ACL code in preparation for IPv6'ifying that. The goal is less to IPv6-ify Cacheboy; its more to tidy up the code to the point where IPv6 becomes trivial.

Working on NNRP proxies, or writing threaded C code..

2008-11-29T12:19:00.000-08:00

So it turns out that I'm working on some closed-source NNRP proxy code. It sits between clients / readers and backend spool servers and directs/balances requests to the correct backend servers as required.

News is a kind of interesting setup. There are servers with just lots of articles, indexed via message ID (or a hash thereof.) There are servers with the overview databases, which keep track of article ids, message ids, group names, and all that junk. The client reader interface has a series of commands which may invoke a combination of access to both the overview databases and the article spools.

I'm working on a bit of code which began life as a reader -> spool load balancer; I'm turning it into a general reader and client facing bit of software which speaks enough NNRP to route connections to the relevant backend servers. The architecture is pretty simplistic - one thread per backend connection, one thread per client connection, "message queues" sit between all of these and use pthread primitives to serialise access. For the number of requests and concurrency, it scales quite well. It won't scale to 100,000 connections by any means but considering the article sizes (megabytes at a time) a 10GE pipe will be filled far, far before that sort of connection and request rate limit is reached.

So, today's post is going to cover a few things I've learnt whilst writing this bit of code. Its in C, so by its very nature its going to be horrible. The question is whether I can make it less horrible to work with.

Each client thread sits in a loop reading requests, parsing them, figuring out what needs to happen, then queuing messages to the relevant spool or reader server queue to be handled by one of the connection threads. Its relatively straightforward. The trick is to figure out how to keep connections around long enough so the thing you've sent the request to is still there when you reply.

There's a couple of options which are used in the codebase.

The first is what the previous authors did - they would parse an article request (ARTICLE, HEAD, BODY), create a request, push it onto the queue, and wait 1 second for a reply. If the reply didn't occur in that time they would push another request to another server. The idea is to minimise latency on the article fetches - instead of waiting around for a potentially overloaded server, they just queue requests to the other servers which may have the article and then stop queuing requests when one issues a reply. The rest of the replies then have to be dequeued and tossed away.

The second is what I did for the reader/overview side - I would parse a client request, (GROUP, STAT, XOVER, etc), create a request to the backend, push it onto the queue, and wait for the reply. The backend code took care of trying the set of commands required to handle that client request (eg a STAT would require a GROUP, then a STAT; but a STAT would only require a STAT on the backend), with explicit timeouts. If the request didn't happen by then, the backend reader thread would send a "timeout" reply to the client thread, and then attempt to complete the transaction before dequeuing the next.

There are some implications from the above!

The first method is easier to code and easier to understand conceptually - the client handles timeouts and throws away unwanted responses. The backend server code is easy - dequeue, attempt the request until completion or error, return. The problem is that there is no guaranteed time in which the client will be notified of the completion of the request.

The second method is trickier. The backend thread handles timeouts and sends them to the client thread. The backend then needs to track the NNTP transaction state so it can resume it and run the request to completion, tossing away whatever data was being returned. The benefit is that the client -will- get a message from the backend in the specified time period.

These approaches aren't mutually exclusive either. The first works better for article fetches where the isn't any code to try and monitor server performance and issue requests to servers that are responding quickly. I'm going to add that code in soon anyway. The second approach works great for the reader commands because they're either nice and quick, or they're extremely long-lived. Article replies are generally maxing out at a few megabytes. Overview commands can server back tens or hundreds of megabytes of database information and this can take time.

One of the important implications is when the client thread can be freed. In the first method, the client thread MUST stay around until all the pending article requests have been replied to in some fashion. In the second method, the client thread waits for a response to its message immediately after queuing it, so it doesn't have to reap queue events on connection shutdown.

The current crash bugs I've seen seem to be related to message queuing. I'm seeing both junk being dequeued from the client reader queue (when there should be NO messages pending in that queue once a command has been fully processed!) and I'm seeing article responses being sent to queues for clients which have been destroyed for one reason or another. I'm going to spend some time over the next few hours putting in assert()ions to track these conditions down and naff them on the head before the stack gets scrambled and I end up with a 4 gigabyte core which gives me absolutely no useful traceback. :P

Oh look, the application cored again, this time in the GNU malloc code! Time to figure out what is going on again..

Updates!

2008-11-22T11:31:00.001-08:00

A few updates!

I've fixed a few bugs in CACHEBOY_PRE which will be back-ported to CACHEBOY_1.5. This is in line with my current goal of stability before features. CACHEBOY_PRE and CACHEBOY_1.5 have passed all the polygraph runs I've been throwing at them and there aren't any outstanding stability issues in the Issue tracker.

I'll roll CACHEBOY_1.6.PRE3 and CACHEBOY_1.5.2 releases in the next day or two and get those out there.

Serving IPv6 from Cacheboy-1.6.PRE2

2008-10-16T21:10:00.000-07:00

I've done the very minimum amount of work required to get Cacheboy-1.6.PRE2 to the point where it'll handle IPv6 client requests. I've put it in front of http://www.cacheboy.net/ which now has v4 and v6 records.

There's still plenty of work to do to bring it up to par with the Squid-3 IPv6 support but that will have to wait a while. Specifically, (if anyone feels up to handling it), the dns, ipcache and fqdncache code all needs to be massaged to support IPv4 and IPv6 handling. It shouldn't be that much work.

Cacheboy-1.6 is definitely now in the "freeze and fix bugs as they creep up" stage. I'll continue the memory allocator and HTTP parser code reimplementation in their respective branches and get them ready for merge once I'm happy 1.6 is stable. The rest of the IPv6 support will also have to wait.

Cacheboy IPv6 update

2008-10-03T05:00:00.001-07:00

I've made some progress in the IPv6 reorganisation in cacheboy. I've converted the ACL, authentication and ident code over to support v4/v6. I'm now going to convert over the client_db, request_t structure and then the related stuff like logging, x-forwarded-for, etc. I'll then revisit what else is required before I enable v6 sockets on the http client-side. It -should- be pretty minimal - persistent connections/connection pinning (for just assembling the hash key) and some SNMP code to just gloss over IPv6 connections for the time being.

Hm, I was hoping to have this all done by the end of September but I've been a bit busy with paid work. I'll hopefully have this done just after NYCBSDCON. I hope. :)

IPv6 ACL code, sort of!

2008-09-21T08:41:00.000-07:00

I'm just doing a spot of testing with my new IPv6 ACL code.

Take a look at this:


(adrian) agnus:~/work/cacheboy/playpen/ipv6_acl/tools% ./squidclient mgr:config@PASSWORD | grep acl
acl all src 0.0.0.0/0.0.0.0
acl all6 src6 ::/::
acl lclnet6 src6 fe80::/fff0::
acl test1 src6 2a01:348:147:5::/ffff:ffff:ffff:ffff::
acl test1 src6 fe80::/fff0::

That there is an IPv6 "src6" ACL (well, three) with somewhat unfriendly netmask display code. I'll tidy that up later. Importantly, the IPv6 code seems to be coming along fine. I'm going to generate up some large random IPv4 and IPv6 ACLs tomorrow to make sure they load in and display out from the splay tree fine, then I'll look at writing some test cases for all of this.

The last bit of code that needs converting before -very basic- client-side IPv6 support can be enabled is to convvert the ACL checklist struct "src_addr" and "my_addr" over to sqaddr_t IPv6 types. This will probably require a whole lot of horrible code changes but luckily I can convert most of them to just be "assign that an IPv4 address thx" and everything should just work as before. Although I need to remind myself to make sure aclMatchIp() checks the _type_ of the ACL its looking up against - doing an IPv4 lookup against an IPv6 splay tree won't really work out.

(Amos / Squid-3 have a single IPv6 "type" for this, and the IPv4 addresses are merged into the IPv6 address space. The ACL types for IP src/dst/myip is then -always- an IPv6 type lookup. I decided to keep seperate IPv4/IPv6 ACL types for now to make testing and development easier. It will double up on the ACL sizes a little - holy crap, I'm doing something less efficient then Squid-3?!? - but thats a small price to pay at the moment for an easier to migrate codebase. Basically, if you compile this up and listen on an IPv6 address, but don't configure an IPv6 ACL, you won't get surprised when IPv6 requests are let through when they shouldn't..)

Cacheboy-1.5: IPv6 DNS servers

2008-09-05T23:29:00.000-07:00

I'm just debugging the last couple of issues with the IPv6-aware UDP/TCP DNS code. The Internal DNS resolver still only understands IPv4 code (and, more importantly, the ipcache/fqdncache layer too!) but the code itself will communicate with IPv4/IPv6 DNS servers.

I think I'll stop the development here and concentrate on getting the Cacheboy-1.5 release out the door. I'll then work on IPv6 record resolution in a seperate branch in preparation for Cacheboy-1.6. I may even break out the ipcache/fqdncache code into external libraries so I can reuse/debug/test that code during development.

Upcoming Cacheboy-1.5.PRE3 development release

2008-09-02T02:34:00.000-07:00

(Yes, I've been slack in posting about this stuff.)

I'm just about to roll the next Cacheboy-1.5 development pre-release. Cacheboy-1.5 is probably the last "almost but not quite squid-2.HEAD" release. Besides the IPv6 core, Cacheboy-1.5 resembles the Squid code but with a more sensible layout of modules and libraries.

Its main difference is the inclusion of core comm layer changes to support IPv6 in preparation of IPv6 client and server support. This particular pre-release includes some changes to the internal DNS code to decouple it from a few routines in src/ relating to TCP socket connection. Its possible I've busted stuff - just run cacheboy with "debug_options ALL,1 78,2" for a while to see if you're falling back to TCP DNS properly.

I'm about to put Cacheboy-1.5.PRE3 in production for a couple of clients to get some real world feedback.

Standalone HTTP header parser!

2008-08-24T21:08:00.000-07:00

I've finally broken out enough of the HTTP header parsing code from src/ into libhttp/ to run the http header parser standalone.

This allows me to write some test cases to make sure I don't break things whilst changing how the HTTP header parser and HTTP header entry code uses (ie, abuses!) the memory allocator. It's also one step closer to being able to reuse bits of the Squid internals in a "simpler" HTTP proxy core.

I'll commit this code reorganisation to Cacheboy trunk after I've released and tested a few developer previews.

So, without further delay:


test1b: test parsing sample headers
| init-ing hdr: 0x7fffffffe6f0 owner: 2
| parsing hdr: (0x7fffffffe6f0)
Host: www.creative.net.au
Content-type: text/html
Foo: bar


| creating entry 0x60ed40: near 'Host: www.creative.net.au'
| created entry 0x60ed40: 'Host: www.creative.net.au'
| 0x7fffffffe6f0 adding entry: 27 at 0
| creating entry 0x60eda0: near 'Content-type: text/html'
| created entry 0x60eda0: 'Content-Type: text/html'
| 0x7fffffffe6f0 adding entry: 18 at 1
| creating entry 0x60ee00: near 'Foo: bar'
| created entry 0x60ee00: 'Foo: bar'
| 0x7fffffffe6f0 adding entry: 68 at 2
  retval from parse: 1
  Parsed Header: Host: www.creative.net.au
  Parsed Header: Content-Type: text/html
  Parsed Header: Foo: bar
| cleaning hdr: 0x7fffffffe6f0 owner: 2
| destroying entry 0x60ed40: 'Host: www.creative.net.au'
| destroying entry 0x60eda0: 'Content-Type: text/html'
| destroying entry 0x60ee00: 'Foo: bar'

IPv6 core merged into cacheboy trunk

2008-08-21T22:24:00.000-07:00

I've just completed merging the IPv6 core into the cacheboy trunk. This doesn't mean it handles IPv6 client/server requests yet - there's a lot more to do before that can happen!

I'll next merge in the IPv6 DNS changes from husni's Squid-2.6 IPv6 patch and do up a basic test suite for all of that. Once done, I'll roll the first Cacheboy-1.5 pre-release.

Merging sockaddr_rework into Cacheboy trunk

2008-08-20T02:38:00.000-07:00

I'm slowly cherrypicking bits and pieces of the Cacheboy sockaddr_rework into trunk. I've merged in the no_addr/any_addr tidyup which makes those comparisons and sets much clearer. I'll next bring over the sqinet_ routines as just files, ignoring the change history. I'll then bring over the changesets implementing the sqinet_ changes to the comm code and main codebase, retaining the basic change history.

I now need some live testing under decent amounts of real traffic so I can make sure I haven't missed some silly corner condition in the base comm code.

All of this work exposed some of the ugliness that happens in the IPC code with filedescriptor creation that bypasses the comm layer. Basically, the IPC helper code creates file descriptors itself and uses fd_open() to tell Squid about them but then unconditionally uses comm_close() to close them. This is .. stupid.

I may drop in some debugging code to ensure that only sockets created by the comm layer are closed by comm_close(). I wonder how many bad uses of file descriptors will be caught out by that..

Cacheboy IPv6 (phase 1): More Updates!

2008-08-12T10:35:00.000-07:00

The IPv6 code hackery is going along well. I'm just sorting out making a few loose ends .. well, slightly less loose.

I'll run polygraph PolyMix-4 over this codebase in the next few days to make sure I haven't busted anything and then I'll start preparing to merge it back into CACHEBOY_PRE.

I'm not quite sure how to conditional-compile IPv6; I'm not bothering to do it at the moment (ie, its always included.) Thats a later problem.

The IPv6 TCP proxy is still happily chugging along. FreeBSD's IPv6 stack seems still partially Giant locked but I'm still pushing ~ 350mbit through this Core 2 Duo test server.

This has been too easy. What the hell have I missed!??

IPv6 tcp proxy success

2008-08-10T09:19:00.000-07:00

I feel like an undergraduate computer science student after all of this. I've managed to coax the cacheboy core to support v4/v6 and am using it in the tcpproxy test application.

I've got a modified apachebench speaking IPv6 to tcpproxy, listening on a :8080 IPv6 socket. It then forwards all requests to a thttpd instance running on IPv4.

Tomorrow's job - making sure the squid proxy codebase is still happy with these latest changes, and then preparing for some further testing and the implementation of some unit tests for the comm and inet libraries. Then it back to commercial projects for a few weeks.


Server Software:        thttpd/2.25b                                       
Server Hostname:        [2a01:348:XXX:3207]
Server Port:            8080

Document Path:          /test8k
Document Length:        8192 bytes

Concurrency Level:      1000
Time taken for tests:   21.690 seconds
Complete requests:      100000
Failed requests:        0
Broken pipe errors:     0
Total transferred:      844171764 bytes
HTML transferred:       819841632 bytes
Requests per second:    4610.42 [#/sec] (mean)
Time per request:       216.90 [ms] (mean)
Time per request:       0.22 [ms] (mean, across all concurrent requests)
Transfer rate:          38919.86 [Kbytes/sec] received

Cacheboy IPv6 (phase 1): Updates!

2008-08-09T19:54:00.000-07:00

I've been working on the IPv6 core support in a cacheboy branch (Changes: http://code.google.com/p/cacheboy/source/list?path=playpen/sockaddr_change) and it seems to be coming along swimmingly.

The current goal is just to get basic IPv6 support into the base libraries and keep the rest of the codebase IPv4-only.

I've converted commBind(), comm_connect_addr() and comm_accept() to my new IPv4/IPv6 address type and nothing seems amiss at the present time. comm_open() and comm_openex() will take a little more time as there are plenty of places which create a new outgoing socket.

My next move is to modify my tcp proxy to listen on both IPv4 and IPv6 incoming ports and proxy to an IPv4 destination. I can then fire off some HTTP clients at it and see what happens.

(I may have to modify apachebench-adrian to support IPv6 though; I'm not sure what other stupidly-high-traffic open source http benchmarking clients exist at the present time.)

I hope to get all of this sorted out in the next week or so and head over to the Sydney Squid developers meet with my "alternate" IPv6 core for Squid-2 and better understand the IPv4/IPv6 requirements before discussing them with Amos.

Benchmarking is available!

2008-07-29T05:36:00.000-07:00

I've begun benchmarking Cacheboy-1.4. The details are available at http://www.cacheboy.net/benchmarks.html. They aren't spectacular - I'm mainly doing them to keep track on development and make sure I'm not introducing regressions anywhere.

I'm not all that happy with 50% CPU (on one CPU too!) at 500 req/sec. Alas, thats what I have to work with - I can't push these disks nor the polygraph hosts any harder at the present time. Maybe if I spent two weeks fixing polygraph so it used kqueue() instead of poll() ..

Commercial work updates!

2008-07-26T00:32:00.000-07:00

I've just completed the development and local testing of the client-side delay pools. That'll go into Squid-2.HEAD in the next few days. I'll try untangling the client-side delay pools from the class 5 delay pool work (which shouldn't be -that- difficult, just slightly tedious) and commit them as two seperate chunks.

I'll post more details on my company blog - http://xenionhosting.blogspot.com/ - as I think the details of my current and future commercial Squid stuff should be detailed over there.

Surviving polymix-4..

2008-07-23T05:20:00.000-07:00

I'm putting Cacheboy-1.4 through a basic polymix-4 polygraph workload. So far so good - its just unfortunate that polygraph still uses poll() / select(). Most of the process CPU time is spent in those two system calls and not doing any useful work.

So far, so good at ~ 500 req/sec (with <10% CPU usage..) I'm going to resolve a few strange issues I'm seeing and then begin publishing some actual performance numbers over the next few weeks. I'll also start publishing some microbench numbers comparing Squid-2.6, Squid-2.7, Squid-3.0, Squid-3.1 and Cacheboy. Cacheboy will come out on top, of that I'm quite sure. :)

Threading Squid - initial observations

2008-07-22T02:55:00.000-07:00

My next task after some IPv6 related reshuffling is to bring in the bare essentials needed to make Squid^WCacheboy SMP-happy.

There are a few potential ideas:

Leave Squid single-threaded. Stop it from doing its own disk/memory caching; push that out to a shared external process and abuse sysvshm IPC/anonymous mmap/etc to share large amounts of data efficiently;

Thread Squid entirely. Allow multiple concurrent copies of squid running in threads - whichever "model" of thread helpers you choose - and parallelise everything;

Provide basic thread services but leave Squid monolithic - push certain things into threads for now, figure out what benefits from being run in parallel;

A mix of all of the above.

Some of the problems that are faced!

cbdata

The cbdata type makes it a pain in the ass. Specifically, anything which wants to be shared between threads needs to be able to be 'locked' into memory until the thread hands it back either completed, or cancelled.

cbdata doesn't give you any guarantees that the pointer is pointing to something even remotely valid - even if you cbdataLock()'ed the item, the owner (or not! Thats how horrible the code can get) can cbdataFree() the underlying pointer and suddenly you're pointing at gunk. It might smell mostly right, it might even have somewhat valid data, but its still freed gunk, and thats not good enough.

Shared Statistics

Squid keeps a lot of statistics and histograms. Something needs to be done to allow these to be kept in multiple threads without lots of fine-grain locks and/or stalling.

I may just get rid of a lot of the complicated statistics and require them to be post-process derived externally.

Memory Pools

The memory pools framework will be a nightmare to thread efficiently. Well, memory allocators in general are. I -could- just fine-grain lock it, but it gets a -lot- of requests and so I'd have to first fix the pool abusers before I consider this. (I'm going to do it anyway, but not so I can then fine-grain thread mempools.) I could figure out the best way to thread it - or run multiple pools per pool, one per thread - but damnit, this is 2008, there are better malloc implementations out there by people who understand concurrency issues better than I. Its a waste of time to try and thread it until I understand the workload and implications better.

So I'll -probably- be turfing mempools as it stands and replacing it with just enough to keep statistics before going direct to malloc(). See the statistics section above. I won't do this until I've modified the heaviest mempool abusers to -not- put such large demands on the allocator system, so it'll be a win/win situation everywhere.

more to come..

Commercial projects and such..

2008-07-15T09:59:00.000-07:00

I've got a few commercial projects to finish up on Squid over the next few weeks which will be taking my time away from Cacheboy development.

Specifically:

I'm adding client-side -write- delay pools, so you can rate limit the replies sent back to clients whether they are a cache hit or miss (specifically for reverse proxies, but I'm sure forward proxies will have a use for them);

Buffering POST requests a bit before connecting to the back-end origin server, which matters when your back-end server pays a high price for holding a connection open with no data going over it;

Finally - some log reporting tools (hopefully written in Lua! :) for basic WebUI logfile reporting in a fast, sensible manner

I've got a few other possibilities which might creep up over the next couple of months but nothing yet concrete.

Client-side IPv6, HTTP/1.1 and a threaded core will have to wait until I've completed the paid work I'm afraid! OSS coders have to eat too!

Watching things evolve..

2008-07-13T06:50:00.000-07:00

I'm finding it interesting to watch myself "evolve" the Cacheboy roadmap over time. Take the previous two cacheboy-users posts: first I thought Cacheboy-1.4 will get the IPv6 enabled core, but after doing the latest set of changes I've decided the best thing to do is to get Cacheboy-1.4 out with the current code layout, sort out whatever bugs crept in, then build the IPv6 enabled core in Cacheboy-1.5 and IPv6 client-side support in Cacheboy-1.6.

I have a general idea where I'd like to take things and I have a specific set of goals in mind along the way, but everything is still evolving with time. Its an interesting experience - there are dozens of areas in the codebase which I'd like to spend time working on but I have to keep the medium and long-term project goals in mind.

Which isn't to say I won't get distracted from time to time and break out a test branch to play with something, like one of the branches playing around with memory allocation overheads. I just treat that, like the last 10 or so years of experimenting with the codebase, as a way to get more of an idea what work needs to be done.

Cacheboy: shuffling around the DNS code

2008-07-12T13:22:00.000-07:00

I'm shuffling around the DNS code in preparation for some work toward an IPv6 core. Strictly speaking, I could have just left the dns code in src/ and IPv6'ed the raw network/socket layer but I've decided "basic" functional IPv6 support will require DNS support and so be it. It'll let me write test cases to make sure that the new code handles IPv4 and IPv6 DNS "right". I still don't know what "right" entails and I'm sure that journey will be very enlightening!

Its been more tedious than complicated. There's a bunch of config file parsing which needs to stay in src/ and I've split out the "libsqdns" DNS initialisation from the "squid" DNS initialisation. It compiles and runs here, resolving DNS requests happily, so I guess I'm mostly on track. I had to shuffle around some config variables so its entirely possible I've screwed that up somewhere.

This highlights the requirement for a much more sensible configuration management framework. It doesn't even have to be that complicated - just not the "one great big Config struct" that Squid currently has. I've got some plans in the back of my head to generic-ify that much later on down the track but it'll have to wait a while. It'll probably come in when the ACL code is split out into squid-specific and generic ACL types. (A lot of the ACL types aren't really specific to HTTP and in reality can be reused in a variety of network applications.)

So tomorrow I'll find some time to get the external DNS code working again which I hope will be slightly easier than the internal DNS code. Then I can let this codebase simmer for a bit, push Cacheboy-1.4 out the door and wait for it to stabilise before my next round of changes towards IPv6.

The Squid Callback Data Type

2008-07-05T01:25:00.000-07:00

One of the issues programmers frequently face is knowing whether some piece of data you have is actually valid. Modern languages provide a variety of methods for creating an "invariant condition" about the validity of your data - reference counting, for example, allows you to ensure that data is not free'd before all references to it have been removed. This invariant is not always what you first think. The invariant condition for reference counting, for example, is that the data is either referenced by something or by nothing at all. Generally the programmer will treat the transition from "referenced by something" to "referenced by nothing" as the important transition and do something like removing the object from whatever lists its on, notifying other objects that its going away, cleaning up allocated memory, etc.

Take traditional "callback" type programming. The programmer decides that some function is to be called after an event has occured (for example, "the ACL lookup has completed", or "the network write has completed") and this function needs some sort of "state" to know what its operating on. You could view this state as a sort of object. The trouble in C is that the language itself doesn't give you any tools to know that the supplied pointer is valid or not. Now, think about this - firstly, whats "valid" mean. The pointer is pointing to some region of memory that hasn't been freed? What about the state of the object? What if the object state changed between the callback being scheduled and the callback being executed? Is this "valid"?

Squid implements "callback data". Initially, this "callback data" (called cbdata in the code) was a registry for callback data pointers. Pointers were reference counted when passed in as part of a scheduled callback; they would be decremented before the callback was about to run, and the callback would only be executed if the callback pointer was "valid". The "owner" (for whatever meanings of "own" you'd like to try and define) could "free" the data pointer - in which case the callback data registry would mark that pointer as invalid; subsequent checks for the validity of said pointer would return invalid, and any callbacks that were going to occur could be ignored. Eventually, the reference count would hit 0 and at 0 the memory at the pointer would be freed.

Expressed as code:

ptr = cbdataAlloc(type);
...
doSomething(someFunc, ptr)

which would:
state->cb = someFunc;
state->cbdata = ptr;
cbdataLock(ptr);

.. then, when the chain of events which doSomething() started would finish, this would occur:

if (state->cb && cbdataValid(ptr)) {
state->cb(state->cbdata);
}
cbdataUnlock(ptr);

This way, the callback would only occur IFF there was a callback and the callback data was still valid.

cbdataAlloc() returns a pointer with refcount = 0 and valid = true ; cbdataLock() incremented refcount; cbdataUnlock() decremented refcount and would free the pointer if (valid == false && refcount == 0); cbdataValid() returned (valid == true); cbdataFree() would set valid = false and free the object if (valid == false && refcount == 0)

This worked out to be quite helpful in preventing callbacks from being run if the data was freed. It however introduces a few assumptions which make certain things difficult to debug and implement.

Firstly, you don't have any guarantee that the callback will be called when you schedule for the call. So in the above code, if something calls cbdataFree(ptr) between the callback registration and the completion of the action initiated by doSomething(), the action will complete but the callback won't be made. The programmer needs to make sure that the code can handle not having the callback ever be made. Traditionally, you would instead either cancel the operation explicitly instead of letting it continue to completion and handle the situation where it couldn't be cancelled, or let the operation complete before transitioning to some "dying" state.

Secondly, generally the "object destructor" here is called not by the cbdata reference count hitting 0, but by some explicit destruction call elsewhere in the code. For example, you would have this in the code:

fooComplete(foo *ptr)
{
free(ptr->data);
cbdataFree(ptr);
}

There still may be references to the callback data but no callbacks will occur on it because cbdataFree() marks that ptr as invalid. So cbdata isn't quite behaving traditional reference counted "types" behave.

Here's where this gets ugly: but it can - you can register a function to be called just before the ptr is finally freed. _SOME_ areas of code do this. _SOME_ areas of code do not. You can't assume that the behaviour for a given cbdata pointer type will be one or the other.

Thirdly, if the action initiated by doSomething() requires some part of ptr to be valid then it will need to wrap every access to the data inside ptr with a if (cbdataValid(ptr)) check. This doesn't always happen :) and has been the cause of all sorts of silly bugs because although the memory pointed to by ptr is still valid, the object may have gone through its "destruction" phase and whats left in memory (which again, hasn't been freed) is actually the last traces of object state. This may be valid, this may be invalid. Who knows. I can't guarantee that accesses to cbdata pointer dereferences are always done conditional to said pointer being valid. That would be a fun thing to hack in as a valgrind module!

This all started rearing its ugly head in Squid-3 as a few things were converted from cbdata type pointers to more traditional reference counted types. The programmers assumed the behaviour was equivalent when it wasn't and all kinds of strange bugs arose some of which took over 12 months to find and fix.

What would I like to see? Thats a good question and will probably form the basis of further improvements in Cacheboy..

libevent httperf!

2008-07-02T08:32:00.001-07:00

I decided to poke httperf a little as a testing suite - and it uses select()! What the hell?

Four hours later, I think I have a libevent enabled httperf.

http://code.google.com/p/httperf-adrian/

Initial Profiling!

2008-06-30T22:34:00.000-07:00

Here's the output trace: I'm running it on the Sun X2100 running a flavour of ubuntu; this is doing ~ 300mbit FDX at about 9000 req/sec (tiny transactions!) w/ 1000 concurrent connections; I'm specifically trying to trace the management overhead versus the data copying overhead. This has maxed out both thttpd on the server-side and the tcp proxy itself.

Gah, look at all of those mallocs and stdio calls doing "stuff"..


root@rachelle:/home/adrian/work/cacheboy/branches/CACHEBOY_PRE/app/tcptest# opreport -l ./tcptest | less
CPU: AMD64 processors, speed 2613.43 MHz (estimated)
Counted CPU_CLK_UNHALTED events (Cycles outside of halt state) with a unit mask of 0x00 (No unit mask) count 100000
samples  %        image name               symbol name
96851    11.3738  libc-2.6.1.so            vfprintf
62317     7.3182  libc-2.6.1.so            _int_malloc
37556     4.4104  tcptest                  comm_select
35405     4.1578  tcptest                  commSetEvents
32901     3.8638  libc-2.6.1.so            _int_free
30245     3.5518  tcptest                  commSetSelect
29890     3.5102  tcptest                  commUpdateEvents
28812     3.3836  libc-2.6.1.so            _IO_default_xsputn
20360     2.3910  tcptest                  sslSetSelect
17279     2.0292  libc-2.6.1.so            malloc_consolidate
16610     1.9506  libc-2.6.1.so            epoll_ctl
16307     1.9150  tcptest                  sslReadServer
16154     1.8971  libc-2.6.1.so            fcntl
14601     1.7147  tcptest                  xstrncpy
12003     1.4096  libc-2.6.1.so            memset
11617     1.3643  tcptest                  memPoolAlloc
10931     1.2837  libc-2.6.1.so            calloc

First milestone - code reuse!

2008-06-30T21:57:00.000-07:00

I've spent the last couple of evenings committing code to break out the last bits of the core event loop. I then added in a chopped up copy of src/ssl.c (the SSL CONNECT tunneling stuff) and voila! I now have a TCP proxy.

A (comparitively) slow TCP proxy (3000 small obj/sec instead of where it should be: ~10,000 small obj/sec). A slow, single-threaded TCP proxy, but a TCP proxy nonetheless.

I can now instrument just the core libraries to find out where they perform and scale poorly, seperate from the rest of the Squid codebase. I count this as a pretty big milestone.

Why memory allocation is a pain in the ass..

2008-06-26T23:20:00.000-07:00

The memory allocator routines in particular are annoying - a lot of work has gone into malloc implementations over the last few years to make them perform -very- well in threaded applications as long as you know what you are doing. This means doing things like allocating/freeing memory in the same thread and limiting memory exchange between threads (mostly a deal with very small allocations).

Unfortunately, the mempools implementation saves a noticable amount of CPU because it hides all of the repetitive small memory allocations which Squid does for a variety of things. Its hard to profile too - I see that the CPU spends a lot of time in the allocator, but figuring out which functions are causing the CPU usage is difficult. Sure, I can find out the biggest malloc users by call - but they're not the biggest CPU users according to the oprofile callgraphs. I think I'll end up having to spend a month or so rewriting a few areas of code that account for the bulk of the malloc'ing to see what affect it has on CPU before I decide what to do here.

I just don't see the point in trying to thread the mempools codebase for anything other than per-pool statistics when others have been doing a much better job of understanding memory allocation contention on massively parallel machines.

Cacheboy-1.3 (.1) released; short-term future

2008-06-26T23:06:00.000-07:00

I've just merged the latest Squid-2.HEAD changes into Cacheboy and released 1.3.1.

1.3 and 1.3.1 fix the Vary related issues which affects hit rates.

1.3.1 fixes the SNMP counter bugs.

This ends the first set of mostly non-intrusive changes which have been made to the codebase. The next area of work will be pulling out the rest of the event/communications/signal code from src/ and into libiapp/ so I can begin treating "Squid" as a client of "libiapp" - ie, the libiapp code handles event, fd, communication and event scheduling (disk stuff is still in src/ for now) making callbacks into the Squid application. I can then begin writing a few test applications to give the core and support libraries a good thrashing.

I'll start planning out threading and ipv6 support in the libraries themselves with the minimum amount of Squid changes required to continue functioning (but still staying in IPv4/non-threaded land.) The plan is to take something like a minimalistic TCP proxy thats been fully debugged and use it as the basis for testing out potential IPv6 and threading related changes, seperate from the rest of the application.

My tentative aim is to run the current "Squid" application in just one thread but have the support libraries support threading (either by explicitly supporting concurrency or being labelled as "not locking" and thus callers must guarantee nothing quirky will happen.) The three areas that strike me as being problematic right now are the shared fd/comm state (fd_table[]), the statistics being kept all over the place and the memory allocator routines. (I'll write up the malloc stuff in a different post.)

Current CPU usage

2008-06-24T22:31:00.000-07:00

Where's the CPU going?

Here's an oprofile output from a very naive custom polygraph workload, ~ 1000 requests a second, ~14kbyte objects. MemPools are disabled; Zero buffers are off so the majority of the allocations aren't zero'ed.

Note that somehow, memPoolAlloc takes 4% of CPU even with memory pools switched off. The allocations still go via the pool code but deallocations aren't "cached". What the hell is taking the 4% of CPU time?


CPU: AMD64 processors, speed 2613.43 MHz (estimated)
Counted CPU_CLK_UNHALTED events (Cycles outside of halt state) with a unit mask of 0x00 (No unit mask) count 100000
samples  %        image name               symbol name
176014    6.7039  libc-2.6.1.so            _int_malloc
160779    6.1236  libc-2.6.1.so            memcpy
128371    4.8893  libc-2.6.1.so            malloc_consolidate
123734    4.7127  squid                    memPoolAlloc
101514    3.8664  libc-2.6.1.so            free
76772     2.9240  libc-2.6.1.so            _int_free
55696     2.1213  libc-2.6.1.so            malloc
55681     2.1207  libc-2.6.1.so            vfprintf
50245     1.9137  libc-2.6.1.so            calloc
48095     1.8318  squid                    httpHeaderIdByName
41172     1.5681  libm-2.6.1.so            floor
37573     1.4310  libc-2.6.1.so            re_search_internal
37434     1.4258  libc-2.6.1.so            memchr
36536     1.3916  squid                    xfree
30646     1.1672  libc-2.6.1.so            memset
30576     1.1646  squid                    memPoolFree
30108     1.1467  squid                    headersEnd
28626     1.0903  squid                    httpHeaderGetEntry
26668     1.0157  squid                    storeKeyHashCmp
...

Updates - comm code, etc

2008-06-19T22:19:00.001-07:00

I've finally managed to divorce the comm code from the base system. Its proving to be a pain in the butt for a few reasons:

The DNS code is involved in the socket connection path - most users just pass a hostname in to the comm connect call and it gets diverted via the ipcache/dns code. Tsk!
There's quite a bit of statistics gathering which goes on - the code is very monolithic and the statistics code keeps 5/60 minute histograms as well as raw counters
The event loop needs to be sorted out quite a bit better - right now the event loop is still stuck in src/main.c and this needs to change

The statistics gathering and reporting for the network/disk syscalls and events will have to change - I don't feel like trying to make the histogram code more generic and modular. I don't think that Squid should be maintaining the histograms - thats the job for a reporting suite. Squid should just export raw counters for a reporting suite to record and present as appropriate. I'll add in a new cachemgr option to report the "application core" statistics in a machine-parsable manner and leave it at that for now. (As a side-note, I also don't think that Squid should have SNMP code integrated. It should have an easier, cleaner way of grabbing statistics and modifying the configuration and an external SNMP daemon to do SNMP stuff.)

I then need to extract out the main event loop somewhat from src/main.c and turn it into something that can be reused. The main loop handles the following:

comm events
store dir events
timed/immediate registered events
signals - which basically just set global variables!
checking signal global variables - for rotate, shutdown, etc

I think I'll implement a libevent setup of sorts - I'll implement some methods in libiapp to register callbacks to occur when certain signals are set (sort of like libevent) but the storedir and signal global variable handler will just be functions called in the src/main.c loop. I'd like to implement a Squid-3 like method of registering event dispatchers but I will leave all of that alone until this is all stable and I've done planning into concurrency and SMP.

Its also possible that the reasons for registering dispatchers will go away with a slightly more sensible event abstraction (eg, if I convert the signal handlers to proper events (exactly like libevent!) which get pushed into the head of the event queue and called at the beginning of the next loop iteration - this however assumes the global variables that are set in the current signal handlers are only checked in the main loop and not elsewhere..!)

Async IO related hackery

2008-06-11T18:32:00.000-07:00

I've been staring at the Async IO code in preparation to migrate stuff out of the aufs directory and into a seperate library.

It requires the fd tracking code (understandable) and the comm code to monitor a notification pipe. This monitor pipe was used by the worker threads to wake up the main process if its waiting inside a select()/poll()/etc call, so it can immediately work on some disk IO.

Squid checks the aio completion queues each time through the comm loop. For aio, there isn't a per-storedir queue, there's just a global queue for all storedirs and other users, so aioCheckCallbacks() is called for each storedir.

There are two problems - firstly, select()/poll() take a while to run on a busy cache, so aioCheckCallbacks() isn't called that often. But the event notification based mechanisms end up running very often, returning a handful of filedescriptors each pass through the comm loop - and so the storedir checks are called. Secondly, its called once per storedir, so if you have 10 storedirs (like I have for testing!) aioCheckCallbacks() is called 10 times per IO loop.

This is a bit silly!

Instead, I've modified the async IO code to only call aioCheckCallbacks() when that pipe is written to. This ends up being the "normal" hack that UNIX thread programmers do to wake up a thread stuck waiting for both network and thread events. This cuts back substantially on the number of aioCheckCallbacks() calls without impacting performance (as far as I can see.)

Next! By default, the aufs store code only does async IO for open() and read() - write() and close() doesn't run asynchronously. Apparently this is due to testing under Linux - unless you're stressing the buffer cache too hard, write() to a disk FD didn't block, so there wasn't a reason to run write() and close() async. Apparently Solaris close() will block as metadata writes are done synchronously, and its possible FreeBSD + softupdates may do something similar. This is all "apparently", I haven't sat down and instrumented any of this!

FreeBSD and Solaris users have reported that diskd performs better than aufs - something I don't understand, as diskd only handles one outstanding disk IO at a time with similar issues with write() and close() to aufs (namely, if the calls block, the whole diskd process stops handling disk IO) but the difference here is the main process won't hang whilst these syscalls complete. Perhaps this is a reason for this behaviour. Its difficult for me to test; aufs has always performed fantastically for me.

There's so much to tidy up and reorganise, I still can't sit down and begin implementing any of the new features I want to!

More reorganisation..

2008-06-05T23:26:00.000-07:00

I've moved cbdata, mempools, fd and legacy disk (file_*) routines out of src/. I also shuffled the comm related -definitions- out but not the code. I hit a big of a snag - the comm code path used for connecting a socket to a remote site actually uses the DNS code. Fixing this will involve divorcing the DNS lookup stuff so sockets can be connected to a remote IP directly - and the DNS lookup path will just be in another module.

This however is more intrusive than "code reorganisation" so its going to have to wait a while. Unfortunately, this means that my grand plans for 1.1 will have to be put on hold a little until I've thought this out a little more and implemented it in a seperate branch.

Thus, things will change a little. 1.1 will be released shortly, with the current set of changes included. I'll then concentrate on planning out the next set of changes required to properly divorce the core event/disk code from src/.

Why do this? Well, the biggest reason is to be able to build "other" bits of code which reuse the Squid core. I can write unit tests for a lot of stuff, sure, but it also means I can write simple network and disk applications which reuse the Squid core and find exactly how hard I can push them. I can also break off a branch and hack up the code to see what impact changes make without worrying that said changes expose strange stuff in the rest of the Squid codebase.

The four main things that I'd like to finally sort out are:

IPv6 socket support - support v4/v6 in the base core, and make sure that it works properly
Sort out the messy disk related code and reintegrate async IO as a top-level disk producer (like it was in Squid-2.2 and it almost is in Squid-3) so it can be again used for things like logfile writing!
Begin looking at scatter/gather disk and network IO - gather disk IO should work out great for writing logfile buffers and objects to disk, for example
Design a parallelism model which allows multiple threads to cooperate on tasks - worker threads implementing callback type stuff for some work; entire seperate network event threads (look at memcached as an example.) "Squid" as it stands will simply run as one thread, but some CPU intensive stuff can be pushed into worker threads for some cheap parallelism gains (as on the roadmap, ACLs and rewriting/content manipulation are two easy targets.)

So there's a lot of work to do, and not a lot of time to do it in.

cacheboy 1.0 released

2008-05-24T17:19:00.001-07:00

Cacheboy 1.0 has been tagged, tarballed and port'ed. Its been in production at my beta testers site for a week or so now and hasn't missed a beat.

There's a lot more work to do to Cacheboy to shape it up like I believe Squid should've been; a stable 1.0 release is the first step along this path.

I'll let this settle for a couple weeks (ie, Adrian needs to sit his mid-year exams in two weeks!) before I begin some more larger-scale code refactoring and shuffling around.

Cacheboy-1.1 changes will include MemBuf, cbdata, most of the http request/reply/header manipulation code and potentially a little of the filedescriptor, disk, event and network communication code. This stuff forms the "core" of Squid/Cacheboy. I'll then look at some basic infrastructure changes to support IPv6 clients.

Like the Cacheboy-1.0 changes, these will not be terribly difficult or intrusive (the IPv6 client-only changes will be the most intrusive by far!) but a lot of refactoring, rewriting and shuffling about of the core needs to take place before I can begin work on the necessary stuff - HTTP/1.1, SMP, modularity, performance.

FreeBSD port update

2008-05-17T09:37:00.000-07:00

I've updated the port to CACHEBOY_0.PRE6; it also now defaults to the replacement shiny english errors (NewEnglish) rather than the default ones (English).

Revalidating objects in Polygraph

2008-05-16T23:14:00.000-07:00

I have a locally hacked up polygraph config based on datacomm-1. Datacomm-1 is a very simple workload which doesn't pretend to be the real world at all; it thus makes it really easy for me to implement custom bits of polygraph to test specific things.

One thing I needed to test was object revalidation. I needed objects to be revalidated in a relatively short period of time so I could trigger a storage revalidation bug in Squid-2.HEAD.

Here's the changes.

include/content.pg; added:

ObjLifeCycle olcRevalid = {

length = const(2min);

variance = 50%;

with_lmt = 100%;

expires = [

lmt + const(2min) : 5%,

now + const(5min) : 15%

];

};

content cntRevalid = {

kind = "revalid";

obj_life_cycle = olcRevalid;

size = logn(32KB, 32KB);

cachable = 80%;

checksum = 1%;

};

I then edited my locally modified datacomm-1.pg to set the contents to cntRevalid.

Now, I get stale objects popping up during the test - and I need to figure out why -that- is happening - but note that my life cycles are very quick (couple minutes). squid _should_ be good down to object lifetime of 1 second so I'm a bit surprised.

In any case, it tripped the bug, which is all that matters..

Cacheboy PRE6 is out

2008-05-16T23:00:00.001-07:00

I've just rolled PRE6. This includes the Squid-2.HEAD fix for the signed vs unsigned comparison bug I introduced earlier (which lead to a crash.)

This code -should- be stable enough for public consumption.

Error page update, phase 2

2008-05-14T13:38:00.000-07:00

I've gone and modified all the English error pages in my little playpen project.

Here's an example of a live DNS failure. Same (confusing) text with Squid; slightly nicer layout.

Errors shouldn't be ugly

2008-05-01T08:57:00.000-07:00

Part of my "things i hate about Squid" list includes the god awful error pages which haven't really changed since .. well, since I got involved with the project in 2000.

Here's my take on the "simple" error page. The text is exactly the same as the old error page (note that I haven't included the "Generated by.." footer text here, as thats included by Squid/Cacheboy) but I've reformatted the error page to use CSS for layout and then crafted a very simple example CSS.

Where is my CPU time going? (or how to divine useful information from oprofile)

2008-04-27T09:18:00.001-07:00

OProfile is cool - it lets you dig into where your CPU is being spent. But aggregating statistics can be aggrevating. (Yes yes, it was bad, I know..)

Take this example from cacheboy:

CPU: Core 2, speed 2194.48 MHz (estimated)
Counted CPU_CLK_UNHALTED events (Clock cycles when not halted) with a unit mask of 0x00 (Unhalted core cycles) count 100000
samples % image name symbol name
216049 6.5469 libc-2.7.so memcpy
115581 3.5024 libc-2.7.so _int_malloc
103345 3.1316 libc-2.7.so vfprintf
85197 2.5817 squid memPoolAlloc
64652 1.9591 libc-2.7.so memchr
60720 1.8400 libc-2.7.so strlen
...

Now, these tell you that CPU is being spent in the function (which is great) but its not the entire picture. The trouble is this: there's 527 functions in the top-level list, and 25 of them account for 1 or more percent of total runtime. Those top 25 account for ~ 45% of the total CPU time - so another 55% is being spent in the 501 functions remaining.

You may now ask yourself what the problem with that is - just optimise those top 25 functions and you'll be fine. Unfortunately, those top 25 functions aren't being called in one place - they're being called all over the shop.

Here's a example. Notice the strlen time:

496 13.7816 squid httpRequestFree
773 21.4782 squid httpHeaderPutStrf
9518 0.3432 libc-2.7.so vsnprintf
85433 55.6846 libc-2.7.so vfprintf
18212 11.8704 libc-2.7.so strchrnul
16037 10.4528 libc-2.7.so _IO_default_xsputn
13351 8.7021 libc-2.7.so _itoa_word
10872 7.0863 libc-2.7.so strlen
9518 6.2038 libc-2.7.so vsnprintf [self]

...

Note that the CPU times above "vsnprintf" are from the functions which call it, and CPU times below "vsnprintf" are the calls which it makes. Its not immediately obvious that I have to optimise "vsnprintf" calls from the top-level trace, as most of the *printf() calls end up being to "vsnprintf" (which shows up at 0.3% of CPU time) rather than "vfprintf" and friends.

Its obvious here that finding those places which call the *printf() functions in performance critical code - and then exorcising them - will probably help quite a bit.

What about the rest of the 500 odd functions? What I'd like to do is build aggregates of CPU time spent in different functions, including their called functions, and figure out which execution stacks are chewing the most CPU. Thats something to do after Cacheboy-1 is stable, and then only after my June exams.

The important thing here is that I have the data to figure out where Squid does things poorly and given enough time, I'm going to start fixing them in the next Cacheboy release.

Solaris Event Ports for Network IO

2008-04-23T10:48:00.000-07:00

What do I do at midnight to try and relax?

Figure out how to make Solaris Event Ports work for Network IO.

It took me a while to realise that "num" needs to be initialised with the minimum number of events you'd like to wait for before port_getn() returns. I haven't any idea whether this will restrict the returned event count to 1 or whether it will grow to MAX - this will need further testing. It is enough to handle single requests though, so its a start!

Knowing what your allocator is doing..

2008-04-20T02:58:00.000-07:00

I committed a change a few years ago which collapsed the mem_node struct + buffer into one structure. This relieved quite a high volume of allocator requests, but it made the structure slightly larger than 4k.

Modern malloc implementations (and its possible earlier ones circa 2001 did too; remember I was only 21 then!) have a separation between "small" and "large" (and "huge"!) objects. Small objects (say, under a page size) will generally go in a pool of just those object sizes. Large objects (from say page size to something larger, like a megabyte) will be allocated a multiple of pages.

This unfortunately means that my 4096 + 12 byte structure may suddenly take 8192 bytes of RAM! Oops.

I decided to test this out. This is what happens when you do that with FreeBSD's allocator. Henrik has tried this under GNUMalloc and has found that the 4108 byte allocation doesn't take two pages.

[adrian@sarah ~]$ ./test1 test1 131072
allocating 12, then 4096 byte structures 131072 times..
RSS: 537708
[adrian@sarah ~]$ ./test1 test2 131072
allocating 4108 byte structure 131072 times..
RSS: 1063840

"Dial before you Dig"

2008-04-19T04:43:00.000-07:00

This is the sort of stuff lurking in the Squid codebase which really needs to be cleaned out.

The short:

http://code.google.com/p/cacheboy/source/detail?r=12592

The long:

I'm going through the legacy memory allocator uses and pushing the allocator initialisation out to the modules themselves rather than having some of them globally initialised. This will let me push the buffer allocator code (ie, the "rest" of the current legacy memory allocator uses) outside of the Squid/cacheboy src/ directory and allows them to be reused by other modules. I can then begin pushing some more code out of the src/ directory and into libraries to make dependencies saner, code reuse easier and unit testing much easier.

One of these types is MEM_LINK_LIST.

A FIFO type queue implementation was implemented using an single linked list. An SLIST has an O(1) dequeue behaviour but an O(n) queue behaviour - the whole list has to be traversed to find the end before it can append to the end. This requires touching potentially dirty pages which may also stall the bus a little. (I haven't measured that in my testing btw; my benchmarking focused on the memory-hit/miss pathway and left ACLs/disk access out - thus thats all currently conjecture!)

The FIFO implementation allocated a temporary list object (MEM_LINK_LIST) to hold the next and data pointers. This was mempooled and thus "cached", rather than hitting the system malloc each time.

The only user is the threaded aufs storage code - to store the pending disk read and write operations for a given open storage file.

Now, the "n" in O(n) shouldn't be that great as not very many operations are queued on an open file - generally, there's one read pending on a store file and potentially many writes pending on a store file (if the object is large and coming in faster than 4kbytes every few milliseconds.) In any case, I dislike unbounded cases like this, so I created a new function in the double-linked list type which pops the head item off the dlink list and returns it (and returns NULL if the list is empty) and re-worked the aufs code to use it. The above link is the second half of the work - read the previous few commits for the dlink changes.

Note: I really want to move all of this code over to the BSD queue/list types. ARGH! But I digress.

Initial testing shows that I haven't screwed anything up too badly. (~400 req/sec to a pair of 10,000 RPM 18gig SCSI disks, ~50mbit client traffic, 80% idle CPU.)

Development thus far

2008-04-17T18:44:00.000-07:00

The initial release has been done. The cacheboy-0pre1 release is just a vanilla Squid-2.HEAD tree with the first part of the code reorganisation included - they should be 1:1 bug compliant.

There's a developer who has found a bug in Squid-2.HEAD relating to larger-than-requested data replies in the data pipeline. That shows up during Vary processing. It shouldn't show up in Squid-2.HEAD / Cacheboy as I committed a workaround.

The Squid-2.HEAD / Cacheboy stuff should give a ~5% CPU reduction over Squid-2.7 (dataflow changes), and a ~10% CPU reduction over Squid-2.6 (HTTP parsing changes).

Next: sorting out the rest of the code shuffling - the generic parts of the mem and cbdata routines, and then a look at the comm and disk code.

Experiences with Google Code

2008-04-13T17:18:00.001-07:00

I've imported a Squid-2.HEAD CVS repository (with complete history!) into Google Code. This -mostly- worked, although!

There were some Subversion gatewaying issues inside Google somewhere which made SVN transactions occasionally fail - they've rolled back these changes and things work again!
I'm not getting any commit messages for some reason!
SVNSYNC takes -far too long- : building the SVN repo from CVS took about 5 minutes. Syncing my local SVN repo to the Google Code repo? 2 days.
The size of my repository hangs browsers that try to run the Google Code "source browse" feature. Heh!
$Id$ tag version numbers have been munged into Subversion revision numbers. Argh! I wish it were obvious this was going to happen! (And because of the above times, I really can't be bothered re-building the repository just yet.)

All in all though I've been happy with the service - Google employees pipe up on the code hosting group and are generally helpful. The "wiki contents in SVN" trick is cute. The source browser was nice when it worked! And I like the simple UI for things like revision browsing.