Content Delivery Networks

In the previous three lessons, the lever stood at a single point throughout: where the request was forced to pass. The reverse proxy in front of the subjects, the forward proxy in front of the clients, but both at a single point, and one with access to all of the content.

A content delivery network multiplies this point: copies of the same content are kept in many edge caches standing close to the clients, and the request does not travel all the way to the source server. The lever changes too. What gets adjusted is no longer how load gets split, but what stands where — and this lever’s tail is the content the edge never sees.

What the Edge Measures

The edge cache’s operating models, which layers can be cached, and distribution’s design decisions were covered in the Traffic Layer course of the System Design and Distributed Systems curriculum; that discussion is not repeated here. The difference is one sentence: there the distribution model was compared as a design, here the tail a single placement decision leaves on forty objects is counted.

In this lesson’s fiction, the forty subjects are content objects. The set is the same set; the only thing that changes is how the capacity field is read — here that field is the object’s size. The forty objects’ total size is the same number as the total capacity in the previous lessons.

The edge’s defining property is that it is smaller than the source server. If it were not smaller, it would not be an edge; it would be a second source server carrying all the content. This is why every edge cache has to make a choice: which of the forty objects will sit there? The lever is this choice’s rule, and it has two basic forms.

Pull and Push

Under the pull model, the edge starts empty. When an object is requested for the first time, it is not at the edge; the request goes to the source server, and as the response comes back it gets cached at the edge, and subsequent requests are served from there. The edge never carries an object that has not been requested — but every object’s first request inevitably misses.

Under the push model, content is placed at the edge without waiting to be requested. The first request too is served from the edge, and misses can be zeroed out. In return, the edge also carries content that will never be requested, and the space set aside for it cannot be given to anything else.

On the configuration side, both are a few lines:

# taught configuration transcript, not run

edge {
  model      pull
  source     source-server
  cache      on-first-request
  size       800 units
  eviction   least-recently-used
}

edge {
  model      push
  source     source-server
  place      at-publish-time
  size       800 units
  selection  object-order
}

The last line carries the push model’s real question: if the edge cannot take all the content, which does it take? The pull model does not ask this question, because it reads the answer from the request stream. The push model has to ask it, and has to give the answer in advance.

The measurement’s assumptions:

• TM21 — The forty subjects are the course’s fixed set. In this lesson, each subject is a content object, and the capacity field is read as its size; the set does not change, the reading does.
• TM22 — The request stream consists of six hundred requests, and its popularity is skewed: a small number of objects take most of the requests, and objects in the tail are never requested.
• TM23 — The popularity order is independent of the object number. The order is shuffled with a separate seed, so a push rule that selects by object number carries no information about popularity.
• TM24 — There is no miss for an object sitting at the edge; a request for an object that is not there goes to the source server and counts as a miss. Objects’ freshness lifetime is infinite in this measurement; a cached copy never goes stale.
• TM25 — On a limited edge, the eviction rule is least recently used: when room needs to be made, the object that has gone longest unrequested is dropped.
• TM26 — Limited push selects objects by number order; this is the plainest form of a placement that does not know popularity.
• TM27 — The measurement is not a network measurement; no request is sent, no edge is set up. What is counted is the placement in the fiction itself.

The Measurement

"""Edge cache: pull waits on the first request, push carries what is never requested."""
SEED = 20260812
CLASSES = ("interactive", "batch", "standby")
EDGE = 800


def generator(seed):
    d = seed % 2147483646 + 1

    def r(n):
        nonlocal d
        d = (d * 48271) % 2147483647
        return d % n
    return r


def subjects(count=40, seed=SEED):
    r, result = generator(seed), []
    for i in range(count):
        result.append({"no": i + 1, "capacity": 20 + r(81), "delay": 5 + r(45),
                       "class": CLASSES[r(3)], "special": r(9) == 0})
    return result


def popularity(subs, seed=SEED + 17):
    """Popularity order is independent of object number."""
    r, order = generator(seed), [s["no"] for s in subs]
    for i in range(len(order) - 1, 0, -1):
        j = r(i + 1)
        order[i], order[j] = order[j], order[i]
    return order


def requests(subs, count=600, seed=SEED + 23):
    """Popularity-skewed request stream: objects in the tail go never requested."""
    r, order, result = generator(seed), popularity(subs), []
    for _ in range(count):
        result.append(order[min(r(len(subs)), r(len(subs)), r(len(subs)))])
    return result


