.for循环

for循环是一种常用的遍历方法，特别适用于已知遍历次数的情况。它由三个部分组成：初始化表达式、循环条件和循环迭代器。这三个表达式用分号分隔。可以使用临时变量将数组的长度缓存起来，避免重复获取数组长度，当数组较大时优化效果会比较明显。

const array = [1,2,3,4,5];
for(let i = 0, len = array.length; i < len; i++ ){ //(初始化表达式; 循环条件; 循环迭代器)
    console.log(array[i]);
}

for循环非常灵活，你可以根据需要自定义循环变量的初始值、循环条件和迭代方式。它适用于各种遍历需求，包括遍历数组、对象的属性等。 2.forEach方法 forEach方法是JavaScript数组对象的一个内置方法，用于遍历数组的每个元素并执行指定的回调函数。以下是forEach方法的基本语法：

array.forEach(function(element, index, array) {});

在forEach方法中，我们传入一个回调函数作为参数。该回调函数接受三个参数：当前元素的值element、当前元素的索引index和正在遍历的数组array。

下面是一个使用forEach方法遍历数组的示例：

array.forEach(function(element, index) {// 对每个元素执行操作
    console.log(element);
});

需要注意的是：

• forEach方法不会改变原数组，也没有返回值；
• forEach方法无法在遍历过程中中止或跳出循环。如果你需要在遍历过程中进行条件判断或中断循环，可以考虑使用其他遍历方法，如for循环或for...of循环，使用 return 时，效果和在 for 循环中使用 continue 一致；
• forEach方法无法遍历对象，仅适用于数组的遍历。

3.for...of循环（适用于数组和可迭代对象） for...of循环是一种用于遍历可迭代对象（如数组、字符串、Set、Map等）的循环结构。它提供了一种简洁的语法来遍历对象的每个元素，而无需使用索引或迭代器。 以下是for...of循环的基本语法：

