In a score-ordered set, where does the ordering come from, and what does it turn into a read instead of a sort?
answer
- the caller brings the number
- order is maintained at write time
- position is a read, not a sort
- rank read, range read, trim
- re-writing a member moves it
basics
~20 sThe caller supplies a number - the ordering score - with every member, and the store keeps the members arranged by it as they are written. Position then becomes a read: the rank of one member, or a slice by position or by score band.
solid answer
~50 sA score-ordered set holds members under one key, each written together with a number the caller computes and passes in. The store places the member by that number at write time and keeps the whole collection in that order, so the caller can ask for one member's rank, for a slice of positions, or for everything between two scores, and get an answer without the collection crossing the network. The member is the identity and the score is the sort key: writing a member that is already present re-scores it and moves it rather than adding a second copy. The order is not free - it is maintained on every write, whether or not anyone reads a rank - and this all sits on a volatile tier, so the ranking can vanish with the entry.
go deeper
Recall the two halves: the caller supplies a number with each member, and the store keeps the members in order of that number. That is what makes a rank or a slice something you read instead of something you compute.
Explain that the ordering work happens on the write, not on the read, and that re-writing an existing member moves it rather than duplicating it. Name the reads the shape makes cheap: one member's rank, a slice by position, a band by score.
Show that you price the write. Ordering cost is paid per write and grows with collection size, it is paid even if no rank is ever read, and a re-scoring workload pays it on every event. Say what you would measure before choosing the shape.
Decide the rule for which ephemeral state may be modelled this way, given that some stores in the class have no such shape at all and push the ordering into every caller. Say how a ranking here is rebuilt after the tier is lost.
## The shape in one sentence A **score-ordered set** is a collection held under a single key in which every member carries a number - the **ordering score** - that the caller supplies when it writes the member, and the store keeps the members arranged by that number at all times. Because the arrangement is maintained while the write happens, a question about position is answered by reading, rather than by pulling the collection to the client and sorting it there. ## Where the score comes from - **The caller computes it and passes it in.** The store does not look inside the member to derive an order. If the order wanted is `newest first`, the caller reads a clock and sends that reading as the score. - **The member is the identity, the score is the sort key.** Two members may share a score; the same member written twice does not appear twice - the second write re-scores it and moves it to the position its new number implies. - Any value the caller can compare works: accumulated points, a clock reading, a due time, a priority band, or several fields packed into one comparable number. - Nothing about the score is validated against the payload. A score that has drifted out of step with the data it is supposed to rank is a caller bug the store cannot see. ## What becomes a read | Read | What you ask for | What comes back | |---|---|---| | Rank read | where one named member sits | its position in the order | | Range read by position | the first ten positions | that slice, already in order | | Range read by score | everything between two scores | the members in that band | | Count over a band | how many members lie between two scores | a number, no members | | Trim | remove a position range or a score band | the removal happens on the server | The important column is the last one: none of these answers requires the whole collection to cross the network. A caller keeping the same data in a shape with no maintained order has to read everything, order it locally and slice it - one large transfer plus client work, repeated by every instance that asks the question. ## What the write pays An ordered write is not an append. Roughly, the store: 1. determines whether the member is already present, 2. works out where the supplied score places it, and 3. links it into that position, doing bookkeeping whose amount depends on how large the collection already is. - The per-write cost **grows with the size of the collection** rather than staying flat, and it is paid on every write - including writes whose only purpose is to re-score a member that is already there. - It is paid whether or not anybody ever performs a rank read. Order is maintained eagerly, not on demand. - A workload that re-scores constantly, such as a presence or heartbeat feed, therefore pays the ordering price on every event. That is the usual reason this shape turns up in an investigation of a slow tier. ## What varies between stores - **Not every store in this class has the shape at all.** A byte-opaque store offers a whole-value read and a whole-value write and nothing else; there the ordering, the slicing and the trimming all happen in the caller, and every change to the collection is a read-modify-write round trip. - Stores that do offer it use **different internal structures** to hold the order, so the constant factors differ. Price a re-score as `more than an append, and growing with size`, never as a published number. - What happens to **members carrying equal scores** is not uniform: some stores define a secondary ordering, others document none. - A **lifetime attaches to the entry** - the whole collection under that key - in the common model. Per-member deadlines exist as extensions on some stores, so treat them as something to verify rather than as part of the shape. ## The volatile premise This collection lives on a tier that may lose everything on a restart and may drop whole entries when memory runs short - and eviction chooses between entries, not between members inside one, so the set disappears whole or not at all. Two design questions follow and cannot be skipped: can the ranking be rebuilt from a durable source, and is the window during which it is missing or stale acceptable to whatever reads it? ## When the order is not worth its price - If every read is `is this member present` or `what is this member's score`, an unordered member collection or a value of named fields answers the same questions without paying for order on every write. - If the only order that matters is arrival order and reads always take from one end, a two-ended sequence is the cheaper shape. - If nothing ever bounds the collection, the ordering cost compounds: the set grows, and every later write pays more to maintain an order nobody reads past the first few positions.
- If the only order that matters is the order things arrived in, what does a score-ordered set buy you?Very little, and it charges for it. Maintaining a position by score costs more per write than appending at an end of a two-ended sequence, and arrival order can be had from the sequence for free. Reach for the score only when position has to be derived from a number - points, a time, a due moment - rather than from when the write landed.
- Who computes the score when the ranking is 'most recently active first'?The caller, at write time, from a clock it reads itself. The store never derives a score from the member or from its own clock. That makes the clock source part of your design: writers on different machines must agree closely enough that the order is meaningful, and every activity event becomes a re-score of a member that is already present.
A library that reshelves each returned book into its place immediately. Finding the tenth book on the shelf is a glance - but the reshelving happened at return time, and it happened whether or not anyone ever walked that aisle.
saying these in an interview costs you the question
- Thinks the store derives the ordering score from the member's contents
- Expects members to be sorted when read rather than when written
- Believes the same member can be stored twice with two different scores
- Calls the shape free because rank reads are cheap
- Treats a ranking held on a volatile tier as durable