From owner-freebsd-hackers@FreeBSD.ORG Thu Jun 28 20:17:11 2012 Return-Path: Delivered-To: hackers@freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [69.147.83.52]) by hub.freebsd.org (Postfix) with ESMTP id 938721065674 for ; Thu, 28 Jun 2012 20:17:11 +0000 (UTC) (envelope-from se@freebsd.org) Received: from nm9.bullet.mail.ukl.yahoo.com (nm9.bullet.mail.ukl.yahoo.com [217.146.182.250]) by mx1.freebsd.org (Postfix) with SMTP id A34F58FC1A for ; Thu, 28 Jun 2012 20:17:10 +0000 (UTC) Received: from [217.146.183.183] by nm9.bullet.mail.ukl.yahoo.com with NNFMP; 28 Jun 2012 20:17:04 -0000 Received: from [77.238.184.71] by tm14.bullet.mail.ukl.yahoo.com with NNFMP; 28 Jun 2012 20:17:04 -0000 Received: from [127.0.0.1] by smtp140.mail.ukl.yahoo.com with NNFMP; 28 Jun 2012 20:17:04 -0000 X-Yahoo-Newman-Id: 600360.4893.bm@smtp140.mail.ukl.yahoo.com X-Yahoo-Newman-Property: ymail-3 X-YMail-OSG: 8f6UlLwVM1n5ttpSZw9NlubZgRSUf7BKNsuxXBI_v5NdV.s srvb_2gSPiC8Bek7UI612_w3lJ8fj95Y7CPiLkhkADG7bFesY3PwkhETfOCk rC1jA.xa5lXBSbnmnx2PjzweLG5vo009IS2_krClPc7Mq_WYTC10cJfV9whq C03ON613fnns3XlPjhaPD1p_3Eo1BDys.sDkR_g.xuFtx1KC2rZPIPCoRdCF oLSpfaSo1XIhLB7PZOZWuWiG68KgGAq7O2Qc986eXXYIzdvK8sV3rKhZSGl. IevowY6PKLGJvV_JdB9U4XdH83KU9IvfWiBS3SdYyvfQ0FcXUnQgfxgufbKC gtC_wSg65oD.rv8yREScN4draZhA40Js9H36tP_ExKbllVliZp_2wO9wUC78 HUA-- X-Yahoo-SMTP: iDf2N9.swBDAhYEh7VHfpgq0lnq. Received: from [192.168.119.11] (se@81.173.146.169 with plain) by smtp140.mail.ukl.yahoo.com with SMTP; 28 Jun 2012 20:17:04 +0000 GMT Message-ID: <4FECBBC1.3000800@freebsd.org> Date: Thu, 28 Jun 2012 22:17:05 +0200 From: Stefan Esser User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:13.0) Gecko/20120614 Thunderbird/13.0.1 MIME-Version: 1.0 To: FreeBSD developers References: <4FEAA3C1.2040807@freebsd.org> In-Reply-To: <4FEAA3C1.2040807@freebsd.org> Content-Type: multipart/mixed; boundary="------------040406000400060803010701" Cc: Subject: [PATCH] Fix for negative cacheing problem in NSCD X-BeenThere: freebsd-hackers@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Technical Discussions relating to FreeBSD List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 28 Jun 2012 20:17:11 -0000 This is a multi-part message in MIME format. --------------040406000400060803010701 Content-Type: text/plain; charset=windows-1252 Content-Transfer-Encoding: 7bit The Name Service Cache Daemon (NSCD) is useful, but may get in your way if you modify data that is cached and have the cache return stale data until expiry. One common scenario is an installation script that creates the required user account, but first checks whether the account name is currently unused. The query result (user does not exist) will be cached by NSCD and will be returned even after the user has been created in the password database (or in LDAP or whatever). One solution is to signal changes of the database to NSCD, but that requires an interfaces between the programs that modify possibly cached data and NSCD. A short timeout for negative query results is possible, but limits the effectiveness of the cache. I propose a different solution, which completely fixes the behavior in the scenario given above: I have prepared a patch to NSCD that allows to specify a threshold for negative queries. Requests for negative entries are only answered from the cache after the specified number of attempts has been made to get the result from the underlying files/databases. A high number does effectively disable negative caching, but I doubt that more than 3 is useful under normal conditions (this allows for 2 failures before the negative entry is trusted). Rate limiting of queries with negative results continues to work with this patch, since at most the specified number of retries is made within the TTL of the cache entry. A patch against -CURRENT is attached. It does not change the default behavior in any way, so I think it would be save to commit to HEAD, with possible MFC (since nothing changes unless you use the new parameters). This patch has been tested with the hosts database and verified to work as expected in my test cases. To activate a negative query threshold you have to add lines like the following to ncsd.conf:: negative-confidence-threshold hosts 3 negative-confidence-threshold passwd 2 negative-confidence-threshold group 2 A value of 2 will generally be sufficient. In the scenario where you query the user DB to check that an account is free to use, there is exactly one pro query with negative reply, before the user is added and the query succeeds. A second probe would cache the negative reply. Please let me know, whether it helps in situations with wrong negative cacheing. I'm also interested in any problems you observe with the patch. It would be great, if a native speaker had a look at the patch for the man-page since I'm not convinced it is correct and easy to understand. And finally: Please suggest a better name for the parameter ... I do not like "negative-confidence-threshold", but did not find any better phrase. Regards, STefan PS: The patch contains an undocumented option to also set the positive confidence threshold. Entries are put into the cache but the original data sources are still queried, if the results do not match for at least the number of successive queries specified. Not sure whether this is useful, it was fall-out of the negative threshold change ... One possible use case is DNS based load-balancing. If NSCD is configured with "positive-confidence-threshold hosts 3" then it will require 3 identical replies for a host name before it is willing to cache that reply. Any host with fixed IP will soon be resolved from the cache, but hosts with changing IP will continue to be queried via DNS (until the specified number of identical results is received). Hmmm, I'm not sure whether this works as advertised, since any change in the returned data (including TTL) would cause the counter to start over ... PPS: I have not tested multipart queries; they should continue to work as before (with a fixed threshold of 1). I have not verified that this is the correct behavior, and have run out of time for today ... --------------040406000400060803010701 Content-Type: text/plain; charset=windows-1252; name="nscd-Negative-Threshold.patch" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="nscd-Negative-Threshold.patch" Index: cachelib.h =================================================================== --- cachelib.h (revision 237713) +++ cachelib.h (working copy) @@ -92,6 +92,7 @@ size_t satisf_elemsize; /* if entry size is exceeded, * this number of elements will be left, * others will be deleted */ + int confidence_threshold; /* number matching replies required */ struct timeval max_lifetime; /* if 0 then no check is made */ enum cache_policy_t policy; /* policy used for transformations */ }; @@ -116,6 +117,7 @@ size_t value_size; struct cache_policy_item_ *fifo_policy_item; + int confidence; /* incremented for each verification */ }; struct cache_ht_item_ { Index: config.c =================================================================== --- config.c (revision 237713) +++ config.c (working copy) @@ -209,6 +209,7 @@ positive_params.max_elemsize = DEFAULT_POSITIVE_ELEMENTS_SIZE; positive_params.satisf_elemsize = DEFAULT_POSITIVE_ELEMENTS_SIZE / 2; positive_params.max_lifetime.tv_sec = DEFAULT_POSITIVE_LIFETIME; + positive_params.confidence_threshold = DEFAULT_POSITIVE_CONF_THRESH; positive_params.policy = CPT_LRU; memcpy(&negative_params, &positive_params, @@ -216,6 +217,7 @@ negative_params.max_elemsize = DEFAULT_NEGATIVE_ELEMENTS_SIZE; negative_params.satisf_elemsize = DEFAULT_NEGATIVE_ELEMENTS_SIZE / 2; negative_params.max_lifetime.tv_sec = DEFAULT_NEGATIVE_LIFETIME; + negative_params.confidence_threshold = DEFAULT_NEGATIVE_CONF_THRESH; negative_params.policy = CPT_FIFO; memset(&default_common_timeout, 0, sizeof(struct timeval)); Index: config.h =================================================================== --- config.h (revision 237713) +++ config.h (working copy) @@ -44,9 +44,11 @@ #define DEFAULT_POSITIVE_ELEMENTS_SIZE (2048) #define DEFAULT_POSITIVE_LIFETIME (3600) +#define DEFAULT_POSITIVE_CONF_THRESH (1) #define DEFAULT_NEGATIVE_ELEMENTS_SIZE (2048) #define DEFAULT_NEGATIVE_LIFETIME (60) +#define DEFAULT_NEGATIVE_CONF_THRESH (1) /* (2) ??? */ #define DEFAULT_MULTIPART_ELEMENTS_SIZE (1024 * 8) #define DEFAULT_MULITPART_SESSIONS_SIZE (1024) Index: nscd.conf.5 =================================================================== --- nscd.conf.5 (revision 237713) +++ nscd.conf.5 (working copy) @@ -107,6 +107,16 @@ The value should be a prime number for optimum performance. You should only change this value when the number of cached elements is significantly (5-10 times) greater than the default hash table size (257). +.It Va negative-confidence-threshold Oo Ar cachename Oc Op Ar value +The number of times a query must have failed before the cache accepts +that the element can not be found. This makes it possible to check for +the existence of an element, before this element is created in one of +the data sources queried by +.Xr nscd 8 . +If this parameter is at its default value of 1, then the negative +result of the first request will be considered valid for the duration +of the TTL. A value of 2 will require two failed queries for the same +element, before this information is returned by the cache. .It Va keep-hot-count Oo Ar cachename Oc Op Ar value The size limit of the cache with the given .Ar cachename . Index: parser.c =================================================================== --- parser.c (revision 237713) +++ parser.c (working copy) @@ -167,6 +167,41 @@ TRACE_OUT(set_negative_time_to_live); } +static void +set_positive_confidence_threshold(struct configuration *config, + const char *entry_name, int conf_thresh) +{ + struct configuration_entry *entry; + + TRACE_IN(set_positive_conf_thresh); + assert(conf_thresh > 0); + assert(entry_name != NULL); + + entry = find_create_entry(config, entry_name); + assert(entry != NULL); + memcpy(&entry->positive_cache_params.confidence_threshold, + &conf_thresh, sizeof(conf_thresh)); + + TRACE_OUT(set_positive_conf_thresh); +} + +static void +set_negative_confidence_threshold(struct configuration *config, + const char *entry_name, int conf_thresh) +{ + struct configuration_entry *entry; + + TRACE_IN(set_negative_conf_thresh); + assert(conf_thresh > 0); + assert(entry_name != NULL); + entry = find_create_entry(config, entry_name); + assert(entry != NULL); + memcpy(&entry->negative_cache_params.confidence_threshold, + &conf_thresh, sizeof(conf_thresh)); + + TRACE_OUT(set_negative_conf_thresh); +} + /* * Hot count is actually the elements size limit. */ @@ -393,6 +428,12 @@ fields[1], value); continue; } else if ((field_count == 3) && + (strcmp(fields[0], "positive-confidence-threshold") == 0) && + ((value = get_number(fields[2], 1, -1)) != -1)) { + set_positive_confidence_threshold(config, + fields[1], value); + continue; + } else if ((field_count == 3) && (strcmp(fields[0], "positive-policy") == 0) && (check_cachename(fields[1]) == 0) && ((value = get_policy(fields[2])) != -1)) { @@ -416,6 +457,12 @@ fields[1], value); continue; } else if ((field_count == 3) && + (strcmp(fields[0], "negative-confidence-threshold") == 0) && + ((value = get_number(fields[2], 1, -1)) != -1)) { + set_negative_confidence_threshold(config, + fields[1], value); + continue; + } else if ((field_count == 3) && (strcmp(fields[0], "negative-policy") == 0) && (check_cachename(fields[1]) == 0) && ((value = get_policy(fields[2])) != -1)) { Index: cachelib.c =================================================================== --- cachelib.c (revision 237713) +++ cachelib.c (working copy) @@ -726,6 +726,12 @@ TRACE_OUT(cache_read); return (-1); } + /* pretend that entry was not found if confidence is below threshold*/ + if (find_res->confidence < + common_entry->common_params.confidence_threshold) { + TRACE_OUT(cache_read); + return (-1); + } if ((common_entry->common_params.max_lifetime.tv_sec != 0) || (common_entry->common_params.max_lifetime.tv_usec != 0)) { @@ -826,6 +832,24 @@ item = HASHTABLE_GET_ENTRY(&(common_entry->items), hash); find_res = HASHTABLE_ENTRY_FIND(cache_ht_, item, &item_data); if (find_res != NULL) { + if (find_res->confidence < common_entry->common_params.confidence_threshold) { + /* duplicate entry is no error, if confidence is low */ + if ((find_res->value_size == value_size) && + (memcmp(find_res->value, value, value_size) == 0)) { + /* increase confidence on exact match (key and values) */ + find_res->confidence++; + } else { + /* create new entry with low confidence, if value changed */ + free(item_data.value); + item_data.value = malloc(value_size); + assert(item_data.value != NULL); + memcpy(item_data.value, value, value_size); + item_data.value_size = value_size; + find_res->confidence = 1; + } + TRACE_OUT(cache_write); + return (0); + } TRACE_OUT(cache_write); return (-1); } @@ -839,6 +863,8 @@ memcpy(item_data.value, value, value_size); item_data.value_size = value_size; + item_data.confidence = 1; + policy_item = common_entry->policies[0]->create_item_func(); policy_item->key = item_data.key; policy_item->key_size = item_data.key_size; --------------040406000400060803010701--