Date: Thu, 28 Jun 2012 22:17:05 +0200 From: Stefan Esser <se@freebsd.org> To: FreeBSD developers <hackers@FreeBSD.org> Subject: [PATCH] Fix for negative cacheing problem in NSCD Message-ID: <4FECBBC1.3000800@freebsd.org> In-Reply-To: <4FEAA3C1.2040807@freebsd.org> References: <CAGE5yCqM4OwUyvW1OW1vz7dP2G0zTQCU4P99bJdVASndg8SpAw@mail.gmail.com> <4FEAA3C1.2040807@freebsd.org>
next in thread | previous in thread | raw e-mail | index | archive | help
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--
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?4FECBBC1.3000800>