December 4, 2022
帕累托改进是说，一种经济行为或经济政策，如果没有任何一个人受损，而至少有一个人受益，这就是帕累托改进。这个概念有非凡的重要性。在平等自愿基础上的商品交换就是帕累托改进，整个市场经济就是建立在此基础之上的。不断进行帕累托改进的结果就是全社会的财富增加。所以商品经济能够使人民生活改善，物质享受增进。不过在经济学里应用的帕累托改进只限于可交换的商品或财富。因为商品和财富是可以客观地用价格来度量的。如果一种政策使少数人受损，多数人受益，只要将多数人所受的利益分一部分给受损的少数人，本来不是帕累托改进的，也可以变成帕累托改进。但条件是损益可以量化比较，少数人得到的补偿应不低于他们受到的损失。
现在我们来讨论如何在不需要牺牲任何一个人的快乐的条件下，至少有一个人增加快乐的方法，也就是快乐的帕累托改进。
孔子说：君子成人之美。这不需要你付出什么，只要不跟人捣乱，或者顺水推舟，顶多出一把小力，帮助别人做成一件好事。自己没有损失，而帮助了别人实现自己的希望，当然使得全社会的快乐总量有所增加。
December 4, 2022
市场经济的道德基础是承认自利并尊重别人的自利。从自利出发，事情可以做得没有浪费，尽心尽力。而靠着利他，就很难做到这样的程度。对这个道理，获得
1976年诺贝尔经济学奖的弗里德曼（Milton Friendman）在他的《自由选择》一书中有很好的论述。他在该书里给出了一个2×2的矩阵，如下：
图中A是用自己的钱为自己花，比如在超级市场为自己买东西，既要省钱又要买得合算。这是最有效的花钱方式。B是为自己花别人的钱，比如可报销的用餐，你不会想着节约，但是会尽量使自己满意。C是为了别人花自己的钱。比如给朋友买礼物，你会想着节省但朋友喜欢什么你只能猜想，很可能花钱买了一个别人并不喜欢的礼物。D是你为别人花别人的钱。比如你负责审批一笔报销，你既不会想着节约，也不会考虑钱花得有没有效果，只要符合规定的报销制度就行。弗里德曼用这个矩阵说明“福利国家的谬论”，意思是说，花钱最好是自己花自己的钱。由国家来安排百姓的福利必然是低效的。他反对先征税，再由国家安排百姓的福利，比如教育、医疗、住房等。
弗里德曼认为通过政府官僚实施百姓的福利计划，弊端很多。官僚们只能靠良心来把事做好，效果远不如强烈得多、可靠得多的私心（A这种情况）。国家的福利计划还使管福利计划的官僚高高在上，自认为是百姓的救星。而另一部分人则把自己看成是必须依靠别人才能生活的人，他们的自我管理的能力因此而萎缩。所以弗里德曼的主张是给低收入的人们发负的所得税，就是给生活补贴。
November 29, 2022
November 29, 2022
DMP（Data Management Platform） DMP中KV数据库、数据管道和数据仓库的选型 移动计算程序到数据所在位置进行计算 MapReduce的shuffle过程 事件时间(Event Time)和处理时间(Processing Time) Lambda架构 典型的互联网大数据平台的架构 物联网大数据平台的架构
一个Source可以对应多个Channel，一个Channel也可以对应多个Source。一个Channel可以对应多个Sink，但一个Sink只能对应一个Channel。
November 29, 2022
DMP 系统的全称叫作数据管理平台（Data Management Platform），从外部看， DMP 特别简单，就是一个 KV 数据库，但是生成这个数据库需要做的事情更多。
在这个系统中，关心的是蓝色的数据管道、绿色的数据仓库和 KV 数据库
为了能够生成这个 KV 数据库，需要有一个在客户端或者 Web 端的数据采集模块，不断采集用户的行为，向后端的服务器发送数据。服务器端接收到数据，就要把这份数据放到一个数据管道（Data Pipeline）里面。数据管道的下游，需要实际将数据落地到数据仓库（Data Warehouse），把所有的这些数据结构化地存储起来。后续，就可以通过程序去分析这部分日志，生成报表或者或者利用数据运行各种机器学习算法。
除了这个数据仓库之外，还会有一个实时数据处理模块（Realtime Data Processing），也放在数据管道的下游。它同样会读取数据管道里面的数据，去进行各种实时计算，然后把需要的结果写入到 DMP 的 KV 数据库里面去。
52 | 设计大型DMP系统（上）：MongoDB并不是什么灵丹妙药
November 29, 2022
还可以换一个角度来理解海明码的作用。对于两个二进制表示的数据，他们之间有差异的位数，称之为海明距离。比如 1001 和 0001 的海明距离是 1，因为他们只有最左侧的第一位是不同的。而 1001 和 0000 的海明距离是 2，因为他们最左侧和最右侧有两位是不同的。
于是，你很容易可以想到，所谓的进行一位纠错，也就是所有和要传输的数据的海明距离为 1 的数，都能被纠正回来。
而任何两个实际想要传输的数据，海明距离都至少是 3。为什么不能是 2 呢？因为如果是 2 的话，那么就会有一个出错的数，到两个正确的数据的海明距离都是 1。当看到这个出错的数的时候，就不知道究竟应该纠正到那一个数了。
在引入了海明距离之后，就可以更形象地理解纠错码了。在没有纠错功能的情况下，看到的数据就好像是空间里面的一个一个点。这个时候，可以让数据之间的距离很紧凑，但是如果这些点的坐标稍稍有错，就可能搞错是哪一个点。
在有了 1 位纠错功能之后，就好像把一个点变成了以这个点为中心，半径为 1 的球。只要坐标在这个球的范围之内，都知道实际要的数据就是球心的坐标。而各个数据球不能距离太近，不同的数据球之间要有 3 个单位的距离。
November 29, 2022
7-4 海明码，就是一共 11 位。
给这 11 位数据从左到右进行编号，并且也把它们的二进制表示写出来。
接着，先把这 11 个数据中的二进制的整数次幂找出来。在这个 7-4 海明码里面，就是 1、2、4、8。这些数，就是的校验码位，把他们记录做 p1～p4。如果从二进制的角度看，它们是这 11 个数当中，唯四的，在 4 个比特里面只有一个比特是 1 的数值。
那么剩下的 7 个数，就是 d1-d7 的数据码位了。然后，对于的校验码位，还是用奇偶校验码。但是每一个校验码位，不是用所有的 7 位数据来计算校验码。而是 p1 用 3、5、7、9、11 来计算。也就是，在二进制表示下，从右往左数的第一位比特是 1 的情况下，用 p1 作为校验码。
剩下的 p2，用 3、6、10、11 来计算校验码，也就是在二进制表示下，从右往左数的第二位比特是 1 的情况下，用 p2。那么，p3 自然是从右往左数，第三位比特是 1 的情况下的数字校验码。而 p4 则是第四位比特是 1 的情况下的校验码。
这个时候，任何一个数据码出错了，就至少会有对应的两个或者三个校验码对不上，这样就能反过来找到是哪一个数据码出错了。如果校验码出错了，那么只有校验码这一位对不上，就知道是这个校验码出错了。
November 29, 2022
把 4 位数据位，分别记作 d1、d2、d3、d4。这里的 d，取的是数据位 data bits 的首字母。把 3 位校验位，分别记作 p1、p2、p3。这里的 p，取的是校验位 parity bits 的首字母。
从 4 位的数据位里面，拿走 1 位，然后计算出一个对应的校验位。这个校验位的计算用之前讲过的奇偶校验就可以了。比如，用 d1、d2、d4 来计算出一个校验位 p1；用 d1、d3、d4 计算出一个校验位 p2；用 d2、d3、d4 计算出一个校验位 p3。
这个时候，如果 d1 这一位的数据出错了，p1 和 p2 和校验的计算结果不一样。 d2 出错了，是因为 p1 和 p3 的校验的计算结果不一样；d3 出错了，则是因为 p2 和 p3；如果 d4 出错了，则是 p1、p2、p3 都不一样。当数据码出错的时候，至少会有 2 位校验码的计算是不一致的。
那倒过来，如果是 p1 的校验码出错了，那意味着只有 p1 的校验结果出错。所以校验码不一致，一共有 2^3-1=7 种情况，正好对应了 7 个不同的位数的错误。
海明码这样的纠错过程，有点儿像电影里面看到的推理探案的过程。通过出错现场的额外信息，一步一步条分缕析地找出，到底是哪一位的数据出错，还原出错时候的“犯罪现场”。
November 29, 2022
混合逻辑时钟（Hybrid Logical Clock，HLC），同样是多时间源、多点授时，但时钟采用了物理时钟与逻辑时钟混合的方式。
TrueTime 依赖 Google 强大的工程能力和特殊硬件，不具有普适性。相反，HLC 作为一种纯软的实现方式，更加灵活，所以在 CockroachDB、YugabyteDB 和很多分布式存储系统得到了广泛使用。
HLC 不只是字面上的意思， TiDB 的 TSO 也混合了物理时钟与逻辑时钟，但两者截然不同。HLC 代表了一种计时机制，它的首次提出是在论文“Logical Physical Clocks and Consistent Snapshots in Globally Distributed Databases”中，CockroachDB 和 YugabyteDB 的设计灵感都来自于这篇论文。下面，我们结合图片介绍一下这个机制。
假如我们有 ABCD 四个节点，方框是节点上发生的事件，方框内的三个数字依次是节点的本地物理时间（简称本地时间，Pt）、HLC 的高位（简称 L 值）和 HLC 的低位（简称 C 值）。
A 节点的本地时间初始值为 10，其他节点的本地时间初始值都是 0。四个节点的第一个事件都是在节点刚启动的一刻发生的。首先看 A1，它的 HLC 应该是 (10,0)，其中高位直接取本地时间，低位从 0 开始。同理，其他事件的 HLC 都是 (0,0)。
然后我们再看一下，随着时间的推移，接下来的事件如何计时。
事件 D2 发生时，首先取上一个事件 D1 的 L 值和本地时间比较。L 值等于 0，本地时间已经递增变为 1，取最大值，那么用本地时间作为 D2 的 L 值。高位变更了，低位要归零，所以 D2 的 HLC 就是 (1,0)。
...
November 29, 2022
最早提出 TSO 的，大概是 Google 的论文“ Large-scale Incremental Processing Using Distributed Transactions and Notifications”。这篇论文主要是介绍分布式存储系统 Percolator 的实现机制，其中提到通过一台 Oracle 为集群提供集中授时服务，称为 Timestamp Oracle。所以，后来的很多分布式系统也用它的缩写来命名自己的单点授时机制，比如 TiDB 和 Yahoo 的 Omid。
考虑到 TiDB 的使用更广泛些，这里主要介绍 TiDB 的实现方式。
TiDB 的全局时钟是一个数值，它由两部分构成，其中高位是物理时间，也就是操作系统的毫秒时间；低位是逻辑时间，是一个 18 位的数值。那么从存储空间看，1 毫秒最多可以产生 262,144 个时间戳（2^18），这已经是一个很大的数字了，一般来说足够使用了。
单点授时首先要解决的肯定是单点故障问题。TiDB 中提供授时服务的节点被称为 Placement Driver，简称 PD。多个 PD 节点构成一个 Raft 组，这样通过共识算法可以保证在主节点宕机后马上选出新主，在短时间内恢复授时服务。
那问题来了，如何保证新主产生的时间戳一定大于旧主呢？那就必须将旧主的时间戳存储起来，存储也必须是高可靠的，所以 TiDB 使用了 etcd。但是，每产生一个时间戳都要保存吗？显然不行，那样时间戳的产生速度直接与磁盘 I/O 能力相关，会存在瓶颈的。
如何解决性能问题呢？TiDB 采用预申请时间窗口的方式。
当前 PD（主节点）的系统时间是 103 毫秒，PD 向 etcd 申请了一个“可分配的时间窗口”。要知道时间窗口的跨度是可以通过参数指定的，系统的默认配置是 3 毫秒，示例采用了默认配置，所以这个窗口的起点是 PD 当前时间 103，时间窗口的终点就在 106 毫秒处。。写入 etcd 成功后，PD 将得到一个从 103 到 106 的“可分配时间窗口”，在这个时间窗口内 PD 可以使用系统的物理时间作为高位，拼接自己在内存中累加的逻辑时间，对外分配时间戳。
...