@fluidframework/id-compressor (英语)

一个库生成一个网络中多个会话对任意非碰撞版本4 UUID("稳定的ID")的少量表示. 该计划使分布式应用能够利用UUID的全球独特性保证,同时保持小整数的性能优势.

使用 Fluid 框架库

对于依赖流体框架库的公共API,我们建议 ^ (caret)版本范围. 例如,使用 ^1.3.4。 。 。 .

依赖不稳定的API,例如: beta API,我们推荐一个更具限制性的版本范围. 例如,使用一个 ~ 版本范围.

安装

运行此命令以安装软件包 :

npm i @fluidframework/id-compressor

从此软件包导入

此软件包使用 packet.json 导出 通过支持级别将API分离. 有关支助保障的信息改为: API 支持级别。 。 。 .

导入 public API 从 @fluidframework/id-compressor。 。 。 .

导入 legacy API 从 @fluidframework/id-compressor/legacy。 。 。 .

API 文档

读取 @fluidframework/id-compressor (英语) API 文档 https://fluidframework.com/docs/apis/id-compressor (中文(简体) )。 。 。 .

导言

这个 流体框架 ID 压缩器 (包装) @fluidframework/id-compressor)提供分布式独特的ID生成和压缩方案. 它允许多个客户端(“会话”)生成 稳定身份证 (v4 UUIDs),是全球独有的,同时代表它们在当地作为小整数. 这在内存和存储效率以及比使用完整的UUID字符串更快的浏览(例如使用压缩的ID作为密钥)方面产生了巨大的好处. 压缩机与集中命令服务(Fluid runtime的总命令广播)同步工作,指定每个生成的ID a 最终 共享内独有的数字值 文档 (协作会议).

每个客户端会话使用压缩机同步生成ID而不协调,可能使用临时 届会-当地形式 (负整数),只在该客户端内独有. 后来,当定义ID的操作被服务排序时,ID被分配为永久的 最后形式 (非负整数)在文档中具有全球独有性. ID 的数字 签名 创建时的(负值或非负值)取决于最终值是否立即被指定(这又取决于分配者当时的状况) — — 一旦创建,ID的形式在该会话的上下文中保持稳定,不会隐含地改变. 压缩器的 API 提供了明确的正常化功能,用于在 ID 之间转换 会话空间 (当地视图)和 行动空间 (最后意见),视需要.

关键概念

会议和文件

A 类 第二届会议 指单个ID压缩机(通常是应用程序的一个客户端或一个组件)的独特标识符. 每个会话都有自己的本地ID序列. 即使一个压缩机被保存并恢复(例如用于下线使用),只要它保留了相同的会话标识符,它就被认为是相同的逻辑会话. 所有在同一合作文档上运行的压缩机在定稿后共享相同的ID空间,但在定稿前它们可能使用会话区分的重叠本地ID.

A 类 文档 在这方面,收集在某个流体容器上合作的所有会议所产生的所有身份证。 压缩的ID只在单一文档范围内独有. (以其完整的UUID形式,它们仍然具有全球的独特性,但小的整数表示是: 没有 打算通过不同文件进行比较或合并。 )

稳定身份证和压缩身份证

A 类 稳定标识 是作为真正全球唯一标识符的完整的128位UUID字符串。 ID压缩机以决定式,低调的方式生成稳定的ID:每会话在开始时选择随机128位从UUID起步,然后通过递增一个计数器(主要是产生相继的UUID)来生成后续的UUID. 这种策略在生成的ID中会大大地减少 en(使其更可压缩并更容易存储)而同时 提高碰撞阻力 相对完全随机生成。 事实上,通过从随机基起分配每个会话中一个独特的UUID空间块,任意两个会话产生同一个UUID的概率在天文上是很低的,甚至低于所有ID都是纯粹随机的,因为只有最初的UUID选择是随机的,之后来自同一会话的ID保证了独特的递增.

