Design a username existence checking service

Design a service that can efficiently check if a username exists in the system. Consider storage mechanisms, search strategies, and handling of false positives when using data structures like bloom filters.