服务器可以使用 KGS 读取/标记数据库中的密钥。 KGS 可以使用两张表来存储密钥：一张用于存储尚未使用的密钥，另一张用于存储所有使用过的密钥。 一旦 KGS 将密钥提供给其中一台服务器，它就可以将它们移动到已使用的密钥表中。 KGS 可以始终在内存中保留一些密钥，以便在服务器需要时快速提供它们。
为了简单起见，一旦KGS在内存中加载了一些键，它就可以将它们移动到所使用的键表中。这确保了每个服务器获得唯一的密钥。如果KGS在将所有加载的密钥分配给某个服务器之前挂掉，这部分密钥将会被浪费，这是可以接受的，因为我们有大量的密钥。
KGS还必须确保不向多个服务器提供相同的密钥。为此，它必须同步(或获得锁)持有密钥的数据结构，然后从该数据结构中删除密钥并将它们交给服务器。
密钥数据库大小是多少?使用 base64 编码，我们可以生成 68.7B 个唯一的六个字母键。如果我们需要一个字节来存储一个字母数字字符，我们可以将所有键存储在412GB的磁盘。
6 (characters per key) * 68.7B (unique keys) = 412 GB
KGS不是单点故障吗?是的。为了解决这个问题，我们可以有一个备用的KGS副本，当主服务器死亡时，备用服务器可以接管生成并提供密钥。
每个应用服务器是否可以从key-DB中缓存一些key?是的，而且可以加快响应速度。尽管在这种情况下，如果应用服务器在使用所有密钥之前就死掉了，我们最终会丢失这些密钥。但这是可以接受的，因为我们有68B唯一的6个字母的key。
如何执行键查找?我们可以在数据库或键值存储中查找键以获得完整的URL。如果存在，则向浏览器发出一个HTTP 302重定向状态，并在请求的Location字段中传递存储的URL。如果该密钥不在我们的系统中，则发出HTTP 404 not Found状态或将用户重定向回主页。
我们应该对自定义别名施加大小限制吗？我们的服务支持自定义别名。 用户可以选择他们喜欢的任何密钥，但提供自定义别名不是强制性的。但是，对自定义别名施加大小限制以确保我们拥有一致的 URL 数据库是合理的（并且通常是可取的）。 假设用户可以为每个客户键指定最多 16 个字符（如数据库架构所示）
为了扩展我们的数据库，我们需要对它进行分区，以便它能够存储数十亿url的信息。我们需要想出一个分区方案，将我们的数据划分并存储到不同的DB服务器上。
区间划分我们可以根据 URL 的第一个字母或哈希键将 URL 存储在单独的分区中。 因此，我们将所有以字母A开头的 URL 保存在一个分区中，将那些以字母`B``开头的 URL 保存在另一个分区中，依此类推。 这种方法称为基于范围的分区。 我们甚至可以将某些不太频繁出现的字母组合到一个数据库分区中。 我们应该提供一个静态分区方案，以便我们可以以可预测的方式存储/查找文件。
这种方法的主要问题是，它可能导致服务器不平衡。例如: 我们决定将所有以字母E开头的url放到一个DB分区中，但后来我们意识到有太多的url以字母E开头。
基于散列分区在这个方案中，我们取所存储对象的哈希值。然后根据散列计算要使用哪个分区。在本例中，我们可以使用键或实际URL的哈希值来确定存储数据对象的分区。
我们的哈希函数将随机地将url分配到不同的分区中(例如，我们的哈希函数总是可以将任意键映射到[1…256]之间的一个数字)，这个数字将代表我们存储对象的分区。
这种方法仍然会导致重载分区，这个问题可以通过一致性哈希来解决。
八. 缓存我们可以缓存频繁访问的url。可以使用一些现成的解决方案，如Memcache，它可以存储带有各自散列的完整url。应用服务器在访问后端存储之前，可以快速检查缓存是否具有所需的URL。
缓存容量应该有多大?我们缓存每日流量的20%，然后根据客户端使用模式调整我们需要多少缓存服务器。如上所述，我们需要170GB内存来缓存每日流量的20%。因为现在的服务器可以有256GB的内存，我们可以很容易地把所有的缓存放到一台机器上。或者，我们可以使用一些较小的服务器来存储所有这些热点URL。
哪种缓存驱逐策略最适合我们的需求？当缓存已满，而我们想用更新/更热的 URL 替换链接时，我们将如何选择？ 最近最少使用 (LRU) 可能是比较合适的。 根据此策略，我们首先丢弃最近最少使用的 URL。 我们可以使用 LinkedHashMap 或类似的数据结构来存储我们的 URL 和 Hash，这也可以跟踪最近访问过的 URL。
为了进一步提高效率，我们可以复制缓存服务器来在它们之间分配负载。
如何更新每个缓存副本?