Opened 10 years ago

Closed 9 years ago

#192 closed enhancement (fixed)

Data source hotspot cache

Reported by: each Owned by: jinmei
Priority: medium Milestone: 05. 3rd Incremental Release: Serious Secondary
Component: b10-auth Version:
Keywords: Cc:
CVSS Scoring: Parent Tickets:
Sensitive: no Defect Severity:
Sub-Project: Feature Depending on Ticket:
Estimated Difficulty: Add Hours to Ticket:
Total Hours: Internal?:

Description

Implement a hotspot cache to improve data source performance. This was item 69 on the list of work items produced in Beijing.

Subtickets

Attachments (2)

datasrcmatch.diff (2.3 KB) - added by jinmei 9 years ago.
cache.diff (4.2 KB) - added by jinmei 9 years ago.

Download all attachments as: .zip

Change History (46)

comment:1 Changed 9 years ago by each

  • Owner changed from each to UnAssigned
  • Status changed from new to reviewing
  • Type changed from defect to enhancement

Ready for review in branches/trac192:

svn diff -r 1885:HEAD branches/trac192

I haven't done query performance measurements other than looking at the "Query time" line in the output of dig... but queries that initially take 4-8 msec (and even NSEC3 NXDOMAIN responses that can take as much as 25 msec) will now respond in 0-1 msec when repeated within the 30 second cache window.

comment:2 Changed 9 years ago by shane

  • Milestone set to 04. 2nd Incremental Release: Early Adopters

comment:3 Changed 9 years ago by shane

  • Component changed from Unclassified to b10-auth
  • Owner changed from UnAssigned to shane
  • Status changed from reviewing to accepted

comment:4 Changed 9 years ago by shane

  • Owner changed from shane to jinmei
  • Status changed from accepted to reviewing

comment:5 follow-up: Changed 9 years ago by shane

  • Milestone changed from 04. 2nd Incremental Release: Early Adopters to 05. 3rd Incremental Release

comment:6 in reply to: ↑ 5 ; follow-up: Changed 9 years ago by jinmei

Review is ongoing, but I'll make my comments cache.{cc,h} with a couple of general comments first.

general:

  • I've made some trivial (I think) cleanups directly on the branch.
  • documentation is much better than other datasrc files (btw we need it for them also), but IMO it's still not sufficient. See specific points below. Also, I suggest you actually convert the doxygen markups into HTML files and browse the results.

cache.h

  • CacheEntry? class
    • why is this defined in the header file? This seems to be an internal type only used within the CacheNode? class. If so, this should be hidden from others (move it to .cc). Plus, although this largely a matter of taste, this looks more like a "struct" rather than a "class". If this must be defined in a public header file, I strongly recommend hiding member variables as private. This should be pretty obvious, but to be redundant: as we can see in my experimental rbt patch, hiding the details will help us when we want to customize it further, without worrying about breaking compatibility.
    • documentation: commenting about the actual implementation would also be useful, but I'd first like to see a conceptual description of "what this is".
  • Cachenode class
    • I normally expect more general documentation about a class of this size (overall design, any non trivial design decision, etc). I'd also expect exception considerations for each public member function.
    • isValid()/getRRset/getFlags() aren't explicitly tested. they should.
    • I'm not sure if copying/assignment is expected to be allowed for CacheNode? objects, but if not, they should be explicitly prohibited. (it seems to be CacheNodes? are generally passed as (shared) pointers, and can be non-copyable)
    • especially if this can be non copyable, I suggest you consider using pimpl for this class to reduce dependency on the DNS related class implementations in the header file. I know it's a common controversial argument of ours. And I also understand this may be a case where the benefit of pimpl may not outweigh its overhead because this class is for performance optimization. But since this is cached information and the overhead of creation time should be relatively minor, I still personally think we should use pimpl here. See also the related comment on HotCache?. Note also that you've already partially adopted pimpl for this class via the entry_ member variable.
    • We should really, really, seriously reconsider the current design of making some of the class member variables public (from prev to qtype). This is something we should always avoid unless there's a very strong reason to do so, and I don't see it in this case. Actually, this is mostly private information only used by HotCache?, so it's much better to encapsulate such implementation specific information in CacheEntryPtr?, define it within .cc, thereby hiding the existence of such notion from others in the first place.
  • QTuple class
    • AFAICS, this is only used within the cache implementation. it should be hidden in the implementation file. I noted the TODO, but unless/until we really do this it's better to hide it.
    • On the other hand, if we really need a public class like QTuple, dns::Question is almost exactly what's needed here. Why not reusing it? (we could add operator< if that's the problem).
    • Constructor: why passing object copies (which is expensive), rather than references?
    • document operator<. why we need this etc. note also that Name::operator< is quite expensive (it calls the generic compare() method).
    • (maybe infeasible if we accept the first comment but) we need tests for this class.
    • is this (intended to be) copyable? If not, make it non copyable explicitly.
  • HotCache? class
    • We tend to abbreviate things, but isn't it better to name it more clearly, e.g., HotSpotCache??
    • Class description: describing internal implementation (using std::map/double linked list, etc) is good, but I'd separate the documentation for the high level interface from that for the actual implementation. For example, entries are managed using a LRU-based algorithm is high level, while it's implemented via a doubly linked list is an implementation detail. I personally separate the latter into a different paragraph, beginning with "note to developers".
    • Class description: like Cachenode, I'd add more design decisions, non trivial points, etc. That would include why the default lifetime is 30 seconds, cache and negative cache, and the rationale of using std::map, what are positive and negative caches, etc.
    • As for design decision, I guess we need to consider multi-thread considerations. Although we are currently not using threads, and I'm not sure if we'll do in our auth server in future versions, our implementation so far is (in my understanding) generally thread safe, except, perhaps within sqlite3/ASIO library implementations. So the access to this cache is going to the first place that is not thread safe. We should at least note that, and describe our future plans on that point. Note also that the data source library is public, and some external developers may want to use it with threads.
    • Class description: I'm not sure if it's a good idea to mention DataSrc::doQueryTask() here, because the cache may be used in other contexts. I'd rather make the description generic, while noting doQueryTask() uses the HotCache? in its own description.
    • Design: I don't think making this as a static is a good idea. One practical reason for this is that we may actually want to have multiple different caches if/when we support views. And, of course, use of static/global objects should be avoided at all costs. In this specific case, I don't see an inevitable reason why we must define it as a non local static object. The cache isn't needed unless query processing happens, so it should be reasonable to assume the application can prepare it by the time it needs the cache. I strongly suggest you reconsider this design.
    • A related point: I saw comments about the initialization of Query::cache(0). Trying to avoid the static initialization order fiasco just by noting it in a comment isn't a good practice. There are many non-trivial pitfalls around this beast, so non-trivial that we can't avoid them just by hoping the developers read the comment and do the right thing. If we really, really, really need it as a static object, we must avoid the fiasco more explicitly using language features. But again, please reconsider the design in the first place before trying to make it work with complicated tricks.
    • Design: now the controversial point:-) I strongly suggest pimpl be used for this class. This class is a perfect example of the case where the advantages of pimpl outweigh its overhead: having an external definition (std::map) inside the implementation, and the overhead of constructing/destructing the object is negligible. I now hope we've all learned how advantageous it is if we minimize dependencies on other implementations in our public header files via the turmoil with the non boost ASIO, and I hope my argument is now more convincing.
    • I believe the HotCache? class is intended to be non-copyable. Please explicitly make it so.
    • description for member functions in general: same comments as that for Cachenode.
    • naming: if we follow our method name convention, cache() is better named setCacheEntry(), s/ncache/setNegativeCacheEntry()/, s/retrieve()/getCache, etc? Maybe a matter of taste, just a comment.
    • description about cache(): it should describe what happens if there's already an entry that matches the key. Also describe what if it's a negative cache. These case should also be tested.
    • description about ncache(). Likewise.
    • methods like retrieve() should normally be definable as a const member function. Hmm, okay the implementation explains why this can't be a const. The method description should explain that.
    • retrieve() signature: why passing object copies?
    • setSlots description: it states "up to the number of RRsets in the data source". I don't understand this. Which data source is it? Whatever it means, since there can be negative cache entries, this description still doesn't make sense to me.
    • constant of 30: I'd define it as a static const class member with doxygen description, and use it other places consistently, so that the magic number appears only once (and we make sure it's described).
    • count_ might be redundant because it should be identical to map_.size().
    • LRU list: why using in-house list, rather than std::list? (see also the comment about the implementation).

