Identity stitching in a distributed environment
In this post, I will discuss how we use the identifiers attached to Snowplow events to build a consistent view of a consumer as they move between browsers and devices. The goal is to provide a single identifier for each consumer.
What is identity stitching?
Identity stitching in this context is the process of linking identifiers together from consumer data to build a unified view of each individual. When a consumer interacts with a website or app in Snowplow, the events they generate contain various identifiers such as cookies, mobile device IDs, and, if they are logged in, their account ID. Identity stitching allows us to link these together so that we have a single event timeline and profile for each consumer, even if they use multiple devices or browsers.
In this particular implementation, we are using Snowplow events, which have the identifiers:
- Network User Id: A cookie-based identifier that is generated by the Snowplow tracker and is unique to a browser and mobile device session. This is always present.
- App Device Id: The Android or iOS advertising ID that is generated by the device and is unique to a mobile device.
- User ID: The account ID that is set when a consumer logs in to the website or app.
As these events are processed, they help us build up a picture of which identifiers belong to the same consumer. Things get interesting when the consumer logs in, and we can associate device IDs with browsers, allowing us to track cross-platform behaviour. The following diagram shows how a single consumer can generate events from multiple devices and how we can use the identifiers to stitch them together into a single profile.
A single consumer generates events from multiple devices. The first is a logged-in browser session where the events have a cookie and a user/account ID. The second is a native app session where the events initially have a cookie and a device ID. Once the consumer logs in on the app, we can assume that all the previous identifiers belong to the same consumer and can be stitched together.
Building an identity graph
We can show how an identity graph is built from the above event stream with the following diagram:
Taking the same event stream as above, we can see that after events p1 –> p3, the graph associates the cookie and user ID with profile 1. After events m1 -> m2, another cookie and device ID are associated with profile 2. When the consumer logs in on the app, the two graphs are merged, all previous identifiers point to profile 1, and profile 2 can be discarded.
We can store this graph using Bigtable, which is a scalable key-value store with ultra-low latency. Bigtable tables have only one index, which is the row key. This means that we must be very careful about our schema design to ensure our query patterns are efficient. Google published an excellent guide to schema design which we followed when designing our identity graph. In the end, we stored our identity graph using just a single column, giving us essentially a very large hash table.
| row_key | profile_id |
|---|---|
N1:n | profile_1 |
A1:a | profile_1 |
U1:u | profile_1 |
Getting the row key right was also very important; we needed to ensure that the keys were evenly distributed across the keyspace to avoid hot nodes. We achieved this by ensuring all identifiers were UUIDs and suffixing the identifier type to the row key. For example, a network ID of N1 would be stored in Bigtable as N1:n. If we had chosen the opposite order, then network IDs would be accessed by the same node, and it would likely become overloaded.
Another key consideration was ensuring the algorithm was deterministic. Bigtable is an eventually consistent datastore, and we are consuming events from a Kafka topic split into 24 partitions. This means that we cannot guarantee the order of events or even that an event will only be processed once. We therefore needed to ensure that the building of the identity graph was deterministic and idempotent. We achieved this by using the hash of the network ID as the profile ID. This means that if two events with the same network ID are processed by different consumers, they will both generate the same profile ID and the graph will converge to a consistent state.
In this scenario, if two events are processed concurrently by different consumers, they both create a new profile for the same network ID. If the profile ID was generated randomly, then we would have two different profiles for the same consumer.
Updating the identity graph
When an event comes in, we can query the identity graph to determine if we have seen this consumer before. Say our original consumer clears their cookies and visits the website logged in again. The event will contain a new network ID cookie but the same user ID:
In this scenario, when we query the identity graph with the new network ID and the user ID, we will get one row back for the user ID and nothing for the new network ID. We can then write back to the graph associating the new network ID with the existing profile ID.
This is where our schema design comes into play; when we are processing a new event, we can very quickly query the graph for all the identifiers. If we get any rows back, then we know that the consumer has been seen before. If each identifier resolves to the same profile, then we don’t need to update the graph; if we get one profile but some identifiers are missing, then we can update the graph.
What happens when we get conflicting identifiers?
This is my favourite part of this algorithm: if we get conflicting identifiers, then we know that these two consumers are the same person and we can merge their profiles!
Following on from the event timeline above, when the event m3 is processed our query on the identities returns multiple profile IDs. This indicates that we must merge the two profiles. To do this, we choose one of the profile IDs to survive and update all the conflicting identifiers to point to the surviving profile. In this case we choose profile 1 to survive and update the graph so that all identifiers point to it.
Again, the algorithm must be deterministic, so the choice of which profile ID survives is based on lexicographical ordering. To ensure the merge happens correctly, we must also copy all the events from the secondary profile to the surviving profile. This ensures that downstream processing has a complete view of the consumer’s history.
Wrapping up
I’ve described here how we can build an eventually consistent identity graph in real time and with ultra-low latency. Bigtable was a great choice for a persistence layer because of its massive scalability, allowing us to process a thousand events per second. Doing this in real time allowed us to build a complete view of the consumer’s behaviour as they switch between devices; this is extremely valuable for the vehicle purchasing journey because people often switch to the ‘big screen’ when they are at the end of the journey and likely to convert. Without this stitching, we would lose their previous behaviour.