Redesign Consensus Simulation Framework (RIPD-1361) #2209

bachase · 2017-08-18T14:24:53Z

This PR contains several changesets related to a redesigned consensus simulation framework (CSF) and reflects joint work between myself and @jmmcgee. Some highlights of the latest iteration of the framework:

Adds an event/collector framework for monitoring invariants and doing calculating statistics.
Allows distinct network and trust connections between Peers
Adds a simple routing strategy to support broadcasting arbitrary messages
Adds a common directed graph (Digraph) class for representing network and trust topologies
Adds a PeerGroup class for simpler specification of the trust and network topologies
Adds a LedgerOracle class to ensure distinct ledger histories and simplify branch checking
Adds a Submitter to send transactions in at fixed or random intervals to fixed or random peers

The framework design is still in its early stages and will continue to be reworked in support of ongoing simulation studies.

For reviewers, there are two main requests

Ensure the changes to generic consensus in [FOLD] Prepare for CSF redesign: 1ca12e1 are satisfactory. The changes are non-behavior changing.
Provide feedback on the design of the CSF. This is probably best done by reviewing the flattened PR and focusing on the src/test/csf directory. Initially, reviewing the brief README may provide better context for the changes.

bachase · 2017-08-18T14:27:45Z

@wilsonianb and @scottschurr I've tagged you both and would request you focus on the prepartion commit [FOLD] Prepare for CSF redesign: 1ca12e1. Reviewing the larger redesign is up to you; I'll solicit volunteers for that larger task.

codecov-io · 2017-08-18T15:07:26Z

Codecov Report

Merging #2209 into develop will increase coverage by 0.01%.
The diff coverage is 90%.

@@             Coverage Diff             @@
##           develop    #2209      +/-   ##
===========================================
+ Coverage    70.22%   70.23%   +0.01%     
===========================================
  Files          692      692              
  Lines        50961    50977      +16     
===========================================
+ Hits         35787    35804      +17     
+ Misses       15174    15173       -1

Impacted Files	Coverage Δ
src/ripple/basics/tagged_integer.h	`94.73% <ø> (-5.27%)`	⬇️
src/ripple/app/consensus/RCLCxLedger.h	`80% <ø> (ø)`	⬆️
src/ripple/app/consensus/RCLConsensus.h	`80% <ø> (ø)`	⬆️
src/ripple/consensus/LedgerTiming.h	`92.3% <100%> (-3.53%)`	⬇️
src/ripple/consensus/Validations.h	`98.47% <100%> (+0.09%)`	⬆️
src/ripple/consensus/DisputedTx.h	`97.26% <100%> (+0.03%)`	⬆️
src/ripple/app/consensus/RCLConsensus.cpp	`66.74% <25%> (+0.97%)`	⬆️
src/ripple/consensus/Consensus.h	`88.86% <90%> (-0.23%)`	⬇️
src/ripple/basics/DecayingSample.h	`77.77% <0%> (-8.34%)`	⬇️
... and 4 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 6dc79c2...ad62c13. Read the comment docs.

wilsonianb · 2017-08-21T20:47:41Z

src/test/consensus/DistributedValidatorsSim_test.cpp

