Improve directory insertion & deletion (RIPD-1353, RIPD-1488) #2165

nbougalis · 2017-07-09T07:53:18Z

This commit introduces the SortedDirectories amendment, which addresses two distinct issues:

First, it corrects a technical flaw that could, in some edge cases, prevent an empty intermediate page from being deleted.

Second, it sorts directory entries within a page (other than order book page entries, which remain strictly FIFO). This makes insert operations deterministic, instead of pseudo-random and reliant on temporal ordering.

Lastly, it removes the ability to perform a "soft delete" where the page number of the item to delete need not be known if the item is in the first 20 pages, and enforces a maximum limit to the number of pages that a directory can span.

miguelportilla · 2017-07-10T13:18:02Z

src/ripple/app/ledger/impl/ApplyView.cpp

+    }
+
+    // Check whether we're out of pages.
+    if (++page == dirNodeMaxPages)


Should this be ++page > dirNodeMaxPages ?

No, since pages are zero-based. But I guess making it >= dirNodeMaxPages is a good idea anyways. There's no directory with that many pages, but using >= will do the right thing if there were..

miguelportilla · 2017-07-10T13:18:53Z

src/ripple/protocol/Protocol.h

@@ -59,4 +62,4 @@ using TxSeq = std::uint32_t;

 } // ripple

-#endif
+#endif


sublimator · 2017-07-10T13:19:21Z

Finally!

ximinez · 2017-07-10T15:54:04Z

The non-unity builds are failing:

/home/travis/build/ripple/rippled/src/test/ledger/Directory_test.cpp: In member function ‘void ripple::test::Directory_test::testDirectoryOrdering()’:

/home/travis/build/ripple/rippled/src/test/ledger/Directory_test.cpp:161:48: error: ‘BookDirs’ was not declared in this scope

                 Book({xrpIssue(), USD.issue()}));

                                                ^

/home/travis/build/ripple/rippled/src/test/ledger/Directory_test.cpp:164:38: error: unable to deduce ‘auto&&’ from ‘book’

             for (auto const& offer : book)

mellery451

👍

mellery451 · 2017-07-10T15:11:13Z

src/ripple/app/ledger/impl/ApplyView.cpp

