There is actually a distributed lock on the UID increment value in row "\x00" for each type (metric, tagk, tagv) in HBase and Bigtable. What happens is that TSD A will get a new string that needs a UID. It will perform a "get" for the string to UID mapping and if it doesn't find it, creates an atomic-increment call on the UID counter. In the mean time TSD B can perform the same task and may start the atomic-increment request. TSD A will execute a CAS mapping the string to the UID expecting the existing column to be null. It will successfully write the mapping. Then TSD B will also execute a CAS but it will find that A already wrote the mapping, so it discards the UID it had and reads the proper UID.
So if multiple TSDs get the same new strings, we can waste UID IDs because the UID counter is incremented, but we won't inappropriately write the same string with the wrong UID.