+        std::chrono::milliseconds delay,
+        Generator &g)
+{
+    std::size_t const size = peers.size();


warning: unused variable 'size' [-Wunused-variable]

wilsonianb · 2017-08-21T20:48:02Z

src/test/consensus/ScaleFreeSim_test.cpp

+    SizePDF unlSizePDF,
+    Generator& g)
+{
+    std::size_t const size = peers.size();


warning: unused variable 'size' [-Wunused-variable]

See earlier assert(peers.size() == ranks.size()); suggestion. Also note there are steps 2 and 3, but not 1.

wilsonianb · 2017-08-21T22:00:26Z

src/ripple/consensus/Validations.h

+/** Determine the preferred ledger based on its support
+
+    @param current The current ledger the node follows
+    @param ledgerCounts Ledger IDs and corresponding counts of support


ledgerCounts --> dist ?

wilsonianb · 2017-08-21T22:27:55Z

src/ripple/consensus/Validations.h

+        // Or stick with ours on a tie
+        if ((it.second > netLgrCount) ||
+            ((it.second == netLgrCount) &&
+             ((it.first == current) || (it.first > netLgr))))


It looks like (it.first == current) || (it.first > netLgr) is new (previously just (it.first == current)).
Should it instead be (it.first == current) || ((it.first > netLgr) && (netLgr != current))?
As is, I think you can get a netLgr of either current or a sequence later than current (assuming they have the same count) depending of which LedgerID appears later in the hash_map.

Good catch. I agree with your suggested change.

scottschurr

Reviewing only the [FOLD] Prepare for CSF redesign commit. I left some comments and thoughts, but saw no particular problems. Looks good. 👍

scottschurr · 2017-08-22T19:25:51Z

docs/consensus.qbk

@@ -458,10 +458,12 @@ struct Ledger
 {


The document contains a few references to the "Ripple network" and "Ripple Consensus Ledger". I'm wondering if those should be changed to "XRP Ledger"? Possibly a marketing or @mDuo13 question...

The references to "Ripple network" and "Ripple Consensus Ledger" are still in the document. @mDuo13, is it important to address this? Or should we let it slide for now?

scottschurr · 2017-08-22T21:50:11Z

src/ripple/consensus/Validations.h

+        // Or stick with ours on a tie
+        if ((it.second > netLgrCount) ||
+            ((it.second == netLgrCount) &&
+             ((it.first == current) || (it.first > netLgr))))


This if condition is slightly different from the original inline code it replaces in RCLConsensus.cpp. I'm unsure whether that difference is intentional, so I thought I'd just call it out. The replacement is not quite a simple refactor...

scottschurr · 2017-08-22T21:56:10Z

src/ripple/app/consensus/RCLConsensus.cpp

@@ -147,7 +147,7 @@ RCLConsensus::Adaptor::relay(RCLCxPeerPos const& peerPos)
 }

 void
-RCLConsensus::Adaptor::relay(RCLCxTx const& tx)
+RCLConsensus::Adaptor::share(RCLCxTx const& tx)
 {
    // If we didn't relay this transaction recently, relay it to all peers


Do you still want to say "relay" in this comment? Or should it say "share"?

Also, there are a few uses of "relay" in RCLValidations.cpp and one in RCLValidations.h. Do you want to change those to "share" as well?

I don't feel strongly on this, just asking...

I went with share in the generic context and left relay in the ripple specific implementation (RCL*). The thought is that the generic version can use a variety of routing strategies to send messages in support of the consensus algorithm, so relay was too specific. However, since rippled's overlay and hashrouter use relay, I stuck with that name.

I agree that having two names is not ideal, but I felt the generic vs concrete boundary was an acceptable spot to diverge.

scottschurr · 2017-08-22T22:18:43Z

src/ripple/app/consensus/RCLCxLedger.h

@@ -37,6 +37,8 @@ class RCLCxLedger
 public:
    //! Unique identifier of a ledger
    using ID = LedgerHash;
+    //! Sequence number of a ledger
+    using Seq = LedgerIndex;


Do you eventually intend to change LedgerMaster to use Seq instead of LedgerIndex? Not insisting, just curious.

Potentially. LedgerMaster and NetworkOps still have functionality that is related to consensus that should arguably be moved to the generic implementation and that might warrant the change.

scottschurr · 2017-08-22T22:19:33Z

src/ripple/app/consensus/RCLCxLedger.h

@@ -55,28 +57,28 @@ class RCLCxLedger
    }

    //! Sequence number of the ledger.
-    auto const&
+    Seq const&


👍 for explicit return types!

scottschurr · 2017-08-22T22:30:52Z

src/ripple/consensus/Consensus.h

@@ -874,7 +875,7 @@ Consensus<Adaptor>::getJson(bool full) const
    if (mode_.get() != ConsensusMode::wrongLedger)
    {
        ret["synched"] = true;
-        ret["ledger_seq"] = previousLedger_.seq() + 1;
+        ret["ledger_seq"] = static_cast<std::uint32_t>(previousLedger_.seq())+ 1;


I'm seeing a couple of these static_cast<>s. That's fine, but you might consider adding a method named, say, seqAsUInt() to your Ledger_t implementations. That would keep the static_cast<> inside the class responsible for supplying the data. Just a thought.

I'm going to leave as is for now since it is just for JSON/debug support. I intend (eventually) to revisit how that is done in the generic code.

scottschurr · 2017-08-22T23:03:11Z

src/ripple/consensus/Validations.h

@@ -192,6 +222,7 @@ class Validations
        decay_result_t<decltype (&Validation::ledgerID)(Validation)>;
    using NodeKey = decay_result_t<decltype (&Validation::key)(Validation)>;
    using NodeID = decay_result_t<decltype (&Validation::nodeID)(Validation)>;


RCLConsensus.h is using NodeID_t instead of NodeID. Is it worth making that consistent? So, for example SeqType would be Seq_t? Just for your consideration. Personally, I really like it when a given type retains the same name for most or all of the code base. That makes it way easier to grep for instances. It's nice when it works that way, but it's hard to enforce.

Yes, I should revisit this. Two follow-ups

Is the decay_result_t style acceptable? Or do you prefer the explicit using style?

If its the latter, I added the _t suffix because NodeID is an existing ripple type, so wasn't sure how to define an alias using NodeID = NodeID?

I'm completely fine with the decay_result_t style. If you want to use the explicit using style, consider

using NodeID = ripple::NodeID;

I believe you can also use

using NodeID = NodeID;

but you'll leave your readers a bit puzzled about what you're up to...

wilsonianb · 2017-08-23T18:11:04Z

src/ripple/app/consensus/RCLConsensus.h

-        using TxSet_t = RCLTxSet;
-        using PeerPosition_t = RCLCxPeerPos;
+        using Ledger = RCLCxLedger;
+        using NodeID = ripple::NodeID;


error: declaration of 'using NodeID = using NodeID = class ripple::base_uint<160ul, ripple::detail::NodeIDTag>' [-fpermissive] using NodeID = ripple::NodeID;

Sigh. Windows was happy at least.

Bummer. Clang on macOS was okay with it too. Sorry for the misdirection.

No worries. I'll just drop that change for now and revisit separately.

bachase · 2017-08-23T18:17:19Z

Force pushed and dropped 51098cf

bachase · 2017-08-29T14:52:26Z

The last commit fixes a bug in the simulation framework uncovered in other simulations that are not part of this review.

bachase · 2017-09-05T13:41:38Z

Rebased on 0.80.0-rc2

scottschurr

Sorry this review took so long. There is a lot of code here! I'm not convinced my particular review really brought much of value, but I noted a few things you might choose to look at. Interesting stuff.

scottschurr · 2017-08-25T20:08:26Z

src/test/csf/README.md

+describing, running and analyzing simulations of the consensus algorithm in a
+controlled manner. It is also used to unit test the generic Ripple consensus
+algorithm implementation. The framework is in its early stages, so the design
+and supported features is subject to change.


micro nit: is -> are?

scottschurr · 2017-08-25T21:05:19Z

src/test/csf/README.md

+each `Peer` has closed one additional ledger.  After closing the additional
+ledger, the `Peer` stops participating in consensus.  The first call is used to
+ensure a more useful prior state of all `Peer`s. After the transaction
+submission, the second call to `run` results in additional ledger that accepts


sub-nit: in "one" or "an" additional...?

scottschurr · 2017-08-25T22:07:14Z

src/ripple/consensus/LedgerTiming.h

@@ -63,14 +63,14 @@ auto constexpr decreaseLedgerTimeResolutionEvery = 1;
    @pre previousResolution must be a valid bin
         from @ref ledgerPossibleTimeResolutions
 */
-template <class duration>
+template <class duration, class seq>


I usually expect types to have initial caps in our code base. So I'd expect to see class Duration, class Seq. I think that change might make the code inside the body a bit easier to read. Just a thought, not a requirement.

scottschurr · 2017-08-25T22:12:50Z

src/ripple/consensus/LedgerTiming.h

 {
-    assert(ledgerSeq);
+    assert(ledgerSeq != seq{0});


The requirements on type seq are not very clear. It looks like it should be integral, and ledgerSeq certainly suggests it should be integral. But if, right here, I insert...

static_assert (std::is_integral<seq>::value, "");

The static_assert fails from an instantiation based here: src/test/csf/Peer.h:818

consensus.timerEntry(now());

Maybe this is expected? Would like to know what you think...

It is basically integral, but it also supports tagged_integer types which aren't exactly integral. I could try adding a concept check if you find that useful, but will at least add some comments.

Comments will be good.

scottschurr · 2017-08-25T23:21:31Z

src/test/consensus/ByzantineFailureSim_test.cpp

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


Isn't the "Inc" supposed to end with a period? I think a global replace went awry.

Yikes. Sorry and thanks for catching the aftermath!

scottschurr · 2017-09-06T22:02:50Z

src/test/csf/ledgers.h

+        //! When the ledger closed (up to closeTimeResolution)
+        NetClock::time_point closeTime;
+
+        //! Whether consenssus agreed on the close time


consenssus -> consensus?

scottschurr · 2017-09-06T22:34:29Z

src/test/csf/random.h

+    return res;
+}
+
+/** Invokable that returns random samples from a range according to a discrete


I think that C++ is drifting toward the spelling "invocable" instead of "invokable".

scottschurr · 2017-09-06T22:37:16Z

src/test/csf/submitters.h

+namespace test {
+namespace csf {
+
+// Submitters are class for simulating submission of transactions to the network


class -> classes?

scottschurr · 2017-09-06T22:38:04Z

src/test/csf/submitters.h

+    to succesive calls of distribution(), until stop.
+
+    @tparam Distribution is a `UniformRandomBitGenerator` from the STL that
+            is usesd by random distributions to generate random samples


usesd -> used?

scottschurr · 2017-09-06T22:39:03Z

src/test/csf/submitters.h

+
+    @tparam Distribution is a `UniformRandomBitGenerator` from the STL that
+            is usesd by random distributions to generate random samples
+    @tparam Generator is a object with member


HowardHinnant

I reviewed the last commit in detail, and tested out the entire P/R. All looks good!

scottschurr

Tagged a few more nits, but nothing that needs to be addressed. 👍

scottschurr · 2017-09-14T17:02:46Z

docs/consensus.qbk

@@ -458,10 +458,12 @@ struct Ledger
 {


The references to "Ripple network" and "Ripple Consensus Ledger" are still in the document. @mDuo13, is it important to address this? Or should we let it slide for now?

scottschurr · 2017-09-14T17:12:47Z

src/ripple/consensus/LedgerTiming.h

@@ -62,15 +61,22 @@ auto constexpr decreaseLedgerTimeResolutionEvery = 1;

    @pre previousResolution must be a valid bin
         from @ref ledgerPossibleTimeResolutions
+
+    @tparam Rep Type representing number of ticks in std::chrono::duration
+    @tparam Period An std::ratioe representing tick period in


ratioe -> ratio?

scottschurr · 2017-09-14T17:13:47Z

src/ripple/consensus/LedgerTiming.h

+                   std::chrono::duration
+    @tparam Seq Unsigned integer-like type corresponding to the ledger sequence
+                number. It should be comparable to 0 and support modular
+                division. Built-in and tagged_integers are supported.


That last sentence really helps. Thanks.

scottschurr · 2017-09-14T17:24:30Z

src/test/consensus/ByzantineFailureSim_test.cpp

+        // an extra non-consensus transaction).
+
+        Sim sim;
+        ConsensusParms parms;


I'm guessing this should be const?

scottschurr · 2017-09-14T17:46:37Z

src/test/consensus/Consensus_test.cpp

+
+            PeerGroup network = loner + clique;
+            network.connect(
+                network, round<milliseconds>(0.2 * parms.ledgerGRANULARITY));


I'm not looking too closely, but I suspect the need for the round is because:

parts.ledgerGranularity == 1 sec (double) 0.2 * 1 sec produces (double) 0.2 sec round<milliseconds>(0.2 sec) produces 200 milliseconds

If that's correct you could probably get away from the round call by

declaring parts.ledgerGRANULARITY as 1000 milliseconds (represented internally as 1000), and

instead of multiply by 0.2, divide by 5, so you stay in the integer world.

Then I think you should automatically get 200 milliseconds without the round call.

scottschurr · 2017-09-14T17:59:27Z

src/test/csf/random.h

+/** Generate a vector of random samples
+
+    @param size the size of the sample
+    @param pdf the distribution to sample


You were considering changing pdf (Probability Distribution Function or Portable Document Format) to rnd (Random Number Distribution). I like rnd and RND much better than pdf and PDF. Is that change still in the cards?

scottschurr · 2017-09-14T18:16:42Z

src/test/consensus/DistributedValidatorsSim_test.cpp

+        argStream >> maxNumValidators;
+        argStream >> delayCount;
+
+        std::chrono::milliseconds delay(delayCount);


I think these three locals can still be const.

scottschurr · 2017-09-14T18:33:18Z

src/test/csf/Digraph.h

+
+/** Directed graph
+
+Basic directed graph that uses an adjacency lists to represent out edges.


lists -> list?

scottschurr · 2017-09-14T18:47:17Z

src/test/csf/Scheduler.h

+            The clock is advanced to the time
+            of the last delivered event.
+
+        @return `true` if a event was processed.


Could still be changed to an event...

mellery451

minor comments - LGTM

mellery451 · 2017-09-20T19:41:28Z

src/test/csf/Digraph.h

+    */
+    template <class VertexName>
+    void
+    saveDot(std::ostream & out, VertexName&& vertexName) const


not to over-engineer it, but couldn't this instead be defined as an ostream operator?

I wasn't sure how to do that conveniently and allow determining how to represent the vertex name at the call-site> I could try wrapping instead, but this seemed good enough for now.

mellery451 · 2017-09-20T23:03:12Z

src/test/consensus/ByzantineFailureSim_test.cpp

+        std::cout << "Fully synchronized: " << std::boolalpha
+                  << sim.synchronized() << "\n";
+    }
+};


