README
¶
Insanely Scalable SMR (ISS)
ISS is the first modular algorithm to make leader-driven total order broadcast scale in a robust way, published in March 2022. At its interface, ISS is a classic state machine replication (SMR) system that establishes a total order of client transactions with typical liveness and safety properties, applicable to any replicated service, such as resilient databases or a blockchain ordering layer. It is a further development and a successor of the Mir-BFT protocol (not to be confused with the Mir library used to implement ISS, see the description of Mir).
ISS achieves scalability without requiring a primary node to periodically decide on the protocol configuration. It multiplexes multiple instances of a leader-driven consensus protocol which operate concurrently and (almost) independently. We abstract away the logic of the used consensus protocol and only define an interface - that we call "Sequenced Broadcast" (SB) - that such a consensus protocol must use to interact with ISS.
ISS maintains a contiguous log of (batches of) client transactions at each node. Each position in the log corresponds to a unique sequence number and ISS agrees on the assignment of a unique request batch to each sequence number. Our goal is to introduce as much parallelism as possible in assigning batches to sequence numbers while avoiding request duplication, i.e., assigning the same request to more than one sequence number. To this end, ISS subdivides the log into non-overlapping segments. Each segment, representing a subset of the log's sequence numbers, corresponds to an independent consensus protocol instance that has its own leader and executes concurrently with other instances.
To prevent the leaders of two different segments from concurrently proposing the same request, and thus wasting resources, while also preventing malicious leaders from censoring (i.e., not proposing) certain transactions, we adopt and generalize the partitioning of the request space introduced by Mir-BFT. At any point in time, ISS assigns a different subset of client transactions (that we call a bucket) to each segment. ISS periodically changes this assignment, such that each request is guaranteed to eventually be assigned to a segment with a correct leader.
The figure below shows the high-level architecture of the ISS protocol.
Documentation
¶
Overview ¶
Package iss contains the implementation of the ISS protocol, the new generation of Mir. For the details of the protocol, see README.md in this directory. To use ISS, instantiate it by calling `iss.New` and use it as the Protocol module when instantiating a mir.Node. A default configuration (to pass, among other arguments, to `iss.New`) can be obtained from `issutil.DefaultParams`.
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func InitialStateSnapshot ¶
func InitialStateSnapshot( appState []byte, params *issconfig.ModuleParams, ) (*trantorpbtypes.StateSnapshot, error)
InitialStateSnapshot creates and returns a default initial snapshot that can be used to instantiate ISS. The created snapshot corresponds to epoch 0, without any committed transactions, and with the initial membership (found in params and used for epoch 0) repeated for all the params.ConfigOffset following epochs.
func New ¶
func New( ownID t.NodeID, moduleConfig ModuleConfig, params *issconfig.ModuleParams, startingChkp *checkpoint.StableCheckpoint, hashImpl crypto.HashImpl, chkpVerifier checkpoint.Verifier, logger logging.Logger, ) (modules.PassiveModule, error)
New returns a new initialized instance of the ISS protocol module to be used when instantiating a mir.Node.
Types ¶
type CommitLogEntry ¶
type CommitLogEntry struct {
// Sequence number at which this entry has been ordered.
Sn tt.SeqNr
// The delivered availability certificate data.
// TODO: Replace by actual certificate when deterministic serialization of certificates is implemented.
CertData []byte
// The digest (hash) of the entry.
Digest []byte
// A flag indicating whether this entry is an actual certificate (false)
// or whether the orderer delivered a special abort value (true).
Aborted bool
// In case Aborted is true, this field indicates the ID of the node
// that is suspected to be the reason for the orderer aborting (usually the leader).
// This information can be used by the leader selection policy at epoch transition.
Suspect t.NodeID
}
The CommitLogEntry type represents an entry of the commit log, the final output of the ordering process. Whenever an orderer delivers an availability certificate (or a special abort value), it is inserted to the commit log in form of a commitLogEntry.
type ISS ¶
type ISS struct {
// The ISS configuration parameters (e.g. Segment length, proposal frequency etc...)
// passed to New() when creating an ISS protocol instance.
Params *issconfig.ModuleParams
// The logic for selecting leader nodes in each epoch.
// For details see the documentation of the LeaderSelectionPolicy type.
// ATTENTION: The leader selection policy is stateful!
// Must not be nil.
LeaderPolicy lsp.LeaderSelectionPolicy
// contains filtered or unexported fields
}
The ISS type represents the ISS protocol module to be used when instantiating a node. The type should not be instantiated directly, but only properly initialized values returned from the New() function should be used.
type ModuleConfig ¶
type ModuleConfig struct {
Self t.ModuleID
App t.ModuleID
Availability t.ModuleID
BatchDB t.ModuleID
Checkpoint t.ModuleID
ChkpValidator t.ModuleID
Net t.ModuleID
Ordering t.ModuleID
PPrepValidator t.ModuleID
PPrepValidatorChkp t.ModuleID
Timer t.ModuleID
}
ModuleConfig contains the names of modules ISS depends on. The corresponding modules are expected by ISS to be stored under these keys by the Node.
Source Files
Directories