Random is tough, but sequential is easy. My current system uses a common scheme. The database has a "next available number" for each component. The component that inserts new records asks the key vendor "give me 1000 numbers". The key vendor might read the database and get the number 1, add 1000 and put 1001 back in the database, then return 1-1000 to the component. Now the component can do 1000 guaranteed unique inserts by just incrementing an in-memory counter before it has to go back to the key vendor. If the system crashes or shuts down for the night, some numbers might go unused but there is no risk of duplicates.
In the early 90s when I first used DB/2 the DBAs told us not to use sequential keys because physical disk storage routines got clogged up when you always add to the end of an index. So we used a timestamp with the digits reversed as the leading part of the key to slightly randomize the inserts. Our Oracle group says sequential is no longer a concern, but ya never know.
Finally, google on
Java GUID generators and see how strongly they guarantee uniqueness.