Page MenuHomePhabricator

radixbuf: implement the main radix tree
ClosedPublic

Authored by quark on Nov 2 2017, 2:45 PM.

Details

Reviewers
durham
Group Reviewers
Restricted Project
Commits
rFBHGX747212d2dd06: radixbuf: implement the main radix tree
Summary

Implement the main radix tree with tests. A quick benchmark shows the
insertion performance is similar to the known revlog.c implementation.

The time complexity is about O(N * log N) for inserting or looking up N
entries. The log part is because the prefix length is increasing. A rough
(not so accurate) real world benchmark is like:

NInsertLookupChecked Lookup [1]Index Size
10k0.70ms0.25ms0.36ms0.25MB
20k1.3ms0.58ms0.8ms0.45MB
50k4.9ms1.9ms2.6ms1.1MB
100k11ms4.5ms6.8ms2.5MB
200k26ms13ms17ms4.9MB
500k68ms46ms54ms11MB
1M170ms130ms150ms24MB
2M420ms300ms350ms51MB
5M1.2s0.9s1.1s110MB
10M2.7s2.3s2.7s220MB
20M6.2s5.1s5.8s490MB
50M19s16s18s1.2GB

[1]: After lookup, verify the key id maps to the key. Can be skipped if key
length is fixed and index data could be trusted.

Test Plan

cargo test --lib. Also use kcov to make sure every line is covered
except for return false in quickcheck functions, or things requiring a
buffer size that exceeds u64.