A 类 压缩 ID 是文档中使用的稳定ID的小整数表示。 压缩机处理两种压缩ID:

• 会话空间标识 : 身份证明 会话空间 以当地形式出现。 对于创建ID的会话,这意味着如果ID尚未定稿,但仍以本地形式存在(在当前执行中以负数表示),并且如果它是以最终任务创建的,则将是最终数字(非负数)。 对其它会话来说, 他们没有创建的ID的会话空间ID将会作为最后的编号出现, 或根本不存在于本地空间中。 简言之,在会话空间中,每个压缩机都尽可能以本地形式看到自己的ID. 应用程序代码在内部提及ID时应当使用会话-空格ID,因为这些ID在压缩器的寿命上是稳定的,并避免本地 vs 最终形式之间的混淆.
• Op- 空格 ID : 身份证明 行动空间 {\fn黑体\fs22\bord1\shad0\3ahbe\4ah00\fscx67\fscy66\2chffffff\3ch808080}最正常的状态 最终 形式已知。 这意味着,任何具有最后(全文件)任务身份的身份证将由该最后(非负)号码代表。 只有尚未按顺序排列的ID才会以会话本地形式出现(而只有与创建会话同时出现的ID才有意义). 在序列化ID用于通信(ops)或持久性时,Op-spaceID被使用,因为它们尽可能接近最终结果,并且经常需要接收方的最小或没有进一步正常化. 然而,op-space ID如果客户端在命令前发送,仍可能包含未定稿的(会话范围)ID;因此,任何包含op-space ID的操作必须注明发端会话,以便接收者能够正确解释这些ID.

重要内容: 压缩机的执行用途 负整数 代表会议当地身份证和 非负整数 代表最终身份证明。 例如,当客户端生成服务器尚未订购的新ID时,它可能在该会话中被代表为-1,-2等. 一旦最终确定,该ID将有一个非负整数(如0,1,42等)作为其最终形式. 一个给定的压缩器在其一生中总是会以相同的会话空间(如–2)的数值来指代该ID,它不会暗示会"滑入"到最后编号. 为了避免出错,在不实现常态化的情况下不应将两个空格相混合:例如,不要使用op空间ID来索引一个按会话空间ID键的数据结构(而且除了串行运输外,从不使用op空间ID). 压缩机提供常态API,以便在需要时在这些空格之间转换.

ID 分配和生命周期国家机器

在高水平上,ID压缩机会在所有会话中将小整数的无限宇宙通过 分组 的正整数空间。 这种分割是动态的,由操作的顺序所驱动. 每个会话都可以使用负位符独立生成ID,从而可以立即, 同步创建 新的身份证,无需等待协调。 后来,当服务器分配命令时,会话会被授予一组正ID(一个集群)来覆盖这些创建. 然后,该会话之后的创建可以直接使用这些保留的正ID(不需要占位符),直到块被用尽. 这样,会话在使用预先分配的最终ID(如有可用)和使用本地负ID(当它们耗尽预先分配的空间时)之间交替进行,这取决于确认的时间.

状态机器概览 : 系统生成的每个ID都经过以下状态或过渡:

1. 生成(会议-当地): 当通过 generateCompressedId() 在压缩机上,它属于压缩机的本地会话。 如果当前会议 没有可用的保留最终ID,新的ID将被分配到一个 本地( 负) ID这意味着,身份证只有在该届会议期间才具有独特性,并有待最后确定。 如果会话已经保留了一组未使用能力的最后ID(来自先前确定的范围),则压缩机将立即指定下一个可用的新ID 最终(非负)ID 在那个集群。 在这种情况下,身份证的最终价值是已知的 事前说明。压缩器可以安全地做到这一点,因为集群是通过一个先行操作获得的,在使用这些最终ID的操作之前,该操作会被排序,从而保持一致性.

