{"id":180,"date":"2020-12-16T19:00:00","date_gmt":"2020-12-16T19:00:00","guid":{"rendered":"https:\/\/fde.cat\/index.php\/2020\/12\/16\/a-b-testing-at-linkedin-assigning-variants-at-scale\/"},"modified":"2021-02-02T13:47:12","modified_gmt":"2021-02-02T13:47:12","slug":"a-b-testing-at-linkedin-assigning-variants-at-scale","status":"publish","type":"post","link":"https:\/\/fde.cat\/index.php\/2020\/12\/16\/a-b-testing-at-linkedin-assigning-variants-at-scale\/","title":{"rendered":"A\/B testing at LinkedIn: Assigning variants at scale"},"content":{"rendered":"
\n
\n <\/a>\n <\/div>\n
\n
\n

Co-authors: Alexander Ivaniuk<\/a> and Weitao Duan<\/a><\/i><\/p>\n

Editor\u2019s note: This blog post is the second in a series providing an overview and history of LinkedIn\u2019s experimentation platform. The previous post on the history of LinkedIn\u2019s experimentation infrastructure can be found here<\/a>.<\/i><\/p>\n

Introducing variant assignment<\/h2>\n

Previously on the blog, we\u2019ve shared a look into how experimentation works at LinkedIn with an overview of our experimentation platform, \u201cT-REX,\u201d and a deep dive into the architecture of the Lix engine<\/a>. 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.<\/p>\n

The validity of A\/B testing is rooted in the assumption that each variant is assigned to a random member. That\u2019s why it\u2019s critical to find a good randomization algorithm. There are three main characteristics of a good variant assignment function:<\/p>\n

    \n
  1. Assignment of variants to members happens according to the desired split (i.e., no sample size ratio mismatch)<\/li>\n
  2. Variant assignment of a single member is deterministic (i.e., repeatable)<\/li>\n
  3. No correlation between the assignments when there are multiple experiments running<\/li>\n<\/ol>\n

    In particular, the third characteristic is critical because it suggests that a member\u2019s 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.<\/p>\n

    General approach<\/h2>\n

    Suppose we have a test T<\/i>, its population P<\/i>, and variants V0<\/sub><\/i>, V1<\/sub><\/i>, V2<\/sub><\/i>, \u2026, VN-1<\/sub><\/i>, where each of the variants is assigned a fraction of P<\/i> equal to A0<\/sub><\/i>, A1<\/sub><\/i>, \u2026, AN-1<\/sub><\/i>, and A0<\/sub><\/i> + A1<\/sub><\/i> + \u2026 + AN-1<\/sub><\/i> = 1. Let\u2019s assume that P<\/i> is a member population\u00a0and that all members are assigned with integer identifiers.<\/p>\n

    Let\u2019s represent the variants in a one-dimensional coordinate system on a line segment [0, 1). All the variants\u2019 subpopulations can be represented as subsegments within the [0, 1) segment: V0<\/sub><\/i>\u2019s population will correspond to [0, A0<\/sub><\/i>), V1<\/sub><\/i>\u2018s population to [A0<\/sub><\/i>, A0<\/sub><\/i> + A1<\/sub><\/i>), \u2026, VN-1<\/sub><\/i>\u2018s population to [A0<\/sub><\/i> + A1<\/sub><\/i> + \u2026 + AN-2<\/sub><\/i>, 1]. The problem of assigning a variant to a member is now reduced to selecting a point on the line segment [0, 1).\u00a0<\/p>\n

    In order to assign a variant, the following algorithm can be used:<\/p>\n

      \n
    1. Project the entire test\u2019s population onto [0, 1)<\/li>\n
    2. Shuffle it in a pseudo-random way along the segment<\/li>\n
    3. Find a variant subsegment that owns the shuffled projection point of a member and return the corresponding variant<\/li>\n<\/ol>\n

      In a more concrete example, let\u2019s assume the following:<\/p>\n

        \n
      1. Population P<\/i> is 100,000 members large.<\/li>\n
      2. The experiment of interest has 3 variants, A<\/i>, B<\/i>, C<\/i>, that are assigned to 20%, 40%, and 40% of P<\/i>, respectively.\u00a0<\/li>\n
      3. We have members with IDs, as shown in the picture below, to perform variant assignment.<\/li>\n<\/ol>\n

        For the purpose of this explanation, we are interested in how member ID #8000 gets his or her treatment:<\/p>\n

          \n
        1. Member ID #8000 is mapped to the point 0.08 as a result of computing <MEMBER_ID> \/ <NUM_MEMBERS><\/span><\/li>\n
        2. Then, we apply a random transformation to point 0.08 and project it into point 0.848.<\/li>\n
        3. 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<\/i>, so member ID #8000 also is assigned with variant C<\/i>.<\/li>\n<\/ol><\/div>\n<\/p><\/div>\n<\/div>\n
          \n
          \n <\/a>\n <\/div>\n