Detailed Explanation of Distributed ID

<section id="nice" style="font-size: 16px; padding-right: 10px; padding-left: 10px; line-height: 1.6; letter-spacing: 0px; word-break: break-word; overflow-wrap: break-word; font-family: Optima-Regular, Optima, PingFangSC-light, PingFangTC-light, &quot;PingFang SC&quot;, Cambria, Cochin, Georgia, Times, &quot;Times New Roman&quot;, serif;"><h2 style="margin-top: 30px; margin-bottom: 15px; font-weight: bold; border-bottom: 2px solid rgb(239, 112, 96); font-size: 1.3em;"><span style="display: none;"></span><span style="display: inline-block; background: rgb(239, 112, 96); color: rgb(255, 255, 255); padding: 3px 10px 1px; border-top-right-radius: 3px; border-top-left-radius: 3px; margin-right: 3px;">Detailed Explanation of Distributed ID</span><span style="display: inline-block; vertical-align: bottom; border-bottom: 36px solid #efebe9; border-right: 20px solid transparent;"> </span></h2> <h3 style="margin-top: 30px; margin-bottom: 15px; font-weight: bold; font-size: 20px;"><span style="display: none;"></span>Introduction to Distributed ID<span style="display: none;"></span></h3> <h3 style="margin-top: 30px; margin-bottom: 15px; font-weight: bold; font-size: 20px;"><span style="display: none;"></span>What is an ID?<span style="display: none;"></span></h3> <p style="padding-top: 8px; padding-bottom: 8px; margin-top: 0px; margin-bottom: 0px; line-height: 26px;">In daily development, we need to use ID to uniquely represent all kinds of data in the system, such as user ID corresponding to and only corresponding to one person, commodity ID corresponding to and only corresponding to one commodity, and order ID corresponding to and only corresponding to one order.</p> <p style="padding-top: 8px; padding-bottom: 8px; margin-top: 0px; margin-bottom: 0px; line-height: 26px;">We also have various IDs in real life, such as ID ID corresponding to and only corresponding to one person, address ID corresponding to and only corresponding to</p> <p style="padding-top: 8px; padding-bottom: 8px; margin-top: 0px; margin-bottom: 0px; line-height: 26px;">Simply put, ** The ID is the unique identification of the data **.</p> <h3 style="margin-top: 30px; margin-bottom: 15px; font-weight: bold; font-size: 20px;"><span style="display: none;"></span>What is a distributed ID?<span style="display: none;"></span></h3> <p style="padding-top: 8px; padding-bottom: 8px; margin-top: 0px; margin-bottom: 0px; line-height: 26px;">Distributed ID is the ID under distributed system. Distributed ID does not exist in real life, and belongs to a concept in computer system.</p> <p style="padding-top: 8px; padding-bottom: 8px; margin-top: 0px; margin-bottom: 0px; line-height: 26px;">Let me give a simple example of sub-database and sub-table.</p> <p style="padding-top: 8px; padding-bottom: 8px; margin-top: 0px; margin-bottom: 0px; line-height: 26px;">A project of our company uses stand-alone MySQL. However, unexpectedly, one month after the project went online, with the increasing number of users, the data volume of the whole system will become larger and larger. Stand-alone MySQL has no way to support, need to sub-library sub-table (recommended Sharding-JDBC).</p> <p style="padding-top: 8px; padding-bottom: 8px; margin-top: 0px; margin-bottom: 0px; line-height: 26px;">After the sub-database, the data is spread all over the databases on different servers, and the self-increasing primary key of the database can no longer meet the unique primary key generated. ** How do we generate globally unique primary keys for different data nodes? **</p> <p style="padding-top: 8px; padding-bottom: 8px; margin-top: 0px; margin-bottom: 0px; line-height: 26px;">This is when you need to generate ** Distributed ID **.</p> <figure style="margin-top: 10px; margin-bottom: 10px; display: flex; flex-direction: column; justify-content: center; align-items: center;"><img src="https://guide-blog-images.oss-cn-shenzhen.aliyuncs.com/github/javaguide/system-design/distributed-system/id-after-the-sub-table-not-conflict.png" alt="" style="display: block; margin-right: auto; margin-left: auto; max-width: 100%;"></figure> <h3 style="margin-top: 30px; margin-bottom: 15px; font-weight: bold; font-size: 20px;"><span style="display: none;"></span>What requirements do distributed IDs need to meet?<span style="display: none;"></span></h3> <figure style="margin-top: 10px; margin-bottom: 10px; display: flex; flex-direction: column; justify-content: center; align-items: center;"><img src="https://guide-blog-images.oss-cn-shenzhen.aliyuncs.com/github/javaguide/system-design/distributed-system/distributed-id-requirements.png" alt="" style="display: block; margin-right: auto; margin-left: auto; max-width: 100%;"></figure> <p style="padding-top: 8px; padding-bottom: 8px; margin-top: 0px; margin-bottom: 0px; line-height: 26px;">As an indispensable part of distributed system, distributed ID is used in many places.</p> <p style="padding-top: 8px; padding-bottom: 8px; margin-top: 0px; margin-bottom: 0px; line-height: 26px;">A basic distributed ID needs to meet the following requirements:</p> <ul style="margin-top: 8px; margin-bottom: 8px; padding-left: 25px;"> <li><section style="margin-top: 5px; margin-bottom: 5px; line-height: 26px; color: rgb(1, 1, 1);">** Global uniqueness **: The global uniqueness of the ID must be the first thing to satisfy!</section></li><li><section style="margin-top: 5px; margin-bottom: 5px; line-height: 26px; color: rgb(1, 1, 1);">** High performance **: Distributed IDs are generated faster and consume less local resources.</section></li><li><section style="margin-top: 5px; margin-bottom: 5px; line-height: 26px; color: rgb(1, 1, 1);">** High availability **: Services that generate distributed IDs are guaranteed infinitely close to 100% availability.</section></li><li><section style="margin-top: 5px; margin-bottom: 5px; line-height: 26px; color: rgb(1, 1, 1);">** Convenient and easy to use **: Ready to use, easy to use, quick access!</section></li></ul> <p style="padding-top: 8px; padding-bottom: 8px; margin-top: 0px; margin-bottom: 0px; line-height: 26px;">In addition to these, a better distributed ID should also guarantee:</p> <ul style="margin-top: 8px; margin-bottom: 8px; padding-left: 25px;"> <li><section style="margin-top: 5px; margin-bottom: 5px; line-height: 26px; color: rgb(1, 1, 1);">** Safety **: The ID does not contain sensitive information.</section></li><li><section style="margin-top: 5px; margin-bottom: 5px; line-height: 26px; color: rgb(1, 1, 1);">** Ordered increment **: If you want to store IDs in the database, the order of IDs can improve the database write speed. Moreover, most of the time, we are likely to sort directly by ID.</section></li><li><section style="margin-top: 5px; margin-bottom: 5px; line-height: 26px; color: rgb(1, 1, 1);">** Have specific business meanings **: If the generated ID has specific business implications, it can make locating problems and development more transparent (you can determine which business it is by ID).</section></li><li><section style="margin-top: 5px; margin-bottom: 5px; line-height: 26px; color: rgb(1, 1, 1);">** Independent deployment **: That is, the distributed system has a separate numberer service dedicated to generating distributed IDs. In this way, the service that generates ID can be decoupled from the business-related service. However, this also brings the problem of increasing network call consumption. Generally speaking, if there are many scenarios where distributed ID is needed, it is necessary to deploy the numberer service independently.</section></li></ul> <h2 style="margin-top: 30px; margin-bottom: 15px; font-weight: bold; border-bottom: 2px solid rgb(239, 112, 96); font-size: 1.3em;"><span style="display: none;"></span><span style="display: inline-block; background: rgb(239, 112, 96); color: rgb(255, 255, 255); padding: 3px 10px 1px; border-top-right-radius: 3px; border-top-left-radius: 3px; margin-right: 3px;">Common Solutions for Distributed ID</span><span style="display: inline-block; vertical-align: bottom; border-bottom: 36px solid #efebe9; border-right: 20px solid transparent;"> </span></h2> <h3 style="margin-top: 30px; margin-bottom: 15px; font-weight: bold; font-size: 20px;"><span style="display: none;"></span>Database<span style="display: none;"></span></h3> <h4 style="margin-top: 30px; margin-bottom: 15px; font-weight: bold; font-size: 18px;"><span style="display: none;"></span>Database primary key self-increment<span style="display: none;"></span></h4> <p style="padding-top: 8px; padding-bottom: 8px; margin-top: 0px; margin-bottom: 0px; line-height: 26px;">This method is relatively simple and straightforward, that is, the unique ID is generated by the self-increasing primary key of relational database.</p> <figure style="margin-top: 10px; margin-bottom: 10px; display: flex; flex-direction: column; justify-content: center; align-items: center;"><img src="https://guide-blog-images.oss-cn-shenzhen.aliyuncs.com/github/javaguide/system-design/distributed-system/the-primary-key-of-the-database-increases-automatically.png" alt="数据库主键自增" style="display: block; margin-right: auto; margin-left: auto; max-width: 100%;"><figcaption style="margin-top: 5px; text-align: center; color: #888; font-size: 14px;">数据库主键自增</figcaption></figure> <p style="padding-top: 8px; padding-bottom: 8px; margin-top: 0px; margin-bottom: 0px; line-height: 26px;">Take MySQL as an example, we can do it in the following ways.</p> <p style="padding-top: 8px; padding-bottom: 8px; margin-top: 0px; margin-bottom: 0px; line-height: 26px;">** 1. Create a database table. **</p> <pre><code style="overflow-x: auto; padding: 16px; color: rgb(171, 178, 191); background: rgb(40, 44, 52); display: -webkit-box; font-family: &quot;Operator Mono&quot;, Consolas, Monaco, Menlo, monospace; border-radius: 0px;"><span style="color: #c678dd; line-height: 26px;">CREATE</span>&nbsp;<span style="color: #c678dd; line-height: 26px;">TABLE</span>&nbsp;<span style="color: #98c379; line-height: 26px;">`sequence_id`</span>&nbsp;(<br>&nbsp;&nbsp;<span style="color: #98c379; line-height: 26px;">`id`</span>&nbsp;<span style="color: #e6c07b; line-height: 26px;">bigint</span>(<span style="color: #d19a66; line-height: 26px;">20</span>)&nbsp;<span style="color: #c678dd; line-height: 26px;">unsigned</span>&nbsp;<span style="color: #c678dd; line-height: 26px;">NOT</span>&nbsp;<span style="color: #56b6c2; line-height: 26px;">NULL</span>&nbsp;AUTO_INCREMENT,<br>&nbsp;&nbsp;<span style="color: #98c379; line-height: 26px;">`stub`</span>&nbsp;<span style="color: #e6c07b; line-height: 26px;">char</span>(<span style="color: #d19a66; line-height: 26px;">10</span>)&nbsp;<span style="color: #c678dd; line-height: 26px;">NOT</span>&nbsp;<span style="color: #56b6c2; line-height: 26px;">NULL</span>&nbsp;<span style="color: #c678dd; line-height: 26px;">DEFAULT</span>&nbsp;<span style="color: #98c379; line-height: 26px;">''</span>,<br>&nbsp;&nbsp;PRIMARY&nbsp;<span style="color: #c678dd; line-height: 26px;">KEY</span>&nbsp;(<span style="color: #98c379; line-height: 26px;">`id`</span>),<br>&nbsp;&nbsp;<span style="color: #c678dd; line-height: 26px;">UNIQUE</span>&nbsp;<span style="color: #c678dd; line-height: 26px;">KEY</span>&nbsp;<span style="color: #98c379; line-height: 26px;">`stub`</span>&nbsp;(<span style="color: #98c379; line-height: 26px;">`stub`</span>)<br>)&nbsp;<span style="color: #c678dd; line-height: 26px;">ENGINE</span>=<span style="color: #c678dd; line-height: 26px;">InnoDB</span>&nbsp;<span style="color: #c678dd; line-height: 26px;">DEFAULT</span>&nbsp;<span style="color: #c678dd; line-height: 26px;">CHARSET</span>=utf8mb4;<br></code></pre> <p style="padding-top: 8px; padding-bottom: 8px; margin-top: 0px; margin-bottom: 0px; line-height: 26px;">The <code style="font-size: 14px; overflow-wrap: break-word; padding: 2px 4px; border-radius: 4px; margin-right: 2px; margin-left: 2px; background-color: rgba(27, 31, 35, 0.05); font-family: &quot;Operator Mono&quot;, Consolas, Monaco, Menlo, monospace; word-break: break-all; color: rgb(239, 112, 96);">stub</code> field is meaningless and is just a placeholder for us to insert or modify data. Also, a unique index is created for the <code style="font-size: 14px; overflow-wrap: break-word; padding: 2px 4px; border-radius: 4px; margin-right: 2px; margin-left: 2px; background-color: rgba(27, 31, 35, 0.05); font-family: &quot;Operator Mono&quot;, Consolas, Monaco, Menlo, monospace; word-break: break-all; color: rgb(239, 112, 96);">stub</code> field to ensure its uniqueness.</p> <p style="padding-top: 8px; padding-bottom: 8px; margin-top: 0px; margin-bottom: 0px; line-height: 26px;">** 2. Insert data with <code style="font-size: 14px; overflow-wrap: break-word; padding: 2px 4px; border-radius: 4px; margin-right: 2px; margin-left: 2px; background-color: rgba(27, 31, 35, 0.05); font-family: &quot;Operator Mono&quot;, Consolas, Monaco, Menlo, monospace; word-break: break-all; color: rgb(239, 112, 96);">replace into</code>. **</p> <pre><code style="overflow-x: auto; padding: 16px; color: rgb(171, 178, 191); background: rgb(40, 44, 52); display: -webkit-box; font-family: &quot;Operator Mono&quot;, Consolas, Monaco, Menlo, monospace; border-radius: 0px;">BEGIN;<br><span style="line-height: 26px;">REPLACE&nbsp;INTO&nbsp;<span style="color: #61aeee; line-height: 26px;">sequence_id</span>&nbsp;<span style="line-height: 26px;">(stub)</span>&nbsp;<span style="color: #61aeee; line-height: 26px;">VALUES</span>&nbsp;<span style="line-height: 26px;">(<span style="color: #98c379; line-height: 26px;">'stub'</span>)</span></span>;<br><span style="line-height: 26px;">SELECT&nbsp;<span style="color: #61aeee; line-height: 26px;">LAST_INSERT_ID</span><span style="line-height: 26px;">()</span></span>;<br>COMMIT;<br></code></pre> <p style="padding-top: 8px; padding-bottom: 8px; margin-top: 0px; margin-bottom: 0px; line-height: 26px;">Insert data Here, instead of using <code style="font-size: 14px; overflow-wrap: break-word; padding: 2px 4px; border-radius: 4px; margin-right: 2px; margin-left: 2px; background-color: rgba(27, 31, 35, 0.05); font-family: &quot;Operator Mono&quot;, Consolas, Monaco, Menlo, monospace; word-break: break-all; color: rgb(239, 112, 96);">insert into</code>, we use <code style="font-size: 14px; overflow-wrap: break-word; padding: 2px 4px; border-radius: 4px; margin-right: 2px; margin-left: 2px; background-color: rgba(27, 31, 35, 0.05); font-family: &quot;Operator Mono&quot;, Consolas, Monaco, Menlo, monospace; word-break: break-all; color: rgb(239, 112, 96);">replace into</code> to insert data, as follows:</p> <p style="padding-top: 8px; padding-bottom: 8px; margin-top: 0px; margin-bottom: 0px; line-height: 26px;">1)Step 1: Try to insert data into the table.</p> <p style="padding-top: 8px; padding-bottom: 8px; margin-top: 0px; margin-bottom: 0px; line-height: 26px;">2)Step 2: If the primary key or unique index field fails to insert due to duplicate data errors, delete the conflicting row with duplicate key values from the table, and then try to insert the data into the table again.</p> <p style="padding-top: 8px; padding-bottom: 8px; margin-top: 0px; margin-bottom: 0px; line-height: 26px;">The advantages and disadvantages of this method are also obvious:</p> <ul style="margin-top: 8px; margin-bottom: 8px; padding-left: 25px;"> <li><section style="margin-top: 5px; margin-bottom: 5px; line-height: 26px; color: rgb(1, 1, 1);">** Advantages **: It is simple to implement, with orderly increment of ID and small storage consumption</section></li><li><section style="margin-top: 5px; margin-bottom: 5px; line-height: 26px; color: rgb(1, 1, 1);">** Disadvantages **: The concurrency supported is not large, and there is a single database problem (which can be solved by using database cluster, but the complexity is increased). ID has no specific business meaning, and security problems (such as calculating the daily order quantity according to the increasing law of order ID, trade secrets! ), accessing the database once every time you get the ID (which increases the pressure on the database and slows down the acquisition speed)</section></li></ul> <h4 style="margin-top: 30px; margin-bottom: 15px; font-weight: bold; font-size: 18px;"><span style="display: none;"></span>Database number segment schema<span style="display: none;"></span></h4> <p style="padding-top: 8px; padding-bottom: 8px; margin-top: 0px; margin-bottom: 0px; line-height: 26px;">Database primary key self-increase this mode, every time you get ID, you have to visit the database. When the ID demand is relatively large, it is definitely not possible.</p> <p style="padding-top: 8px; padding-bottom: 8px; margin-top: 0px; margin-bottom: 0px; line-height: 26px;">If we can get it in batches and then exist in memory, when we need it, it is comfortable to take it directly from memory! This is what we call ** Generate distributed ID based on the number segment schema of database. **</p> <p style="padding-top: 8px; padding-bottom: 8px; margin-top: 0px; margin-bottom: 0px; line-height: 26px;">The number segment mode of database is also a mainstream distributed ID generation mode at present. <a href="https://github.com/didi/tinyid/wiki/tinyid%E5%8E%9F%E7%90%86%E4%BB%8B%E7%BB%8D" style="overflow-wrap: break-word; font-weight: bold; color: rgb(239, 112, 96); border-bottom: 1px solid rgb(239, 112, 96);">Tinyid</a>, like Didi Open Source, is based on this way. However, TinyId uses double-numbered segment caching and adds multi-db support to further optimize.</p> <p style="padding-top: 8px; padding-bottom: 8px; margin-top: 0px; margin-bottom: 0px; line-height: 26px;">Take MySQL as an example, we can do it in the following ways.</p> <p style="padding-top: 8px; padding-bottom: 8px; margin-top: 0px; margin-bottom: 0px; line-height: 26px;">** 1. Create a database table. **</p> <pre><code style="overflow-x: auto; padding: 16px; color: rgb(171, 178, 191); background: rgb(40, 44, 52); display: -webkit-box; font-family: &quot;Operator Mono&quot;, Consolas, Monaco, Menlo, monospace; border-radius: 0px;"><span style="color: #c678dd; line-height: 26px;">CREATE</span>&nbsp;<span style="color: #c678dd; line-height: 26px;">TABLE</span>&nbsp;<span style="color: #98c379; line-height: 26px;">`sequence_id_generator`</span>&nbsp;(<br>&nbsp;&nbsp;<span style="color: #98c379; line-height: 26px;">`id`</span>&nbsp;<span style="color: #e6c07b; line-height: 26px;">int</span>(<span style="color: #d19a66; line-height: 26px;">10</span>)&nbsp;<span style="color: #c678dd; line-height: 26px;">NOT</span>&nbsp;<span style="color: #56b6c2; line-height: 26px;">NULL</span>,<br>&nbsp;&nbsp;<span style="color: #98c379; line-height: 26px;">`current_max_id`</span>&nbsp;<span style="color: #e6c07b; line-height: 26px;">bigint</span>(<span style="color: #d19a66; line-height: 26px;">20</span>)&nbsp;<span style="color: #c678dd; line-height: 26px;">NOT</span>&nbsp;<span style="color: #56b6c2; line-height: 26px;">NULL</span>&nbsp;<span style="color: #c678dd; line-height: 26px;">COMMENT</span>&nbsp;<span style="color: #98c379; line-height: 26px;">'当前最大id'</span>,<br>&nbsp;&nbsp;<span style="color: #98c379; line-height: 26px;">`step`</span>&nbsp;<span style="color: #e6c07b; line-height: 26px;">int</span>(<span style="color: #d19a66; line-height: 26px;">10</span>)&nbsp;<span style="color: #c678dd; line-height: 26px;">NOT</span>&nbsp;<span style="color: #56b6c2; line-height: 26px;">NULL</span>&nbsp;<span style="color: #c678dd; line-height: 26px;">COMMENT</span>&nbsp;<span style="color: #98c379; line-height: 26px;">'号段的长度'</span>,<br>&nbsp;&nbsp;<span style="color: #98c379; line-height: 26px;">`version`</span>&nbsp;<span style="color: #e6c07b; line-height: 26px;">int</span>(<span style="color: #d19a66; line-height: 26px;">20</span>)&nbsp;<span style="color: #c678dd; line-height: 26px;">NOT</span>&nbsp;<span style="color: #56b6c2; line-height: 26px;">NULL</span>&nbsp;<span style="color: #c678dd; line-height: 26px;">COMMENT</span>&nbsp;<span style="color: #98c379; line-height: 26px;">'版本号'</span>,<br>&nbsp;&nbsp;<span style="color: #98c379; line-height: 26px;">`biz_type`</span>&nbsp;&nbsp;&nbsp;&nbsp;<span style="color: #e6c07b; line-height: 26px;">int</span>(<span style="color: #d19a66; line-height: 26px;">20</span>)&nbsp;<span style="color: #c678dd; line-height: 26px;">NOT</span>&nbsp;<span style="color: #56b6c2; line-height: 26px;">NULL</span>&nbsp;<span style="color: #c678dd; line-height: 26px;">COMMENT</span>&nbsp;<span style="color: #98c379; line-height: 26px;">'业务类型'</span>,<br>&nbsp;&nbsp;&nbsp;PRIMARY&nbsp;<span style="color: #c678dd; line-height: 26px;">KEY</span>&nbsp;(<span style="color: #98c379; line-height: 26px;">`id`</span>)<br>)&nbsp;<span style="color: #c678dd; line-height: 26px;">ENGINE</span>=<span style="color: #c678dd; line-height: 26px;">InnoDB</span>&nbsp;<span style="color: #c678dd; line-height: 26px;">DEFAULT</span>&nbsp;<span style="color: #c678dd; line-height: 26px;">CHARSET</span>=utf8mb4;<br></code></pre> <p style="padding-top: 8px; padding-bottom: 8px; margin-top: 0px; margin-bottom: 0px; line-height: 26px;">The <code style="font-size: 14px; overflow-wrap: break-word; padding: 2px 4px; border-radius: 4px; margin-right: 2px; margin-left: 2px; background-color: rgba(27, 31, 35, 0.05); font-family: &quot;Operator Mono&quot;, Consolas, Monaco, Menlo, monospace; word-break: break-all; color: rgb(239, 112, 96);">current_max_id</code> fields and the <code style="font-size: 14px; overflow-wrap: break-word; padding: 2px 4px; border-radius: 4px; margin-right: 2px; margin-left: 2px; background-color: rgba(27, 31, 35, 0.05); font-family: &quot;Operator Mono&quot;, Consolas, Monaco, Menlo, monospace; word-break: break-all; color: rgb(239, 112, 96);">step</code> fields are used primarily to obtain the batch id, which is <code style="font-size: 14px; overflow-wrap: break-word; padding: 2px 4px; border-radius: 4px; margin-right: 2px; margin-left: 2px; background-color: rgba(27, 31, 35, 0.05); font-family: &quot;Operator Mono&quot;, Consolas, Monaco, Menlo, monospace; word-break: break-all; color: rgb(239, 112, 96);">current_max_id ~ current_max_id+step</code>.</p> <figure style="margin-top: 10px; margin-bottom: 10px; display: flex; flex-direction: column; justify-content: center; align-items: center;"><img src="https://guide-blog-images.oss-cn-shenzhen.aliyuncs.com/github/javaguide/system-design/distributed-system/database-number-segment-mode.png" alt="数据库号段模式" style="display: block; margin-right: auto; margin-left: auto; max-width: 100%;"><figcaption style="margin-top: 5px; text-align: center; color: #888; font-size: 14px;">数据库号段模式</figcaption></figure> <p style="padding-top: 8px; padding-bottom: 8px; margin-top: 0px; margin-bottom: 0px; line-height: 26px;">The <code style="font-size: 14px; overflow-wrap: break-word; padding: 2px 4px; border-radius: 4px; margin-right: 2px; margin-left: 2px; background-color: rgba(27, 31, 35, 0.05); font-family: &quot;Operator Mono&quot;, Consolas, Monaco, Menlo, monospace; word-break: break-all; color: rgb(239, 112, 96);">version</code> field is primarily used to address concurrency (optimistic locking), and the <code style="font-size: 14px; overflow-wrap: break-word; padding: 2px 4px; border-radius: 4px; margin-right: 2px; margin-left: 2px; background-color: rgba(27, 31, 35, 0.05); font-family: &quot;Operator Mono&quot;, Consolas, Monaco, Menlo, monospace; word-break: break-all; color: rgb(239, 112, 96);">biz_type</code> field is primarily used to indicate the type of business.</p> <p style="padding-top: 8px; padding-bottom: 8px; margin-top: 0px; margin-bottom: 0px; line-height: 26px;">** 2. Insert a row of data first. **</p> <pre><code style="overflow-x: auto; padding: 16px; color: rgb(171, 178, 191); background: rgb(40, 44, 52); display: -webkit-box; font-family: &quot;Operator Mono&quot;, Consolas, Monaco, Menlo, monospace; border-radius: 0px;"><span style="color: #c678dd; line-height: 26px;">INSERT</span>&nbsp;<span style="color: #c678dd; line-height: 26px;">INTO</span>&nbsp;<span style="color: #98c379; line-height: 26px;">`sequence_id_generator`</span>&nbsp;(<span style="color: #98c379; line-height: 26px;">`id`</span>,&nbsp;<span style="color: #98c379; line-height: 26px;">`current_max_id`</span>,&nbsp;<span style="color: #98c379; line-height: 26px;">`step`</span>,&nbsp;<span style="color: #98c379; line-height: 26px;">`version`</span>,&nbsp;<span style="color: #98c379; line-height: 26px;">`biz_type`</span>)<br><span style="color: #c678dd; line-height: 26px;">VALUES</span><br>&nbsp;(<span style="color: #d19a66; line-height: 26px;">1</span>,&nbsp;<span style="color: #d19a66; line-height: 26px;">0</span>,&nbsp;<span style="color: #d19a66; line-height: 26px;">100</span>,&nbsp;<span style="color: #d19a66; line-height: 26px;">0</span>,&nbsp;<span style="color: #d19a66; line-height: 26px;">101</span>);<br></code></pre> <p style="padding-top: 8px; padding-bottom: 8px; margin-top: 0px; margin-bottom: 0px; line-height: 26px;">** 3. Get the batch unique ID under the specified service by SELECT **</p> <pre><code style="overflow-x: auto; padding: 16px; color: rgb(171, 178, 191); background: rgb(40, 44, 52); display: -webkit-box; font-family: &quot;Operator Mono&quot;, Consolas, Monaco, Menlo, monospace; border-radius: 0px;"><span style="color: #c678dd; line-height: 26px;">SELECT</span>&nbsp;<span style="color: #98c379; line-height: 26px;">`current_max_id`</span>,&nbsp;<span style="color: #98c379; line-height: 26px;">`step`</span>,<span style="color: #98c379; line-height: 26px;">`version`</span>&nbsp;<span style="color: #c678dd; line-height: 26px;">FROM</span>&nbsp;<span style="color: #98c379; line-height: 26px;">`sequence_id_generator`</span>&nbsp;<span style="color: #c678dd; line-height: 26px;">where</span>&nbsp;<span style="color: #98c379; line-height: 26px;">`biz_type`</span>&nbsp;=&nbsp;<span style="color: #d19a66; line-height: 26px;">101</span><br></code></pre> <p style="padding-top: 8px; padding-bottom: 8px; margin-top: 0px; margin-bottom: 0px; line-height: 26px;">Results:</p> <pre><code style="overflow-x: auto; padding: 16px; color: rgb(171, 178, 191); background: rgb(40, 44, 52); display: -webkit-box; font-family: &quot;Operator Mono&quot;, Consolas, Monaco, Menlo, monospace; border-radius: 0px;">id&nbsp;current_max_id&nbsp;step&nbsp;version&nbsp;biz_type<br>1&nbsp;0&nbsp;100&nbsp;0&nbsp;101<br></code></pre> <p style="padding-top: 8px; padding-bottom: 8px; margin-top: 0px; margin-bottom: 0px; line-height: 26px;">** 4. If it is not enough, re-SELECT after updating. **</p> <pre><code style="overflow-x: auto; padding: 16px; color: rgb(171, 178, 191); background: rgb(40, 44, 52); display: -webkit-box; font-family: &quot;Operator Mono&quot;, Consolas, Monaco, Menlo, monospace; border-radius: 0px;"><span style="color: #c678dd; line-height: 26px;">UPDATE</span>&nbsp;sequence_id_generator&nbsp;<span style="color: #c678dd; line-height: 26px;">SET</span>&nbsp;current_max_id&nbsp;=&nbsp;<span style="color: #d19a66; line-height: 26px;">0</span>+<span style="color: #d19a66; line-height: 26px;">100</span>,&nbsp;<span style="color: #c678dd; line-height: 26px;">version</span>=<span style="color: #c678dd; line-height: 26px;">version</span>+<span style="color: #d19a66; line-height: 26px;">1</span>&nbsp;<span style="color: #c678dd; line-height: 26px;">WHERE</span>&nbsp;<span style="color: #c678dd; line-height: 26px;">version</span>&nbsp;=&nbsp;<span style="color: #d19a66; line-height: 26px;">0</span>&nbsp;&nbsp;<span style="color: #c678dd; line-height: 26px;">AND</span>&nbsp;<span style="color: #98c379; line-height: 26px;">`biz_type`</span>&nbsp;=&nbsp;<span style="color: #d19a66; line-height: 26px;">101</span><br><span style="color: #c678dd; line-height: 26px;">SELECT</span>&nbsp;<span style="color: #98c379; line-height: 26px;">`current_max_id`</span>,&nbsp;<span style="color: #98c379; line-height: 26px;">`step`</span>,<span style="color: #98c379; line-height: 26px;">`version`</span>&nbsp;<span style="color: #c678dd; line-height: 26px;">FROM</span>&nbsp;<span style="color: #98c379; line-height: 26px;">`sequence_id_generator`</span>&nbsp;<span style="color: #c678dd; line-height: 26px;">where</span>&nbsp;<span style="color: #98c379; line-height: 26px;">`biz_type`</span>&nbsp;=&nbsp;<span style="color: #d19a66; line-height: 26px;">101</span><br></code></pre> <p style="padding-top: 8px; padding-bottom: 8px; margin-top: 0px; margin-bottom: 0px; line-height: 26px;">Results:</p> <pre><code style="overflow-x: auto; padding: 16px; color: rgb(171, 178, 191); background: rgb(40, 44, 52); display: -webkit-box; font-family: &quot;Operator Mono&quot;, Consolas, Monaco, Menlo, monospace; border-radius: 0px;">id&nbsp;current_max_id&nbsp;step&nbsp;version&nbsp;biz_type<br>1&nbsp;100&nbsp;100&nbsp;1&nbsp;101<br></code></pre> <p style="padding-top: 8px; padding-bottom: 8px; margin-top: 0px; margin-bottom: 0px; line-height: 26px;">Compared with the way the database primary key is self-incremented, ** The number segment mode of the database has less access to the database and less pressure on the database. **</p> <p style="padding-top: 8px; padding-bottom: 8px; margin-top: 0px; margin-bottom: 0px; line-height: 26px;">In addition, in order to avoid single-point problems, you can improve usability by using master-slave mode.</p> <p style="padding-top: 8px; padding-bottom: 8px; margin-top: 0px; margin-bottom: 0px; line-height: 26px;">** advantages and disadvantages of database number segment schema: **</p> <ul style="margin-top: 8px; margin-bottom: 8px; padding-left: 25px;"> <li><section style="margin-top: 5px; margin-bottom: 5px; line-height: 26px; color: rgb(1, 1, 1);">** Advantages **: ID is incremented in order, and the storage consumption is small</section></li><li><section style="margin-top: 5px; margin-bottom: 5px; line-height: 26px; color: rgb(1, 1, 1);">** Disadvantages **: There are single-point database problems (which can be solved by database cluster, but the complexity is increased), ID has no specific business meaning, and security problems (such as calculating the daily order quantity according to the increasing law of order ID, trade secrets!)</section></li></ul> <h4 style="margin-top: 30px; margin-bottom: 15px; font-weight: bold; font-size: 18px;"><span style="display: none;"></span>NoSQL<span style="display: none;"></span></h4> <figure style="margin-top: 10px; margin-bottom: 10px; display: flex; flex-direction: column; justify-content: center; align-items: center;"><img src="https://guide-blog-images.oss-cn-shenzhen.aliyuncs.com/github/javaguide/system-design/distributed-system/nosql-distributed-id.png" alt="" style="display: block; margin-right: auto; margin-left: auto; max-width: 100%;"></figure> <p style="padding-top: 8px; padding-bottom: 8px; margin-top: 0px; margin-bottom: 0px; line-height: 26px;">In general, NoSQL schemes use Redis more. We can sequentially increment id atoms through Redis' <code style="font-size: 14px; overflow-wrap: break-word; padding: 2px 4px; border-radius: 4px; margin-right: 2px; margin-left: 2px; background-color: rgba(27, 31, 35, 0.05); font-family: &quot;Operator Mono&quot;, Consolas, Monaco, Menlo, monospace; word-break: break-all; color: rgb(239, 112, 96);">incr</code> command.</p> <pre><code style="overflow-x: auto; padding: 16px; color: rgb(171, 178, 191); background: rgb(40, 44, 52); display: -webkit-box; font-family: &quot;Operator Mono&quot;, Consolas, Monaco, Menlo, monospace; border-radius: 0px;">127.0.0.1:6379&gt;&nbsp;<span style="color: #e6c07b; line-height: 26px;">set</span>&nbsp;sequence_id_biz_type&nbsp;1<br>OK<br>127.0.0.1:6379&gt;&nbsp;incr&nbsp;sequence_id_biz_type<br>(<span style="color: #e6c07b; line-height: 26px;">integer</span>)&nbsp;2<br>127.0.0.1:6379&gt;&nbsp;get&nbsp;sequence_id_biz_type<br><span style="color: #98c379; line-height: 26px;">"2"</span><br></code></pre> <p style="padding-top: 8px; padding-bottom: 8px; margin-top: 0px; margin-bottom: 0px; line-height: 26px;">To improve availability and concurrency, we can use the Redis Cluster. Redis Cluster is the official Redis Cluster solution (version 3.0 +).</p> <p style="padding-top: 8px; padding-bottom: 8px; margin-top: 0px; margin-bottom: 0px; line-height: 26px;">In addition to the Redis Cluster, you can also use the open source Redis Cluster solution <a href="https://github.com/CodisLabs/codis" style="overflow-wrap: break-word; font-weight: bold; color: rgb(239, 112, 96); border-bottom: 1px solid rgb(239, 112, 96);">Codis</a> (recommended for large-scale clusters such as hundreds of nodes).</p> <p style="padding-top: 8px; padding-bottom: 8px; margin-top: 0px; margin-bottom: 0px; line-height: 26px;">In addition to high availability and concurrency, we know that Redis is memory-based, and we need to persist data to avoid data loss after machine restart or machine failure. Redis supports two different ways of persistence: ** Snapshot (RDB) ** and ** append-only file (AOF) **. Also, Redis 4.0 begins to support ** Mixed Persistence of RDB and AOF ** (off by default and can be turned on through the configuration item <code style="font-size: 14px; overflow-wrap: break-word; padding: 2px 4px; border-radius: 4px; margin-right: 2px; margin-left: 2px; background-color: rgba(27, 31, 35, 0.05); font-family: &quot;Operator Mono&quot;, Consolas, Monaco, Menlo, monospace; word-break: break-all; color: rgb(239, 112, 96);">aof-use-rdb-preamble</code>).</p> <p style="padding-top: 8px; padding-bottom: 8px; margin-top: 0px; margin-bottom: 0px; line-height: 26px;">As for Redis persistence, I will not introduce too much here. For those who don't know this part, you can look at <a href="http://bbs.tamanyuan.top" style="overflow-wrap: break-word; font-weight: bold; color: rgb(239, 112, 96); border-bottom: 1px solid rgb(239, 112, 96);"> JavaGuide Summary of Redis Knowledge Points </a>.</p> <p style="padding-top: 8px; padding-bottom: 8px; margin-top: 0px; margin-bottom: 0px; line-height: 26px;">** advantages and disadvantages of the Redis scenario: **</p> <ul style="margin-top: 8px; margin-bottom: 8px; padding-left: 25px;"> <li><section style="margin-top: 5px; margin-bottom: 5px; line-height: 26px; color: rgb(1, 1, 1);">** Advantages **: The performance is good and the generated ID is incremented in an orderly manner</section></li><li><section style="margin-top: 5px; margin-bottom: 5px; line-height: 26px; color: rgb(1, 1, 1);">** Disadvantages **: Similar disadvantages to database primary key self-increment scheme</section></li></ul> <p style="padding-top: 8px; padding-bottom: 8px; margin-top: 0px; margin-bottom: 0px; line-height: 26px;">Besides Redis, MongoDB ObjectId is often used as a distributed ID solution.</p> <figure style="margin-top: 10px; margin-bottom: 10px; display: flex; flex-direction: column; justify-content: center; align-items: center;"><img src="https://guide-blog-images.oss-cn-shenzhen.aliyuncs.com/github/javaguide/system-design/distributed-system/mongodb9-objectId-distributed-id.png" alt="" style="display: block; margin-right: auto; margin-left: auto; max-width: 100%;"></figure> <p style="padding-top: 8px; padding-bottom: 8px; margin-top: 0px; margin-bottom: 0px; line-height: 26px;">MongoDB ObjectId requires a total of 12 bytes of storage:</p> <ul style="margin-top: 8px; margin-bottom: 8px; padding-left: 25px;"> <li><section style="margin-top: 5px; margin-bottom: 5px; line-height: 26px; color: rgb(1, 1, 1);">0 ~ 3: Time stamp</section></li><li><section style="margin-top: 5px; margin-bottom: 5px; line-height: 26px; color: rgb(1, 1, 1);">3 ~ 6: Represents the machine ID</section></li><li><section style="margin-top: 5px; margin-bottom: 5px; line-height: 26px; color: rgb(1, 1, 1);">7 ~ 8: Machine process ID</section></li><li><section style="margin-top: 5px; margin-bottom: 5px; line-height: 26px; color: rgb(1, 1, 1);">9 ~ 11: Self-increment</section></li></ul> <p style="padding-top: 8px; padding-bottom: 8px; margin-top: 0px; margin-bottom: 0px; line-height: 26px;">** advantages and disadvantages of MongoDB scheme: **</p> <ul style="margin-top: 8px; margin-bottom: 8px; padding-left: 25px;"> <li><section style="margin-top: 5px; margin-bottom: 5px; line-height: 26px; color: rgb(1, 1, 1);">** Advantages **: The performance is good and the generated ID is incremented in an orderly manner</section></li><li><section style="margin-top: 5px; margin-bottom: 5px; line-height: 26px; color: rgb(1, 1, 1);">** Disadvantages **: Duplicate IDs need to be resolved (which may result in duplicate IDs when the machine time is wrong), security issues (ID generation is regular)</section></li></ul> <h3 style="margin-top: 30px; margin-bottom: 15px; font-weight: bold; font-size: 20px;"><span style="display: none;"></span>Algorithm<span style="display: none;"></span></h3> <h4 style="margin-top: 30px; margin-bottom: 15px; font-weight: bold; font-size: 18px;"><span style="display: none;"></span>UID<span style="display: none;"></span></h4> <p style="padding-top: 8px; padding-bottom: 8px; margin-top: 0px; margin-bottom: 0px; line-height: 26px;">UUID is an abbreviation for Universally Unique Identifier. The UUID contains 32 hexadecimal digits (8-4-4-4-12).</p> <p style="padding-top: 8px; padding-bottom: 8px; margin-top: 0px; margin-bottom: 0px; line-height: 26px;">The JDK provides a ready-made way to generate a UUID, just one line of code.</p> <pre><code style="overflow-x: auto; padding: 16px; color: rgb(171, 178, 191); background: rgb(40, 44, 52); display: -webkit-box; font-family: &quot;Operator Mono&quot;, Consolas, Monaco, Menlo, monospace; border-radius: 0px;"><span style="color: #5c6370; font-style: italic; line-height: 26px;">//输出示例：cb4a9ede-fa5e-4585-b9bb-d60bce986eaa</span><br>UUID.randomUUID()<br></code></pre> <p style="padding-top: 8px; padding-bottom: 8px; margin-top: 0px; margin-bottom: 0px; line-height: 26px;">The example of a UUID in <a href="https://tools.ietf.org/html/rfc4122" style="overflow-wrap: break-word; font-weight: bold; color: rgb(239, 112, 96); border-bottom: 1px solid rgb(239, 112, 96);">RFC 4122</a> looks like this:</p> <figure style="margin-top: 10px; margin-bottom: 10px; display: flex; flex-direction: column; justify-content: center; align-items: center;"><img src="https://guide-blog-images.oss-cn-shenzhen.aliyuncs.com/github/javaguide/system-design/distributed-system/rfc-4122-uuid.png" alt="" style="display: block; margin-right: auto; margin-left: auto; max-width: 100%;"></figure> <p style="padding-top: 8px; padding-bottom: 8px; margin-top: 0px; margin-bottom: 0px; line-height: 26px;">Let's focus on this Version here. Different versions have different UUID generation rules.</p> <p style="padding-top: 8px; padding-bottom: 8px; margin-top: 0px; margin-bottom: 0px; line-height: 26px;">The corresponding meanings of five different Version values (refer to <a href="https://zh.wikipedia.org/wiki/%E9%80%9A%E7%94%A8%E5%94%AF%E4%B8%80%E8%AF%86%E5%88%AB%E7%A0%81" style="overflow-wrap: break-word; font-weight: bold; color: rgb(239, 112, 96); border-bottom: 1px solid rgb(239, 112, 96);"> Wikipedia's introduction to UUID </a>):</p> <ul style="margin-top: 8px; margin-bottom: 8px; padding-left: 25px;"> <li><section style="margin-top: 5px; margin-bottom: 5px; line-height: 26px; color: rgb(1, 1, 1);">** Version 1 **: UUID is generated based on time and node ID (usually MAC address);</section></li><li><section style="margin-top: 5px; margin-bottom: 5px; line-height: 26px; color: rgb(1, 1, 1);">** Version 2 **: UUID is generated based on identifier (usually group or user ID), time, and node ID;</section></li><li><section style="margin-top: 5px; margin-bottom: 5px; line-height: 26px; color: rgb(1, 1, 1);">** Version 3, Version 5 **: Version 5-Deterministic UUIDs are generated by hashing namespace identifiers and names;</section></li><li><section style="margin-top: 5px; margin-bottom: 5px; line-height: 26px; color: rgb(1, 1, 1);">** Version 4 **: UUID is generated using <a href="https://zh.wikipedia.org/wiki/%E9%9A%8F%E6%9C%BA%E6%80%A7" style="overflow-wrap: break-word; font-weight: bold; color: rgb(239, 112, 96); border-bottom: 1px solid rgb(239, 112, 96);">随机性</a> or <a href="https://zh.wikipedia.org/wiki/%E4%BC%AA%E9%9A%8F%E6%9C%BA%E6%80%A7" style="overflow-wrap: break-word; font-weight: bold; color: rgb(239, 112, 96); border-bottom: 1px solid rgb(239, 112, 96);">伪随机性</a>.</section></li></ul> <p style="padding-top: 8px; padding-bottom: 8px; margin-top: 0px; margin-bottom: 0px; line-height: 26px;">The following is an example of a UUID generated under Version 1:</p> <figure style="margin-top: 10px; margin-bottom: 10px; display: flex; flex-direction: column; justify-content: center; align-items: center;"><img src="https://guide-blog-images.oss-cn-shenzhen.aliyuncs.com/github/javaguide/system-design/distributed-system/version1-uuid.png" alt=" Sample UUID generated under Version 1 " style="display: block; margin-right: auto; margin-left: auto; max-width: 100%;"><figcaption style="margin-top: 5px; text-align: center; color: #888; font-size: 14px;"> Sample UUID generated under Version 1 </figcaption></figure> <p style="padding-top: 8px; padding-bottom: 8px; margin-top: 0px; margin-bottom: 0px; line-height: 26px;">The version of the UUID generated by the <code style="font-size: 14px; overflow-wrap: break-word; padding: 2px 4px; border-radius: 4px; margin-right: 2px; margin-left: 2px; background-color: rgba(27, 31, 35, 0.05); font-family: &quot;Operator Mono&quot;, Consolas, Monaco, Menlo, monospace; word-break: break-all; color: rgb(239, 112, 96);">randomUUID()</code> method of <code style="font-size: 14px; overflow-wrap: break-word; padding: 2px 4px; border-radius: 4px; margin-right: 2px; margin-left: 2px; background-color: rgba(27, 31, 35, 0.05); font-family: &quot;Operator Mono&quot;, Consolas, Monaco, Menlo, monospace; word-break: break-all; color: rgb(239, 112, 96);">UUID</code> in the JDK defaults to 4.</p> <pre><code style="overflow-x: auto; padding: 16px; color: rgb(171, 178, 191); background: rgb(40, 44, 52); display: -webkit-box; font-family: &quot;Operator Mono&quot;, Consolas, Monaco, Menlo, monospace; border-radius: 0px;">UUID&nbsp;uuid&nbsp;=&nbsp;UUID.randomUUID();<br><span style="color: #c678dd; line-height: 26px;">int</span>&nbsp;version&nbsp;=&nbsp;uuid.version();<span style="color: #5c6370; font-style: italic; line-height: 26px;">//&nbsp;4</span><br></code></pre> <p style="padding-top: 8px; padding-bottom: 8px; margin-top: 0px; margin-bottom: 0px; line-height: 26px;">In addition, Variant also has four different values, which correspond to different meanings. I won't introduce it here. It seems that I don't need much attention at ordinary times.</p> <p style="padding-top: 8px; padding-bottom: 8px; margin-top: 0px; margin-bottom: 0px; line-height: 26px;">When you need to use it, just look at Wikipedia's introduction to UUID Variant.</p> <p style="padding-top: 8px; padding-bottom: 8px; margin-top: 0px; margin-bottom: 0px; line-height: 26px;">From the above introduction, it can be seen that UUID can guarantee uniqueness, because its generation rules include MAC address, timestamp, Namespace, random or pseudo-random number, time series and other elements, and UUID generated by computer based on these rules will definitely not be repeated.</p> <p style="padding-top: 8px; padding-bottom: 8px; margin-top: 0px; margin-bottom: 0px; line-height: 26px;">Although UUID can be globally unique, we rarely use it.</p> <p style="padding-top: 8px; padding-bottom: 8px; margin-top: 0px; margin-bottom: 0px; line-height: 26px;">For example, it is very inappropriate to use UUID as the primary key of MySQL database:</p> <ul style="margin-top: 8px; margin-bottom: 8px; padding-left: 25px;"> <li><section style="margin-top: 5px; margin-bottom: 5px; line-height: 26px; color: rgb(1, 1, 1);">The database primary key should be as short as possible, while UUID consumes a large storage space (32 strings, 128 bits).</section></li><li><section style="margin-top: 5px; margin-bottom: 5px; line-height: 26px; color: rgb(1, 1, 1);">UUID is out of order. Under InnoDB engine, the disorder of database primary key will seriously affect database performance.</section></li></ul> <p style="padding-top: 8px; padding-bottom: 8px; margin-top: 0px; margin-bottom: 0px; line-height: 26px;">Finally, let's briefly analyze ** Advantages and disadvantages of UUID ** (which may be asked during the interview!) :</p> <ul style="margin-top: 8px; margin-bottom: 8px; padding-left: 25px;"> <li><section style="margin-top: 5px; margin-bottom: 5px; line-height: 26px; color: rgb(1, 1, 1);">** Advantages **: The build is fast and easy to use</section></li><li><section style="margin-top: 5px; margin-bottom: 5px; line-height: 26px; color: rgb(1, 1, 1);">** Disadvantages **: Large storage consumption (32 strings, 128 bits), unsafe (the algorithm of generating UUID based on MAC address will cause MAC address leakage), disordered (non-self-increasing), no specific business meaning, and need to solve the problem of duplicate ID (when the machine time is wrong, it may lead to duplicate ID)</section></li></ul> <h4 style="margin-top: 30px; margin-bottom: 15px; font-weight: bold; font-size: 18px;"><span style="display: none;"></span>Snowflake (Snowflake algorithm)<span style="display: none;"></span></h4> <p style="padding-top: 8px; padding-bottom: 8px; margin-top: 0px; margin-bottom: 0px; line-height: 26px;">Snowflake is Twitter's open source distributed ID generation algorithm. Snowflake consists of 64-bit binary numbers, which are divided into several parts, and each part stores data with specific meanings:</p> <ul style="margin-top: 8px; margin-bottom: 8px; padding-left: 25px;"> <li><section style="margin-top: 5px; margin-bottom: 5px; line-height: 26px; color: rgb(1, 1, 1);">** The 0 th bit **: Sign bit (identifying plus or minus), always 0, no use, don't worry about it.</section></li><li><section style="margin-top: 5px; margin-bottom: 5px; line-height: 26px; color: rgb(1, 1, 1);">** Position 1 ~ 41 **: A total of 41 bits, used to denote a timestamp, in milliseconds, that lasts 2 ^ 41 milliseconds (approximately 69 years)</section></li><li><section style="margin-top: 5px; margin-bottom: 5px; line-height: 26px; color: rgb(1, 1, 1);">** Bits 42 ~ 52 **: There are 10 digits in total. Generally speaking, the first 5 digits represent the machine room ID, and the last 5 digits represent the machine ID (which can be adjusted according to the actual situation in actual projects). In this way, you can distinguish the nodes of different clusters/computer rooms.</section></li><li><section style="margin-top: 5px; margin-bottom: 5px; line-height: 26px; color: rgb(1, 1, 1);">** Bits 53 ~ 64 **: A total of 12 bits, used to denote the serial number. The serial number is self-increment, which represents the maximum number of IDs that a single machine can generate per millisecond (2 ^ 12 = 4096), which means that a single machine can generate up to 4096 unique IDs per millisecond.</section></li></ul> <figure style="margin-top: 10px; margin-bottom: 10px; display: flex; flex-direction: column; justify-content: center; align-items: center;"><img src="https://guide-blog-images.oss-cn-shenzhen.aliyuncs.com/github/javaguide/system-design/distributed-system/snowflake-distributed-id-schematic-diagram.png" alt=" Schematic diagram of Snowflake " style="display: block; margin-right: auto; margin-left: auto; max-width: 100%;"><figcaption style="margin-top: 5px; text-align: center; color: #888; font-size: 14px;"> Schematic diagram of Snowflake </figcaption></figure> <p style="padding-top: 8px; padding-bottom: 8px; margin-top: 0px; margin-bottom: 0px; line-height: 26px;">If you want to use the Snowflake algorithm, you generally don't need to recreate the wheel yourself. There are many open source implementations based on Snowflake algorithm, such as Leaf of Meituan and UidGenerator of Baidu, and these open source implementations optimize the original Snowflake algorithm.</p> <p style="padding-top: 8px; padding-bottom: 8px; margin-top: 0px; margin-bottom: 0px; line-height: 26px;">In addition, in actual projects, we will generally transform the Snowflake algorithm, and the most common one is to add business type information to the ID generated by Snowflake algorithm.</p> <p style="padding-top: 8px; padding-bottom: 8px; margin-top: 0px; margin-bottom: 0px; line-height: 26px;">Let's look at the advantages and disadvantages of Snowflake algorithm:</p> <ul style="margin-top: 8px; margin-bottom: 8px; padding-left: 25px;"> <li><section style="margin-top: 5px; margin-bottom: 5px; line-height: 26px; color: rgb(1, 1, 1);">** Advantages **: The generation speed is relatively fast, and the generated ID increases in an orderly manner, which is relatively flexible (the Snowflake algorithm can be simply modified, such as adding business ID)</section></li><li><section style="margin-top: 5px; margin-bottom: 5px; line-height: 26px; color: rgb(1, 1, 1);">** Disadvantages **: Duplicate IDs need to be resolved (time-dependent, which can result in duplicate IDs if the machine time is wrong).</section></li></ul> <h3 style="margin-top: 30px; margin-bottom: 15px; font-weight: bold; font-size: 20px;"><span style="display: none;"></span>Open source framework<span style="display: none;"></span></h3> <h4 style="margin-top: 30px; margin-bottom: 15px; font-weight: bold; font-size: 18px;"><span style="display: none;"></span>UidGenerator (Baidu)<span style="display: none;"></span></h4> <p style="padding-top: 8px; padding-bottom: 8px; margin-top: 0px; margin-bottom: 0px; line-height: 26px;"><a href="https://github.com/baidu/uid-generator" style="overflow-wrap: break-word; font-weight: bold; color: rgb(239, 112, 96); border-bottom: 1px solid rgb(239, 112, 96);"> Urine generator </a> is a unique ID generator based on Snowflake, which is open source by Baidu.</p> <p style="padding-top: 8px; padding-bottom: 8px; margin-top: 0px; margin-bottom: 0px; line-height: 26px;">However, UidGenerator has improved on Snowflake, and the unique ID generated is composed as follows.</p> <figure style="margin-top: 10px; margin-bottom: 10px; display: flex; flex-direction: column; justify-content: center; align-items: center;"><img src="https://guide-blog-images.oss-cn-shenzhen.aliyuncs.com/github/javaguide/system-design/distributed-system/uidgenerator-distributed-id-schematic-diagram.png" alt="" style="display: block; margin-right: auto; margin-left: auto; max-width: 100%;"></figure> <p style="padding-top: 8px; padding-bottom: 8px; margin-top: 0px; margin-bottom: 0px; line-height: 26px;">As you can see, the composition of the unique ID generated by the original Snowflake algorithm is different. Moreover, we can customize the above parameters.</p> <p style="padding-top: 8px; padding-bottom: 8px; margin-top: 0px; margin-bottom: 0px; line-height: 26px;">The UidGenerator official documentation describes the following:</p> <figure style="margin-top: 10px; margin-bottom: 10px; display: flex; flex-direction: column; justify-content: center; align-items: center;"><img src="https://guide-blog-images.oss-cn-shenzhen.aliyuncs.com/github/javaguide/system-design/distributed-system/uidgenerator-introduction-official-documents.png" alt="" style="display: block; margin-right: auto; margin-left: auto; max-width: 100%;"></figure> <p style="padding-top: 8px; padding-bottom: 8px; margin-top: 0px; margin-bottom: 0px; line-height: 26px;">Since 18 years later, UidGenerator has been basically no longer maintained, and I will not introduce it too much here. For those who want to know more, you can see <a href="https://github.com/baidu/uid-generator/blob/master/README.zh_cn.md" style="overflow-wrap: break-word; font-weight: bold; color: rgb(239, 112, 96); border-bottom: 1px solid rgb(239, 112, 96);"> Official introduction of UidGenerator </a>.</p> <h4 style="margin-top: 30px; margin-bottom: 15px; font-weight: bold; font-size: 18px;"><span style="display: none;"></span>Leaf (US Mission)<span style="display: none;"></span></h4> <p style="padding-top: 8px; padding-bottom: 8px; margin-top: 0px; margin-bottom: 0px; line-height: 26px;">** <a href="https://github.com/Meituan-Dianping/Leaf" style="overflow-wrap: break-word; font-weight: bold; color: rgb(239, 112, 96); border-bottom: 1px solid rgb(239, 112, 96);">Leaf</a> ** is an open source distributed ID solution of Meituan. The name of this project Leaf originated from the words of German philosopher and mathematician Leibniz: "There are no two identical leaves in the world" (There are no two identical leaves in the world). This name is really good, and it tastes like a literary youth!</p> <figure style="margin-top: 10px; margin-bottom: 10px; display: flex; flex-direction: column; justify-content: center; align-items: center;"><img src="https://img-blog.csdnimg.cn/20210422145229617.png" alt="" style="display: block; margin-right: auto; margin-left: auto; max-width: 100%;"></figure> <p style="padding-top: 8px; padding-bottom: 8px; margin-top: 0px; margin-bottom: 0px; line-height: 26px;">Leaf provides two modes, ** Segment mode ** and ** Snowflake (Snowflake algorithm) **, to generate distributed IDs. Moreover, it supports double-numbered segments and solves the clock callback problem of snowflake ID system. However, the solution to the clock problem needs to be weakly dependent on Zookeeper.</p> <p style="padding-top: 8px; padding-bottom: 8px; margin-top: 0px; margin-bottom: 0px; line-height: 26px;">Leaf was born mainly to solve the problems of various and unreliable methods for generating distributed IDs in various business lines of Meituan.</p> <p style="padding-top: 8px; padding-bottom: 8px; margin-top: 0px; margin-bottom: 0px; line-height: 26px;">Leaf improves on the original number segment mode, for example, it adds double-numbered segments here to avoid blocking the thread requesting to obtain ID when obtaining the number segment. To put it simply, before I finished one number segment, I took the initiative to get the next number segment in advance (the picture comes from the official article of Meituan: <a href="https://tech.meituan.com/2017/04/21/mt-leaf.html" style="overflow-wrap: break-word; font-weight: bold; color: rgb(239, 112, 96); border-bottom: 1px solid rgb(239, 112, 96);"> [Leaf-Meituan Review Distributed ID Generation System] </a>).</p> <figure style="margin-top: 10px; margin-bottom: 10px; display: flex; flex-direction: column; justify-content: center; align-items: center;"><img src="https://img-blog.csdnimg.cn/20210422144846724.png" alt="" style="display: block; margin-right: auto; margin-left: auto; max-width: 100%;"></figure> <p style="padding-top: 8px; padding-bottom: 8px; margin-top: 0px; margin-bottom: 0px; line-height: 26px;">According to README introduction of the project, based on 4C8G VM, it is called by RPC mode of the company, and the QPS pressure measurement result is nearly 5w/s, TP999 1ms.</p> <h4 style="margin-top: 30px; margin-bottom: 15px; font-weight: bold; font-size: 18px;"><span style="display: none;"></span>Tinyid (Didi)<span style="display: none;"></span></h4> <p style="padding-top: 8px; padding-bottom: 8px; margin-top: 0px; margin-bottom: 0px; line-height: 26px;"><a href="https://github.com/didi/tinyid" style="overflow-wrap: break-word; font-weight: bold; color: rgb(239, 112, 96); border-bottom: 1px solid rgb(239, 112, 96);">Tinyid</a> is a unique ID generator based on database number segment schema.</p> <p style="padding-top: 8px; padding-bottom: 8px; margin-top: 0px; margin-bottom: 0px; line-height: 26px;">The principle of database number segment mode has been introduced above. ** What are the highlights of Tinyid? **</p> <p style="padding-top: 8px; padding-bottom: 8px; margin-top: 0px; margin-bottom: 0px; line-height: 26px;">To figure this out, let's first look at a simple schema based on the database number segment schema. (Image from Tinyid's official wiki: <a href="https://github.com/didi/tinyid/wiki/tinyid%E5%8E%9F%E7%90%86%E4%BB%8B%E7%BB%8D" style="overflow-wrap: break-word; font-weight: bold; color: rgb(239, 112, 96); border-bottom: 1px solid rgb(239, 112, 96);"> Introduction to Tinyid Principle </a>)</p> <figure style="margin-top: 10px; margin-bottom: 10px; display: flex; flex-direction: column; justify-content: center; align-items: center;"><img src="https://oscimg.oschina.net/oscnet/up-4afc0e45c0c86ba5ad645d023dce11e53c2.png" alt="" style="display: block; margin-right: auto; margin-left: auto; max-width: 100%;"></figure> <p style="padding-top: 8px; padding-bottom: 8px; margin-top: 0px; margin-bottom: 0px; line-height: 26px;">In this architecture pattern, we request a unique ID from the numberer service via an HTTP request. The load balancing router sends our request to one of the tinyid-servers.</p> <p style="padding-top: 8px; padding-bottom: 8px; margin-top: 0px; margin-bottom: 0px; line-height: 26px;">What's wrong with this scheme? In my opinion (Tinyid's official wiki is also introduced), it is mainly caused by the following two questions:</p> <ul style="margin-top: 8px; margin-bottom: 8px; padding-left: 25px;"> <li><section style="margin-top: 5px; margin-bottom: 5px; line-height: 26px; color: rgb(1, 1, 1);">In the case of obtaining a new number segment, the program is slow to obtain a unique ID.</section></li><li><section style="margin-top: 5px; margin-bottom: 5px; line-height: 26px; color: rgb(1, 1, 1);">It is necessary to ensure high availability of DB, which is troublesome and resource-consuming.</section></li></ul> <p style="padding-top: 8px; padding-bottom: 8px; margin-top: 0px; margin-bottom: 0px; line-height: 26px;">In addition, HTTP calls also have network overhead.</p> <p style="padding-top: 8px; padding-bottom: 8px; margin-top: 0px; margin-bottom: 0px; line-height: 26px;">The principle of Tinyid is relatively simple, and its architecture is shown in the following figure:</p> <figure style="margin-top: 10px; margin-bottom: 10px; display: flex; flex-direction: column; justify-content: center; align-items: center;"><img src="https://oscimg.oschina.net/oscnet/up-53f74cd615178046d6c04fe50513fee74ce.png" alt="" style="display: block; margin-right: auto; margin-left: auto; max-width: 100%;"></figure> <p style="padding-top: 8px; padding-bottom: 8px; margin-top: 0px; margin-bottom: 0px; line-height: 26px;">Compared with the simple architecture scheme based on the database number segment schema, Tinyid scheme mainly makes the following optimizations:</p> <ul style="margin-top: 8px; margin-bottom: 8px; padding-left: 25px;"> <li><section style="margin-top: 5px; margin-bottom: 5px; line-height: 26px; color: rgb(1, 1, 1);">** Double segment cache **: In order to avoid the slow speed of obtaining unique ID in the case of obtaining new number segment. When the number segment in Tinyid is used to a certain extent, it will load the next number segment asynchronously to ensure that there are always available number segments in memory.</section></li><li><section style="margin-top: 5px; margin-bottom: 5px; line-height: 26px; color: rgb(1, 1, 1);">** Adding multi-db support **: Multiple DBs are supported, and each DB can generate a unique ID, which improves availability.</section></li><li><section style="margin-top: 5px; margin-bottom: 5px; line-height: 26px; color: rgb(1, 1, 1);">** Add tinyid-client **: Pure local operation, no HTTP request consumption, significant performance and availability improvements.</section></li></ul> <p style="padding-top: 8px; padding-bottom: 8px; margin-top: 0px; margin-bottom: 0px; line-height: 26px;">The advantages and disadvantages of Tinyid will not be analyzed here, but can be known by combining the advantages and disadvantages of database number segment mode and the principle of Tinyid.</p> <h2 style="margin-top: 30px; margin-bottom: 15px; font-weight: bold; border-bottom: 2px solid rgb(239, 112, 96); font-size: 1.3em;"><span style="display: none;"></span><span style="display: inline-block; background: rgb(239, 112, 96); color: rgb(255, 255, 255); padding: 3px 10px 1px; border-top-right-radius: 3px; border-top-left-radius: 3px; margin-right: 3px;">Summarize</span><span style="display: inline-block; vertical-align: bottom; border-bottom: 36px solid #efebe9; border-right: 20px solid transparent;"> </span></h2> <p style="padding-top: 8px; padding-bottom: 8px; margin-top: 0px; margin-bottom: 0px; line-height: 26px;">Through this article, I have basically summarized the most common distributed ID generation schemes.</p> <p style="padding-top: 8px; padding-bottom: 8px; margin-top: 0px; margin-bottom: 0px; line-height: 26px;">In addition to the methods described above, middleware like ZooKeeper can also help us generate unique IDs. ** Without silver bullets, we must choose the most suitable scheme according to the actual project. **</p></section>