2. 顺序( 定稿):在生成一个或多个ID(有些可能以本地形式)后,客户的下一个操作将包括: 创建范围 新的身份证 运行时间内部调用 takeNextCreationRange() 以获取一批新产生的身份证及其细节。 这个范围包含会话的ID上下文(会话ID和相接的生成索引范围,外加集群大小提示),发送到服务器后转发到所有客户端. 为了保持一致性,必须按压缩机的顺序发送范围。 在排序时,每个客户端的ID压缩机 定稿 范围 通过 finalizeCreationRange()组合 最后身份证号码 (a) 如果一个会话不存在,或者如果可能的话,将一个现有的会话群,并且将每个会话本地ID的分布范围映射到特定的最终ID. 在此之后,这些身份证具有永久的证件-唯一数字身份.

3. 定稿(文件独有): 身份证定稿后 最后压缩的ID 所有参与者都知道,并将用于需要全文件独有性的所有场合(例如业务、存储、其他客户的当地状态)。 ID压缩机保证给定的会话本地ID总是映射到所有客户端的同一个最终ID. 它还保证与身份证有关的稳定的UUID在整个期间保持不变。 换句话说,在定稿后,每个人都同意绘制地图:例如,会话QQs local ID – 1对应最终ID 100(这又对应特定的UUID). 创建 ID 的本地会话仍然可以在会话空间 – 1 中引用它, 但是它也可以通过实现 op 空间的正常化来获得 100 。 其它会议则会称为100个.

因为每一会都保留毗连性 分组 ,在最后确定范围时,由不同会话产生的最终ID是 软化 (分出)过数行. 例如,A会话可能会得到一组最终ID [0..99] 其首个100个ID, B 会话然后得到 [100..199] 身份证等,取决于订单。 这些任务都是单调的;没有两个会话会产生相同的最终ID,每个会话组由一会话拥有. 一段时间以来,一个会话可能有多个集群(如果它在不同时间生成ID,与其他会话的代相接),形成该会话的 集群链。 。 。 .

集群链 : A 类 分组 是一个为会话预留的最后ID的相接范围,由基准的最后ID和一个能力(该范围内的ID数量)代表. 一个会话的集群链是指定给该会话的所有集群的顺序,顺序是它们创建的顺序(这也是该会话最后ID的上升顺序). 集群链使得从会话本地ID到最终ID的高效映射成为可能:在一个集群内,映射是一个抵消. 例如,如果会话的A组拥有最终的ID 0和容量为5的基数,并且是第一个组数(因此是本地的ID-1),那么A组的本地的ID数 -1, -2, -3, -4, -5 对应最终的ID 0, 1, 2, 3, 4 页:1 如果A会话后来得到第二个集群,其中基底为ID 10,容量为5,其中基底为本地ID -6(指A在之前生成了5个ID),那么A的 -6, -7, -8, -9, -10 将映射到最后的ID 10, 11, 12, 13, 14 页:1 因此,每个集群只存储两个整数 — — 它的起始最终ID和大小 — — 这是一个非常紧凑的表示. 如果一个会话本地ID,压缩器可以确定它属于哪个集群的范围(通过集群链上的二进制搜索)并用相抵计算最终ID,或者确定它是否超出最后敲定的本地ID,则尚未定稿. 这种集群结构是压缩机空间效率和速度的核心.

为什么是集群? 使用集群链有多种用途:

• 独特和硬化: 通过为每个会话分配最后ID空间的相分离块,方案避免了每个ID协调 — — 届会不会踩到对方的ID,因为每次会话使用不同的数字范围. 最后的身份证基本上 软化 由会话所有权.
• 压缩映射 : 压缩机不为每个ID存储映射,而只需要存储集群描述符. 如果一个会话产生一个大序列的ID,它们很可能会掉入几个相接的集群. 每组包含许多ID,因此内存管理费用较低(每组有2个数字).
• 当地无惩罚的一代: 负会话- 本地ID 允许应用程序立即刻出未限制数量的新ID 。 集群机制确保一旦确认这些ID,它们就会被折叠成最后数字线相接的块. 无论创建了多少身份证,最后敲定步骤的费用都是一样的.
• Eager 定稿 : 如果一个会话已经有一个带空位的已分配组, 新ID可以完全跳过占位符阶段 - 他们是 创建时急切地指定了最后的ID在集群链中,这种ID从一开始就被标记为最终的(压缩器知道“本次会话的ID编号N最终将是最终的X”而不等待)。 这大大提高了快速ID生成的效率,因为经过一次获得集群的往返旅行后,接下来的许多ID不需要额外的协调费用.

