Support multiple uids cookies

[bretg]

So it looks like 3rd party cookies may survive well into the future at a rate high enough to make match-rate work worthwhile.

This issue proposes an alternate to the shrink the cookie plan where we add a protobuf+brotli compression to the existing uids cookie. The downside to that plan is mainly that there's not a lot of upside... it adds maybe around ~50% to the number of adapter IDs that could be supported in a single cookie. Since the current cookie supports around 30 IDs, several staff months of work will only allow us to support around 45 IDs.

On the other hand, putting a similar amount of work into supporting multiple uids cookies can multiply the amount of IDs that can be stored to to 60, 90, 120, or more. For example, Magnite has more than 110 bid adapters enabled in their PBS -- way more than can fit into the single cookie, whether protobufed or not. Better ROI on the time spent.

This alternate plan builds on the requirements detailed in #2173 to generalize cookie storage. The concept is pretty straightforward:

• allow the host company to configure how many uids cookies it supports. Defaults to 1.
• for example, besides uids, the server could also set and receive uids1, uids2, etc.
• the /cookie_sync and /auction endpoints just need to look for cookies of this pattern concatenate the values
• the /setuid endpoint has the harder job of determining how many cookies to set and dealing with edge cases like removing cookies that are no longer needed.

configuration

the proposed host-level config is setuid.number-of-uid-cookies

setuid:
  number-of-uid-cookies: 2

The values can be 1-30. Anything outside of that range should cause a startup failure. If not specified, the default value is 1.

The number of cookies allowed by browsers per domain is 30, so host companies need to consider how many are allowed for Prebid Server.

cookie_sync, auction, and amp endpoints

All existing requirements are still relevant: privacy, sync limits, etc.

But instead of looking just for uids, a pre-processing step is added that also scans all incoming cookies matching the pattern "uids\d". Then join the tempUIDs objects all together. If a cookie family name is duplicated in the set, only pay attention to the entry with the most distant expiration timestamp.

Don't worry about checking the config for how many uid cookies should exist. That's /setuid's job. If there's too many, it will get fixed in the next /setuid. If there's too few, maybe this is a new user.

setuid endpoint

1. check GDPR permissions for the incoming cookie-family on the bidder parameter
   1. if the request specifies gdpr=1 or if gdpr not specified and the IP address resolves to the EEA. Note that this assumes the cookie-family name can be looked up for GVLID.
   2. if not allowed by GDPR, log metric 'usersync.BIDDER.tcf.blocked' and respond with the cookie-family not added
2. Parse the existing set of uids cookies. (uids, uids2, uids3, etc.) and merge them into one working list.
3. Remove any expired entries.
4. If an 'optout' flag is specified in any of the cookies, the user doesn't want any IDs set. Remove all entries.
5. If a cookie family name is duplicated in the set, remove all of them except the one with the most distant expiration timestamp.
6. If the incoming cookie-family (i.e. map the bidder to the cookie-family, which is normally the main adapter after resolving aliases) already exists in the working list, remove it. Re-add it with the new uuid value and a new timestamp. There are 3 scenarios where this entire step is skipped: (1) missing uid parameter. (2) uid=0 (3) missing bidder parameter. In any of these cases, don’t remove any existing working list entries incoming cookie-family.
7. Check the setuid.number-of-uid-cookies config.
8. Sort the working list by: priority bidders, then timestamp -- oldest first, meaning the one with the most distant expiration timestamp will be on the bottom. It is done this way to reduce churn. Note that a non-priority incoming cookie-family will be the very last entry on the working list.
9. Spread the working list across the allowable uids cookies.
   1. Loop through the allowable number of cookies
      1. loop through the IDs remaining on the working list
         1. Add the current ID to the current cookie list and temporarily base64 encode. Note: it may be possible to estimate the base64 encoding here rather than actually encoding. And in any case, we can probably safely assume that at least 15 IDs will fit in a cookie before having to be careful about adding new ones.
         2. If the encoded size is less than 4KB, go on the next ID.
         3. If the encoded size is greater than 4KB, remove the current ID from this cookie list and put it back on the top of the working list. Break out of the ID loop and go on to the next cookie.
   2. if there are no IDs on the working list, then we're done. Everything fit. Yay.
   3. if there are still IDs on the working list, then we're in a situation where there are too many IDs to fit into the available cookie space.
      1. loop through each entry still on the list
         1. if the incoming entry was a priority bidder, then log usersync.FAMILY.sizedout
         2. if the incoming entry was not a priority bidder, then log usersync.FAMILY.sizeblocked
10. Create the set-cookie headers. Note: Set-Cookie headers should always be set for all N cookies even if not needed, even if empty. This is the way to delete the value in the browser. e.g. say number-of-uid-cookies: 2 but only one cookie is needed. There should still be a header to empty out uids2. e.g. Set-Cookie: uids2=; Path=/; SameSite=None; MaxAge=0
    1. Be sure to copy any existing optout flag through to the uid cookie.

Notes:

• there are likely optimizations with less redundant encoding. That's left up to the development team.
• yes, it's possible that the 'sizedout' and 'sizeblocked' metrics can also be emitted when the cookie count goes down or if the updated ID is a lot longer than the previous value.