Separate disk related functions in CClaimTrieDb #175
No reviewers
Labels
No labels
area: devops
area: discovery
area: docs
area: livestream
area: proposal
consider soon
Epic
good first issue
hacktoberfest
hard fork
help wanted
icebox
Invalid
level: 0
level: 1
level: 2
level: 3
level: 4
needs: exploration
needs: grooming
needs: priority
needs: repro
needs: tech design
on hold
priority: blocker
priority: high
priority: low
priority: medium
resilience
soft fork
Tom's Wishlist
type: bug
type: discussion
type: improvement
type: new feature
type: refactor
type: task
type: testing
unplanned
work in progress
No milestone
No project
No assignees
1 participant
Notifications
Due date
No due date set.
Dependencies
No dependencies set.
Reference: LBRYCommunity/lbrycrd#175
Loading…
Add table
Reference in a new issue
No description provided.
Delete branch "separate_disk_claim_rebased"
Deleting a branch is permanent. Although the deleted branch may continue to exist for a short time before it actually gets removed, it CANNOT be undone in most cases. Continue?
This is a rebased and squashed version of @bvbfan 's CClaimTrieDb commits which separates disk related function from the claimtrie into its own class (from https://github.com/lbryio/lbrycrd/pull/160)
I removed here commits which renamed CClaimTrieCache and nCurrentHeight, as well as the new management of CClaimTrieNode, they will be put into seperate PR's.
This PR is not downgrade compatible (once you upgrade to this commit, you will not be able to downgrade to previous versions without wiping your claim database) and should be accompanied by a version bump.
Why not an unordered_map? (or map if ordering matters). It appears from the method below that we commonly need to find by key. I suppose changing to a dictionary structure is not the intent of this story.
unordered_map is a hash_map, so we should provide a hash algorithm for some classes, like base_blob derived.
No, this is broken.
@ -248,2 +195,3 @@return current->haveClaim(outPoint);const CClaimTrieNode* current = getNodeForName(name);return current && current->haveClaim(outPoint);}If this style change (and others like it) isn't pulled in from clang-format, remove it.
If this style change (and others like it) isn't pulled in from clang-format, remove it. (Please apply to other cases as well -- alternatively, just run clang-format and rebase and comment that that's why it's here.)
@ -437,4 +364,3 @@return false;}claimsForNameType CClaimTrie::getClaimsForName(const std::string& name) constAdding this else isn't needed.
@ -1072,3 +621,4 @@return db.Sync();}bool CClaimTrie::InsertFromDisk(const std::string& name, CClaimTrieNode* node)name.empty() ?
@ -1320,3 +855,1 @@}else{} else {Again, unless it's clang-format specified, don't add lines that aren't needed.
@ -1359,3 +893,3 @@{if (cachedNode != cache.end()) {currentNode = cachedNode->second;continue;Suggested style: if (current && !current->claims.empty())
@ -2520,2 +1796,3 @@{hashMapType::const_iterator cachedHash = cacheHashes.find(leafPosition.str());if (cachedHash != cacheHashes.end()) {return cachedHash->second;Alternative style:
I'll stop commenting on style, perhaps it's pointless, or maybe clang-format will help (although not on things like this, which are adding unnecessary lines).
Why are we removing const from all of the methods? Are we also removing mutable members?
This answers my previous question about removing mutable members. Disregard.
I don't think the queues get to be that large, but perhaps someday it's worth measuring the performance. As it is, you gain cache effects due to locality (I think this wins), but with a well defined hash and unordered_map you gain constant time retrieval. This is not urgent for this PR and it's fine as-is. I'd also advise (style) to just use std::find.std::find_if with a comparator if/when it's supported by the compiler (certainly after upstream merges).
As a compromise (and simplicity), perhaps it's worth considering 2 step hashes such that the above hash == some_map[K][V]? I see why you need these now, but we're jumping through some hoops to get there, no? What I proposed is probably less space efficient, but I want to be sure we're doing this in a sustainable way going forward.
Where did these definitions come from? It should be documented because 1) Not all hashes are equally appropriate, and 2) I'd hope we can replace most/all of these with boost:: or std:: hash implementations. I don't think supporting these in our code forever is ideal.
If we really want to do this, there are plenty of template specialization varieties that can be made that resort to std::hash which eliminates the need for many of the custom hash variants.
I really wish we could avoid this kind of test, but if we go this route, at least it helps locate regressions.
@ -248,2 +195,3 @@return current->haveClaim(outPoint);const CClaimTrieNode* current = getNodeForName(name);return current && current->haveClaim(outPoint);}Update: Hopefully this has already been clang-formatting because a large portion of it is just mechanical style changes, and it's distracting for such a large commit. I realize that as we're requiring clang-format now this should be less an issue in the future. If these were added manually, I suggest an immediate format/rebase.
What is broken?
@ -248,2 +195,3 @@return current->haveClaim(outPoint);const CClaimTrieNode* current = getNodeForName(name);return current && current->haveClaim(outPoint);}The style is recommended bitcoin style which @kaykurokawa describe days ago.
@ -248,2 +195,3 @@return current->haveClaim(outPoint);const CClaimTrieNode* current = getNodeForName(name);return current && current->haveClaim(outPoint);}See above.
@ -437,4 +364,3 @@return false;}claimsForNameType CClaimTrie::getClaimsForName(const std::string& name) constSame as above.
Yes.
Get it from here -> http://lolengine.net/blog/2011/12/20/cpp-constant-string-hash it should be unique.
Yes, it's helper macro. There is no need to write class names by hand.
The test aims to guarantee that all distinct type has an unique id, when new type is added unit test should be updated as well. The algorithm should produce same results on all different compilers and all its versions, which is not guaranteed nor by std::type_id nor by boost::type_id.
Is there some stopper to merge my changes on master? I plan to rebase my last changes for wed meet.
I agree that this is a bad pattern. This should technically cause linker problems due to double definition.
I like the change. Saying that a removal method is
constis misleading. The only place I would expect to see themutablekeyword is in an immutable object for the caching of expensive-to-compute fields.It looks like but is not. Template has a external linking and it has few hacks to prevent problems:
I made the file safety included in all conditions, that's needed when it has a templates in.
Including a cpp file from another means incorrect/bad organization. That is what I meant by broken.
@ -248,2 +195,3 @@return current->haveClaim(outPoint);const CClaimTrieNode* current = getNodeForName(name);return current && current->haveClaim(outPoint);}This is produced from clang-format?
This is under review. Feel free to rebase, but it won't be merged (i.e. don't merge it) until review is complete.
So this is no correct, i don't want to opposite you but describe some pattern as incorrect by default is not serious.
This link didn't work for me. It's also not really documenting why we want to use these hash values in our code base indefinitely, as opposed to re-organizing or sticking with existing boost/std ones (or some composition of).
So it was accepted month ago, this is only separate review original was #140
This is not a strong argument for why we want/need to support our own hashing here. This seems like a case of NIH, which should be avoided (https://en.wikipedia.org/wiki/Not_invented_here#In_computing). I don't have an understanding of why we must go this route without considering other options. What should be an organizational PR (as the name states separating methods out), looks to be far larger, including a breaking database re-organization which is something else entirely.
@bvbfan If you've had discussions about this work that I was not a part of (surely you have), I'd like to chat with whoever had them with you :-) @kaykurokawa ? If it's just a matter of me not being caught-up, I'll adjust the review accordingly.
I hadn't reviewed it then. Being a team that is responsible for maintaining this code might mean multiple rounds of reviews. If @kaykurokawa is going to merge it as-is, that's up to him, but my concerns are worth noting here anyway.
There is no problem to be reviewed but let be conceptional rather than a silly comments. I mean when you know better way to do it, describe it how to do.
What silly comment(s)? I'm mostly asking questions on or pointing out things I don't know, or don't look right to me. As you said, if this has already been reviewed despite my concerns, it'll be merged anyway.
I'm only reviewing it because I care about this code and wonder about future maintenance. This work was not assigned to me, so I don't know a better way to do all of it (and haven't thought about it as much as you and/or @kaykurokawa). If you've exhausted all alternative implementations and arrived here, it'll be merged and this is all disregarded anyway. Since I don't know, I've added my 2 cents. I don't know if that provides any value though. 2 "lbrynaut tokens" worth of input may not be worth much :-)
Only for clarification -> "Including a cpp file from another means incorrect/bad organization. That is what I meant by broken." is a silly comment. This not broke anything and it's not forbidden or anything else. Templates want it, adding an *impl files is not better about me, if you know better describe it.
Of course it's not forbidden, but that doesn't mean that it's common or required either. In fact, it would be a first for this entire code base, which is why it stands out.
There is not problem to be implemented in other way, but i'm against pattern to described to be bad by default. About me, only better pattern can make other to be marked as bad.
Ok. I don't agree though. Most times I've seen cpp files included from others was due to bad organization and/or laziness. Similar to "goto" statements. There's nothing wrong with them, and often you can achieve a lot using them. But I think they are also bad organizationally. What I mean by organization in this sense affects readability and comprehension. There are many ways to implement things that hide other issues (such as linker problems, or basic error checking), but that doesn't mean they're all 'good' to use, even if allowed. In most cases, a slight re-organization can improve readability/flow, which also helps comprehension, which leads to better maintenance, etc.
We may not agree on style, and I'm ok with that. But since we're both working on this code and this is not a common use for the project, I hesitate to introduce it just because we can. My opinion on introducing this is "it's broken", meaning it absolutely should not be introduced. But like I said, my token input may be worthless ;-)
As i say before this is not a regular cpp file, it's like a template implementation file, since i'm not prefer to separate cpp and impl files i've made a trick to combine them.
@bvbfan , can you explain why these hash methods weren't necessary before but are now?
Sure. Whole idea behind these hashes is to use as safe as possible db. Till now they a predefined chars 'n', 'r' etc. which was used in claimtrie.cpp now we separated it and calls can be type safe e.g. you can only declare type and don't care what is predefined char, hash or anything else. The first idea was to use boost::type_id but for sake of not generate same hashes in all its versions (e.g. in 1.59 and 1.64 are not same) i aim to provide a proven algorithm to generate same hashes in all compilers and OS'es. That's why unit test matters to prove any type that we need has a unique value.
Not only this, generic functions prevent code duplication and it does not need to update db implementation every time when new type is introduced. I've notice many code duplication in claimtrie i aim to remove it at all, this kind of implementation do it.
I think the linker problem where we have to include "claimtriedb.cpp" in claimtrie.cpp is just an unfortunate problem when working with template classes in C++. In one of my past project we put implementations in the header file to get around this. I believe you can also use forward declaration (not sure if that is the right term , see last solution here: http://www.cs.technion.ac.il/users/yechiel/c++-faq/separate-template-class-defn-from-decl.html ) but that looks like the worst solution in this case due to the number of functions and possible types.
So I think in this case, the solution chosen here seems fine given that the other two solutions are equally bad.
The point regarding the new hashing features @lbrynaut brought up is good. Maybe it was a bad idea to change the original simple hashing function (where each type was assigned a unique letter) to this one , considering that we could have avoided a database migration and the code would have been simpler. This is not @bvbvfan 's fault , I said that it would be OK to do this but in hindsight this was not the best idea (I can take responsibility and fix this ).
I can propose a fix that will not introduce migration nor cpp include. It can be done by template implicit instantiation of every function like this:
template<> inline char hashType<std::string, CClaimTrieNode>() { return 'n'; } template CClaimTrieDb::getQueueRow<>(const std::string &key, CClaimTrieNode &row); // explicit instantiationThis can be done in claimtrie.db so it will not needed to be include anywhere, when we add new type new explicit instantiation should be provided. I can do that on master and make a new RR if it accept by all of us.
I think the above new solution looks good to me
I'm aware of the issue, but if we really have to go this route, I think it should be made clear in a more standard way. For example, under the include dir having an impl directory with the implementation defined in .ipp files makes it clear what's going on at least. It's true it's more or less the same thing, but projects like boost chose to do it that way, and a lot of projects have followed with good reason (a de facto standard).
That said, I still don't like the idea of needing these methods in the first place and would prefer to see the solution that does not require the new types at all nor the DB migration. @kaykurokawa The one way migration makes me nervous because usually migrations are done for underlying reasons other than a migration for the sake of it. Second, if the migration simplified the code or allowed us to eliminate unnecessary code, I'd be all on board -- but instead this is the opposite, taking on responsibility for more untested code that adds complexity. If you see the need to go this route, let me know what's on your mind (I still think I'm missing some background on this). Otherwise, I want to avoid all unnecessary code to avoid the future maintenance costs.
I'd like to review this solution as a PR.
There is no migrations or cpp/ipp include, see better. The worst case to me is separate directory with ipp files in.
I push it in this branch, now it's able for review.
I've perform some style fixes, more to come when CClaimCache is renamed and separated in its own file, in feature RR.
@bvbfan I discussed this briefly with @kaykurokawa and here is where I'm at with it:
If anyone else thinks this work is urgently needed and @kaykurokawa is unable to add the required input, let me know and I'll re-prioritize.
For me, existing code base is redundant and it contains duplicate code fragments, RR-s, not only this, solve issues, later ones memory leaks. So after all it's not an over-engineering at all, furthermore it simplifies all logic.
Rebase to master, @kaykurokawa if you have a comments or advice please share them otherwise it ready to go in.
Hey, this seems to have some problem syncing, seems to be a new problem that was not present in previous iterations of this PR.
After CClaimTrie::WriteToDisk() is called to write buffers to disk ..
this problem occurs:
2018-08-18 22:25:59 incrementBlock: nCurrentHeight (before increment): 33913
2018-08-18 22:25:59 ERROR: ConnectBlock() : the merkle root of the claim trie does not match (actual=0000000000000000000000000000000000000000000000000000000000000001 vs block=c4827743b4a73ca1b35275805f0564b1fe6d294ea316199173d9039f41fa3f40)
2018-08-18 22:25:59 Misbehaving: 103.100.44.62:9246 (0 -> 100) BAN THRESHOLD EXCEEDE
It seems like the merkle root of the claim trie gets calculated the same as an empty trie after CClaimTrie::WriteToDisk() is called. I'm investigating the problem.
You tests with some mock data, unit tests pass when i test them, maybe we should update them.
Can you provide steps to reproduce?
I wiped the data directory and started lbrycrdd from scratch.
So i found what you mean i think, so
call WriteToDisk()
then not call ReadFromDisk
lead to not finding claims
I'll investigate if mean that.
I found the problem
void CClaimTrieDb::updateQueueRow makes a swap on IN parameter (i don't want to change this behavior but it's not used on node) witch cause root to became empty, so with patch above issue is fixed and ready to land. Branch is updated with related patch.
@ -2705,15 +1848,12 @@ bool CClaimTrieCache::getProofForName(const std::string& name, CClaimTrieProof&nodes.push_back(node);current = nextCurrent;}Why do we need to clone this? That looks like a good way to make a memory leak.
I think this method needs to return a read-only collection. Are people going to add to modify that data thinking that they're updating the actual queue? In looking at the code, it appears that we do return the real buffer, but that's only one of three cases. The other two: we read something off disk or we use that
createIfNotExistsflag.What does this line do if getQueueCacheRow actually called Read?
Any way we can do these updates in a
forloop instead? We have all the buffers in a collection, no?What if this inherited from std::map instead? You wouldn't need the find and insert methods below. You wouldn't need the dataType stuff. It seems like that would be less code.
@ -0,0 +126,4 @@itData = map->push_back(std::make_pair(key, V()));}std::swap(itData->second, row);}If you were using a real map here, the above four lines would turn into a single
map->at(key) = row;. That seems more straightforward to me. Are you intentionally trying to return the old row here? If so, it should use the method return. The way that's coded is going to lead to unintended consequences.Map is ordered i.e. it'll reorder every insert, list benefits speed over it O(log N) vs O(N)
@ -0,0 +126,4 @@itData = map->push_back(std::make_pair(key, V()));}std::swap(itData->second, row);}Yeah, but i don't think it's worst, no?
@ -2705,15 +1848,12 @@ bool CClaimTrieCache::getProofForName(const std::string& name, CClaimTrieProof&nodes.push_back(node);current = nextCurrent;}It should, i'll provide memleak free RR next to this.
It private one, so it safe to return iterator over second argument, which is map.
CClaimTrieCache::update has a for loop.
Yeah, but when it's found it added to map then it's erased from cache map.
Your current use of a list is O(1) insertion time; it's the lookup time that suffers. Once we get the upstream c++11, we could use an unordered_list, which is definitely faster. However, the number of buffers we have is small; none of these solutions are going to be a performance problem. Hence, I prefer the "less code" option.
@ -0,0 +126,4 @@itData = map->push_back(std::make_pair(key, V()));}std::swap(itData->second, row);}I do think it's pretty bad; it's what caused the problem that Kay found, right?
CDBWrapper::Read does not automatically add to the cache as far as I can tell.
@ -0,0 +126,4 @@itData = map->push_back(std::make_pair(key, V()));}std::swap(itData->second, row);}I don't have good reason for swap, but follows current behavior.
getQueueCacheRow put it to cache, line:1079, this is safe, it ease from cache.
Update unit test from @kaykurokawa and adjust @lbrynaut fix in #197 + perform clang-format on affected files.
Fix clang issue.
Rebase to resolve conflicts.
@lbrynaut has requested that we hold on this until his upstream merge changes come in.
Pull request closed