示例 - ID 生成工作流程 : 考虑一个简单的方案,包括两个客户会议(A和B),以说明本地和最后的ID任务:

• 步骤1: 会议 A通过呼叫创建第一个ID generateCompressedId()。对于 A 尚未存在集群,因此指定了会话本地ID -1号同样,A创建了第二个身份,获得 -2号。这些负的ID在A内部是独一无二的,但是会话B也可以同时在自己的空间中创建一个ID-1(没有冲突,因为B是不同的会话).

• 步骤2: 会议 一个行动准备宣布新的身份 流体运行时间呼叫 takeNextCreationRange() 在 A 的压缩器上,该压缩器返回一个描述两个新ID的范围(会话 A 的ID, 第一代计数 = 1,计数 = 2等). 这已包括在A的操作中并发送给服务器。 服务器排序此操作( 确保所有客户端都按相同的顺序处理) .

• 步骤3: 当A的操作被排序时,每个客户(包括A本身)都会打电话 finalizeCreationRange() 与范围。 每边的ID压缩器分配A 第一组假设执行中选择一个大小组,例如A5。 如果该文件中尚未分配最后的ID, A 的集群可能在最后的ID开始 0 个。该组被记录为属于A类会议,具有基准最终ID 0和能力5。 两张身份证已经敲定:A - 1 — 0 个 财务报告和审定财务报表 -2 - 1个. 该组仍有3个未使用的空档(最终ID 2, 3, 4),预留给A的未来ID.

• 步骤4: 会议 一个生成第三个ID。 现在 A 的压缩器找到一个带有空闲空间的现有集群( 保留了 3 个插槽) 。 因此,这个 急切地指派 下一个最后的ID: 新ID 获得最后的ID 2个 立即(而不是负数). 同样,来自A的第四和第五身份证也会获得最后身份证 3个 财务报告和审定财务报表 页:1. 此时,A的集群已经填满(其所有5个保留的ID0–4被使用). Session A 的压缩器还没有需要发送另一个范围,因为这些范围已经保留在第一组中.

• 步骤5: 同时,假设会议 B还生成了一些ID,并在它的操作被排序时获得了它的第一组. 也许B的第一个组从最后的ID开始 页:1 装有5个容量(涵盖5-9个容量)。 如果B创建了一个ID并发送,B的 -1号 将映射到最后 页:1,而B现在有最后的ID 6–9的储备,用于更多的创作.

• 步骤6: 会议 A现在生成第六个ID. A的第一个集群已经耗尽,由于另一个会话(B)已经分配了ID空间的下一块(上到9),A无法将之前的集群相接地延伸. 因此,A的第六身份证被分配到 会话本地编号 - 6 (负面)在创造。 运行时间在后续的操作中为这个新的ID发送了另一个创建范围.

• 步骤7: A的压缩机将完成新的范围。 由于A的前一组(0-4)不是全球订单中的最后一组(B有5-9),压缩机分配 一个新的群组 (单位:千美元) 第二组可能从最后的ID开始 10个 (9后有下册). 该组的能力可能还是5个(涵盖10-14个)。 现在A的身份证 -6号 最终确定为 10个。如果A生成更多的ID(第7个、第8个等),其中最多4个可以立即指定最后ID11、12、13、14,而无需前往当地.

