Opened 9 years ago

Closed 9 years ago

#356 closed enhancement (complete)

Resolver address database

Reported by: stephen Owned by: vorner
Priority: medium Milestone:
Component: Unclassified Version:
Keywords: Cc:
CVSS Scoring: Parent Tickets:
Sensitive: no Defect Severity:
Sub-Project: Feature Depending on Ticket:
Estimated Difficulty: 0.0 Add Hours to Ticket: 0
Total Hours: 0 Internal?: no

Description

Part of the early work on recursion, this is the component that stores address information for nameservers.

Subtickets

Change History (25)

comment:1 Changed 9 years ago by stephen

  • Owner changed from stephen to UnAssigned
  • Status changed from new to reviewing

I've just committed (r3272) a set of basic classes that will be used in this component, and feel that it would be useful to have a review done of the work to date.

comment:2 Changed 9 years ago by ocean

  • Owner changed from UnAssigned to stephen
  1. zone_entry.h
    • Suggest to remove "using namespace std;" from .h file and put 'std' prefix to related type.
    • Suggest to change ZoneEntry's ctor from
ZoneEntry(AbstractRRset* nsrrset, vector<AbstractRRSet*> additional);

to

ZoneEntry(AbstractRRset* nsrrset, const vector<AbstractRRSet*>& additional);

to avoid additional copying.

  • Suggest to change the member variable of nameserver_ to nameservers_ to indicate that it may contain multiple items.
  1. nsas_types.h
    • Suggest to change NasAddress to NsasAddress to keep the acronyms consistent.
  1. nameserver_entry.h
  • Suggest to remove "using namespace" statements from header file.
  • Suggest to add "const" to the input pointer variable:
NameserverEntry(AbstractRRset* v4Set, AbstractRRset* v6Set, time_t curtime = 0);

to

NameserverEntry(const AbstractRRset* v4Set, const AbstractRRset* v6Set, time_t curtime = 0); 
  • Suggest to add a "virtual destructor" to NameServer class.

See. http://www.parashift.com/c++-faq-lite/virtual-functions.html#faq-20.7

  • Suggest to add "inline" indicator to the small "accessor" functions.

I'm not sure whether the compiler will inline the code automatically, but add "inline" should do no harm.

  • For class of AddressSelection, what is the type lf "result_type" ?

A little confused.

  • Suggest to change member variable "class_" of class ZoneEntry to "classCode_" to keep consistent with the same variable in NameserverEntry.
  1. address_entry.h
    • Suggest to move declaration of "UNREACHABLE" to "private" section, since it is used only internally.
  • Suggest to initialize UNREACHABLE in the header file
static const uint32_t UNREACHABLE =UINT32_MAX;  ///< RTT indicating unreachable address
  • Suggest to change