cache.cc

  • CacheNode::~CacheNode?(): if you use the default destructor you can omit the declaration and the definition.
  • HotCache::~HotCache?(): I don't understand what the for loop does. Does this do something correct? Also recall my other comment about why using in-house list. If we use std::list, we don't even have to bother to clean up these things.
  • HotCache::retrieve(): map::operator[] creates a new entry if it doesn't have one for the key. It's probably not necessarily incorrect, but I suspect it's error-prone behavior. For example, consider the case where the caller continuously calls retrieve() for different non-existent keys. I suggest you use map::find() instead.
  • HotCache::insert(): why do we need to have a while loop? if count_ > slots_ > 0, count_ must be slots_ + 1, and we should only need a single remove operation. if this doesn't hold it's an internal bug, and I'd rather let it fail with assert (which I prefer) or exception than preparing for the "impossible case" with a complicated logic.
  • HotCache::ncache(): the condition of ANY()s isn't documented (and not intuitive).

comment:7 Changed 9 years ago by jinmei

  • Owner changed from jinmei to each

comment:8 in reply to: ↑ 6 ; follow-ups: Changed 9 years ago by each

Replying to jinmei:

Review is ongoing, but I'll make my comments cache.{cc,h} with a couple of general comments first.

Thank you, as always, for the very thorough review. (But if you're not finished yet, I'm not sure why you assigned the ticket to me at this point. Is there more coming? If so I'd rather you held the ticket; I'm busy on BIND 9 this week and would rather address your comments all at once than iterate repeatedly.)

I'm fine with most of your suggestions. In particular, in the case of the HotCache? class, I have no objection to using pimpl. I simply didn't do it on the first pass, because I had a week allotted to coding and wanted to avoid adding code complexity while I got the proof-of-concept working.

A few individual remarks and explanations below.

  • Also, I suggest you actually convert the doxygen markups into HTML files and browse the results.

(General question to anyone reading: How do you do this? I really have no idea.)

  • especially if this can be non copyable, I suggest you consider using pimpl for this class to reduce dependency on the DNS related class implementations in the header file.

For this class I'm less enthusiastic about pimpl, for reasons you already alluded to, but I'll consider it.

  • We should really, really, seriously reconsider the current design of making some of the class member variables public (from prev to qtype).

With qname/qclass/qtype, we've been inconsistent in libdatasrc; sometimes they're public member variables, sometimes they're functions. I agree we should pick a way and stick with it. I've begun to wonder if we should move toward using a QTuple struct for this.

I had a specific reason for making next and prev public--originally I hid them, but there was code in the HotCache? class that became much simpler if it had access to them. (This could be done by making them protected and giving HotCache? friend status, but we have avoided using friend so far. Or it could be done by having next_ and prev_ be private but exposed via next() and prev() accessor functions. But as this is CacheNode?, and next and prev both point to CacheNode? and always will, it seemed unlikely to me that there would ever be any implementation details that would need to be hidden inside those accessor functions. I'm okay with doing it that way if you wish, though.

  • QTuple class
    • On the other hand, if we really need a public class like QTuple, dns::Question is almost exactly what's needed here. Why not reusing it? (we could add operator< if that's the problem).

Because I didn't remember its existence. It should be fine.

  • Constructor: why passing object copies (which is expensive), rather than references?

Just a mistake.

  • document operator<. why we need this etc. note also that Name::operator< is quite expensive (it calls the generic compare() method).

Can it be made cheaper?

  • HotCache? class
    • Design: I don't think making this as a static is a good idea.

I am open to suggestions. But we want every query to have access to the same cache that all the other queries used. (And perhaps also every update, etc.) How do we achieve this without making it global, or effectively so? Every solution I thought of seemed to have essentially the same problems as the one I chose.

One practical reason for this is that we may actually want to have multiple different caches if/when we support views.

Perhaps, but then we'll be wanting to

  • retrieve() signature: why passing object copies?

If you see me do that and don't know why I did it, the answer is nearly always going to be "I forgot the &" and nothing more. Unfortunately the C++ compiler isn't capable of telling me when I've made that mistake, and I make it a lot.

  • setSlots description: it states "up to the number of RRsets in the data source". I don't understand this. Which data source is it? Whatever it means, since there can be negative cache entries, this description still doesn't make sense to me.

Yeah, doesn't make sense to me either. I was probably stoned or something. :)

  • LRU list: why using in-house list, rather than std::list? (see also the comment about the implementation).

It just seemed more straightforward to roll my own type with built-in promotion-on-access and LRU-cleanup behavior, rather than try to backfill that behavior into the std::list type.

cache.cc

  • HotCache::~HotCache?(): I don't understand what the for loop does.

Hm. Not sure this is still needed, it may be left over from an earlier code iteration. But what it does is successively remove references to each item on the list so that shared_ptr will deallocate them.

  • HotCache::insert(): why do we need to have a while loop? if count_ > slots_ > 0, count_ must be slots_ + 1, and we should only need a single remove operation. if this doesn't hold it's an internal bug, and I'd rather let it fail with assert (which I prefer) or exception than preparing for the "impossible case" with a complicated logic.

I was thinking that slots_ might have been modified recently, but actually setSlots() takes care of that case, so perhaps you're right.

comment:9 in reply to: ↑ 8 ; follow-up: Changed 9 years ago by each

Replying to each:

Oops, a bunch of text got cut out by mistake.

One practical reason for this is that we may actually want to have multiple different caches if/when we support views.

Perhaps, but then we'll be wanting to

Then we'll be wanting to declare a cache for each view which every query reaching that view would use... and it seems to me to this presents much the same set of problems as a global variable (or nonlocal static member) when it comes to thread safety and such.

In the current case, when we don't have a need for multiple caches--and in fact we explicitly prefer that the server only use one--using a nonlocal static member means we can instantiate a Query and it Just Works--there's no need for the caller to explicitly set up a cache in advance. b10-auth doesn't need to know there's any such thing as a HotCache?.

I have no particular objection to doing it the way you suggested, but I do think there's some advantage to code that does the right thing without being told.

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

Replying to each:

Replying to jinmei:

Review is ongoing, but I'll make my comments cache.{cc,h} with a couple of general comments first.

Thank you, as always, for the very thorough review. (But if you're not finished yet, I'm not sure why you assigned the ticket to me at this point. Is there more coming? If so I'd rather you held the ticket; I'm busy on BIND 9 this week and would rather address your comments all at once than iterate repeatedly.)

Okay, in that case I'll just keep going. The reason why I gave it back to you at that point was because I expected it would take some more time and the comments so far seemed to be able to be addressed separately.

comment:11 Changed 9 years ago by jinmei

  • Owner changed from each to jinmei

comment:12 Changed 9 years ago by jinmei

