On Thu, Oct 10, 2002, Geoff Thorpe wrote about "Re: Question about session-cache algorithms": > I suppose as the author of the implementation you're disecting I should > probably respond in some way :-)
Thanks. Your response was very educating. > If you check the "shmht" implementation (which is what "shmcb" was > created to replace) you'll see that a linear search was being conducted Yes, I didn't mention that, but I had already known that shmcb was a lot better than shmht, for a number of reasons, which is why I didn't even try looking into the (non-)scalability of shmht. I had already read http://marc.theaimsgroup.com/?l=apache-modssl&m=98531062704750&w=2 in which you explained the differences between shmcb and shmht - it was a very good explanation. > operation, you've got serious trouble. I'm quietly confident that you > could add a "for(loop=0;loop<1000;loop++){}" loop around the cache I guess that if that's the case (I have to admit, I didn't do any benchmarking before asking my question), then indeed even a growth of typical cache sizes 1000-fold won't make a noticable difference - so indeed there is no need to worry about this scalability issue - at all. > subcache of order O(sqrt(N)) to "search" rather than N (I think you > muddled this up in your analysis). The second-byte tests in the > subcache iteration are so considerably faster than an ASN1 decode > function call that we can generally ignore them for complexity > arguments. Oh, I counted the second-byte comparisons in my complexity analysis, which is why I always got 256 times what you got :) > So you will likely ASN1 decode (sqrt(N)/256)/2 sessions (ie. > sqrt(N)/512 of them) during a lookup in a full (sub)cache. This is less Note that the number sqrt(N) is correct only till N=65536. From there on (if I understand correctly), the number of subcaches remains 256, and you start having N/256 entries per cache, so on average have something like N/65536 (not sqrt(N)/256)) ASN1 decodes. But obviously this only makes a difference for huge Ns, and you convinced me that these are anyway not as useful as I thought they may be. > cache without optimisations like the second-byte test. As for lowering > the number of false-positives in the lookup as you seem to be > suggesting - that's not that hard; rather than taking the second byte > as an optimisation, we could take the fifth, sixth, seventh and eighth > bytes (ie. the second word) and memcpy() them into a "second word" This will only the number of false-positive ASN1 decodes, not the number of indices that are compared. But you did convince me that even these O(sqrt(N)) or O(N/256) comparisons can scale to much more than anything even high-end servers will want to handle in the next decade :) > > To put the numbers in perspective (and to show that the example Ns > > above are untypically large), a session cache of size 500Kbytes is > > typically used in Apache, making room for only about N=3000 > > session-cache entries. In this case, the typical number of one-byte > > That's if your sessions are "normal" (between 100 and 150 bytes each). > If you're using client-certs then each such client-authenticated > session can easily blow out to over 1Kb (the sessions contain the > client-cert encoded within them). This is a very good point, I forgot about it. > finish. The numbers you start to talk about would bury any kind of > conventional server - and having worked with a lot of crypto hardware I > can assure you that even when offloading *all* crypto operations to > hardware (in a zero-overhead zero-latency utopia) you will still bang > your head against processing overheads in the SSL/TLS logic (the ASN1 > code particularly) and of course in the kernel - there's a lot of > networking and memory paging involved, and if you're using hardware, > the driver's going to be busy as hell too. Yes, although I did personally see a demonstration of a server, using an SSL acceleration card, that could do 500 new SSL sessions per second (note that all the requests were very quick and came from a LAN - otherwise Apache couldn't handle this with its 250-process limit). > The problem that shmcb did not address is parallelism - if you ran a > benchmark against a version of mod_ssl using shmht that was built with > profiling, and benchmarked using multiple requests in parallel, I > expect that you'd have found that httpd processes were often waiting on > the mutex lock for the cache. Whilst a single process is doing a (slow) > lookup on the cache, all other processes needing to do a cache This is a very good point. Naturally, any super-server like I imagined in my first post will have multiple CPUs, so you're right, this issue will be more important than whether 10 or 500 bytes are being compared. > However, I suspect that once you get into these sorts of extra-planetary > demands you're already going to be using multiple servers to handle > loads - apart from the fact you need to be able scale your server > environment without buying a brand new super-computer each time you > need more juice, you also need some redundancy and fault-tolerance; Again, you're right. I'm convinced - there's no need to change shmcb :) > Which leads to a shameless plug for *another* cache implementation you > might want to analyse when you start to look beyond the limits of > shmcb; > http://www.distcache.org/ > > BTW: Apache 2.0.43 support for distcache will be released in a day or > two, as will the first patch kit for Apache 1.3.*+mod_ssl. Thanks, I'll look at it. Thanks for explaining to me how silly my worries about shmcb's scalability were (oh, and thanks for writing it in the first place :) ). Nadav. -- Nadav Har'El | Thursday, Oct 10 2002, 5 Heshvan 5763 [EMAIL PROTECTED] |----------------------------------------- Phone: +972-53-245868, ICQ 13349191 |"Outlook not so good." Wow! That magic 8- http://nadav.harel.org.il |ball knows everything! So, what about IE? ______________________________________________________________________ Apache Interface to OpenSSL (mod_ssl) www.modssl.org User Support Mailing List [EMAIL PROTECTED] Automated List Manager [EMAIL PROTECTED]
