Techniques are disclosed relating to implementing synthetic identifiers (IDs) for a non-relational database. A server system may operate a database, which includes receiving requests to access records of the database using synthetic IDs. But the database may be searchable using natural IDs. The server system may receive a request to insert a record. In response, the server system may obtain, from a first instance of multiple ID generator instances that implement a distributed ID generator service, a synthetic ID generated based on an identifier assigned to the first ID generator instance. The server system may insert the record with the synthetic ID and a natural ID that corresponds to one or more values of the record. The server system may cause the synthetic ID and the natural ID to be stored in an index of the database to enable the record to be accessed via the synthetic ID.