这个例子说明会话 A 如何 集群链 由两组组成:一组跨越最后ID 0-4,另一组跨越10-14。 B会话有自己的分组(5-9). 每个会话的本地ID从第一集群的 - 1 开始, 并持续到负( A 使用 - 1 到 - 5 用于前5 个ID, 然后 - 6 用于下一个集群的第一 个ID等) 。 在所有情况下 第一个集群的基础本地化Id是 -1 (按设计) finalizeCreationRange,如果不是,则会出错。 每个组内的映射都是直截了当的线性相抵,没有两个会话的最后ID范围重叠. 通过使用负ID,系统允许每场会议在空出保留空间时独立行动,并通过使用慷慨的集群保留和扩大,系统将需要这些独立行动的频率降到了最低限度.

API 概览和使用

ID压缩器提供了生成ID和在各种表达方式(会话空间,op空间,稳定ID)之间转换的方法:

• generateCompressedId(): 创建新的稳定 ID (UUID)并返回其压缩形式 会话空间返回时 SessionSpaceCompressedId 要么是负数(如果没有立即获得最后的ID),要么是上述非负数的最后ID(如果从现有集群中分配)。 无论哪种情况,压缩机内部都会为此生成一个新的UUID. 这个电话是 同步 并且总是成功为会话制作出独特的ID. 稳定的UUID可随时通过 decompress()生成是 O(1) 及时.

• takeNextCreationRange(): 收集自上次射程被取出以来产生的所有ID,并将其包装成 IdCreationRange 对象。 这包括会话的ID(sessionId),如果创建了任何ID,则描述第一个ID的生成指数,有多少ID(英语:count),请求的集群大小,以及属于会话本地的ID的跨度. Fluid运行时间在内部在准备包括新创建的ID在内的出行操作时使用这种方法. 应用程序开发者 无需直接调用 - 提交行动时由框架处理。 范围 必须 将按顺序发送; 称这将增加一个内部标记,以强制执行该命令.

• finalizeCreationRange(range: IdCreationRange): 将一系列ID(可以是远程会话或本地会话)纳入压缩机最终状态. 此调用将为指定的会话分配或更新集群 。 如果这是第一次看到会话Id,则将开始一个新的集群链(并且第一个集群的基础本地ID必须像内部检查的那样与-1一致). 如果会话已经存在集群链,压缩器将尝试 扩展上一组 如果可能,或创建新的集群。 具体地说,如果正在最后确定的范围能准确发现会议最后一组会议所剩位置 财务报告和审定财务报表 最后一组也是整个系统中最高的最终ID,压缩机将扩大集群容纳新ID的能力(可能还有一些额外的保留能力). 这是 集群扩展 优化:通过在安全时扩大最后一个集群,压缩机避免了ID空间被分解,并允许会话继续使用单个相接范围,从而减少未来本地ID的需求. 如果最后一组不能扩大(例如,另一组届会在全球之后),则为本届会议的新范围分配了一个新的分组。 在最后敲定后,所有客户都固定和一致地将这些会话当地身份证绘制成最后身份证。 这种方法在O(1)时间运行.