+//------------------------------------------------------------------------------
+/*
+    This file is part of rippled: https://github.com/ripple/rippled
+    Copyright (c) 2012, 2013 Ripple Labs Inc.


consider updating the date ?

mellery451 · 2017-07-10T17:26:13Z

src/ripple/ledger/ApplyView.h

+
+     @param directory the base of the directory
+     @param key the entry to insert
+     @param strictOrder keep entries in order of insertion


I was slightly confused by the name of this parameter - "strict" could mean a number of things. Maybe "preserveOrder" is closer to the intent? Just a suggestion - I'm ok with name as is, since the doc here is clear.

This function is actually giving me heartburn. I dislike functions that take a bool and implement two different kinds of behavior based on that. Very error prone.

I seriously considered having two functions. Something like this:

boost::optional<std::uint64_t> ApplyView::dirInsertSorted ( Keylet const& directory, uint256 const& key, std::function<void (std::shared_ptr<SLE> const&)> describe) { // dirInsert is a private function: return dirInsert (directory, key, describe, [](STVector256& indexes, uint256 const& key) { // We can't be sure if this page is already sorted because // it may be a legacy page we haven't yet touched. Take // the time to sort it. std::sort (indexes.begin(), indexes.end()); auto pos = std::lower_bound(indexes.begin(), indexes.end(), key); if (pos != indexes.end() && key == *pos) LogicError ("dirInsert: double insertion"); indexes.insert (pos, key); }); } boost::optional<std::uint64_t> ApplyView::dirInsertUnsorted ( Keylet const& directory, uint256 const& key, std::function<void (std::shared_ptr<SLE> const&)> describe) { // dirInsert is a private function: return dirInsert (directory, key, describe, [](STVector256& indexes, uint256 const& key) { if (std::find(indexes.begin(), indexes.end(), key) != indexes.end()) LogicError ("dirInsert: double insertion"); indexes.push_back(key); } }

I like this. Perhaps a better name for dirInsertUnsorted would be dirAppend?

codecov-io · 2017-07-10T18:42:27Z

Codecov Report

Merging #2165 into develop will decrease coverage by 0.06%.
The diff coverage is 82.84%.

@@             Coverage Diff             @@
##           develop    #2165      +/-   ##
===========================================
- Coverage    69.48%   69.42%   -0.07%     
===========================================
  Files          685      686       +1     
  Lines        50520    50644     +124     
===========================================
+ Hits         35105    35159      +54     
- Misses       15415    15485      +70

Impacted Files	Coverage Δ
src/ripple/protocol/Feature.h	`100% <ø> (ø)`	⬆️
src/ripple/ledger/View.h	`100% <ø> (ø)`	⬆️
src/ripple/app/main/Amendments.cpp	`100% <ø> (ø)`	⬆️
src/ripple/protocol/impl/STTx.cpp	`81.46% <100%> (ø)`	⬆️
src/ripple/ledger/ApplyView.h	`100% <100%> (ø)`	⬆️
src/ripple/app/tx/impl/CancelTicket.cpp	`100% <100%> (ø)`	⬆️
src/ripple/protocol/STVector256.h	`100% <100%> (ø)`	⬆️
src/ripple/protocol/impl/Feature.cpp	`94.33% <100%> (+0.1%)`	⬆️
src/ripple/app/tx/impl/Transactor.cpp	`81.46% <33.33%> (+0.25%)`	⬆️
src/ripple/ledger/impl/ApplyView.cpp	`79.13% <79.13%> (ø)`
... and 11 more

Continue to review full report at Codecov.

Legend - Click here to learn more
Δ = absolute <relative> (impact), ø = not affected, ? = missing data
Powered by Codecov. Last update 87742a5...3bb42ac. Read the comment docs.

seelabs

Left some nits

seelabs · 2017-07-12T14:55:13Z

src/ripple/app/ledger/impl/ApplyView.cpp

+    Keylet const& directory,
+    uint256 const& key,
+    bool strictOrder,
+    std::function<void (std::shared_ptr<SLE> const&)> describe)


describe should be passed by const&

seelabs · 2017-07-12T14:55:25Z

src/ripple/app/ledger/impl/ApplyView.cpp

+    Keylet const& directory,
+    Keylet const& key,
+    bool strictOrder,
+    std::function<void (std::shared_ptr<SLE> const&)> describe)


describe should be passed by const&

seelabs · 2017-07-12T15:02:24Z

src/ripple/protocol/STVector256.h

+    std::vector<uint256>::iterator
+    insert(std::vector<uint256>::const_iterator pos, uint256&& value)
+    {
+        return mValue.insert(pos, value);


uint256 is not move friendly, so I don't think we need this function. However, if we do want to keep it, we should still std::move(value) here.

I'd rather keep it, ~~for when~~ in case we make base_uint move-friendly.

This commit introduces the "SortedDirectories" amendment, which addresses two distinct issues: First, it corrects a technical flaw that could, in some edge cases, prevent an empty intermediate page from being deleted. Second, it sorts directory entries within a page (other than order book page entries, which remain strictly FIFO). This makes insert operations deterministic, instead of pseudo-random and reliant on temporal ordering. Lastly, it removes the ability to perform a "soft delete" where the page number of the item to delete need not be known if the item is in the first 20 pages, and enforces a maximum limit to the number of pages that a directory can span.

seelabs

Unit tests are failing. I took a look at the first one, and it looks like a problem in the unit test, rather than this code, but those need to be resolved. You might consider asking the people who originally wrote the now failing tests to resolve the failures.

seelabs · 2017-07-17T17:29:47Z

src/ripple/ledger/impl/View.cpp

    Keylet const&                           dir,
    uint256 const&                          uLedgerIndex,
+    bool                                    strictOrder,
    std::function<void (SLE::ref)>          fDescriber,
    beast::Journal j)


We should consider splitting dirAdd into dirAppend and dirInsert as well. I don't like that the high-level interface still has the bool parameter, while the lower level one is actually cleaner. I'd have less objection if it were the other way around (i.e. a high level function then sets the correct flags to a lower level function).

There are two dirAdd functions:

The existing legacy, free function, which this PR deprecates and which will be removed after the amendment activates. I had to insert the bool parameter to it, temporarily, but the function is going away.

The new low-level dirAdd function (which is private to the class) and accepts a lambda for the insertion strategy. Users only invoke ApplyView::dirInsert or ApplyView::dirAppend.

seelabs · 2017-07-17T17:41:05Z

src/ripple/ledger/impl/ApplyView.cpp

+                LogicError ("dirInsert: double insertion");
+
+            v.insert (pos, k);
+        });


I think the low level, private dirAdd should just have a bool (or better, an enum, but bool is fine), and we should just embed this code into the main low-level function. There isn't a need for dirAdd to be as generic as it is. We really only need the two options. And inlining the code makes is easier to understand dirAdd

One more quick note on this: If you want to keep the std::function<void(STVector256&, uint256 const&)> const& add parameter on dirAdd, consider making it a template instead of a std::function. Rational: using std::function incurs a virtual function call, and may require allocation (though since our lambdas don't have captures, unlikely in our cases). Since it's private, and only called from the cpp, we can easily declare it in the header and define it in the cpp.

seelabs · 2017-07-20T14:43:49Z

👍

JoelKatz

👍

seelabs · 2017-07-31T22:52:01Z

In 0.80.0-b4

nbougalis requested review from mellery451, JoelKatz and seelabs July 9, 2017 07:53

miguelportilla reviewed Jul 10, 2017

View reviewed changes

mellery451 approved these changes Jul 10, 2017

View reviewed changes

seelabs reviewed Jul 12, 2017

View reviewed changes

nbougalis added 7 commits July 15, 2017 14:05

Make code self-documenting by using symbolic constants

228c13e

[FOLD] Tighten page limit check

f809f48

[FOLD] Move files into the correct directories

984b320

[FOLD] Don't use a bool to control sorting in dirInsert

158d1f2

[FOLD] Address review comments & fix rebase buglet

f225bcf

[FOLD] Update vcxproj file

ea339fa

seelabs suggested changes Jul 17, 2017

View reviewed changes

nbougalis added 2 commits July 17, 2017 12:13

[FOLD] Don't use lambdas for dirAdd

30c8214

[FOLD] Fix unit tests to account for new ordering

3bb42ac

seelabs approved these changes Jul 20, 2017

View reviewed changes

seelabs added Passed Passed code review & PR owner thinks it's ready to merge. Perf sign-off may still be required. and removed Passed Passed code review & PR owner thinks it's ready to merge. Perf sign-off may still be required. labels Jul 20, 2017

JoelKatz approved these changes Jul 31, 2017

View reviewed changes

seelabs added the Passed Passed code review & PR owner thinks it's ready to merge. Perf sign-off may still be required. label Jul 31, 2017

seelabs closed this Jul 31, 2017

nbougalis deleted the ripd1488 branch March 22, 2018 03:29

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Improve directory insertion & deletion (RIPD-1353, RIPD-1488) #2165

Improve directory insertion & deletion (RIPD-1353, RIPD-1488) #2165

nbougalis commented Jul 9, 2017 •

edited

Loading

miguelportilla Jul 10, 2017

nbougalis Jul 10, 2017

miguelportilla Jul 10, 2017

sublimator commented Jul 10, 2017 via email

ximinez commented Jul 10, 2017

mellery451 left a comment

mellery451 Jul 10, 2017

mellery451 Jul 10, 2017

nbougalis Jul 10, 2017

scottschurr Jul 10, 2017

codecov-io commented Jul 10, 2017 •

edited

Loading

seelabs left a comment

seelabs Jul 12, 2017

seelabs Jul 12, 2017

seelabs Jul 12, 2017

nbougalis Jul 15, 2017 •

edited

Loading

seelabs left a comment

seelabs Jul 17, 2017

nbougalis Jul 17, 2017 •

edited

Loading

seelabs Jul 17, 2017

seelabs Jul 17, 2017

seelabs commented Jul 20, 2017

JoelKatz left a comment

seelabs commented Jul 31, 2017

Improve directory insertion & deletion (RIPD-1353, RIPD-1488) #2165

Improve directory insertion & deletion (RIPD-1353, RIPD-1488) #2165

Conversation

nbougalis commented Jul 9, 2017 • edited Loading

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

sublimator commented Jul 10, 2017 via email

ximinez commented Jul 10, 2017

mellery451 left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

codecov-io commented Jul 10, 2017 • edited Loading

Codecov Report

seelabs left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

nbougalis Jul 15, 2017 • edited Loading

Choose a reason for hiding this comment

seelabs left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

nbougalis Jul 17, 2017 • edited Loading

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

seelabs commented Jul 20, 2017

JoelKatz left a comment

Choose a reason for hiding this comment

seelabs commented Jul 31, 2017

nbougalis commented Jul 9, 2017 •

edited

Loading

codecov-io commented Jul 10, 2017 •

edited

Loading

nbougalis Jul 15, 2017 •

edited

Loading

nbougalis Jul 17, 2017 •

edited

Loading