cargo rustc --lib --profile test -- -Ccodegen-units=1 -Clink-dead-code -Zno-landing-pads
kcov --include-path $PWD/src --verify target/kcov ./target/debug/*-????????????????

Diff Detail

Repository
rFBHGX Facebook Mercurial Extensions
Lint
Automatic diff as part of commit; lint not applicable.
Unit
Automatic diff as part of commit; unit tests not applicable.

Event Timeline

quark created this revision.Nov 2 2017, 2:45 PM
Herald added a reviewer: Restricted Project. · View Herald TranscriptNov 2 2017, 2:45 PM
quark edited the summary of this revision. (Show Details)Nov 2 2017, 3:02 PM
quark added a subscriber: durin42.Nov 2 2017, 3:03 PM
quark edited the summary of this revision. (Show Details)Nov 3 2017, 2:17 AM
quark updated this revision to Diff 3251.
quark edited the summary of this revision. (Show Details)Nov 3 2017, 4:04 AM
quark added a comment.Nov 3 2017, 2:52 PM

@durin42 I'm going to re-send my Rust code to internal Phabricator since Rust reviewers are much more active there and the code could be highlighted properly. I will probably send new Rust code directly there. Let me know if you still want copies to be sent here.

Frankly I don't see the point of doing the review in two places, since I won't be able to see things.

Can we please just get your rust reviewers to respond here instead of developing this in secret?

quark added a comment.EditedNov 3 2017, 4:17 PM

Frankly I don't see the point of doing the review in two places, since I won't be able to see things.
Can we please just get your rust reviewers to respond here instead of developing this in secret?

I have asked several Rust reviewers and they all prefer the internal instance. I just sent a few patches and put #rustreviewers as reviewer and got instant feedback from people I haven't explicitly notified. I think it's possible to ping certain people to check here but len(#rustreviewers) is 20+ that are harder to move here. (most of them are not doing Mercurial development).

Well, I'm 100% unwilling to participate in reviews that aren't happening in the open, so I guess come back with a giant code bomb and be prepared for it to take a *long* time to land in core. It's just too hard to coordinate.

quark edited the summary of this revision. (Show Details)Nov 6 2017, 2:10 PM
quark updated this revision to Diff 3296.
quark planned changes to this revision.Nov 10 2017, 1:08 PM

While trying to integrate with Python. The Shared type is causing trouble. I'm going to change the API to be lower-level.

quark edited the summary of this revision. (Show Details)Nov 11 2017, 1:33 AM
quark edited the test plan for this revision. (Show Details)
quark retitled this revision from radix204: implement the main radix tree to radix20: implement the main radix tree.
quark updated this revision to Diff 3419.
stash added a subscriber: stash.Nov 13 2017, 5:40 AM

I had to spend quite a lot of time understanding the logic. Probably this problem can be solved with just a few comments:

  1. Mention why do we have 16 pointers in RadixNode
  2. Mention how does this radix tree work - that we may have "fat" leafs, that they may need to be split etc.
quark edited the summary of this revision. (Show Details)Nov 15 2017, 8:55 PM
quark retitled this revision from radix20: implement the main radix tree to radixbuf: implement the main radix tree.
quark updated this revision to Diff 3546.
In D1291#22839, @stash wrote:

I had to spend quite a lot of time understanding the logic. Probably this problem can be solved with just a few comments:

  1. Mention why do we have 16 pointers in RadixNode
  2. Mention how does this radix tree work - that we may have "fat" leafs, that they may need to be split etc.

Sorry for the late response - got addicted writing Rust code. Will draw some ASCII graphs to explain things.

durham added a subscriber: durham.Nov 29 2017, 8:24 PM
durham added inline comments.
rust/radixbuf/src/radix.rs
11

Does this mean a KeyId can only be at most 2^31 instead of 2^32?

52

I'd make it clear that the match may not actually be a match for the sequence, and is instead the match for some prefix of the sequence. So the caller needs to check that the return 'i' is the length of KeyId, even if the first return parameter is not None.

53

Maybe make this sentence a bit clearer. I didn't realize that you were listing the contents of the follow state after the hyphen, so I was confused about what I was reading. Something like:

Also returns the last follow state, which is useful for write operations. It is a tuple containing the RadixOffset, the position we reached within `seq`, and the last base16 index number. So a tuple of `(r, i, b)` means `buf[r.0 + b]` points to the result `KeyId` (if returned), and `b` represents the location representing `seq.nth(i)`.
71

Why to_le here? I assumed to_le was used when we have a value in memory and we want to serialize it to little endian to send somewhere that assumes it will receive little endian (so we take our in memory form and convert it to little endian for sending). But we don't appear to be doing that in this case.

95

Should we assert that the key id bit isn't set?

117

Looks like we call to_le before putting it in the buffer, and to_le after taking it out of the buffer. Should one of those be from_le? Sounds like they do the same thing, but would be less confusing if it was symmetrical.

264

Could we do tests that check for corruption handling? Like if the process is killed mid-write, what is the expected behavior when the next process tries to read the tree?

durham requested changes to this revision.Nov 29 2017, 8:41 PM

I've made it up to radix_insert_with_key. Will finish later this evening. Throwing back in your queue for now.

rust/radixbuf/src/radix.rs
52

Ignore that second sentence. The caller has to verify the key matches, but they can't do that via sequence length checking.

125

Maybe document what the offset parameter means.

127

The above code uses RB for the radix buffer parameter. Should it be consistent here?

141

I'd document all the parameters on the public facing functions, since it's not always clear what some of these do.

154

Should we use '?' Instead of unwrap here? Like you do in prefix_lookup below? Seems like a common code path that we wouldn't want to panic in.

This revision now requires changes to proceed.Nov 29 2017, 8:41 PM
quark added inline comments.Nov 29 2017, 9:11 PM
rust/radixbuf/src/radix.rs
11

Yes. I tried u64 which removes some boundary checks but doubles the size of everything and it did introduce I/O overhead. Maybe we will need u64 one day but probably not right now.

52

Good point.

53

Yeah, this is confusing but those states do need to be shared - I didn't come up with better ideas about the interface.

Since this isn't user-facing, I didn't pay much attention to it. Will probably draw some ASCII graphs here.

71

buf is the raw mmap-ed buffer. So when we are reading or writing buf, we need to take care of endianness. I didn't pay much attention to to_le or from_le since they are the same. Will change some of them to from_le. Maybe we should use be everywhere so errors like missed a "to_be" will be caught.

95

Good idea.

117

Yes.

264

Errors like out-of-range access are covered by test_errors, which are basically what this library can provide at its best. Arbitrary data corruption (ex. some u32 is changed to 0 in a random radix node) cannot be detected. But simpler ones (ex. an offset is larger than the buffer size) can.

Data integrity is a much more complex problem so I intentionally avoided them here - the library does not even have I/O code - all it speaks are raw buffers. It's up to the upper layer to guarantee data integrity. Currently we use atomic replace and tiprev + tipnode verification.

durham added inline comments.Nov 29 2017, 9:15 PM
rust/radixbuf/src/radix.rs
247

I wonder if writing them backwards like this has any perf implication, like on cache line reads or anything.

252

Or the keys are identical but the key_id is different. Not sure if that's worth special casing.

quark added inline comments.Nov 29 2017, 9:34 PM
rust/radixbuf/src/radix.rs
247

This is more about allowing concurrent read - no bad "pointer"s are exposed. It seems like a nice property to have although we don't really depend on that right now.

I'll add a comment.

252

Yes. Will change the comment.

quark marked 19 inline comments as done.Dec 8 2017, 9:32 PM
quark updated this revision to Diff 4282.
quark added inline comments.Dec 8 2017, 9:53 PM
rust/radixbuf/src/radix.rs
95

I actually changed it a bit so RadixNode is not aligned but the offset is shifted by one when writing. This is more consistent with KeyId handling.

141

Added.

154

Good catch. I cannot recall why I used unwrap in the first place.

durham accepted this revision.Dec 14 2017, 7:16 PM
durham added inline comments.
rust/radixbuf/src/radix.rs
164

Why drop the #[inline]? Just curious

275

Why set new_key = key here? I guess the same question applies to new_key_id

307

You use from_bin(&new_key) (with the &) in the previous two call sites but not here?

This revision is now accepted and ready to land.Dec 14 2017, 7:16 PM
quark updated this revision to Diff 4450.Dec 14 2017, 9:21 PM
quark added inline comments.Dec 14 2017, 9:26 PM
rust/radixbuf/src/radix.rs
164

Jeremy's suggestion on a later diff. It's too large to inline.

275

Just make it more obvious since the following code uses new_key and old_key. So they are aligned.

307

Wrong codemod. Will remove & in previous code. Rust inserts * automatically so the previous ones become Base16Iter::from_bin(*&new_key).

quark updated this revision to Diff 4459.Dec 14 2017, 10:15 PM
This revision was automatically updated to reflect the committed changes.