In Approach 2 (KGS) - I think following are the drawbacks:
- Since there is only 1 instance of KGS, it will be overloaded and will impact latency.
- Whenever a key is used, KGS will move (delete + insert) that key from unused to used table which results in 2 more queries.
I think better approach is to use Zookeeper (& range based approach) as mentioned in this url https://www.youtube.com/watch?v=JQDHz72OA3c&t=1486s