Clarify definition and intent of "replacement algorithm" in update()

[xhwang-chromium]

Description

The EME specification currently mentions a "replacement algorithm" in the notes for the update() method (https://www.w3.org/TR/encrypted-media/#dom-mediakeysession-update):

1. "The replacement algorithm within a session is Key System-dependent."
2. "It is RECOMMENDED that CDM implementations support a standard and reasonably high minimum number of keys per MediaKeySession object, including a standard replacement algorithm... This enables a reasonable number of key rotation algorithms to be implemented across user agents and may reduce the likelihood of playback interruptions in use cases that involve various streams in the same element (e.g., adaptive streams, various audio and video tracks) using different keys."

However, the term "replacement algorithm" is not defined anywhere in the current specification. This makes it ambiguous for implementers and the behavior unpredictable for web developers.

Historical Context

The related text existed in the first commit of the EME spec in 2012 (8f067598985f3c8dc3832482626537a8f98e74b7). From the text, it seems that it's for the case that a key for a key ID already existed, and we need to replace that key when update() is called. The following is the quote from the initial EME draft (converted from xml):

If key contains a key or license, store the key.

1. Let key ID be null.
2. If sessionId is not null and refers to a session with Initialization Data that contains a key ID, let key ID be that ID.
3. If key is not null and contains a key ID, let key ID be that ID.
4. If initData is not null and contains a key ID, let key ID be that ID.
5. Store the key by following the steps for the first matching condition from the following list:
   • If key ID is not null:
     1. Clear any key not associated with a key ID.
     2. If a key already exists for key ID, delete that element.
     3. Store the key and/or license in key indexed by key ID. The replacement algorithm is Key System-dependent.
   • Otherwise:
     1. Clear all stored keys.
     2. Store the key and/or license in key with no associated key ID.

Notes: It is recommended that CDM providers support a standard and reasonably high minimum number of cached keys/licenses (with IDs) per media element as well as a standard replacement algorithm. This enables a reasonable number of key rotation algorithms to be implemented across user agents and may reduce the likelihood of playback interruptions in use cases that involve various streams in the same element, such as adaptive streams or various audio and video tracks using different keys.

The Problem

Because this context is now buried in decade-old commits, mailing lists and issue threads, the current spec text is confusing.

It's unclear whether "replacement" simply means overwriting a key with the same key ID, as the text suggested, or some eviction algorithm which is related to "reasonably high minimum number of cached keys/licenses" and "key rotation".

I'd suggest the working group to discuss this and update the notes to make it clear and better matching the current update() algorithm.

[chrisn]

@xhwang-chromium We have a meeting scheduled for Tuesday next week. Do you want us to agenda this?

[marcoscaceres]

For historical context: the phrase "replacement algorithm" dates back to the very first EME draft in 2012. It was discussed in Bug 19809 and the associated mailing list thread, where David Dorwin explained:

"The replacement algorithm was made a quality of implementation issue because we did not want to specify how many keys can be stored."

In other words, "replacement algorithm" refers to what happens when update() provides a new key but the session's key storage is already at capacity. This was intentionally left to CDM implementations.

In 2013, commit ed0f8560 (resolving Bug 19809) removed the normative key storage algorithm from the spec, but the two notes referencing a "replacement algorithm" survived:

1. "The replacement algorithm within a session is Key System-dependent."
2. "It is RECOMMENDED that CDM implementations support a standard and reasonably high minimum number of keys per MediaKeySession object, including a standard replacement algorithm..."

These notes are now somewhat orphaned: the normative algorithm they originally accompanied no longer exists.

Separately: note 2 uses "RECOMMENDED" (an RFC 2119 keyword) inside a non-normative note, which is a markup issue (same category as PR #549).

Options I see:

• Define it: Add a one-sentence definition so the notes have a clear referent.
• Remove the notes: The normative algorithm was removed in 2013; these can follow.
• Clarify in-place: Expand the notes to explain what "replacement" means, and fix "RECOMMENDED" → non-normative wording.

[xhwang-chromium]

Thank you so much for the detailed explanation. I was trying to find more historical context but failed :)

FWIW, we also have the following NOTE for keyStatuses attribute that mentions removed keys, which is related.

... Key IDs may be added as the result of a load() or update() call. Key IDs may be removed as the result of a update() call that removes knowledge of existing keys (or replaces the existing set of keys with a new set). Key IDs MUST NOT be removed because they became unusable, such as due to expiration. Instead, such keys MUST be given an appropriate status, such as "expired".

For the options, I do believe key eviction is a legit case that can happen in real world. For example, for continuous key rotation (#132), I've heard about discussions on high frequency key rotation recently, which would result in a large number of keys. In that case, having the CDM continuously evicting older keys would be an elegant solution, even if it's not hitting the device's resource limit, instead of having the player to manage the keys explicitly. With that, I'd recommend option 1, to actually define the concept of key eviction and/or replacement for better interoperability.