• decompress(id: SessionSpaceCompressedId): StableId: 将压缩的ID(在会话空间)转换回128位稳定的UUID字符串. 这适用于压缩器知道的任何压缩ID — — 无论是本地的负ID还是最终的ID。 如果ID是会话本地和负(不是最终的),压缩机仍然知道稳定的UUID,因为它是在创建时间生成的,并将通过计算一个从基会话UUID中简单的抵消而返回. 如果ID是最终的,它同样通过找到包含的集群并计算偏移来返回稳定的UUID. 解压缩为 O(log 最大 ()无, (中文(简体) ), 页:1(b) 在哪些方面 无 是最后空格中的组数,以及 页:1 是本地会话中本地ID的"运行"数量(相接的负ID生成,没有急切的决赛). 前者是解压最终空间ID的时间,而后者是负ID的时间(它会是O(1),但检查校正器错误).

• recompress(uncompressed: StableId): SessionSpaceCompressedId 财务报告和审定财务报表 tryRecompress(uncompressed: StableId): SessionSpaceCompressedId | undefined:这些API执行去压平的倒置 — 由于UUID稳定,它们试图为这个压缩器的会话空间找到其压缩的ID代表. 如果UUID是 最初由此压缩机生成 (或者在压缩器的集群记录中被其他识别),这将返回相应的会话-空格ID. 例如,如果你用这个会话所创建的稳定ID通过, recompress 将返回原先为它签发的同一种负ID(或最终ID)。 如果您通过另一个会话所创建的稳定ID, 而该会话已经定稿, 它将会返回最后的ID( 因为在本会话的空间里, 这是该ID的唯一形式) 。 如果压缩机根本不知道稳定的ID(这意味着这个压缩机在文件中的任何会话都没有意识到), tryRecompress 将返回 undefined 财务报告和审定财务报表 recompress 将投出一个错误。 这种情况仅仅表明UUID从未通过这种压缩方案引入过,例如,它可能是一个完全外部的ID或来自另一个文档.

• normalizeToOpSpace(id: SessionSpaceCompressedId): OpSpaceCompressedId: 将会话- 空格 ID 转换为 op 空格, 用于输出的 op 或其他序列化形式。 如果给定的身份证来自当地会议,并有最后的身份证(要么急于定稿,要么已经定稿),这将产生最后的身份证。 如果它来自当地会议, 且仍未定稿(一个负ID OpSpaceCompressedId 类型(基本相同的数值)。 如果传入的ID实际上已经是一个最终的ID(包括任何非本地会话-空格ID),那么它只是返回到没有改变的(已经正常化). 如果ID无效或压缩机未知(如果ID来自一个有效的来源,则不应发生),这种方法会抛出错误.

• normalizeToSessionSpace(id: OpSpaceCompressedId, originSessionId: SessionId): SessionSpaceCompressedId: 将 Op- space ID 加上它的发端会话转换为此压缩器的会话空间形式 。 在收到操作或读取持续数据时使用。 源代码SessionId告诉其上下文创建了ID的压缩机。 逻辑如下: 如果 id 是最终的ID(非负数),如果它属于本地会话中的任何一组,则压缩机检查。 如果它属于本地会话本身的集群链(指ID实际上由本会话创建并定稿),压缩器将查看该ID是否有本地形式. 如果确实如此(正常人知道它是作为本地创建的),它会返回本地的负ID. 如果它没有(这是本场会话的急切指定决赛), 它只会返回和SessionSpaceCompressedId相同的最终ID. 如果最后的ID不属于本地会话的集群,压缩机会检查它是否属于整个文档中分配到的最终ID的范围(以确保它不超过任何已知的ID). 如果它已经知道并且属于其他会话, 它会返回ID as-is(因为从这个会话的角度来看, 最终的ID是ID的唯一形式; 在这个压缩器中没有本地的负数) 。 另一方面,如果 id 如果源代码与压缩机的会话相匹配, 它只需验证ID是我们自己的(我们生成的)并返回它。 如果源代码SessionId是某个其他会话,压缩机会查看该会话的集群链,并尽可能将远程本地ID转换为最终的ID. 如果偏远的本地身份证在我们这个州还没有最终确定,那就意味着我们还没有为它处理过创建操作(如果收到操作异常) normalizeToSessionSpace 将会为“ 未知的操作空间 ID” 投出一个错误 。 在实践中,"流体运行时间"确保了创建范围在任何引用这些ID的操作之前得到处理,因此这种出轨情景通常被避免.

• serialize(withSession: boolean): 将压缩器状态导出为二进制/ 不可读格式进行存储 。 若为 withSession 包括当前会议未定稿状态(任何本地生成的ID尚未定稿,以及会议继续生成相继UUID的能力)。 这用于离线存储(例如快照本地客户端的状态),以便在重新装入时可以恢复精确的序列. 若为 withSession 错误,它只序列化最终状态(所有已知的集群和会话,但没有关于正在进行的本地生成的信息). 这适合于持续提供服务的摘要,因为摘要不与特定客户在建状况挂钩。 在去序列化上,可从序列化数据中重建出压缩机. 通常,流体容器的运行时间处理ID压缩机的序列化/去序化,作为文件摘要或加载的一部分。 应用程序开发者通常不直接调用,但维护者应确保对压缩机内部进行的任何修改保持与序列化格式的相容性(通过内部版本号转换出).

业绩和优化

ID压缩机是为协作运行时的高性能而设计的:

• 生成通量 : 创建新的ID( N)generateCompressedId)是一款O(1)操作——它只是增加一个计数器,并对集群的可用性做了几次检查. 即使身份证是本地的, 也立即生成.

• 压缩/减压: 在稳定的ID和压缩的ID之间转换依赖于通过会话集群或本地ID范围搜索. 由于集群按排序顺序被存储,而数字通常很少,并且由于本地ID范围被存储在一个紧凑的跑长格式中,这些转换非常快. 最糟糕的复杂情况是 O( log) 无),在其中 无 是最后空格中的组数.