It looks like this test doesn't actually have any assertions, so the test runner aborts at the end. Maybe add a pass() or some other trivial assertion ?

bachase · 2017-09-26T13:23:20Z

Rebased on 0.80.0-rc3

bachase · 2017-10-25T14:03:29Z

Rebased on 0.80.0, squashed and marking as passed.

- Separate `Scheduler` from `BasicNetwork`. - Add an event/collector framework for monitoring invariants and calculating statistics. - Allow distinct network and trust connections between Peers. - Add a simple routing strategy to support broadcasting arbitrary messages. - Add a common directed graph (`Digraph`) class for representing network and trust topologies. - Add a `PeerGroup` class for simpler specification of the trust and network topologies. - Add a `LedgerOracle` class to ensure distinct ledger histories and simplify branch checking. - Add a `Submitter` to send transactions in at fixed or random intervals to fixed or random peers. Co-authored-by: Joseph McGee

bachase · 2017-11-30T22:21:24Z

Rebased on 0.80.1

seelabs · 2017-12-01T20:33:32Z

In 0.90.0-b1

bachase requested review from wilsonianb and scottschurr August 18, 2017 14:26

bachase assigned wilsonianb and scottschurr Aug 18, 2017

wilsonianb reviewed Aug 22, 2017

View reviewed changes