def pull(subs, reqs, limit):
    """Object enters the edge on first request; if limited, the oldest use gets evicted."""
    size = {s["no"]: s["capacity"] for s in subs}
    edge, used, misses = [], 0, 0
    for n in reqs:
        if n in edge:
            edge.remove(n)
            edge.append(n)
            continue
        misses += 1
        if limit is not None:
            while used + size[n] > limit and edge:
                used -= size[edge.pop(0)]
            if used + size[n] > limit:
                continue
        edge.append(n)
        used += size[n]
    return set(edge), used, misses


def push(subs, reqs, limit):
    """Forty objects are pushed ahead of time; if limited, selected by number order."""
    size, edge, used = {s["no"]: s["capacity"] for s in subs}, set(), 0
    for s in subs:
        if limit is None or used + s["capacity"] <= limit:
            edge.add(s["no"])
            used += s["capacity"]
    return edge, used, sum(1 for n in reqs if n not in edge)


subs = subjects()
reqs = requests(subs)
size = {s["no"]: s["capacity"] for s in subs}
requested = set(reqs)
print(f"objects {len(subs)} | total size {sum(size.values())} | edge limit {EDGE} units")
print(f"requests {len(reqs)} | requested objects {len(requested)} | "
      f"never requested {len(subs) - len(requested)} "
      f"({sum(size[s['no']] for s in subs if s['no'] not in requested)} units)")
print()
print(f"{'model':<20s} {'at edge':>10s} {'used':>11s} {'misses':>6s} "
      f"{'hits':>7s} {'edge never sees':>18s} {'wasted idle':>11s}")
for name, edge, used, misses in (
        ("pull, unlimited", *pull(subs, reqs, None)),
        ("pull, limited", *pull(subs, reqs, EDGE)),
        ("push, unlimited", *push(subs, reqs, None)),
        ("push, limited", *push(subs, reqs, EDGE))):
    print(f"{name:<20s} {len(edge):10d} {used:11d} {misses:6d} {len(reqs) - misses:7d} "
          f"{len(subs) - len(edge):18d} "
          f"{sum(size[n] for n in edge if n not in requested):11d}")

objects 40 | total size 2336 | edge limit 800 units
requests 600 | requested objects 33 | never requested 7 (402 units)

model                   at edge        used misses    hits    edge never sees wasted idle
pull, unlimited              33        1934     33     567                  7           0
pull, limited                15         788    245     355                 25           0
push, unlimited              40        2336      0     600                  0         402
push, limited                15         798    379     221                 25          30

The Cost of the First Request

The pull model’s unlimited row shows the model’s pure form. 33 of the six hundred requests miss, and this number is no coincidence: the requested-object count is also 33. Under the pull model, every object misses exactly once — on first request. The remaining 567 requests are served from the edge.

This model’s tail is therefore a very specific tail: each object’s first requester. That request travels all the way to the source server, sees the longest delay, and clears the path for the next requester. Being in the tail here is not a flaw, it is how the model works; but who is in the tail matters.

This tail is not distributed equally. On a popular object, a single miss gets lost among hundreds of hits, and almost none of the people requesting that object pay the cost. On a rarely requested object, on the other hand, every requester is, in practice, the first requester: if the time between two requests is longer than the cache’s lifetime, the copy gets fetched fresh every time. So the party that actually pays the pull model’s cost is the minority that already receives the least service — and a gauge that looks at the overall hit rate never shows this minority, because 33 misses against 567 hits is a good ratio.

The column to the right gives the second number: the object the edge never sees is 7. Seven of the forty objects were not requested even once across six hundred requests, and the pull model never brought them to the edge at all. By the model’s own measure, this is flawless behavior — wasted idle units are 0. Whatever is at the edge has been requested.

The Cost of Never Being Requested

The push model’s unlimited row zeroes out the cost the pull model pays: misses are 0, all six hundred of the six hundred requests are served from the edge. There is no tail left called the first requester.

The cost sits in the column to the right. The edge carries all 2336 units, but 402 of them belong to seven objects that are never requested. Roughly a sixth of the edge’s space is filled with content that goes unread even once across six hundred requests.

The two models’ tails are therefore each other’s opposite. The pull model’s tail is in time: the first request until an object enters the edge. The push model’s tail is in space: content sitting at the edge that is never read. A model that zeroes out one grows the other, and there is no model that zeroes out both — because there is no way to know in advance what will be requested.

When a Limit Is Placed

The two rows above assumed the edge was unlimited, and that assumption goes against the edge’s own definition. The rows below repeat the same measurement with a realistic 800- unit limit.

Under the pull model, misses rise from 33 to 245. The cause is eviction: when the edge fills up, the least-recently-used object gets dropped, and when the evicted object is requested again, it misses again. The rule “every object misses once” no longer holds; an object misses as many times as it enters and leaves the edge. The object the edge never sees also rises from 7 to 25 — because there are now objects that never find room at the edge.

