# Ordering

* [Ordering definition](#ordering-definition)
  * [Ordering across partition](#ordering-across-partition)
* [Flowchart for ordering guarantee within business domain](#flowchart-for-ordering-guarantee-within-business-domain)
  * [Cons - Uneven data distribution](#cons---uneven-data-distribution)
    * [Slot allocation](#slot-allocation)
    * [Consistent hashing](#consistent-hashing)
  * [Cons - Message disorder due to resizing](#cons---message-disorder-due-to-resizing)
    * [Problem](#problem)
    * [Solution](#solution)

## Ordering definition

* If the msg producing order is the same with msg consuming order, then msgs are in order.
  * The msg producing order is the order when msg arrives at broker.

![](https://1010073591-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-Mk8dv8Mfudl_6ziUzDf%2Fuploads%2Fgit-blob-5ca6754cdda2d99407a5f46c369990ef47e0d604%2FmessageQueue_ordering.png?alt=media)

### Ordering across partition

* For Kafka, it could not guarantee the order across different partitions.
* Cross-partition ordering would typically need a role for coordinator.
  1. Suppose msg1 is produced before msg2 but msg2 arrives at consumer before msg1
  2. Then the coordinator needs to hold msg2 until msg1 is consumed.

## Flowchart for ordering guarantee within business domain

![](https://1010073591-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-Mk8dv8Mfudl_6ziUzDf%2Fuploads%2Fgit-blob-8cce7491a3c54ce799e3103437bff63714f6dc49%2FmessageQueue_ordering_flowchart.png?alt=media)

### Cons - Uneven data distribution

#### Slot allocation

* Steps
  1. Calculate a hashing value according to the business key.
  2. Calculate a slot index according to hashing\_value % slot\_num.
  3. Decide the mapping between slot and partition based on load.
* The mapping between slot and partition could be stored inside service registry.
* Redis uses 16385 slots, and the number of slots could be decided based on business cases.

![](https://1010073591-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-Mk8dv8Mfudl_6ziUzDf%2Fuploads%2Fgit-blob-9d37cfcfea23b31f19d85b258094fe587f2a5c61%2FmessageQueue_ordering_slot_allocation.png?alt=media)

#### Consistent hashing

* Adjust the partition allocation on ring for data distribution.

![](https://1010073591-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-Mk8dv8Mfudl_6ziUzDf%2Fuploads%2Fgit-blob-3a9403ebbdb585975a16de086916f9463b2357dc%2FmessageQueue_ordering_consistentHashing.png?alt=media)

### Cons - Message disorder due to resizing

#### Problem

* For example, message id = 3 and id = 7 will land on the same partition after resizing.
* However, when there are many backlogs on partition 0 for id = 3 and there is no backlog on partition 3 for id = 7 due to resizing, then id = 7 will be consumed before id = 3.

![](https://1010073591-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-Mk8dv8Mfudl_6ziUzDf%2Fuploads%2Fgit-blob-0570ee266d41497206e221c12f1e9dc7157ca8c4%2FmessageQueue_ordering_resizing.png?alt=media)

#### Solution

* For all new partitions, wait for certain period which is long enough for old backlog messages to be consumed.