• 内存效率 : 每个 分组 以四个整数加会话参考值的倒数存储:基底最终ID,容量,当前计数,和基底本地ID(与集群中第一个最终ID相关的本地ID). 这意味着即使数量非常多的身份证也可以用紧凑的表示. 例如,一个会话分配的10,000个ID带有默认的集群大小,最多将导致20个集群条目(视其他会话的交互操作情况而定,可能要少得多)。 这个 会话空间调节器 (追踪以本地身份创建的ID)存储运行长编码的生成指数范围,也很少使用内存(每个相接本地运行两个数字). 压缩机通过利用相继生成来避免为每个ID存储完整的UUUID:它可以通过抵消数学来存储单个基础UUID并生成其它.

• 分组保留和扩大: 默认行为是在第一个分配(如默认情况下的512个ID)上请求一个合理大的集群来分期摊还协调成本. 如果一个会话只产生几个ID,成本只是一个小集群. 如果它能产生很多,那么拥有一个大的集群就可以使大多数ID被急切地定稿. 这个 集群扩展 优化可以进一步提高效率:当一个会话正在积极生成ID,并且仍然处于全球ID空间的前列(其集群是全球顺序中最后的)时,最终确定一个新的范围将只是延长该集群的能力,而不是开始一个新的集群。 这意味着会话可以不间断地继续使用最终的ID. 只有当另一会话“ 超过” 时, 在您的集群结束后再分配 ID 时, 您需要一个新的集群, 从而需要另一个本地的 ID 。 在最好的情况下(一次生成所有ID或产生最多ID),一次生成可能会在很长一段时间内不使用一个扩大的集群. 在典型的多会情况下,每届会议将有一些分组,这些分组与其生成的ID与他人之间间隔的频率有关。 总的来说,这一策略确保了数字空间的近乎最优化的利用,并尽量减少了临时身份证的间接费用.

• 空间正常化成本: SessionSpaceNormalizer结构帮助确定给定的ID索引是作为本地还是最终分配的. 它以二进制搜索在排序范围列表中执行封装检查,该列表是 O(log) 页:1何处 页:1 是会话中本地ID区域的数目。 实际上, 页:1 是会话必须回到本地 ID 生成的次数 — — 基本上是集群边界的计数。 随着集群规模的扩大, 页:1 在大多数会议上,预计仍然很小(往往只有一届或只有几届)。 因此,在普通案件中,查验身份证或使身份证正常化是有效的经常时间。 规范化器只有在生成新的本地ID时才会被更新(simple application/相接到范围列表的末尾,O(1)).

附录:会话空间常态器(详细)