Under the push model, the same limit charges a heavier price: misses are 379. More than half of the six hundred requests go to the source server. The cause is clear, and TM23 and TM26 were put in place exactly to measure this: the push rule selects objects by number order, and number order has nothing to do with popularity. The edge fills to 798 units and carries 15 of the forty objects — almost the same occupancy as pull — but carries the wrong fifteen objects.

On top of that, limited push still carries 30 units of never-requested content. Even when space is scarce, the lever spends part of that scarce space on something no one wants.

The real lesson here concerns the placement rule itself. The push model requires a prediction, and the prediction’s wrongness is invisible unless it is measured. The pull model requires no prediction; in return, it pays a miss for every new object, and this cost is always visible. In a set of forty objects, the smallest measurable difference is 1/40 = 0.025; the gap between 245 and 379 is far above this, and the two models’ ranking can be defended with this set.

The Edge Is Not Singular

The measurement modeled a single edge cache, and this goes against the content delivery network’s own definition: a network is a network because it multiplies the edge. Multiplication’s effect on both models is direct.

Under the pull model, the first request’s cost is paid per edge. Every edge misses its own first request, because the copy one edge caches is not on another edge. The 33 misses in the measurement are a single edge’s cold start; as the edge count grows, this cost is multiplied along with it. If two clients requesting the same object land on separate edges, both are the first requester.

This is the pull model’s most commonly overlooked cost: adding an edge lowers the delay the client sees but raises the number of misses falling on the source server. Increasing the edge count does not remove the tail, it multiplies it — the same pattern as in previous lessons.

Under the push model, the multiplication shows up in space. The 402 never-requested units sit separately on every edge; pushing forty objects to a large number of edges means carrying content no one wants that many times over.

The intermediate form that builds a balance here is edges pulling from each other, or from a shared upper tier, rather than from the source server. The first requester still misses, but the miss goes to a nearer copy, not to the source server. The lever is still single: which edge pulls from whom is written by a single rule and applied to all forty of the forty objects at once.

The Cached Copy Going Stale

TM24 assumed in the measurement that the cached copy does not go stale, and it has to be said that this assumption is not real. If the content changes, the copy at the edge turns wrong, and the edge does not know this on its own.

What closes this gap is a third lever: invalidation. When content changes, its copies at the edges have to be dropped, and this too is a single decision — which objects get dropped at which edges is written by a single rule.

Its tail has two ends, and by now it is familiar. If the rule is written narrow, the changed content’s stale copy stays at the edge and every requester gets the wrong answer; worse, such a copy gives no sign of it unless someone actually looks. If the rule is written broad — say, the entire edge is dropped on every publish — objects that never changed also leave the edge, and the pull model’s first-request cost gets paid all over again. The 33 misses in the measurement, under a broad invalidation rule, are reborn on every publish; the limited edge’s 245 grows even further as eviction and invalidation stack on top of each other.

Freshness lifetime, validator fields, and the cache directives themselves were measured in the Server-Side Fundamentals and Application Layer Protocols courses; they are not repeated here. What matters on this lesson’s axis is that invalidation, too, takes the form of one decision, many subjects, and its tail’s two ends do not close together.

Summary

• The content delivery network lever adjusts not load but placement: which of the forty objects sit at the edge. The tail is the content the edge never sees.
• Under the pull model, every object misses exactly once: 33 requested objects, 33 misses, 567 hits, wasted idle units 0; the edge carries only what has been requested.
• Under the push model, misses are 0, but 402 never-requested units sit at the edge; the two models’ tails are each other’s opposite — one in time, the other in space.
• An 800-unit limit raises pull’s misses from 33 to 245; an evicted object misses again when requested again, and the object the edge never sees rises from 7 to 25.
• At the same limit, push that does not know popularity gives 379 misses: filled to 798 units, the same occupancy as pull, but with the wrong 15 objects, plus 30 units of never-requested content.
• Push requires a prediction, and the prediction’s wrongness is invisible unless measured; pull requires no prediction and always pays its cost visibly.

Next Step

The four levers up to this lesson all asked a single question in different forms: where should the work go? The balancer to which subject, the proxy to whose ownership, the edge to which copy. None of them accounted for work potentially being of different importance; the forty subjects all waited in the same line. The next lesson lifts this assumption: traffic gets split into classes, one class gets moved ahead, the other gets made to wait. The measure directly asks this too — the delay a class gains is taken from whose tail, and the two numbers are always written together.