for (let element of iterable){// 对每个元素执行操作 }

在for...of循环中，我们使用of关键字来指定要遍历的可迭代对象，并将每个元素赋值给一个变量（这里是element）。循环体内的代码将针对每个元素执行操作。下面是一个使用for...of循环遍历数组的示例：

for (let element of array) { // 对每个元素执行操作
    console.log(element);
}

需要注意的是：

• for...of方法只会遍历当前对象的属性，不会遍历其原型链上的属性；
• for...of循环不能用于遍历普通对象（Plain Object），因为普通对象不是可迭代对象。如果你需要遍历普通对象的属性，可以考虑使用for...in循环。
• 可以使用break、continue、return来中断循环遍历。

4.for...in循环（适用于对象） for...in循环是一种用于遍历对象的属性的循环结构。它可以用于遍历对象的可枚举属性（包括自身属性和继承的属性）。以下是for...in循环的基本语法：

for (let key in object) { // 对每个属性执行操作 }

在for...in循环中，我们使用in关键字来指定要遍历的对象，并将每个属性的键赋值给一个变量（这里是key）。循环体内的代码将针对每个属性执行操作。

下面是一个使用for...in循环遍历对象的示例：

for (let key in object) { // 对每个属性执行操作 
    console.log(key + ": " + object[key]);
}

在上述示例中，我们使用for...in循环遍历对象object的每个属性，并在循环体内打印每个属性的键和对应的值。 需要注意的是：

• for...in循环遍历的是对象的属性，而不是值。
• 它会遍历对象的可枚举属性，包括自身属性和其原型链上的属性。如果只需要遍历对象自身的属性，可以使用Object.hasOwnProperty()方法进行过滤。
• for...in循环不保证属性的遍历顺序，因此在遍历过程中不要依赖属性的顺序。

5.map方法 map方法用于对数组的每个元素执行指定的操作，并返回一个新的数组，新数组的元素是原数组经过操作后的结果。 以下是map方法的基本语法：

const newArray = array.map(function(element, index, array) { // 对每个元素执行操作，并返回新的值
    return modifiedElement;
});

在map方法中，我们传入一个回调函数作为参数。该回调函数接受三个参数：当前元素的值element、当前元素的索引index和正在遍历的数组array。 在回调函数中，我们对每个元素执行操作，并返回经过操作后的新值modifiedElement。map方法会遍历数组的每个元素，并将每个元素经过回调函数处理后的结果组成一个新的数组。 下面是一个使用map方法的示例：

const newArray = array.map(function(element) { // 对每个元素执行操作，并返回新的值
    return element * 2;
});

在上述示例中，我们使用map方法对数组array的每个元素进行操作，将每个元素乘以2，并将操作后的结果组成一个新的数组newArray。 map方法是一种非常有用的方法，它可以方便地对数组的每个元素进行操作，并生成一个新的数组。 需要注意的是：

• map方法不会修改原始数组，而是返回一个新的数组。
• map方法无法遍历对象，仅适用于数组的遍历。
• map方法不会对空数组进行检测；

6.reduce方法 reduce方法用于对数组的每个元素进行累积操作，并返回一个最终的累积结果。 以下是reduce方法的基本语法：

// 对每个元素执行累积操作，并返回累积结果
const result = array.reduce(function(accumulator, element, index, array) {
    return accumulatedValue;
}, initialValue);

在reduce方法中，我们传入一个回调函数作为参数。该回调函数接受四个参数：累积值accumulator、当前元素的值element、当前元素的索引index和正在遍历的数组array。 在回调函数中，我们对每个元素执行累积操作，并将累积结果返回。reduce方法会遍历数组的每个元素，并将每个元素经过回调函数处理后的累积结果作为下一次迭代的累积值。 下面是一个使用reduce方法的示例：

const array = [1, 2, 3, 4, 5];
const result = array.reduce(function(accumulator, element) { // 对每个元素执行累积操作，并返回累积结果
    return accumulator + element;
}, 0);
console.log(result); // 输出: 15

在上述示例中，我们使用reduce方法对数组array的每个元素进行累积操作，将所有元素相加得到最终的累积结果。 需要注意的是:

• reduce方法不会改变原数组。
• reduce方法可以接受一个可选的初始值initialValue作为第二个参数。如果提供了初始值，累积值accumulator的初始值将为该值；如果未提供初始值，则累积值将为数组的第一个元素，且从数组的第二个元素开始进行累积操作。
• 如果数组为空，且未提供初始值，则reduce方法会抛出一个TypeError。在处理可能为空的数组时，要确保提供了合适的初始值或进行适当的错误处理。

7.filter方法 filter方法用于筛选数组中满足指定条件的元素，并返回一个新的数组。 以下是filter方法的基本语法：

const newArray = array.filter(function(element, index, array) { // 返回一个布尔值，表示是否保留该元素 },thisArg);

在filter方法中，我们传入一个回调函数作为参数。该回调函数接受三个参数：当前元素的值element、当前元素的索引index和正在遍历的数组array。thisArg是可选的参数，用于指定回调函数中的this值。如果省略了thisArg参数，回调函数中的this将指向全局对象（在浏览器中为window对象）。 在回调函数中，我们根据指定的条件判断是否保留该元素。如果回调函数返回true，则该元素将被保留在新的数组中；如果返回false，则该元素将被过滤掉。 下面是一个使用filter方法的示例：

const array = [1, 2, 3, 4, 5];
const newArray = array.filter(function(element) { // 返回一个布尔值，表示是否保留该元素
    return element % 2 === 0; // 保留偶数元素
});
console.log(newArray); // 输出: [2, 4]

在上述示例中，我们使用filter方法筛选数组array中的偶数元素，并将满足条件的元素组成一个新的数组newArray。 filter方法非常灵活，可以根据不同的条件筛选数组中的元素。回调函数应该返回一个布尔值，表示是否保留该元素。返回true表示保留，返回false表示过滤掉。 需要注意的是：

• filter方法会返回一个新的数组，该数组包含满足指定条件的元素。请确保在回调函数中返回一个布尔值，表示是否保留该元素。
• filter方法不会对空数组进行检测。

8.some方法 some方法用于检测数组中是否至少有一个元素满足指定条件。 以下是some方法的基本语法：

const result = array.some(function(element, index, array) { // 返回一个布尔值，表示是否满足条件 });

在some方法中，我们传入一个回调函数作为参数。该回调函数接受三个参数：当前元素的值element、当前元素的索引index和正在遍历的数组array。 在回调函数中，我们根据指定的条件判断是否满足条件。如果回调函数返回true，则表示至少有一个元素满足条件；如果所有元素都不满足条件，回调函数返回false。 下面是一个使用some方法的示例：

const array = [1, 2, 3, 4, 5];
const result = array.some(function(element) { // 返回一个布尔值，表示是否满足条件
    return element > 3; // 判断是否存在大于3的元素
});
console.log(result); // 输出: true

在上述示例中，我们使用some方法检测数组array中是否存在大于3的元素。由于数组中存在元素4和5满足条件，所以some方法返回true。 some方法可以用于检测数组中是否满足某个条件的元素。它提供了一种简洁的方式来进行条件判断。 需要注意的是：

• some方法在找到满足条件的元素后会立即停止遍历，不会继续遍历剩余的元素。
• some方法不会改变原数组，会返回一个布尔值。

获取指定站点的所有图片，您可以使用C#中的HttpClient和HTML解析库（如HtmlAgilityPack）来实现。

下面是一个简单的示例：

using System;
using System.Collections.Generic;
using System.Net.Http;
using HtmlAgilityPack;

public class Program
{
    public static async Task Main()
    {
        string url = "https://example.com"; // 指定站点的URL

        // 创建HttpClient实例
        using (HttpClient client = new HttpClient())
        {
            // 发送GET请求并获取响应内容
            HttpResponseMessage response = await client.GetAsync(url);
            string htmlContent = await response.Content.ReadAsStringAsync();

            // 使用HtmlAgilityPack解析HTML内容
            HtmlDocument htmlDocument = new HtmlDocument();
            htmlDocument.LoadHtml(htmlContent);

            // 获取所有img标签
            List<string> imageUrls = new List<string>();
            foreach (HtmlNode imgNode in htmlDocument.DocumentNode.Descendants("img"))
            {
                string imageUrl = imgNode.GetAttributeValue("src", "");
                if (!string.IsNullOrEmpty(imageUrl))
                {
                    // 如果图片URL是相对路径，则拼接成绝对路径
                    if (!Uri.IsWellFormedUriString(imageUrl, UriKind.Absolute))
                    {
                        imageUrl = new Uri(new Uri(url), imageUrl).AbsoluteUri;
                    }
                    imageUrls.Add(imageUrl);
                }
            }

            // 打印所有图片URL
            foreach (string imageUrl in imageUrls)
            {
                Console.WriteLine(imageUrl);
            }
        }
    }
}

在上面的示例中，我们使用HttpClient发送GET请求来获取指定站点的HTML内容。

然后，使用HtmlAgilityPack解析HTML内容，并找到所有的img标签。

最后，我们将图片的URL打印出来。

请注意，这只是一个简单的示例，仅用于演示如何获取指定站点的所有图片。

在实际应用中，您可能需要处理更复杂的HTML结构和处理异常情况。

希望这个示例对您有所帮助！

听说过 CRDT 并想知道它们是什么吗？也许你对它们进行过一些研究，但却遇到了一大堆学术论文和数学术语？在我开始我的Recurse Center批次之前，我就是这样的。但我花了大约一个月的时间进行研究和编写代码，事实证明，只需几件简单的事情，你就可以构建很多东西！

在本系列中，我们将了解什么是 CRDT。然后我们将编写一个原始 CRDT，将其组合成更复杂的数据结构，最后使用我们学到的知识构建一个协作像素艺术编辑器。所有这些都假设您没有关于 CRDT 的先验知识，并且只具有 TypeScript 的基本知识。

为了激起你的好奇心，我们最终会得到以下结果：

Network

Latency

使用鼠标单击并拖动即可绘制。使用左下角的颜色输入更改颜料颜色。您可以在任一画布上绘制，您的更改将显示在另一个画布上，就像它们在同一张图片上协作一样。

单击网络按钮可防止更改到达另一个画布（尽管当它们重新“在线”时，它们会再次同步）。延迟滑块会在一个画布上的更改显示在另一个画布上之前添加延迟。

我们将在下一篇文章中构建它。首先，我们需要了解 CRDT！

什么是 CRDT？

好的，让我们从头开始。CRDT 代表“无冲突复制数据类型”。这是一个很长的首字母缩略词，但概念并不太复杂。它是一种可以存储在不同计算机（对等点）上的数据结构。每个对等点都可以立即更新自己的状态，而无需通过网络请求与其他对等点进行检查。对等点在不同时间点可能具有不同的状态，但最终保证会收敛到一个商定的状态。这使得 CRDT 非常适合构建丰富的协作应用程序，例如 Google Docs 和 Figma — 而无需中央服务器来同步更改。

广义上，CRDT 有两种类型：基于状态的和基于操作的。1基于状态的 CRDT 在对等体之间传输其完整状态，并通过将所有状态合并在一起来获得新状态。基于操作的 CRDT 仅传输用户采取的操作，这些操作可用于计算新状态。

它们也分别被称为 CvRDT（“Cv”代表“收敛”）和 CmRDT（“Cm”代表“交换”），尽管我认为“基于状态”和“基于操作”是首选术语。

这可能会让基于操作的 CRDT 听起来更好。例如，如果用户更新列表中的一项，则基于操作的 CRDT 可以仅发送该更新的描述，而基于状态的 CRDT 必须发送整个列表！缺点是基于操作的 CRDT 对通信渠道施加了限制：消息必须按因果顺序准确地传递给每个对等点一次。2

还有增量 CRDT，即混合 CRDT，允许对等体协商需要相互发送的状态子集。这是混合基于操作和基于状态的 CRDT 的一个例子。但根本的权衡仍然存在：对等体之间发送的数据越少，通信的限制就越多。

这篇文章将专门关注基于状态的 CRDT。为简洁起见，从现在开始我只说“CRDT”，但要知道我指的是基于状态的 CRDT。

我一直在谈论 CRDT 的作用，但什么是CRDT？让我们具体一点：CRDT 是实现此接口的任何数据结构：3

从技术上讲，只要遵循下述合并规则，CRDT 可以是任何东西。这是一个工作定义；实际上，面向对象语言中的实现最终会看起来像这样。

interface CRDT<T, S> {
  value: T;
  state: S;
  merge(state: S): void;
}

也就是说，一个 CRDT 至少包含三样东西：

• 一个值，T。这是我们程序其余部分关心的部分。CRDT 的全部目的是在对等点之间可靠地同步该值。
• 状态，S。这是对等体就同一值达成一致所需的元数据。为了更新其他对等体，整个状态将被序列化并发送给它们。
• 合并函数。该函数接收一些状态（可能是从另一个对等点接收的）并将其与本地状态合并。

合并函数必须满足三个属性，以确保所有对等点都得出相同的结果（我将使用符号A ∨ B来表示将状态合并A到状态中B）：

• 交换性：状态可以按任何顺序合并；A ∨ B = B ∨ A。如果 Alice 和 Bob 交换状态，他们可以将对方的状态合并到自己的状态中并得出相同的结果。
• 结合性：当合并三个（或更多）状态时，先合并哪个状态并不重要；(A ∨ B) ∨ C = A ∨ (B ∨ C)如果 Alice 同时收到 Bob 和 Carol 的状态，她可以按任意顺序将它们合并到自己的状态中，结果都是一样的。4
• 幂等性：将一个状态与自身合并不会改变状态；A ∨ A = A。如果 Alice 将自己的状态与自身合并，结果将与她开始时的状态相同。

交换律和结合律听起来可能一样，而且实际上大多数交换运算也是结合律。但有一些数学运算只是其中之一。例如，矩阵乘法是结合律但不是交换律。令人惊讶的是，浮点运算（即 JavaScript 中的任何数学运算符）是交换律但不是结合律！

从数学上证明合并函数具有所有这些属性可能听起来很难。但幸运的是，我们不必这么做！相反，我们可以结合已经存在的 CRDT，依靠有人已经为我们证明了这些事实。

说到已经存在的 CRDT：让我们来了解一下！

最后写入有效寄存器

寄存器是保存单个值的 CRDT。有几种类型的寄存器，但最简单的是最后写入获胜寄存器（或 LWW 寄存器）。

顾名思义，LWW 寄存器只是用最后写入的值覆盖其当前值。它们使用时间戳来确定最后发生的写入，这里用整数表示，每当值更新时，整数就会递增。5算法如下：

你可能会问：为什么不使用实际时间？不幸的是，准确同步两台计算机之间的时钟是一个极其困难的问题。使用像这样的递增整数是逻辑时钟的一个简单版本，它捕获事件相对于彼此而不是“挂钟”的顺序。

• 如果收到的时间戳小于本地时间戳，则寄存器不会改变其状态。
• 如果收到的时间戳大于本地时间戳，则寄存器将用收到的值覆盖其本地值。它还会存储收到的时间戳和某种特定于最后写入该值的对等方的标识符（对等方 ID）。
• 通过将本地对等 ID 与接收状态下的对等 ID 进行比较来打破平局。

使用下面的游乐场尝试一下。

Network

Latency

ID: alice

alice1

ID: bob

bob1

您是否了解了 LWW 寄存器的工作原理？以下是一些可供尝试的特定场景：

• 关闭网络，对 进行大量更新bob，然后重新打开。当您从 发送更新时alice，它们将被拒绝，直到时间戳超过bob的时间戳。
• 执行相同的设置，但一旦您重新打开网络，就将更新从bob发送到alice。请注意，时间戳现在已同步，并且alice可以再次写入bob！
• 增加延迟并同时从两个对等点发送更新。alice将接受bob的更新，但bob将拒绝 的alice。由于bob的对等点 ID 更大，因此它打破了时间戳绑定。

以下是 LWW 寄存器的代码：

class LWWRegister<T> {
  readonly id: string;
  state: [peer: string, timestamp: number, value: T];

  get value() {
    return this.state[2];
  }

  constructor(id: string, state: [string, number, T]) {
    this.id = id;
    this.state = state;
  }

  set(value: T) {
    // set the peer ID to the local ID, increment the local timestamp by 1 and set the value
    this.state = [this.id, this.state[1] + 1, value];
  }

  merge(state: [peer: string, timestamp: number, value: T]) {
    const [remotePeer, remoteTimestamp] = state;
    const [localPeer, localTimestamp] = this.state;

    // if the local timestamp is greater than the remote timestamp, discard the incoming value
    if (localTimestamp > remoteTimestamp) return;

    // if the timestamps are the same but the local peer ID is greater than the remote peer ID, discard the incoming value
    if (localTimestamp === remoteTimestamp && localPeer > remotePeer) return;

    // otherwise, overwrite the local state with the remote state
    this.state = state;
  }
}

让我们看看这与 CRDT 接口相比如何：

• state是最后写入寄存器的对等方 ID、最后写入的时间戳和存储在寄存器中的值的三元组。
• value只是state元组的最后一个元素。
• merge是一种实现上述算法的方法。

LWW 寄存器还有一个名为 的方法set，该方法在本地调用以设置寄存器的值。它还会更新本地元数据，将本地对等 ID 记录为最后一个写入者，并将本地时间戳加一。

就是这样！虽然看起来很简单，但不起眼的 LWW 寄存器是一个强大的构建块，我们可以使用它来创建实际的应用程序。

最后写入获胜地图

大多数程序涉及多个值，6这意味着我们需要一个比 LWW 寄存器更复杂的 CRDT。我们今天要学习的是 Last Write Wins Map（或 LWW Map）。

[需要引用]

让我们先定义几个类型。首先，我们的值类型：

type Value<T> = {
  [key: string]: T;
};

如果每个单独的映射值都保留类型T，则整个 LWW 映射的值就是字符串键到T值的映射。

这是我们的状态类型：

type State<T> = {
  [key: string]: LWWRegister<T | null>["state"];
};

你看出其中的窍门了吗？从我们的应用程序的角度来看，LWW 映射只保存普通值 — — 但实际上它保存的是 LWW 寄存器。当我们查看完整状态时，每个键的状态就是该键的 LWW 寄存器的状态。7

如果值类型是T，为什么状态类型是 的联合T | null？稍后会详细介绍！

我想暂停一下，因为它很重要。组合让我们将原始 CRDT 组合成更复杂的 CRDT。当需要合并时，父级所做的就是将传入状态的片段传递给相应子级的合并函数。我们可以根据需要多次嵌套此过程；每个复杂 CRDT 将越来越小的状态片段传递到下一级，直到我们最终找到执行实际合并的原始 CRDT。

从这个角度来看，LWW Map 合并功能很简单：遍历每个键并将该键的传入状态交给相应的 LWW 寄存器进行合并。在下面的操场上尝试一下：

Network

Latency

ID: alice

• barbob1
• fooalice1

ID: bob

• barbob1
• fooalice1

这里发生的事情有点难以追踪，所以我们将每个键的状态分开。不过请注意，这只是一种可视化辅助手段；完整状态仍作为单个单元进行传输。

尝试增加延迟，然后在每个对等点上更新不同的密钥。您将看到每个对等点都接受具有较高时间戳的更新值，同时拒绝具有较低时间戳的值。

Network

Latency

ID: alice

• barbob1
• fooalice1

ID: bob

• barbob1
• fooalice1

完整的 LWW Map 类相当强大，因此让我们逐一介绍每个属性。以下是它的开头：

class LWWMap<T> {
  readonly id = "";
  #data = new Map<string, LWWRegister<T | null>>();

  constructor(id: string, state: State<T>) {
    this.id = id;

    // create a new register for each key in the initial state
    for (const [key, register] of Object.entries(state)) {
      this.#data.set(key, new LWWRegister(this.id, register));
    }
  }
}

#data是一个私有属性，包含 LWW Register 实例的键映射。要实例化具有预先存在状态的 LWW Map，我们需要遍历状态并实例化每个 LWW Register。

请记住，CRDT 需要三个属性：value和state。merge我们首先看一下value：

  get value() {
    const value: Value<T> = {};

    // build up an object where each value is set to the value of the register at the corresponding key
    for (const [key, register] of this.#data.entries()) {
      if (register.value !== null) value[key] = register.value;
    }

    return value;
  }

它是一个遍历键并获取每个寄存器的 getter value。对于应用程序的其余部分而言，它只是普通的地图！

现在让我们看看state：

  get state() {
    const state: State<T> = {};

    // build up an object where each value is set to the full state of the register at the corresponding key
    for (const [key, register] of this.#data.entries()) {
      if (register) state[key] = register.state;
    }

    return state;
  }

与 类似value，它是一个从每个寄存器的 构建映射的 getter state。

这里有一个明显的趋势：遍历输入的键#data并将内容传递给存储在该键处的寄存器。您可能认为merge会以相同的方式工作，但它更复杂一些：

  merge(state: State<T>) {
    // recursively merge each key's register with the incoming state for that key
    for (const [key, remote] of Object.entries(state)) {
      const local = this.#data.get(key);

      // if the register already exists, merge it with the incoming state
      if (local) local.merge(remote);
      // otherwise, instantiate a new `LWWRegister` with the incoming state
      else this.#data.set(key, new LWWRegister(this.id, remote));
    }
  }

首先，我们遍历传入state参数而不是本地参数#data。这是因为如果传入状态缺少一个键#data，我们知道我们不需要触摸该键。8

你可能会想：如果另一个对等点从他们的地图中删除了一个键，我们是否也应该从本地地图中删除它？这与状态保持的原因相同T | null。我们快到了！

对于传入状态中的每个键，我们都会获取该键处的本地寄存器。如果我们找到一个，则说明对等方正在更新我们已经知道的现有键，因此我们会使用该merge键处的传入状态调用该寄存器的方法。否则，说明对等方已将新键添加到映射中，因此我们会使用该键处的传入状态实例化一个新的 LWW 寄存器。

除了 CRDT 方法之外，我们还需要实现在地图上更常见的方法：set、get和。deletehas

让我们从以下开始set：

  set(key: string, value: T) {
    // get the register at the given key
    const register = this.#data.get(key);

    // if the register already exists, set the value
    if (register) register.set(value);
    // otherwise, instantiate a new `LWWRegister` with the value
    else this.#data.set(key, new LWWRegister(this.id, [this.id, 1, value]));
  }

就像在合并方法中一样，我们要么调用寄存器set来更新现有密钥，要么实例化新的 LWW 寄存器来添加新密钥。初始状态使用本地对等 ID、时间戳 1 和传递给 的值set。

get更简单：

  get(key: string) {
    return this.#data.get(key)?.value ?? undefined;
  }

从本地映射中获取寄存器，如果有则返回其值。

为什么要合并到undefined？因为每个寄存器都保存T | null。有了该delete方法，我们就可以解释为什么了：

  delete(key: string) {
    // set the register to null, if it exists
    this.#data.get(key)?.set(null);
  }

我们不会将键从映射中完全移除，而是将寄存器值设置为null。元数据会保留下来，这样我们就可以消除尚无键的状态的删除歧义。这些被称为墓碑——CRDT 过去的幽灵。

考虑一下如果我们真的从映射中删除了键，而不是留下墓碑，会发生什么。这是一个操场，同行可以添加键，但不能删除它们。你能想出如何让同行删除键吗？

Network

Latency

ID: alice

Key

Value

• fooalice1

ID: bob

Key

Value

• fooalice1

关闭网络，向alice的地图添加一个密钥，然后重新打开网络。最后，对bob的地图进行更改。由于alice发现 的传入状态bob缺少该密钥，因此她将其从自己的状态中删除 — — 尽管她bob从一开始就不知道该密钥。哎呀！

这是具有正确行为的操场。您还可以看到删除键时会发生什么。

Network

Latency

ID: alice

Key

Value

• fooalice1

ID: bob

Key

Value

• fooalice1

请注意，我们永远不会从映射中删除已删除的键。这是 CRDT 的一个缺点——我们只能添加信息，而不能删除信息。虽然从应用程序的角度来看，该键已被完全删除，但底层状态仍然记录该键曾经存在。从技术术语上讲，我们说 CRDT 是单调递增的数据结构。9

有几种方法可以缓解这一缺陷，但这两种方法都超出了本文的讨论范围。一种方法是“垃圾收集”：从 CRDT 中修剪墓碑，这可以防止您将状态与删除墓碑之前所做的任何更改合并。另一种方法是创建一种有效的格式来编码数据。您也可以结合使用这些方法。研究表明，与“普通”数据相比，这可以只产生 50% 的开销。如果您想跳过前面的内容并查看其中的一些优化效果，请查看本系列的最后一部分：使 CRDT 效率提高 98%。

最后一个 LWW Map 方法是has，它返回一个布尔值，指示映射是否包含给定的键。

  has(key: string) {
    // if a register doesn't exist or its value is null, the map doesn't contain the key
    return this.#data.get(key)?.value !== null;
  }

这里有一个特殊情况：如果映射在给定键处包含一个寄存器，但该寄存器包含null，则该映射被视为不包含该键。

为了方便后人参考，下面是完整的 LWW 地图代码：

class LWWMap<T> {
  readonly id: string;
  #data = new Map<string, LWWRegister<T | null>>();

  constructor(id: string, state: State<T>) {
    this.id = id;

    // create a new register for each key in the initial state
    for (const [key, register] of Object.entries(state)) {
      this.#data.set(key, new LWWRegister(this.id, register));
    }
  }

  get value() {
    const value: Value<T> = {};

    // build up an object where each value is set to the value of the register at the corresponding key
    for (const [key, register] of this.#data.entries()) {
      if (register.value !== null) value[key] = register.value;
    }

    return value;
  }

  get state() {
    const state: State<T> = {};

    // build up an object where each value is set to the full state of the register at the corresponding key
    for (const [key, register] of this.#data.entries()) {
      if (register) state[key] = register.state;
    }

    return state;
  }

  has(key: string) {
    return this.#data.get(key)?.value !== null;
  }

  get(key: string) {
    return this.#data.get(key)?.value;
  }

  set(key: string, value: T) {
    // get the register at the given key
    const register = this.#data.get(key);

    // if the register already exists, set the value
    if (register) register.set(value);
    // otherwise, instantiate a new `LWWRegister` with the value
    else this.#data.set(key, new LWWRegister(this.id, [this.id, 1, value]));
  }

  delete(key: string) {
    // set the register to null, if it exists
    this.#data.get(key)?.set(null);
  }

  merge(state: State<T>) {
    // recursively merge each key's register with the incoming state for that key
    for (const [key, remote] of Object.entries(state)) {
      const local = this.#data.get(key);

      // if the register already exists, merge it with the incoming state
      if (local) local.merge(remote);
      // otherwise, instantiate a new `LWWRegister` with the incoming state
      else this.#data.set(key, new LWWRegister(this.id, remote));
    }
  }
}

作者:Jake

出处:https://jakelazaroff.com/words/an-interactive-intro-to-crdts/