Editor’s note: This blog post is the second in a series providing an overview and history of LinkedIn’s experimentation platform. The previous post on the history of LinkedIn’s experimentation infrastructure can be found here.
Introducing variant assignment
Previously on the blog, we’ve shared a look into how experimentation works at LinkedIn with an overview of our experimentation platform, “T-REX,” and a deep dive into the architecture of the Lix engine. However, no matter how well-designed an infrastructure is, the ability to scale depends on an efficient and scientifically-valid variant assignment method. In this post, we will discuss a practical approach of making variant assignment blazing fast to handle trillions of invocations per day, as well as invariants and tricky parts of using such methods for online experiments.
The validity of A/B testing is rooted in the assumption that each variant is assigned to a random member. That’s why it’s critical to find a good randomization algorithm. There are three main characteristics of a good variant assignment function:
- Assignment of variants to members happens according to the desired split (i.e., no sample size ratio mismatch)
- Variant assignment of a single member is deterministic (i.e., repeatable)
- No correlation between the assignments when there are multiple experiments running
In particular, the third characteristic is critical because it suggests that a member’s assignment in one experiment has no effect on the probability of being assigned to a variant in other experiments. This is important because we want to analyze each experiment separately. We will talk more about this characteristic when we go through an example below.
Suppose we have a test T, its population P, and variants V0, V1, V2, …, VN-1, where each of the variants is assigned a fraction of P equal to A0, A1, …, AN-1, and A0 + A1 + … + AN-1 = 1. Let’s assume that P is a member population and that all members are assigned with integer identifiers.
Let’s represent the variants in a one-dimensional coordinate system on a line segment [0, 1). All the variants’ subpopulations can be represented as subsegments within the [0, 1) segment: V0’s population will correspond to [0, A0), V1‘s population to [A0, A0 + A1), …, VN-1‘s population to [A0 + A1 + … + AN-2, 1]. The problem of assigning a variant to a member is now reduced to selecting a point on the line segment [0, 1).
In order to assign a variant, the following algorithm can be used:
- Project the entire test’s population onto [0, 1)
- Shuffle it in a pseudo-random way along the segment
- Find a variant subsegment that owns the shuffled projection point of a member and return the corresponding variant
In a more concrete example, let’s assume the following:
- Population P is 100,000 members large.
- The experiment of interest has 3 variants, A, B, C, that are assigned to 20%, 40%, and 40% of P, respectively.
- We have members with IDs, as shown in the picture below, to perform variant assignment.
For the purpose of this explanation, we are interested in how member ID #8000 gets his or her treatment:
- Member ID #8000 is mapped to the point 0.08 as a result of computing <MEMBER_ID> / <NUM_MEMBERS>
- Then, we apply a random transformation to point 0.08 and project it into point 0.848.
- We check the variant allocation axis and see that members with ids mapped to points with coordinates between 0.6 and 1 get variant C, so member ID #8000 also is assigned with variant C.