An additional comment on the cache feature: we may want to make it possible to purge the cache.

comment:13 Changed 9 years ago by jinmei

cache_unittest:

  • please don't hardcode flags (e.g. for the second arg of HotCache::cache()), even though it's opaque for the HotCache module
  • the LRU test is insufficient. this essentially only tests the upper limit of cacheable entries. I added a test for the LRU feature (r2134).
  • C-style cast "(time_t)" seems redundant. If we really need it, the use of it is inconsistent in the .cc, and in that case we should use C++ style cast (after rethinking the design several times). I removed them in r2135.

comment:14 follow-up: Changed 9 years ago by jinmei

High level comments about data_source.cc and some other related files:

I don't think it a good idea to overload additional things onto NameMatch. It was originally intended to be a simple supplimental class to encapsulate the logic of searching data sources for the longest match name. Now it seems to encapsulate more complecated query logic, and even includes a very specific trick about DS query. It has become way too monolithic.

If we really need to encapsulate the compound logic (on which I'm not sure, especially in the context of hot spot cache patch), we should consider a cleaner refactoring. It may be a new supplemental class which perhaps contains NameMatch, or it may be refactoring the logic of existing classes, or some other types of refactoring which may even result in removing NameMatch. But in any case, it shouldn't be making NameMatch a kitchen sink monolithic class.

As a related note, it's not clear whether the tweak for NameMatch is essential for the hot spot cache feature. Since it's already a pretty large patch with substantial behavioral changes, it's much easier to begin with a minimal diff to the existing code with new classes for the new feature, and then, if necessary, to refactor the resulting code. Right now, the changes to the NameMatch interfaces reqruire so many changes to other part of the code, including test cases, which make the review difficult. And yet it's not clear these changes are inevitable for the new feature.

Another high-level comment is about doQueryTask(). It has become a monster function, consisting of 309 lines of code with two sets of long switch-case blocks. In general, it's mostly impossible to get comprehensive view of such a function, much less being confident about whether it's implemented correctly. Also, from a quick glance many code fragments in the case segments to have the same pattern. Overall, this function is alredy requiring a refactoring.

At this point I'm stopping my review. Let's resolve the high level issues before moving forward. My personal suggestion is to restart with a minimal change that is absolutely necessary to support the hot spot cache, and, if necessary, think about tweaking the query logic.

comment:15 Changed 9 years ago by jinmei

  • Owner changed from jinmei to each

comment:16 in reply to: ↑ 14 ; follow-ups: Changed 9 years ago by each

Regarding cache_unittest.cc, you appear to have already addressed at least two of your comments in the branch, and maybe all three. Does that need any further attention from me?

Replying to jinmei:

High level comments about data_source.cc and some other related files:

I don't think it a good idea to overload additional things onto NameMatch.

A note on that: I have kept the class name as "NameMatch" for the moment, because that was the class that I had extended, but my intention was to change its name to ZoneInfo or something similar. The only reason I didn't do this already was that I thought it would be slightly easier for the reviewer to follow the logic if it was still obvious that I had based the new code on an existing class. (I thought I had mentioned this in the comments, but I probably removed that by mistake during cleanup; sorry.)

If we really need to encapsulate the compound logic (on which I'm not sure, especially in the context of hot spot cache patch)

I believe we do. Otherwise every query still requires at least one database access to find the concrete data source before anything else can happen. That one change, keeping track of the data source in which the best enclosing zone had been found, massively improved the query performance.

It may be a new supplemental class which perhaps contains NameMatch, or it may be refactoring the logic of existing classes, or some other types of refactoring which may even result in removing NameMatch. But in any case, it shouldn't be making NameMatch a kitchen sink monolithic class.

As I already mentioned, my intention was to change NameMatch to a new name. NameMatch has no purpose other than this one, so I don't there's any reason to keep it around in its old form. It's not a kitchen-sink monolithic class; it's a fairly straightforward structure for determining the best matching zone for a given query, and the data source in which the zone resides.

Another high-level comment is about doQueryTask(). It has become a monster function, consisting of 309 lines of code with two sets of long switch-case blocks. In general, it's mostly impossible to get comprehensive view of such a function, much less being confident about whether it's implemented correctly. Also, from a quick glance many code fragments in the case segments to have the same pattern. Overall, this function is alredy requiring a refactoring.

That's a fair criticism. The fragments do generally differ in their patterns, for good reasons; I eliminated code duplication when I could, but the behavior of a GLUE_QUERY is different from an AUTH_QUERY in critical ways.

However, it can be split into smaller service functions handling the separate query task types. I'm accustomed to doing this last, after satisfying myself that the overall structure is correct (you may recall that we went through a similar process with doQuery() earlier).

If you insist on stopping the review until this has been done, okay. But if you could treat each switch block branch as a separate logical unit and carry on, or else just pass over doQueryTask() entirely and continue reviewing other things, that would make things easier when I have time to work on this again next week.

comment:17 in reply to: ↑ 16 Changed 9 years ago by jinmei

Replying to each:

Regarding cache_unittest.cc, you appear to have already addressed at least two of your comments in the branch, and maybe all three. Does that need any further attention from me?

The first one hasn't been addressed, although it's quite minor.

comment:18 in reply to: ↑ 16 Changed 9 years ago by jinmei

Replying to each:

If we really need to encapsulate the compound logic (on which I'm not sure, especially in the context of hot spot cache patch)

I believe we do. Otherwise every query still requires at least one database access to find the concrete data source before anything else can happen. That one change, keeping track of the data source in which the best enclosing zone had been found, massively improved the query performance.

I see the effect of checking the cache before trying to identify the best data source. But that doesn't mean you have to alter the definition and interfaces of an existing class (NameMatch), affecting many other parts of code that have nothing to do with hot spot caching. That was my point.

For example, you changed NameMatch?, the signature of DataSRc::findClosestEnclosure() has also changed, affecting many other data source implementations and unit tests. One specific case is this:

 void
-TestDataSrc::findClosestEnclosure(NameMatch& match,
-                                  const RRClass& qclass) const {
+TestDataSrc::findClosestEnclosure(NameMatch& match) const {
     const Name& qname = match.qname();
     NameComparisonResult::NameRelation cmp;
 
-    if (qclass != getClass() && qclass != RRClass::ANY()) {
+    if (match.qclass() != getClass() && match.qclass() != RRClass::ANY()) {
         return;
     }

This is totally irrelevant to hot spot caching, and I saw many such changes. They are distracting.

We could (and IMO should) only tweak the code logic so that cache is tried before real data sources without (or with minimally) modifying public classes.

Then, the introduction of the cache suggests refactoring the public interfaces (which I'm not convinced but we can discuss it), do that in a separate task as a pure refactoring.

I must confess when I'm in the developer side asking for review I'm not very good at it either, but the developer is often blind to how confusing it is for reviewers because the developer already understands the whole picture and everything tends to look so natural.

Am I now clearer (and hopefully more convincing)? If so, I'm rather happy to make a counter proposal by simplying the data source part of the patch with a minimal change. Possibly rebasing the branch also (as we missed the previous release this branch is quite different from the latest trunk).

comment:19 in reply to: ↑ 16 Changed 9 years ago by jinmei

Replying to each:

If you insist on stopping the review until this has been done, okay. But if you could treat each switch block branch as a separate logical unit and carry on, or else just pass over doQueryTask() entirely and continue reviewing other things, that would make things easier when I have time to work on this again next week.

Actually, I more focused on the first part of "high-level issues" when I said "let's resolve them first". Right now I wouldn't request further refacotring on this part as a prerequisite of moving forward. And, in fact, it's probably better to defer refactoring for the exact reason I pointed out in the first high level issue.

comment:20 in reply to: ↑ 8 Changed 9 years ago by jinmei

Replying to each:

  • We should really, really, seriously reconsider the current design of making some of the class member variables public (from prev to qtype).

With qname/qclass/qtype, we've been inconsistent in libdatasrc; sometimes they're public member variables, sometimes they're functions. I agree we should pick a way and stick with it. I've begun to wonder if we should move toward using a QTuple struct for this.

I had a specific reason for making next and prev public--originally I hid them, but there was code in the HotCache? class that became much simpler if it had access to them. (This could be done by making them protected and giving HotCache? friend status, but we have avoided using friend so far. Or it could be done by having next_ and prev_ be private but exposed via next() and prev() accessor functions. But as this is CacheNode?, and next and prev both point to CacheNode? and always will, it seemed unlikely to me that there would ever be any implementation details that would need to be hidden inside those accessor functions. I'm okay with doing it that way if you wish, though.

In public APIs any unlikely things will happen by some user. So, yes, I insist we should hide them.

Note, however, that we could adopt pimpl for CacheNode? and hide the implementation details within .cc. That way I'm okay with handling them directly (I myself take that approach sometimes).

  • document operator<. why we need this etc. note also that Name::operator< is quite expensive (it calls the generic compare() method).

Can it be made cheaper?

Perhaps. MessageRenderer? implements a bit simpler version of comparison, but I must say that might be a premature optimization. This comment is actually a heads-up rather than suggesting something else (one of the disadvantages of operator overloading, which is they can make expensive operations look cheaper). Before trying to tweak this, we should perform benchmark first.

  • retrieve() signature: why passing object copies?

If you see me do that and don't know why I did it, the answer is nearly always going to be "I forgot the &" and nothing more. Unfortunately the C++ compiler isn't capable of telling me when I've made that mistake, and I make it a lot.

I see. btw, making classes non copyable whenever possible helps avoid it. that's one of the reasons why it's a good idea. unfortunately, however, in this specific case these arguments objects are supposed to be copyable and we can't exploit this technique.

  • LRU list: why using in-house list, rather than std::list? (see also the comment about the implementation).

It just seemed more straightforward to roll my own type with built-in promotion-on-access and LRU-cleanup behavior, rather than try to backfill that behavior into the std::list type.

Admittedly, I expect the use of std::list will have its own negative implications in this case. But you seem to underestimate the risk of in-house based development with such reasons as "because it seems more straightforward". In house list implementation requires us to write non trivial manipulation code like this:

    if (lru_head_) {
        node->next = lru_head_;
        lru_head_->prev = node;
        lru_head_ = node;
    } else {

which is not so trivial as the original developer might believe, and we in fact often make bugs in the handmade logic. In fact, you probably actually made one (see the ~HotCache?() comment below).

So, while I don't insist std::list is definitely better in this case, I would suggest you at least try a version with std::list, not just making a decision based on seeming observation. If, after playing with both ways, you are still sure the advantage of in-house implementation outweighs its negative consequences, it's your call.

cache.cc

  • HotCache::~HotCache?(): I don't understand what the for loop does.

Hm. Not sure this is still needed, it may be left over from an earlier code iteration. But what it does is successively remove references to each item on the list so that shared_ptr will deallocate them.

One thing I cannot understand is the loop condition:

    for (node = lru_head_; node = node->next; node != CacheNodePtr()) {

At least the third statement doesn't make sense. I'm also not sure if this loop ever stops because node doesn't seem to be changed in the loop.

Note also that if you used an STL container you wouldn't have to be bothered with these things. Objects remaining in the container will automatically cleaned up when the container is destructed.

comment:21 in reply to: ↑ 9 Changed 9 years ago by jinmei

Replying to each:

Oops, a bunch of text got cut out by mistake.

Design: I don't think making this as a static is a good idea.

I have no particular objection to doing it the way you suggested, but I do think there's some advantage to code that does the right thing without being told.

The fact that the user app of the data source doesn't have to be aware of a cache is indeed a plus. I agree with that; however, that advantage is way too weak to justify troubles as a result of relying on an essentially global object. But I realize which one is more substantial may be a matter of opinion, so, instead of explaining why essentially-global is so dangerous, I'm going to make a different style of argument.

Actually, we already required the user app to prepare an app-specific object: an entry point to the data source. In our auth server case, it's AuthSrvImpl::data_sources_, a MetaDataSrc object. With your logic (that these things should require some type of global object), we could/should also make this a static object defined in the data source module. Putting this in another way, we can pass the cache information on the creation of the MetaDataSrc, or if we really want to hide it from the app, we can let MetaDataSrc create a cache within it unconditionally (but I actually think we'd rather let the app configure the cache explicitly. I can easily think of an app that wants to disable the cache). This way, we can make the cache common to all lookups for the app, still avoiding to have a singleton object.

For a middle term plan, I'd suggest refactoring the current data source/query handle logic as we discussed before, so that we define a separate class of top level query handling instead of the monolithic hierarchy of the current data source variants. (I thought we generally agreed with the idea) Then we can create (or hide) the cache with the top level object.

comment:22 follow-ups: Changed 9 years ago by each

  • Owner changed from each to jinmei

CacheEntry class
CacheNode class

By changing the signature of HotCache::retrieve(), I was able to
refactor both of these into a completely hidden objects in cache.cc,
I hope this addresses most of your concerns with the code. I'll also
update them tomorrow with the suggestions you made for their
documentation, but I haven't done that yet.

QTuple class

I've removed this class entirely, in favor of isc::dns::Question (which has
had an an less-than operator added to it for use by std::map).

We tend to abbreviate things, but isn't it better to name it more clearly, e.g., HotSpotCache

I personally prefer HotCache, but it's not particularly important to me.
I'll change it if you think it's important.

Class description: like Cachenode, I'd add more design decisions, non trivial points, etc.

Okay, I've done some of that...

As for design decision, I guess we need to consider multi-thread considerations.

Good point. Documented.

Design: I don't think making this as a static is a good idea.

We discussed this further, and I'm convinced. HotCache? is now instantiated
a member of AuthSrvImpl?.

Design: now the controversial point:-) I strongly suggest >pimpl be used for this class.

Done.

I believe the HotCache?? </wiki/HotCache> class is intended to be non-copyable. Please explicitly make it so.

Done.

naming: if we follow our method name convention, cache() is better named setCacheEntry()

I had been thinking of the word cache() as a verb, not a noun, but since
there's now a cache() function in the Query objct now that returns a
reference to the HotCache?, I decided you're right about this. I chose the
names addPositive() and addNegative().

description about cache(): it should describe what happens if there's already an entry that matches the key. Also also be tested.

Done.

HotCache::~HotCache?(): I don't understand what the for loop does. Does this do something correct? Also recall my other comment about why using in-house list. If we use std::list, we don't even have to bother to clean up these things.

I'm pretty sure this is correct, now that I've fixed the for loop.

HotCache::retrieve(): map::operator[] creates a new entry if it doesn't have one for the key. It's probably not necessarily incorrect, but I suspect it's error-prone behavior. For example, consider the case where the caller continuously calls retrieve() for different non-existent keys. I suggest you use map::find() instead.

Done.

HotCache::insert(): why do we need to have a while loop?

Changed to an if (and an assert()).

HotCache::ncache(): the condition of ANY()s isn't documented (and not intuitive).

Documented.

please don't hardcode flags (e.g. for the second arg of HotCache::cache()), even though it's opaque for the HotCache? module

Not yet done, but I will get to it tomorrow.

I see the effect of checking the cache before trying to identify the best data source. But that doesn't mean you have to alter the definition and interfaces of an existing class (NameMatch?), affecting many other parts of code that have nothing to do with hot spot caching. That was my point.

If you prefer, you could think of it as eliminating a class that's no
longer needed (NameMatch) and replacing it with one that serves our
needs better (ZoneInfo).

The NameMatch class is *not* a pristine general-purpose class; its sole
function, prior to this change, was the one it's still being used for now:
to iterate through through a list of data sources looking for the one that
is authoritative for a given name. There is no other use to which it can
be put. It already had several quirks, such as the special-case code for
rrtype==DS.

I haven't really changed it, I've just given it a slightly broader remit,
in order to eliminate unnecessary database searches. I don't think there's
any simpler way to accomplish this that still makes sense.

For example, you changed NameMatch, the signature of DataSrc::findClosestEnclosure() has also changed, affecting many other data source implementations and unit tests. One specific case is this:

This is totally irrelevant to hot spot caching, and I saw many such changes. They are distracting.

I don't agree that it's irrelevant--though perhaps it's a little
tangential. In the interests of making it easier to review, I can change
the signature of findClosestEnclosure() back to what it was--but I would
still want to make this change as soon as possible afterward, because IMHO
it's a bug waiting to happen. You specify a class when you create the
ZoneInfo object; if you then call findClosestEnclosure() with a
*different* class, it would cause a confusing failure. It makes a lot more
sense to preserve the information you used when you created the ZoneInfo
object.

However, if you think it's urgent that split this into multiple separate
fixes, I can do that.

For the present, however, what I've done is to fully commit to the change I
had made before: I've changed the NameMatch? class to be called ZoneInfo?,
which is clearer and more descriptive. As I say, however, if you think
it's necessary to split this into multiple changes, I will attempt it
tomorrow.

So, while I don't insist std::list is definitely better in this case, I would suggest you at least try a version with std::list, not just making a decision based on seeming observation. If, after playing with both ways, you are still sure the advantage of in-house implementation outweighs its negative consequences, it's your call.

I have now tried it with std::list, but I think it will damage performance
(unless I've missed some key features of std::list, which is certainly
possible).

As near as I can tell, to use a std::list, I would have to promote entries
by to the head of the list by using list::remove() followed by
list::push_front(). But list::remove() works by iterating over the list
searching for entries with the matching value to remove.

As I've currently written it, you get access to the CacheNode in O(log n)
time via the std::map, and then you can promote it to the head of the list
in constant time. With std::list, the promotion would be O(n).

One thing I cannot understand is the loop condition:

for (node = lru_head_; node = node->next; node != CacheNodePtr?()) {

Oops, yes, I had reversed the second and third statements.

comment:23 in reply to: ↑ 22 ; follow-up: Changed 9 years ago by jinmei

Replying to each:

I see the effect of checking the cache before trying to identify the best data source. But that doesn't mean you have to alter the definition and interfaces of an existing class (NameMatch?), affecting many other parts of code that have nothing to do with hot spot caching. That was my point.

If you prefer, you could think of it as eliminating a class that's no
longer needed (NameMatch) and replacing it with one that serves our
needs better (ZoneInfo).

The NameMatch class is *not* a pristine general-purpose class; its sole
function, prior to this change, was the one it's still being used for now:
to iterate through through a list of data sources looking for the one that
is authoritative for a given name. There is no other use to which it can
be put. It already had several quirks, such as the special-case code for
rrtype==DS.

I haven't really changed it, I've just given it a slightly broader remit,
in order to eliminate unnecessary database searches. I don't think there's
any simpler way to accomplish this that still makes sense.

I've been partially convinced, but not fully:-)

I'm okay with encapsulating zone related information (along with its data source) in a separate class and having the class the search logic.

I'm (personally) not okay with merging this responsibility into the class responsible for name matching over data sources. This is what I called "monolithic" (or leaky abstraction). Since you seemed to disagree with this view, I'm giving some more detailed explanation.

First, NameMatch now needs to be aware of RRType and do something tricky in the case of the type DS and the name root on construction (btw, this is a new change in this branch while you seemed to say otherwise: 'It already had several quirks, such as the special-case code for rrtype==DS'). Since NameMatch is a public class that may be used in other context than processing an incoming query, the added mandatory parameter and the additional embeeded logic make unnecessarily limit the applicability of the class.

Second, NameMatch now has both the search logic itself, even if the logic is only used in the top level query processing, that is, it's not necessary in each data source. For example, the name() method is only meaningful at the top level, but is open to public, resulting in a slippery interface. Consider a case where findClosestEnclosure() of a specific data source is called with NameMatch (or ZoneInfo) and it accidentally calls name().

So, I'd suggest separating these responsibilities, and hiding the matching logic class within the data_source.cc implementation. For example, it would be something like this:

class DataSrcMatch {
    DataSrcMatch(const RRClass& rrclass, const Name& qname);
    ~DataSrcMatch();
    const RRClass& getClass();
    const Name& getQname() const { return (qname_); }
    const Name* getClosestName() const { return (closest_name_); }
    const DataSrc* getBestDataSrc() const { return (best_source_); }
    void update();
};

class ZoneInfo() {
    const Name* getName();
    const DataSRc* getDataSrc();
    DataSrcMatch datasrc_match_;
};

ZoneInfo::getName() {
    if (datasrc_match_.getClosestName() != NULL) {
        toplevel_datasourc.findClosestEnclosure(datasrc_match_);
    }
    return (datasrc_match_.getClosestName());
}

ZoneInfo::getDataSrc() {
    if (datasrc_match_.getBestDataSrc() != NULL) {
        toplevel_datasourc.findClosestEnclosure(datasrc_match_);
    }
    return (datasrc_match_.getBestDataSrc());
}

where I renamed NameMatch to DataSrcMatch, because this is actually what the original NameMatch was supposed to be, and we could then avoid passing the class to findClosestEnclosure() separately. But it may be better to defer this change as it's now truely an irrelevant refactoring. Likewise, I changed some "getter" method names to be aligned with our coding guideline, but this is probably better to be deferred.

ZoneInfo is intended to be a private class, declared and defined within data_source.cc (not in a public header file).

And I'd keep the ./DS consideration outside the DataSrcMatch class and letting doQuery() do the job.

comment:24 Changed 9 years ago by jinmei

  • Owner changed from jinmei to each

comment:25 Changed 9 years ago by jinmei

Oh, and one more thing (different topic than NameMatch, etc).

I suspect the current implementation is very susceptible to DoS. I'd simply keep sending different queries that result in negative responses. They'll simply be cached and never purged.

I suggest by default we should disable cache, and by default impose some finite limit on the # of cache entries.

comment:26 in reply to: ↑ 23 ; follow-ups: Changed 9 years ago by each

Replying to jinmei:

I'm (personally) not okay with merging this responsibility into the class responsible for name matching over data sources. This is what I called "monolithic" (or leaky abstraction). Since you seemed to disagree with this view, I'm giving some more detailed explanation.

First, NameMatch now needs to be aware of RRType and do something tricky in the case of the type DS and the name root on construction (btw, this is a new change in this branch while you seemed to say otherwise: 'It already had several quirks, such as the special-case code for rrtype==DS').

Hmm, my mistake... I really thought that had been part of an earlier refactoring, sorry.

But still...

Since NameMatch is a public class that may be used in other context than processing an incoming query, the added mandatory parameter and the additional embeeded logic make unnecessarily limit the applicability of the class.

What other context? It currently returns the best enclosing zone match and the best data source; I really can't think of a purpose for this other than "figure out which zone and data source is authoritative for this name". (Remember, the whole original purpose was to avoid the need for a Name() constructor.)

That said, I'm fine with the separation you suggested (for the reason below). But I don't see why DataSrcMatch needs to be kept general-purpose, because I can't think of anything *other* than query or update processing that would ever need to find a zone and data source.

Second, NameMatch now has both the search logic itself, even if the logic is only used in the top level query processing, that is, it's not necessary in each data source. For example, the name() method is only meaningful at the top level, but is open to public, resulting in a slippery interface. Consider a case where findClosestEnclosure() of a specific data source is called with NameMatch (or ZoneInfo) and it accidentally calls name().

This is what sold me on the idea. I had noticed that concern with the ZoneInfo interface earlier, but it hadn't occurred to me that separating the functions would solve the problem.

You said something about this being "irrelevant refactoring", though. Are you saying we can do this in a different ticket? I'm fine either way.

And I'd keep the ./DS consideration outside the DataSrcMatch class and letting doQuery() do the job.

Here's where I don't see the advantage anymore. We're looking for the authoritative zone for a given query; the answer to that question depends on rrtype, so let's pass in rrtype and get the right answer. doUpdate() would want the same answer as doQuery().

I suggest by default we should disable cache, and by default impose some finite limit on the # of cache entries.

Imposing a default limit, good idea. I'll also add a function to HotCache so it can be enabled or disabled at runtime, and later on we can hook that into the config system. I'd really rather not have it be disabled by default, though (I'd like people to *notice* the performance improvement :) ).

I'm not sure what the default limit should be. Currently on my system the non-caching version can serve about a thousand queries per second; figuring it'll be about the same if every query that comes in is a cache miss, we should be able to cache 30,000 names before they start expiring. Does that seem like a reasonable size limit?

comment:27 in reply to: ↑ 26 ; follow-up: Changed 9 years ago by each

  • Owner changed from each to jinmei

Replying to each:

You said something about this being "irrelevant refactoring", though. Are you saying we can do this in a different ticket? I'm fine either way.

I went ahead and did this last night, so moot point now. :)

And I'd keep the ./DS consideration outside the DataSrcMatch class and letting doQuery() do the job.

I compromised by having ZoneInfo? do it, but not DataSrcMatch?. (However, I had to disable one of the unit tests because of this. I still think it makes more sense to have this live in DataSrcMatch?.)

I also added an enable/disable flag (and tests), and a default size limit of 30,000. Back to you...

comment:28 in reply to: ↑ 27 ; follow-up: Changed 9 years ago by jinmei

Replying to each:

You said something about this being "irrelevant refactoring", though. Are you saying we can do this in a different ticket? I'm fine either way.

I went ahead and did this last night, so moot point now. :)

And I'd keep the ./DS consideration outside the DataSrcMatch class and letting doQuery() do the job.

I compromised by having ZoneInfo? do it, but not DataSrcMatch?. (However, I had to disable one of the unit tests because of this. I still think it makes more sense to have this live in DataSrcMatch?.)

Okay, I think I can live with that compromize. It's very counter-intuitive that that made a test fail, though...I'll look into it.

I'll also check other points later.

comment:29 in reply to: ↑ 28 Changed 9 years ago by jinmei

Replying to jinmei:

I compromised by having ZoneInfo? do it, but not DataSrcMatch?. (However, I had to disable one of the unit tests because of this. I still think it makes more sense to have this live in DataSrcMatch?.)

Okay, I think I can live with that compromize. It's very counter-intuitive that that made a test fail, though...I'll look into it.

Please check the attached diff (not committed to the branch).

The failed test itself is a simple regression. Now that the search key (name) is adjusted in the caller side, type dependent consideration isn't necessary.

This also means we don't have to (or even shouldn't) pass RRtype to the DataSrcMatch constructor. In fact, the type isn't used any other part of this class. It was the case in your initial implementation, too, so we could have avoided having rrtype as a class member in the first place. This is another reason why I didn't think it makes sense to impose this responsibility to the Name/DataSrcMatch? class. The attached diff cleans this up, too.

Furthermore, we now don't need a separate test for DataSrcMatchByType because it's no different from other lookups. My proposed diff didn't do this cleanup yet.

On the other hand, we need more tests of other types for this class, including the case where class doesn't match.

Changed 9 years ago by jinmei

comment:30 Changed 9 years ago by each

I had almost committed the exact same change.

It looks fine, except that I would remove the DataSrcMatchByType? test entirely. There's no point to it any longer, it's now just two repetitions of the same test scenario (which should already be covered by the DataSrcMatch? unit test).

The other test you committed to the branch looks fine too.

Changed 9 years ago by jinmei

comment:31 in reply to: ↑ 22 ; follow-up: Changed 9 years ago by jinmei

On the specific point of std::list vs in-house list for LRU-based cleaning:

Replying to each:

So, while I don't insist std::list is definitely better in this case, I would suggest you at least try a version with std::list, not just making a decision based on seeming observation. If, after playing with both ways, you are still sure the advantage of in-house implementation outweighs its negative consequences, it's your call.

I have now tried it with std::list, but I think it will damage performance
(unless I've missed some key features of std::list, which is certainly
possible).

As near as I can tell, to use a std::list, I would have to promote entries
by to the head of the list by using list::remove() followed by
list::push_front(). But list::remove() works by iterating over the list
searching for entries with the matching value to remove.

No, in this case you would use list::erase().

See the attached patch. This is what I'd do if I were to use std::list for this purpose. This version doesn't have the performance problem you raised.

HotCache::~HotCache?(): I don't understand what the for loop does. Does this do something correct? Also recall my other comment about why using in-house list. If we use std::list, we don't even have to bother to clean up these things.

I'm pretty sure this is correct, now that I've fixed the for loop.

Maybe you are as you are the author of the implementation, but look at it pretending to be you are a reviewer who happens to take a look at it:

    for (node = lru_head_; node != CacheNodePtr(); node = node->next) {
        lru_head_ = node->next;
        if (lru_head_) {
            lru_head_->prev = CacheNodePtr();
        }
    }

    lru_head_ = lru_tail_ = CacheNodePtr();

this is way too far from intuitive logic. I can guess what this code is trying to do, but I need to use my brain heaviy to follow the logic, and it made me write a separate test (CacheTest.cleanup) to confirm it really does what it seemingly tries to do.

As I said, on the other hand, we don't even need the destructor in the std::list version (see the patch). With the properties of STL containers and shared pointers, it's obvious there shouldn't be any leak.

Another example: the in-house version has this code in insert():

    if (lru_head_) {
        node->next = lru_head_;
        lru_head_->prev = node;
        lru_head_ = node;
    } else {
        node->next = lru_head_;
        lru_head_ = node;
        lru_tail_ = node;
    }

I can see this code tries to insert the new node to the head of list, but it's not super obvious that it really does what it's supposed to do, so as a reviewer I'd need to use my brain to follow the in-house logic line by line.

The corresponding code in the std::list version is as follows:

    lru_.push_front(node);

Anyone who knows STL should be able to understand what it does instantly, and can be sure it actually does what it's expected to do.

You should be able to see many such contrasts in the patch.

As I said before, std::list version has its own drawbacks. For example, it would require a bit more memory. But after writing this version myself and seeing the difference, I now see the simplified code logic outweighs the overhead very much. What do you think?

comment:32 in reply to: ↑ 31 ; follow-up: Changed 9 years ago by each

Replying to jinmei:

See the attached patch. This is what I'd do if I were to use std::list for this purpose. This version doesn't have the performance problem you raised.

If you're certain of that, then I have no objection.

I sort of disagree about the readability; I find the C-like version easier to understand--but that's just because I understand C and don't really understand STL very well. Take this, for example:

    lru_.erase(node->lru_entry_); 
    lru_.push_front(node); 
    node->lru_entry_ = lru_.begin(); 

I accept your assurance that it does the right thing, but I would never have guessed it did. An old iterator can be preserved through list state changes and still be meaningful? I'm surprised to learn this, but if it works, I'm happy with it.

comment:33 in reply to: ↑ 26 ; follow-up: Changed 9 years ago by jinmei

Follow up comments on the Name/DataSrcMatch? desgin. I'm okay with the resulting code, but will respond to your points:

Since NameMatch is a public class that may be used in other context than processing an incoming query, the added mandatory parameter and the additional embeeded logic make unnecessarily limit the applicability of the class.

What other context? It currently returns the best enclosing zone match and the best data source; I really can't think of a purpose for this other than "figure out which zone and data source is authoritative for this name". (Remember, the whole original purpose was to avoid the need for a Name() constructor.)

That's actually my point. And, for the purpose of "figure out which zone and data source is authoritative for this name", we don't need RRtype.

As for "what other context", I can think of various cases, but as you yourself noted (in the next paragraph) dynamic update is one possibility. XFR is another.

You'd perhaps say we can pass a special RRType value such as ANY to indicate it's type independent, but adding the additional argument, which also requires additional test cases as we saw (and found it unnecessary in the end), just for a very special case of DS query doesn't make sense to me at all.

The additional dependency for a niche purpose is itself a problem in general. Consider, for example, the name to be matched may differ for some specific type of network in some very limited cases, and we add an argument of asio::io_service to the Name/DataSrcMatch? constructor for the convenient of that specifi case. In such an extreme case I guess we can all agree that it's overkilling.

Admittedly, this is a hypothetical example, and in this specific case importing RRType in addition to RRClass wouldn't be so different from importing just RRClass. However, in the generic sense of dependency concerns, IMO we should keep dependency as small as possible unless there's a strong reason to do so (instead of "it may be useful in some cases").

Looking at this issue from this point of view, while we *could* pass RRType to Name/DataSrcMatch? and have it tweak the name depending on the type, we *do not have to*: the only caller of this class for now is in data_source.cc, so it's just a matter of where we do this. If we do it in Name/DataSrcMatch?, we increase dependency in a public header file; if we do it in data_source.cc, we can hide it from other applications. In the sense of generic dependency consideration, the choice is obvious to me.

If, in the future, it turns out we need to tweak the name based on some RRType in so many places, we can then consider extending the class so that it will also accept an RRtype argument and adjust the behavior depending on the type. And, this can be a backward compatible change. Until then, we should keep public classes as small as possible.

That said, I'm fine with the separation you suggested (for the reason below). But I don't see why DataSrcMatch needs to be kept general-purpose, because I can't think of anything *other* than query or update processing that would ever need to find a zone and data source.

comment:34 in reply to: ↑ 32 Changed 9 years ago by jinmei

Replying to each:

See the attached patch. This is what I'd do if I were to use std::list for this purpose. This version doesn't have the performance problem you raised.

If you're certain of that, then I have no objection.

This is true. See http://www.cplusplus.com/reference/stl/list/erase/

Complexity: Linear on the number of elements erased (destructors).

Since in our case the number of elements is 1, it's constant. push_front() and push_back() are also constant-time operations (as we can reasonably expect for lists).

I sort of disagree about the readability; I find the C-like version easier to understand--but that's just because I understand C and don't really understand STL very well. Take this, for example:

    lru_.erase(node->lru_entry_); 
    lru_.push_front(node); 
    node->lru_entry_ = lru_.begin(); 

I accept your assurance that it does the right thing, but I would never have guessed it did. An old iterator can be preserved through list state changes and still be meaningful? I'm surprised to learn this, but if it works, I'm happy with it.

It's difficult to parse the question...but if I understnad it correctly, the answer is yes. Again, see http://www.cplusplus.com/reference/stl/list/erase/

lists are sequence containers specifically designed to be efficient inserting and removing elements in any position, even in the middle of the sequence. Compared to the other base sequence containers (vector and deque), lists are the most efficient container erasing at some position other than the beginning or the end of the sequence, and, unlike in these, all of the previously obtained iterators and references remain valid after the erasing operation and refer to the same elements they were referring before (except, naturally, for those referring to erased elements).

Overall, std::list is carefully designed so that it ensures the properties we'd expect for "a list".

Admittedly, though, the validity of iterators on modification to the list may not be so obvious, especially because it's not the case for std::vector.

comment:35 in reply to: ↑ 33 ; follow-up: Changed 9 years ago by each

Replying to jinmei:

That's actually my point. And, for the purpose of "figure out which zone and data source is authoritative for this name", we don't need RRtype.

As for "what other context", I can think of various cases, but as you yourself noted (in the next paragraph) dynamic update is one possibility. XFR is another.

But, whether you're doing an update or an XFR or a query, the authoritative zone for example.com/DS is *always* going to be different from the authoritative zone for example.com/NS or any other qtype. So I don't see the point of omitting it from consideration by the DataSrcMatch? class. However, I'm content with the code we have, so let's agree to disagree. :)

comment:36 in reply to: ↑ 35 ; follow-up: Changed 9 years ago by jinmei

Replying to each:

As for "what other context", I can think of various cases, but as you yourself noted (in the next paragraph) dynamic update is one possibility. XFR is another.

However, I'm content with the code we have, so let's agree to disagree. :)

Okay, but I'm afraid we were probably not on the same page, so let me clarify a few things.

But, whether you're doing an update or an XFR or a query, the authoritative zone for example.com/DS is *always* going to be different from the authoritative zone for example.com/NS or any other qtype. So I don't see the point of omitting it from consideration by the DataSrcMatch? class.

I don't understand the logic. Neither update nor XFR request takes into account the "RR type" (DS or NS, etc) in identifying the appropriate authoritative zone (or the data source that stores the zone). For XFR requests the server checks its question, which is a tuple of "zone name, class (and type=AXFR)". For update requests the server checks its zone section, which is a tuple of "zone name, class (and type=SOA)". There's another example, notify, in which case the server checks its question, which is a tuple of "zone name, class (and type=SOA)".

Only the DS query in normal queries require special considerations.

And, I'd expect a C++ implementation of xfr/update/notify handlers would use the DataSrcMatch interface to identify the appropriate data source for the request, in which case the additional information for qtype is just distracting. (I know in our current development plan of BIND 10 these will be python scripts, but I'm talking in the context of the design of a public API, which will be used by any external developers)

Do you mean, by "don't see the point of omitting it from consideration by the DataSrcMatch class", we should include this special consideration in DataSrcMatch simply because the specific case of DS normal query requires it while others don't need it?

If so, this is something like a proposal that we should extend BIND 9's dns_zt_find() (which are called from query/update/xfrout/notify routines) by adding a type argument and having it behave differently if the type is DS (and even more differently if the qname is root) because among various usage cases query.c:query_find() requires this consideration.

If you also don't see the point of why this is awkaward, yeah, I must admit we have to disagree.

comment:37 in reply to: ↑ 36 Changed 9 years ago by each

Replying to jinmei:

I don't understand the logic. Neither update nor XFR request takes into account the "RR type" (DS or NS, etc) in identifying the appropriate authoritative zone (or the data source that stores the zone).

True, XFR was a bad example, of course it doesn't care about a specific rrtype. But here's an UPDATE, on a BIND 9.7.1 server which is authoritative for example.nil:

$ nsupdate -l
> ttl 3600
> update add example.nil. IN DS 9498 7 1 5164B0246FD74DB21DBC97B7AB2247426C79E02B
could not find enclosing zone

However, that works fine for example.nil/A or example.nil/TXT. You can silence the complaint from nsupdate by specifying "zone example.nil" in advance, but the zone won't accept the DS record--it appears successful, but the record doesn't show up later in an AXFR or in the zone file after rndc freeze. The update failed.

The bottom line is that example.nil is not authoritative for example.nil/DS; nil is. The question "which zone is authoritative for this RR?" is partially dependent on rrtype. So if I'm designing a tool to answer that specific question--which I was--I'd want to include an optional rrtype as one of the input parameters.

(Note "optional". The DataSrcMatch constructor had a default RRType::ANY() for the third parameter, ZoneMatch still does. So when rrtype isn't relevant, you can construct with only name and rrclass and get the expected result.)

If so, this is something like a proposal that we should extend BIND 9's dns_zt_find()

dns_zt_find() doesn't determine the authoritative zone for a resource record, it looks up a zone by name in the zone table, which BIND 10 doesn't have. So it's not really analogous.

But, again, we've settled on a version that we're both okay with. Not that arguing isn't fun, of course! But let's pick a new topic. :)

comment:38 Changed 9 years ago by jinmei

On in-house list implementation vs std::list.

I've written a simple performance benchmarks using my framework in the experiments/jinmei-onmemdb branch (r2292).

It focuses on the performance of moving one entry of the list to the head of the list. The implementations are mostly a verbatim copy from the relevant part of cache.cc (and my counter proposal version).

Interestingly, in-house version is much slower than std::list version. Here are the results:

Move-to-front benchmark using std::list with erace/push
Performed 200000 iterations in 0.031950s (6259780.91ips)
Move-to-front benchmark using std::list with splice
Performed 200000 iterations in 0.004197s (47653085.54ips)
Move-to-front benchmark using in-house list implementation
Performed 200000 iterations in 0.058643s (3410466.72ips)

The "with splice" version introduces an additional optimization so that we can avoid overhead of erace/push operation. but the in-house version is even slower than the naive erace/push version. and it's more than 10 times slower than the std::list+splice version.

I've not figured out exactly why it was, but one possible explanation is the in-house version requires many operations on shared_ptr's, not bare pointers, and seemingly cheap operation such as ptr1 == ptr2 or ptr1 = ptr2 can be a bit more expensive than it might look.

This result seems quite informative. Most notably, when it comes to performance, we should measure it rather than guess.

comment:39 follow-up: Changed 9 years ago by jinmei

On the DataSrcMatch class:

I've updated the code based on the agreement (or at least what I believe we agreeded on) in the review (r2298).

A few notes, including a substantial one:

  • I guess there's a bug in the current implementation (not specific to this branch. it should be the same for the current trunk version). see DISABLED_initialUpdateWithNoMatch.
  • I've added many more tests and more detailed doxygen description. I'd expect any new document to be as detailed as this one. And, it helps us, too; I noticed the bug through this process.
  • and this is a substantial note: in the end, I'm feeling even DataSrcMatchTest dropping RR type is leaky. this interface cannot well explain test cases like DataSrcMatchTest.updateWithWrongClass. we could provide artificial restriction such as an exception to be thrown or simply ignoring RR class in update(), but it looks like counter intuitive and error prone. To me, this suggests we should revisit the abstraction, and my updated suggestion is to simply go back to the original design of NameMatch. And we pass an RR class parameter to findClosestEnclosure() separately. As we discussed, whether to include RRclass in Name/DataSrcMatch? doesn't affect the hot spot caching itself, and, as a bonus, the diff will be smaller and review will be easier.

comment:40 in reply to: ↑ 39 Changed 9 years ago by each

  • I guess there's a bug in the current implementation (not specific to this branch. it should be the same for the current trunk version). see DISABLED_initialUpdateWithNoMatch.

Not sure I'd exactly call it a bug, because it could never have occurred in normal processing, but you're right that it's an API flaw. Thanks for noticing it.

  • I've added many more tests and more detailed doxygen description. I'd expect any new document to be as detailed as this one. And, it helps us, too; I noticed the bug through this process.

Thanks for that too.

  • and this is a substantial note: in the end, I'm feeling even DataSrcMatchTest dropping RR type is leaky. this interface cannot well explain test cases like DataSrcMatchTest.updateWithWrongClass. we could provide artificial restriction such as an exception to be thrown or simply ignoring RR class in update(), but it looks like counter intuitive and error prone. To me, this suggests we should revisit the abstraction, and my updated suggestion is to simply go back to the original design of NameMatch.

IMHO the original design of NameMatch isn't much better in this respect. I think you'll find that the initialUpdateWithNoMatch test would have failed before too.

The design from day one was that there's an interplay between the update() function of the NameMatch object and the findClosestEnclosure() function of the DataSrc object. They essentially ping-pong back and forth, and we've been treating them as if they're effectively two parts of a single function.

This was always slightly odd. Allowing uninitialized Name() objects would have solved the specific problem more cleanly, but introduced a different set of risks elsewhere in the code. Keeping update() hidden away in data_source.cc as a static function or a bit of PIMPL implementation would have helped, but unfortunately there are lots of data sources that all need direct access to it, so that wasn't an option. So, it was exposed as public API and yet we've treated it as conceptually static. Oops.

IMHO the right fix is to check the input to update(). We ought to do this anyway, whether we're using the old NameMatch or the new DataSrcMatch, so I don't see it as a strong argument in favor of either option.

I'm adding a fix to the branch (r2314) which checks for class mismatch in all cases, and for name mismatch in the initial case. This addresses the initialUpdateWithNoMatch problem. The updateWithWrongClass test had to be changed because the first match now fails. We should add some tests using two different data sources, one class CH and the other class IN, but if you'll allow it, I'd like defer that until after this branch has been merged so I can take advantage of your refactoring of the test data source.

comment:41 follow-up: Changed 9 years ago by each

BTW I just noticed that your refactoring of the LRU queue to use std::list had not been committed to the branch. I've done so.

comment:42 in reply to: ↑ 41 Changed 9 years ago by jinmei

Replying to each:

BTW I just noticed that your refactoring of the LRU queue to use std::list had not been committed to the branch. I've done so.

That's because I thought it was still under discussion:-) But thanks. Will continue reviewing the rest of the code...

comment:43 Changed 9 years ago by jinmei

quick review comments on r2363 as requested:

  • I have some proposed style fixes. directly committed to branch. r2368. not using default parameter may be a matter of style preference, but IMO it can easily cause surpring bugs we should avoid using it unless we use the default parameter in so many cases (which is not the case here).
  • in data_source.cc
    +        flags = count = 0;
    
    I don't see why we need to reset count here. (actually the same for flags). as I noted before, the long and complecated code logic tends to make us confused and introduce unnecessary or buggy operations. this seems to be another indication of the need for refactor, but for now I don't require that. Either just remove it, or according to BIND 9's coding guideline use separate lines for the two assignments.
  • DuplicateQuery? looks okay, although I want to have more comprehensive tests in this sense.

not a direct comment on the patch:

-            return (DataSrc::SUCCESS);
+            return (true);

this type of error is one major reason why I generally prefer types instead of numerics. In this specific case I may choose enum, though.

comment:44 Changed 9 years ago by each

  • Resolution set to fixed
  • Status changed from reviewing to closed
  1. [func] each

Added a hot-spot cache to libdatasrc to speed up access to
repeatedly-queried data and reduce the number of queries to
the underlying database; this should substantially improve
performance. Also added a "-n" ("no cache") option to
bind10 and b10-auth to disable the cache if needed.
(Trac #192, svn r2383)

Note: See TracTickets for help on using tickets.