scottschurr approved these changes Aug 22, 2017

View reviewed changes

wilsonianb reviewed Aug 23, 2017

View reviewed changes

bachase force-pushed the consensus-sim-flatten branch from 51098cf to ea0fe89 Compare August 23, 2017 18:16

bachase force-pushed the consensus-sim-flatten branch from 1d946c3 to 53d4bda Compare September 5, 2017 13:41

bachase force-pushed the consensus-sim-flatten branch from 53d4bda to 73dba2e Compare September 5, 2017 15:31

bachase mentioned this pull request Sep 6, 2017

Use rounded close time in Consensus (RIPD-1528) #2221

Closed

scottschurr reviewed Sep 6, 2017

View reviewed changes

bachase requested review from mellery451, nbougalis and HowardHinnant September 13, 2017 18:50

bachase assigned mellery451, nbougalis and HowardHinnant and unassigned wilsonianb Sep 13, 2017

HowardHinnant approved these changes Sep 13, 2017

View reviewed changes

scottschurr approved these changes Sep 14, 2017

View reviewed changes

mellery451 approved these changes Sep 20, 2017

View reviewed changes

bachase force-pushed the consensus-sim-flatten branch from 8bc1c62 to 212bd2d Compare September 26, 2017 12:20

bachase force-pushed the consensus-sim-flatten branch from 212bd2d to 59f28e6 Compare October 25, 2017 14:02

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