这个 会话空间调节器 是一个内部助手,负责记录以本地形式创建的会话。 其目的是回答下述问题:“....................... 无- 本会话产生的第一种ID,它最初是作为本地(负)ID还是作为最终(正)ID创建的?” 这对于压缩机正确规范会话空间和操作空间之间的ID至关重要. 例如,如果本地会话生成一个ID,并立即给予它一个最终号码(eager final),那么在稍后将该ID转换为会话空间时,我们应该把它留作最终号码(因为从来没有负表). 反之,如果ID是作为负数创建的,我们应该在会话空间中代表它,即使它拥有了最终的ID.

如何运作: 规范化者保持一个排序范围(间距)列表: 生成指数 被分配为当地身份证。 一代指数本质上是一个计数器(从第一个生成的ID开始为1,第二个生成为2等). 当压缩器生成新的ID并确定它必须是本地的ID时,正常化者的ID addLocalRange() 用于记录该索引(或扩展最近的范围)。 如果多个本地ID相继被创建,它们就会形成相接的生成指数范围. 如果创建了最后的ID,那么该索引就完全没有记录为本地的. 因此,正常化者最后说:“身份证1-2是当地身份证,3-5是最后身份证,6是当地身份证,7-9是最后身份证,10是当地身份证等。”.

例如,提及A场会议早先的设想:

• 世代指数1和2(ID-1和2)是本地的,所以正常化者持有范围[1],计数=2].
• 指数3,4,5是最终数字(eger,集群有空间),因此是 没有 在任何局部范围内.
• Index 6是本地的(当第一组用完时),所以添加了一个新的范围 [6,count=1].
• 指数7,8,9是最终数字(第2组空间),因此不在局部范围.
• 指数10是本地的(第2组已耗尽,等待第3组),所以一个新的范围[10,计数=1].

因此,正常化者会将 { (1, 2, (6, 1, (10, 1))} 之类的东西存储为本地范围( 使用基准指数和计数) 。 从中可以推断出任何指数的形式.

具体地说,如果被问到“第5个身份证是本地的吗?” ,我们看到5个没有被记录的范围,这意味着它不是作为本地的(是最终的)分配。 如果问起6号,6号坠入了 [6,1] 范围,所以是当地的。 这种信息在正常化到会话空间时被使用:例如,如果我们有一个对应我们会话的生成5的最终ID,压缩机检查常态器 — 看到5不是一个本地分配,它知道ID没有负态,所以它会话空间中作为最终的. 如果它是第6代,正常化者说那是本地的,所以在我们的会议空间里,我们更喜欢本地代表(负数).

数据结构 : SessionSpaceNormalizer使用仅由附件排序的由起始生成索引键入的区域地图. 它为了效率而合并了相接范围(如果创建出两个本地的ID后相接,它将它们合并为一个范围). 询问一个ID是否是本地的,是在该索引或该索引之前找到范围的问题,并检查该索引是否属于该索引范围——一个二进制搜索操作. 它还可以在一定的指数范围内检索所有局部范围,在形成指数时使用 localIdRanges 字段为 IdCreationRange (通知其他客户,范围中的哪些身份证是本地的)。 由于射程和二进制搜索数量较少,这些操作速度快.

性能 : 如前所述,正常化者的业务是O(日志) 页:1查询,在何处 页:1 是本地区域不连接的数目。 实际 页:1 这是非常小。 每次压缩机从生成最终的ID切换到本地的ID(即当集群耗尽时),都可能会添加一个新的范围. 但随着大型集群和集群扩张,这种情况可能很少发生. 即使在有许多互换的最坏情况下,相差幅度会远远小于ID. 内存使用是最小的(每个范围有两个整数). 常态化者不强加任何重大的间接费用,也不需要在正常运行期间被重置或被刷新 — — 一旦一个ID被标记为本地,这一事实仍然与压缩机的生命相关.

简言之,会议空间气象学家确保 时间方面 iD创建(ID是否必须是占位符)被记住。 这保证了压缩机能够以正确的形式(局部 vs final)对申请和序列化进行一致的解释和呈现ID,保持了整个系统的ID稳定性和等同性的变异.