系统设计面试王牌分布式ID生成器

　　一、简介
　　当您将图像上传到Instagram或在您最喜欢的经纪应用程序上进行交易时，后端系统会为新创建的对象分配一个唯一ID（UID）。此ID通常用作某些数据库表中的主键，可用于高效地检索对象。我猜你知道我要去哪里我们如何生成UID？
　　嗯，你肯定知道SQL中的自增主键。依赖这个特性的问题很明显它只适用于单机数据库，因为它涉及锁定，因此不可扩展。如果我每秒需要数百万个UID用于Slack、AWS、Youtube等应用程序怎么办？在本文中，我想与大家分享我的大型UID生成器的设计。1。1要求
　　在生成UID时，必须区分两种类型的UID。首先是没有明显语义的随机UID。其次，有顺序UID，带有排序等固有信息。
　　图1。两种类型的UID，作者图
　　随机UID不会泄漏任何有意义的信息，因此将其提供给人类更安全（客户端和人类不同！客户端是代码，它会尝试猜测其他人的URL）。给定一个随机UID，很难猜测其他对象的ID，从而提供一些隐私。Youtube上的视频或TinyUrl上的链接都是以这种方式编码的。例如，如果我创建了一个tinyUrl并获得了tinyurl。com2p8u9m2d，我很难猜测其他新创建的URL（事实上，tinyurl。com2p8u9m3d或tinyurl。com2p8u9m2c并不存在）。
　　顺序UID有其自身的优点。它的内在含义帮助应用程序组织数据。例如，在Instagram的Slackimages中为聊天消息提供连续的UID是有意义的，因为我们想保留项目顺序。此外，如果UID不暴露给人类，即使不使用固有顺序，也可以使用顺序UID。
　　在本文中，我将重点关注顺序UID，因为大多数百万WPS级别的应用程序不会向人类提供UID。以下是系统的核心功能需求：能够每秒生成一千万个顺序UIDUID必须保留一定程度的排序信息能够根据消耗调整发电率
　　不用说，系统应该是可扩展的和高度可用的。2。高层设计
　　通常在系统设计面试中，我会从访问模式和数据库模式开始。但是，我们的系统不需要任何数据库支持，稍后我会向您展示。整个系统几乎是无状态的；如果一台发电机崩溃了，可以重新启动另一台发电机并重新开始。2。1API设计
　　我们的UID生成器只有一个目的为任何需要它们的人提供新的UID。因此，它只需要以下面向客户端的RPC接口：getuidbatch（batchsize：int）列表〔int64〕
　　为了最小化通信开销，客户端每约100毫秒获取一批UID，并将UID缓存在内存中。如果客户端崩溃，本地UID就会丢失，这很好，因为我们有很多东西可以浪费。2。2高层架构由于应用程序的任务是每秒生成数百万个UID，因此我们需要多台计算机同时工作才能满足需求。我们需要某种集群管理器来监控节点健康状况和工作负载。如果供不应求，经理将增加更多工人。
　　图2。架构，作者图2。3控制逻辑启动ZooKeeper服务和集群主管。在实践中，监督者可以被自动扩展容器的Kubernetes等软件的内置功能所取代。集群主管默认创建N个worker。当一个worker被创建时，它向ZooKeeper注册并获得一个唯一的workerID（简单的整数，例如，从0到256）。每个worker对应于ZooKeeper上的一个临时znode。当一个worker死亡时，它的znode将被删除，ZooKeeper会通知supervisor。所有工作人员定期将他们的CPU负载发送到集群管理器。经理删除添加工人以最好地满足消耗率。三、细节3。1UID分解
　　到目前为止，我们的讨论都集中在API和架构等高级功能上。在本节中，我们需要最终确定UID格式。应该多长时间？它捕获什么信息？
　　UID长度
　　UID长度由应用程序及其存储需求决定。我们假设外部服务每秒最多消耗1000万个UID。让我们检查耗尽不同长度的UID需要多长时间：
　　图3。UID耗尽日期，作者图
　　显然，我们至少需要56位，以便应用程序在其生命周期内永远不会用完新的UID。
　　UID时间戳
　　我们希望UID是可排序的，所以它的一部分必须是某种时间戳。对于我们的应用程序，将时间戳保持在毫秒粒度就足够了。一个好的起点是UNIX时间戳。但是，它有64位，对我们的应用程序来说太长了。为了解决这个问题，我们可以建立一个自定义纪元（而不是UNIX时间戳使用的纪元1970110：0：0）并计算经过的毫秒数。
　　图4。如何使用epoch，作者图
　　那么，应该用多少位来存储时间戳呢？图5显示了不同时间戳大小的溢出时间：
　　图5。不同时间戳大小的溢出时间，作者图
　　假设项目寿命为20年，我们使用40位是安全的。
　　UID附加信息
　　很想在这里停下来完成我们的UID设计。但是，无论时间戳多么精确，都无法防止UID冲突。两台计算机可能会生成两个具有相同时间戳的UID。为了区分同时生成的UID，我们必须投入新的信息。以下是我的建议，基于实践中使用的流行设计（TwitterSnowflake）：
　　图6。UID分解，作者图WorkerID：我们可以使用分配给每台计算机的唯一WorkerID来区分。位数由集群中的最大工人数决定。线程ID：为了最大化吞吐量，多线程用于利用现代多核CPU机器提供的并行性。为什么不是进程ID？进程间通信更昂贵，我们希望将所有生成的ID放入一个共享的内存缓冲区中，以供RPC线程访问。本地计数器：即使在20年的老电脑上，一个线程也能在一毫秒内产生两个时间戳。因此，我们需要一个本地计数器来进一步区分两个UID。当计数器满时，线程在当前毫秒内进入休眠状态。
　　我在我的笔记本电脑上做了一个简单的实验，这是一台2019款六核MacBookpro。这是我实现的吞吐量（此处为代码）：
　　图7。单机吞吐量，作者图
　　在不运行RPC服务器和其他繁重的东西的情况下，我的笔记本电脑可以达到每百万秒约40K个UID。理想沙箱中的吞吐量高得惊人，我认为性能只会在实践中下降。根据有根据的猜测，假设计算机可以生成5KUIDms。要达到1000万个UIDs，我们需要两台计算机。当然，在实践中，我们可能需要更多。
　　现在，将所有东西放在一起，峰值性能（对于我的笔记本电脑）是通过13个线程（4位）实现的，每个线程都有12位的本地计数器。不包括工人ID，我们的UID至少需要56位。因此，最好使用64位UID。
　　图8。UID细分，作者图3。2为什么不用队列
　　你们中的一些人可能想知道使用专用队列将外部服务与此ID生成系统分离是否是个好主意。一个可能的架构如下所示：
　　图9。具有队列接口的替代架构，由作者绘制
　　像Kafka这样的中间件服务提供了很好的特性，例如解耦、缓冲、重试和简单的接口。但是，此应用程序不需要这些功能。我们不需要缓冲多余的UID，因为它们可以被丢弃。该系统具有我能想象到的最简单的RPC接口，这使得Kafka的接口看起来像火箭科学。使用Kafka，消费者的数量受分区数量的限制，这很不方便。
　　在所有反对队列的理由中，这是让我相信RPC更好的最重要的理由。一些队列不会透露缓冲的消息数量，这使得我们的服务无法在需求上升下降时增加减少容量。使用RPC，集群主管可以更轻松地监控整体工作负载。如果没有人使用UID，一些工人将被解雇以节省资金。4。总结
　　在这篇文章中，我们设计了一个具有疯狂吞吐量的分布式顺序UID生成器。我们深入研究了各种方法之间的技术权衡。在面试中，没有最佳答案。所有解决方案都有优点和缺点；我们的工作是评估他们中的每一个，并根据面试官给出的限制做出最合理的权衡。