bachase removed the Passed Passed code review & PR owner thinks it's ready to merge. Perf sign-off may still be required. label Nov 2, 2017

bachase force-pushed the consensus-sim-flatten branch from 59f28e6 to ad62c13 Compare November 30, 2017 22:14

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

seelabs closed this Dec 1, 2017


		/** Directed graph

		Basic directed graph that uses an adjacency lists to represent out edges.

Redesign Consensus Simulation Framework (RIPD-1361) #2209

Redesign Consensus Simulation Framework (RIPD-1361) #2209

Conversation

bachase commented Aug 18, 2017 • edited Loading

bachase commented Aug 18, 2017

codecov-io commented Aug 18, 2017 • edited Loading

Codecov Report

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

Choose a reason for hiding this comment

scottschurr 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

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

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

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

bachase commented Aug 23, 2017

bachase commented Aug 29, 2017

bachase commented Sep 5, 2017

scottschurr 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

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

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

HowardHinnant left a comment

Choose a reason for hiding this comment

scottschurr 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

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

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

bachase commented Sep 26, 2017

bachase commented Oct 25, 2017

bachase commented Nov 30, 2017

seelabs commented Dec 1, 2017

bachase commented Aug 18, 2017 •

edited

Loading

codecov-io commented Aug 18, 2017 •

edited

Loading