virtual uint32_t size() {

to

virtual uint32_t size() const  {

BTW, I'm a little confused by the comments:

/// as list.size() may take some time if the list is big.

In my understanding, the std::list should also keep a separate count_ internally, so std::list::size() should also be O(1) no matter how big the list is.

  • Suggest to change
virtual uint32_t getMaxSize() {

to

virtual uint32_t getMaxSize() const { 
  • Since LruList is also a virtual class, so I suggest to add a "Virtual Destructor" to it.
  1. hash.h
    • Shall this be shared by other component? If so, suggest to move it to a more common library such as utility. otherwise change its name to nsas_hash.h
    • Suggest to add "const" to the operator() and mapLower() function, since they do not modify any member variable
    virtual uint32_t operator()(const char* key, uint32_t keylen, bool ignorecase = true) const;
    unsigned char mapLower(unsigned char inchar) const {
  • suggest to remove "using namespace std" declaration in header file
  1. hash_table.h
    • The HASHTABLE_SIZE is defined but not used

comment:3 Changed 9 years ago by stephen

  • Owner changed from stephen to ocean
  1. zone_entry.h
  • Suggest to remove "using namespace std;" from .h file and put 'std' prefix to related type.

Good point - done.

  • Suggest to change ZoneEntry's ctor from

ZoneEntry(AbstractRRset* nsrrset, vector<AbstractRRSet*> additional);
to
ZoneEntry(AbstractRRset* nsrrset, const vector<AbstractRRSet*>& additional);
To avoid additional copying.

Whoops, missed the "&" - done.

  • Suggest to change the member variable of nameserver_ to nameservers_ to indicate that it may contain multiple items.

Done.

  1. nsas_types.h
  • Suggest to change NasAddress to NsasAddress to keep the acronyms consistent.

Done.

  1. nameserver_entry.h
  • Suggest to remove "using namespace" statements from header file.

Done.

  • Suggest to add "const" to the input pointer variable:

NameserverEntry(AbstractRRset* v4Set, AbstractRRset* v6Set, time_t curtime = 0);
to
NameserverEntry(const AbstractRRset* v4Set, const AbstractRRset* v6Set, time_t curtime = 0);

Done.

  • Suggest to add a "virtual destructor" to NameServer class.

See. http://www.parashift.com/c++-faq-lite/virtual-functions.html#faq-20.7

Done.

  • Suggest to add "inline" indicator to the small "accessor" functions.

I'm not sure whether the compiler will inline the code automatically, but add "inline" should do no harm.

My understanding is that declaring the body of the code in the class definition is an implicit inline request, so the "inline" keyword is not needed here.

  • For class of AddressSelection, what is the type lf "result_type" ?

A little confused.

bool. This is a data type from the binary_function class, the others being "first_argument_type" and "second_argument_type". They are typedefs to the template argument parameters, and using them means that the implementation of the function does not have to be altered if the template arguments are changed. In this case though, the function is sufficiently simple and so unlikely to be altered that the advantage of result_type is outweighed by its obscurity. I've changed it to bool.

Also, I've rearranged the boolean expression to make it clearer.

  • Suggest to change "class_" of class ZoneEntry to "classCode_" to keep consistent with NameserverEntry.

Good suggestion - done.

  1. address_entry.h
  • Suggest to move declaration of "UNREACHABLE" to "private" section, since it is used only internally.

True. However, it's been set public so that the internal operation can be tested.

  • Suggest to initialize UNREACHABLE in the header file
  • static const uint32_t UNREACHABLE =UINT32_MAX; /< RTT indicating unreachable address

I've left it in the .cc file because of the need to define the macro __STD_LIMIT_MACROS before including stdint.h in order to get UINT32_MAX defined. Isolating it in the .cc file avoids any problems with this additional macro definition.

(lru_list.h)
BTW, I'm a little confused by the comments:
/ as list.size() may take some time if the list is big.
In my understanding, the std::list should also keep a separate count_ internally, so std::list::size() should also be O(1)

I'd thought that as well, but Scott Meyers in "Effective STL" (ISBN 978-0-201-74962-5) suggests that in some implementations, this may not be the case. The problem is the splice() call - knowing how many elements are being spliced into a list requires counting those elements, which can only be done by a traversal of the range being spliced; this slows down the operation. So he suggests that some implementations, in a bid to keep splice() fast, may not keep a running count of the list size. (This is actually discussed in "item 4", an article where he advocates the use of list.empty() in preference to (list.size() == 0).)

It may be an unnecessary complication but as it is just an increment/decrement of a counter, I suggest we leave it it for now.

  • Suggest to change

virtual uint32_t size() {
to
virtual uint32_t size() const {

Done.

  • Since LruList is also a virtual class, so I suggest to add a "Virtual Destructor" to it.

Done.

  1. hash.h
  • Shall this be shared by other component? If so, suggest to move it to a more common library such as utility, otherwise change its name to nsas_hash.h

Probably not, although I think there are some parts of the code that may well be more general. I suggest we stay as we are and if it turns out that some code proves more generally useful, we'll move them at that time.

  • Suggest to "const" to the operator() and mapLower() function, since they do not modify any member variable

virtual uint32_t operator()(const char* key, uint32_t keylen, bool ignorecase = true) const;

unsigned char mapLower(unsigned char inchar) const {

Done.

  • suggest to remove "using namespace std" declaration in header file

Done.

Good review, thank you. These changes have been committed to the branch in r3372.

comment:4 Changed 9 years ago by ocean

  • Owner changed from ocean to stephen
  1. hash_table_unittest.cc

Suggest to declaration and define one const static variable named HASHTABLE_DEFAULT_SIZE = 1009 in HashTable class,
so in HashTableTest don need to use magic number 1009 directly (ref UNREACHABLE in AddressEntry class), so when
someday if we need to change the default value, we only need to change in one place.

  1. hash_unittest.cc

The comments:

    // unique values, so it does change the size of the array.  The call to

should be

    // unique values, so it does not change the size of the array.  The call to
  1. lru_list_unittest.cc

Maybe we should choose a better name for Expired in LruList to avoid confusion with expiration of TTL.

  1. nameserver_entry_unittest.cc

line 102:

    BasicRRset rrns_;           ///< Non-NS RRset (MX in this case)

It seems that the comment is not right, the rrns_ is a NS RRset instead of MX

comment:5 Changed 9 years ago by stephen

  1. hash_table_unittest.cc

Suggest to declaration and define one const static variable name
HASHTABLE_DEFAULT_SIZE = 1009 in HashTable class, so in HashTableTest don need to use
magic number 1009 directly (ref UNREACHABLE in AddressEntry class), so when someday if we
need to change the default value, we only need to change in one place.

Done. The constant is defined in the new NSAS test include file "nsas_test.h"

  1. hash_unittest.cc

The comments:
// unique values, so it does change the size of the array. The call to
should be
// unique values, so it does not change the size of the array. The call to

Done.

  1. lru_list_unittest.cc

Maybe we should choose a better name for Expired in LruList to avoid confusion with
expiration of TTL.

Good point. I've used the name Dropped and the terminology that an element drops off the end of the list.

  1. nameserver_entry_unittest.cc

line 102:
BasicRRset rrns_; /< Non-NS RRset (MX in this case)
It seems that the comment is not right, the rrns_ is a NS RRset instead of MX

Done.

These changes are included in r3402.

comment:6 Changed 9 years ago by vorner

As I start #408, I read the code and documentation (NameserverAddressStoreDesign) and I would like to point few things out, even when I'm not reviewing this.

The hash tables has mutex on each cell, to minimise the locking contention. However, the LRU has only one global mutex and each lookup in the hash table will result in one update of the LRU as well, so it seems the many mutexes on the hash tables are useless, as the threads will collide in the LRU. Or is there a plan to address this somehow?

I'm little bit concerned about locking of the data (zone entry and nameserver entry). Currently it seems there's not enough of it. For example, NameserverEntry::getExpiration does not lock, but the expiration_ may change, when new referral data come. With lru_data, size, getMaxSize and setMaxSize assume that uint32_t are atomic types, which is not the case (or, is not guaranteed to be the case in all architectures). Speaking about the sizes, why we use uint32_t? Shouldn't we use size_t?

Why we use string as the zone name and uint16_t as the class type? Shouldn't we use isc::dns::Name and isc::dns::RRClass?

comment:7 follow-up: Changed 9 years ago by stephen

The hash tables has mutex on each cell, to minimise the locking contention. However,
the LRU has only one global mutex and each lookup in the hash table will result in
one update of the LRU as well, so it seems the many mutexes on the hash tables are
useless, as the threads will collide in the LRU. Or is there a plan to address this
somehow?

Good point, you are right, that was something I missed as the LRU list was added after I'd noted down my first thoughts about the hash table.

One way round this is not to update the LRU on each lookup, but on each n'th lookup. As entries are (or will be) protected by their own mutex, when modifying/accessing the entry, decrement a counter inside it. When the counter reaches zero, reset it and move the entry to the tail of the LRU list. Essentially instead of a LRU list it becomes a least-frequently used list. By tweaking "n", we should be able to reduce contention for the global LRU lock.

I'm little bit concerned about locking of the data (zone entry and nameserver entry). > Currently it seems there's not enough of it. For example,
NameserverEntry::getExpiration does not lock, but the expiration_ may change, when
new referral data come.

A call to getExpiration() that comes just before the expiration time were modified could (if there are thread scheduling delays) arrive just after. In that case, there is a small amount of randomness as to the value returned close to the time the value is reset anyway. So it was felt that if the get were atomic, a lock would not add very much here.

With lru_data, size, getMaxSize and setMaxSize assume that
uint32_t are atomic types, which is not the case (or, is not guaranteed to be the
case in all architectures).

You're right, there is a supposition that a 32-bit get or set is atomic. I'm assuming that BIND10 won't be available for 16-bit architectures (purely on the grounds of address space size). I'm also implicitly assuming that the compiler will align 32-values on 32-bit boundaries to allow atomic reads/writes elsewhere (although now that you've pointed it out, I must admit that I'm not sure that is the case in some of the modern 64-bit architectures). But it is trivial to add a mutex specifically to protect those elements if needed.

Speaking about the sizes, why we use uint32_t? Shouldn't we use size_t?

With uint32_t we know what the maximum value is and that it will be sufficient for our needs. But I'm easy - we could use size_t if it is felt to be better.

Why we use string as the zone name and uint16_t as the class type? Shouldn't we use
isc::dns::Name and isc::dns::RRClass?

The string as the zone name is a place holder for now; mainly because I was not sure what is the best format and what operations are needed. I'm also wary about using Name if we need to construct intermediate objects - there is a lot of processing in the constructor which we might not need.

As to class, you are right - it could be RRclass - although that is just a fancy wrapper around a uint16_t.

comment:8 in reply to: ↑ 7 Changed 9 years ago by vorner

Replying to stephen:

With lru_data, size, getMaxSize and setMaxSize assume that
uint32_t are atomic types, which is not the case (or, is not guaranteed to be the
case in all architectures).

You're right, there is a supposition that a 32-bit get or set is atomic. I'm assuming that BIND10 won't be available for 16-bit architectures (purely on the grounds of address space size). I'm also implicitly assuming that the compiler will align 32-values on 32-bit boundaries to allow atomic reads/writes elsewhere (although now that you've pointed it out, I must admit that I'm not sure that is the case in some of the modern 64-bit architectures). But it is trivial to add a mutex specifically to protect those elements if needed.

I guess 64bit architectures must have them alligned as well, because unalligned data access can get really slow. I'm not sure if there's any current architecture where 32bit integer would not act atomically, but who knows, in theory. What about some small arms things used in the small plastic boxes people call routers?

Anyway, I'm not sure if anything bad can happen with setMaxSize when add is in progress. Or what optimisations might a compiler do with the code.

With uint32_t we know what the maximum value is and that it will be sufficient for our needs. But I'm easy - we could use size_t if it is felt to be better.

I'm not sure. Do we need the maximum value?

I like to use size_t for sizes, as it is a type designed for that kind of thing and says what it is supposed to be. It might turn out that uint32_t would be too small in 5 years on 128bit architectures and people want large caches. And it might turn out to be slow on that kind of machine (but it is unlikely).

The string as the zone name is a place holder for now; mainly because I was not sure what is the best format and what operations are needed. I'm also wary about using Name if we need to construct intermediate objects - there is a lot of processing in the constructor which we might not need.

As to class, you are right - it could be RRclass - although that is just a fancy wrapper around a uint16_t.

I know it is. But interacting with the rest of the code would be easier, with the same interface, now lot of conversion calls is needed even in test code. I guess worying about the overhead in constructor smells little bit as a premature optimisation. Furthermore, I think that we will have Name object in most cases, so we need to call toText() on it and when it gets out, it would need to get converted back to Name(). Now I'm checking that authoritative section contains the correct zone and that contains Name too.

So I think using the same stuff as the rest of code is more convenient.

comment:9 follow-up: Changed 9 years ago by stephen

  • Owner changed from stephen to ocean

nameserver_address.h
Rather than check that the ns_ shared_ptr is non-NULL in both updateRTT() and getAddress(), it might be better to check that it is non-NULL when the object is constructed and to throw an exception if it is. (There should be no case when a NameserverAddress object is constructed with a null NameserverEntry pointer.)

nameserver_entry.cc
Comment: Since NameserverEntry::getAddressAtIndex() should only be called from NameserverAddress::getAddress() - where the index is presumed to be valid - using "assert" instead of throing an exception is OK. (No change is needed.)

nameserver_address_unittest.cc
The RTT update test only tests that the RTT of the address at the specified index is updated. It does not test that the RTT of other addresses associated with the nameserver are not changed.

The tests should also test what happens if the index is out of range.

comment:10 in reply to: ↑ 9 Changed 9 years ago by ocean

  • Owner changed from ocean to stephen

Replying to stephen:

nameserver_address.h
Rather than check that the ns_ shared_ptr is non-NULL in both updateRTT() and getAddress(), it might be better to check that it is non-NULL when the object is constructed and to throw an exception if it is. (There should be no case when a NameserverAddress object is constructed with a null NameserverEntry pointer.)

Done, remove unnecessary checks.

nameserver_entry.cc
Comment: Since NameserverEntry::getAddressAtIndex() should only be called from NameserverAddress::getAddress() - where the index is presumed to be valid - using "assert" instead of throing an exception is OK. (No change is needed.)

nameserver_address_unittest.cc
The RTT update test only tests that the RTT of the address at the specified index is updated. It does not test that the RTT of other addresses associated with the nameserver are not changed.

Done

The tests should also test what happens if the index is out of range.

Done

comment:11 follow-up: Changed 9 years ago by stephen

  • Owner changed from stephen to ocean

Reviewed r3533

nameserver_address.h
The check has been removed from updateRTT() although it is still there in getAddress(). My suggestion was to do the check in the constructor of NameserverAddress and to throw an exception from there if the pointer to the nameserver is NULL.

comment:12 in reply to: ↑ 11 Changed 9 years ago by ocean

  • Owner changed from ocean to stephen

Replying to stephen:

Reviewed r3533

nameserver_address.h
The check has been removed from updateRTT() although it is still there in getAddress(). My suggestion was to do the check in the constructor of NameserverAddress and to throw an exception from there if the pointer to the nameserver is NULL.

Done

comment:13 Changed 9 years ago by stephen

  • Owner changed from stephen to ocean

OK, go ahead and merge.

comment:14 Changed 9 years ago by stephen

  • Owner changed from ocean to stephen

comment:15 follow-up: Changed 9 years ago by stephen

  • Owner changed from stephen to ocean

Reviewed differences between latest version at time of writing (r3706) and the last-reviewed revision (r3533)

src/lib/nsas/random_number_generator.h
Need to #include <math.h> (on Ubuntu at least) to get the declaration of fabs().

WeightedRandomIntegerGenerator::isProbabilitiesValid
Although the compiler will do the appropriate conversions, I suggest using literals that are doubles (1.0, 0.0) instead of integers to emphasise the fact that we are comparing floating-point numbers.

WeightedRandomIntegerGenerator::isProbabilitiesValid
It is clearer to combine the two range checks in one statement, i.e.

if ((*it < 0.0) || (*it > 1.0)) {
    return false;
}

src/lib/nsas/tests/random_number_generator_unittest.cc
Some of the tests use the ASSERT_DEATH macro. This relies on the assert() macro in the constructor to call isProbabilitiesValid() and, if it returns false, to call abort(). However, if the code is compiled with NDEBUG set, assert() is a no-op and the test fails.

src/lib/nsas/tests/Makefile.am
Should include a dependency on random_number_generator.h

src/lib/nsas/nameserver_address.h
The constructor contains the line:

 if(!ns_.get()) isc_throw(NullNameserverEntryPointer, "NULL NameserverEntry pointer.");

The coding guidelines request that braces be used even for a single-line "if" block.

src/lib/nsas/nameserver_entry.h
src/lib/nsas/nameserver_entry.cc

NameserverEntry::getAddress()
The first argument must be a shared_ptr pointing to "this". As it is only used in constructing a NameserverAddress object (which is then copied over the passed NameserverAddress object), the argument seems redundant. Suggest either:

  1. the passed-in NameserverAddress object could be partially constructed using the current NameserverEntry before calling this method. (The assert() call in this method would be kept to ensure that the argument is compatible with this object.)
  2. Derive NamserverEntry (or perhaps its base class NsasEntry, so avoiding multiple inheritance) from boost::enable_shared_from_this, which will allow the construction of a shared_ptr for "this" within the method.

NameserverEntry::updateAddressRTTAtIndex()
The coding guidelines request that braces be used for all "if" and "else" clauses.

comment:16 in reply to: ↑ 15 Changed 9 years ago by ocean

  • Owner changed from ocean to stephen

Replying to stephen:

Reviewed differences between latest version at time of writing (r3706) and the last-reviewed revision (r3533)

src/lib/nsas/random_number_generator.h
Need to #include <math.h> (on Ubuntu at least) to get the declaration of fabs().

Done. Add #include <cmath>

WeightedRandomIntegerGenerator::isProbabilitiesValid
Although the compiler will do the appropriate conversions, I suggest using literals that are doubles (1.0, 0.0) instead of integers to emphasise the fact that we are comparing floating-point numbers.

Done.

WeightedRandomIntegerGenerator::isProbabilitiesValid
It is clearer to combine the two range checks in one statement, i.e.

if ((*it < 0.0) || (*it > 1.0)) {
    return false;
}

Done

src/lib/nsas/tests/random_number_generator_unittest.cc
Some of the tests use the ASSERT_DEATH macro. This relies on the assert() macro in the constructor to call isProbabilitiesValid() and, if it returns false, to call abort(). However, if the code is compiled with NDEBUG set, assert() is a no-op and the test fails.

Add #ifndef NDEBUG .... #endif macro on these tests.
Since some validation will incur performance penalty, so do the validation only on debug version.

src/lib/nsas/tests/Makefile.am
Should include a dependency on random_number_generator.h

Done.

src/lib/nsas/nameserver_address.h
The constructor contains the line:

 if(!ns_.get()) isc_throw(NullNameserverEntryPointer, "NULL NameserverEntry pointer.");

The coding guidelines request that braces be used even for a single-line "if" block.

Done.

src/lib/nsas/nameserver_entry.h
src/lib/nsas/nameserver_entry.cc

NameserverEntry::getAddress()
The first argument must be a shared_ptr pointing to "this". As it is only used in constructing a NameserverAddress object (which is then copied over the passed NameserverAddress object), the argument seems redundant. Suggest either:

  1. the passed-in NameserverAddress object could be partially constructed using the current NameserverEntry before calling this method. (The assert() call in this method would be kept to ensure that the argument is compatible with this object.)
  2. Derive NamserverEntry (or perhaps its base class NsasEntry, so avoiding multiple inheritance) from boost::enable_shared_from_this, which will allow the construction of a shared_ptr for "this" within the method.

Done. I choose method b, so the code will be more clear. Actually this has bothered me very much to figure out how to get shared_ptr that points to this object.

NameserverEntry::updateAddressRTTAtIndex()
The coding guidelines request that braces be used for all "if" and "else" clauses.

Done.

comment:17 follow-up: Changed 9 years ago by stephen

  • Owner changed from stephen to ocean

I've looked at the differences between the current head (r3754) and the last reviewed revision (r3706).

src/lib/nsas/tests/random_number_generator_unittest.cc
It would be worth adding a comment for future maintainers to explain the #ifndef NDEBUG brackets.

src/lib/nsas/nameserver_entry.cc
NameserverEntry::updateAddressSelector:

if(rtt == 0) isc_throw(RTTIsZero, "The RTT is 0");

The "isc_throw" should be in braces.

If all the nameservers are unreachable, all probabilities will be set to 0. This will lead to an attempt to calculate 0/0 during normalisation which will most likely generate a floating point error.

comment:18 in reply to: ↑ 17 Changed 9 years ago by ocean

  • Owner changed from ocean to stephen

Replying to stephen:

I've looked at the differences between the current head (r3754) and the last reviewed revision (r3706).

src/lib/nsas/tests/random_number_generator_unittest.cc
It would be worth adding a comment for future maintainers to explain the #ifndef NDEBUG brackets.

Done.

src/lib/nsas/nameserver_entry.cc
NameserverEntry::updateAddressSelector:

if(rtt == 0) isc_throw(RTTIsZero, "The RTT is 0");

The "isc_throw" should be in braces.

Done.

If all the nameservers are unreachable, all probabilities will be set to 0. This will lead to an attempt to calculate 0/0 during normalisation which will most likely generate a floating point error.

Done. If all the servers are unreachable, give each one the same opportunity to be selected.

comment:19 follow-up: Changed 9 years ago by stephen

  • Owner changed from stephen to ocean

src/lib/nsas/tests/nameserver_entry_test.cc
Changes are OK but in checking them I noticed what appears to be an error in the checks in test AddressSelection. The first test attempts to check that three addresses are selected with equal probability and tests this by iterating 10,000 times and incrementing one of three counters (c1, c2, c3). The test is then:

    // c1, c2 and c3 should almost be equal
    ASSERT_EQ(1, (int)(c1*1.0/c2 + 0.5));
    ASSERT_EQ(1, (int)(c2*1.0/c3 + 0.5));

But these two assertions are true if (for example) c1 = 4713, c2 = 3163 and c3 = 2124, i.e. c1 > 2*c3 - which is a significant deviation from equal probability.

(Figures obtained by noting that (int) 1.99 = 1 then setting c1/c2 = c2/c3 = 1.49 and c1+c2+c3 = 10000. BTW the iteration count is 10,000 for the first loop in this test and 100,000 for the rest - I suggest that the higher number be used.)

Similar comments apply to the ASSERT_EQ checks at the end of the test.

Testing the output of a random number generator is an involved process. I am not an expected on statistics, but I analyze the first test (where we expect each of three addresses to be selected with equal probability) as follows:

For each address, each time through the loop we expected it to be selected with a probability of p (= 1/3) and not selected with a probability of q (= 1-p = 2/3). This suggests a binomial distribution, but as the number of selections (N) is large, we end up with a normal distibution with mean Np (= N/3) and variance of Npq (= 2N/9) (see for example http://mathworld.wolfram.com/NormalDistribution.html). With N = 100,000, the standard deviation (= sqrt(variance)) is about 149 or roughly 0.15% of N.

Although we want an even distribution, it doesn't really matter too much if the numbers vary slightly. So checking that the actual number of selections of a given address is within 1% of its expected value is probably good enough. With the figures used here, one percent of N away from the mean is over six standard deviations, and we expect that actual value will be closer than this to the expected value well over 99.99% of the time.

In summary, testing that "abs(c1 - (N/3)) <= (N/100)" (and the same for c2 and c3) should check that they are selected with equal probability and work virtually every time.

Note that slightly different values are required when the probabilities are unequal.

comment:20 in reply to: ↑ 19 Changed 9 years ago by ocean

  • Owner changed from ocean to stephen

Replying to stephen:

src/lib/nsas/tests/nameserver_entry_test.cc
Changes are OK but in checking them I noticed what appears to be an error in the checks in test AddressSelection. The first test attempts to check that three addresses are selected with equal probability and tests this by iterating 10,000 times and incrementing one of three counters (c1, c2, c3). The test is then:

    // c1, c2 and c3 should almost be equal
    ASSERT_EQ(1, (int)(c1*1.0/c2 + 0.5));
    ASSERT_EQ(1, (int)(c2*1.0/c3 + 0.5));

But these two assertions are true if (for example) c1 = 4713, c2 = 3163 and c3 = 2124, i.e. c1 > 2*c3 - which is a significant deviation from equal probability.

(Figures obtained by noting that (int) 1.99 = 1 then setting c1/c2 = c2/c3 = 1.49 and c1+c2+c3 = 10000. BTW the iteration count is 10,000 for the first loop in this test and 100,000 for the rest - I suggest that the higher number be used.)

Similar comments apply to the ASSERT_EQ checks at the end of the test.

Testing the output of a random number generator is an involved process. I am not an expected on statistics, but I analyze the first test (where we expect each of three addresses to be selected with equal probability) as follows:

For each address, each time through the loop we expected it to be selected with a probability of p (= 1/3) and not selected with a probability of q (= 1-p = 2/3). This suggests a binomial distribution, but as the number of selections (N) is large, we end up with a normal distibution with mean Np (= N/3) and variance of Npq (= 2N/9) (see for example http://mathworld.wolfram.com/NormalDistribution.html). With N = 100,000, the standard deviation (= sqrt(variance)) is about 149 or roughly 0.15% of N.

Although we want an even distribution, it doesn't really matter too much if the numbers vary slightly. So checking that the actual number of selections of a given address is within 1% of its expected value is probably good enough. With the figures used here, one percent of N away from the mean is over six standard deviations, and we expect that actual value will be closer than this to the expected value well over 99.99% of the time.

In summary, testing that "abs(c1 - (N/3)) <= (N/100)" (and the same for c2 and c3) should check that they are selected with equal probability and work virtually every time.

Note that slightly different values are required when the probabilities are unequal.

Done. Correct the test methods to make sure that fabs(c - mu) < 4*sigma.

comment:21 Changed 9 years ago by stephen

  • Owner changed from stephen to vorner

4 * sigma is fine. During the merge though could you replace the line:

double mu1 = repeats * 0.7347;

with

double mu1 = repeats * p1;

(as 0.7347 is just the value of p1 calculated three of lines earlier), and do the the similar replacement in the expressions for mu2 and mu3.

comment:22 Changed 9 years ago by vorner

  • Owner changed from vorner to stephen

Ok, I merged #408 into this and changed it (I did other small modification, using arrays instead of numbers in names).

comment:23 Changed 9 years ago by stephen

All looks OK. Please merge with trunk.

comment:24 Changed 9 years ago by stephen

  • Owner changed from stephen to vorner

comment:25 Changed 9 years ago by vorner

  • Resolution set to complete
  • Status changed from reviewing to closed

Merged to trunk, closing.

Note: See TracTickets for help on using tickets.