Hi. I've been looking at the algorithms modssl uses for managing the SSL session cache in shared memory, and specifically at the newer "cyclic buffer" algorithm.
I have an question/idea/rambling about it, it's going to be a little long, sorry ;) I believe the cyclic-buffer design is very good, especially its natural handling of expiration and overflow of the cache before sessions expire. The time-complexity of additions of new sessions to the cache, as well as that of expiring old ones or making more room when needed, is O(1) (where N is the number of sessions in the cache), and these operations always succeed. However, it appears to me that the session-cache lookup is *not* O(1), and I've been wondering if this is considered acceptable, e.g., because other Apache and hardware constraints limit the server's scalability anyway? As I mention below, the current lookup algorithm is indeed very good for all "normal" session-cache sizes, so my question is more theoretical, about how well it will scale as very-high-end servers get better specialized hardware, have more memory, and expect to handle higher loads. If I understand correctly, the lookup works by searching the index of a whole "division" (when a cache is full, 1/256 of the N entries or more, usually around sqrt(N) entries), one by one, until a match for the second byte is found (at which point the whole session id is compared). For N < 65000 or so, this means (again, if I understand correctly) a lookup length of around sqrt(N)/2. For larger N, the lookup length is worse, around N/256/2, with the search becoming even slower because the second-byte comparisons start yielding more false positives at this point. As always, O(sqrt(N)) or O(N) complexities become worse as N increases. When N=65536, and the cache is full, the average number of comparisons for a session-id lookup is (if I'm calculating correctly) 128. When N=131072, the average number of comparisons for a lookup grows to 256, and the fact that only 2 bytes are used for the quick comparison will start taking its additional toll. 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 comparisons a lookup needs is roughly 32 (if I'm calculating this correctly). This is certainly not bad, and should give excellent results for this algorithm (as indeed I see people are reporting). While N=3000 is typical, N=65536 is probably not because it results in a very big cache, about 10MB. N=131072, 20MB, is probably considered ridiculously large. Is this why such N's were considered uninteresting and this lookup algorithm was deemed good enough in all practical cases? If anyone is wondering why I'm thinking about this issue, and why someone may want more than the 500Kbyte session-cache (N=3000 sessions), think about the following calculation: let's say that from a bit of research you find that most browsers will reuse a session within two minutes of its first creation. If you want the session cache to hold each new session for two minutes (120 seconds), you would want to hope that you will not get more than 25 (=3000/120) new sessions (i.e., new users) per second. For most moderately-loaded servers with ordinary hardware, this assumption is good - the CPU might not even be able to handle much more than 25 RSA operations per second, and 25 new sessions a second translates to 2 million SSL sessions a day - a very busy server indeed. But what about a very-high-end server with an "SSL acceleration" card (a card that, among other things, does RSA operations in hardware)? Such cards are typically rated for doing 1,000, or even much more, RSA operations per second, meaning that the server can theoretically now easily handle, for example, 500 new sessions per second (I'm saying theoretically, because in real life Apache might not be able to handle such a load because of limits on the number of processes, memory, and so on). 500 new sessions per second, each we hope to keep for 120 seconds, dictates 60,000 entries in the session cache. For example. Anyway, if such huge session caches will ever be of interest, perhaps the lookup algorithm should be replaced by something else, perhaps an additional simple hash table using the session-id as key (no need for hash function other than a modulo)? I'm not talking about a complicated generic hash table like the "ht" session cache - I'm talking about a simple array of indices pointing into positions of the cyclic buffer, and each entry in that buffer will also hold "next" indices for keeping the bucket's chain. If we assume that no "subcache" will hold more than 65536 entries, we can use 2-byte indices for all those "pointers", and such hash-table's overhead will be as low as 4-6 bytes per session in the cache. A slight computational overhead will also be incurred for updating the hash-table structure on changes to the cyclic buffer. I've implemented such a data structure once (for holding a cache of recently seen packet numbers to avoid acting on a retransmitted packet twice), and it seemed to work quite well. I'm guessing that because the current lookup algorithm is quite good for all typical session-cache size, it might not make too much sense modifying the algorithm now. but perhaps it's worth thinking about for the future. What do you think? -- Nadav Har'El | Wednesday, Oct 9 2002, 4 Heshvan 5763 [EMAIL PROTECTED] |----------------------------------------- Phone: +972-53-245868, ICQ 13349191 |Disclaimer: The opinions expressed above http://nadav.harel.org.il |are not my own. ______________________________________________________________________ Apache Interface to OpenSSL (mod_ssl) www.modssl.org User Support Mailing List [EMAIL PROTECTED] Automated List Manager [EMAIL PROTECTED]
