Posts

《Redis深度历险》记录 基础与应用 分布式锁 分布式锁用于高并发或分布式事务中保护临界资源。 最常见的实现方式是使用 SET 命令的 NX (不存在时设置)和 PX (设置过期时间)选项： 1 SET lock_name my_random_value NX PX 30000 lock_name : 锁的名称。 my_random_value : 唯一标识(通常使用 UUID)。 NX : 只有键不存在时才设置。 PX 30000 : 设置 30 秒的过期时间。 释放分布式锁时需要验证唯一标识是否匹配，防止误删其他客户端的锁。 超时问题 超时问题有三类： 锁过期，可以通过锁续约机制，即获取锁后启动一个守护线程，定期检查锁是否仍由自己持有，如果是则延长锁的过期时间。 客户端获取锁后崩溃，没有主动释放锁，锁就只能等待超时后才能被其他客户端获取。所以要设置合理的锁超时时间。 Redis 服务器和客户端之间的时钟不同步，可能导致锁提前或延后过期。尽量确保服务器和客户端时钟同步(NTP)，同时适当增加锁的超时时间作为缓冲。 分布式锁的实现有 Redlock 算法、go-redis 中的简易 mutex 分布式锁。 延时队列 通过 List 来作为简易的消息队列使用。 通过 rpush , lpush 控制入队，rpop , lpop 控制出队。 使用 List 实现延时队列会出现一个问题，假设 List 为空，那么之后的 pop 操作就是死循环。此时可以使用阻塞读来避免这种情况，即使用 blpop, brpop 两个命令代替之前的出队命令。阻塞读在队列没有数据的时候，会立即进入休眠状态。 同时需要注意，List 长时间为空，Redis 客户端连接可能会因为空闲而被回收。所以需要加入重试机制。...

《高性能MySQL》记录 创建高性能的索引 索引基础 B-Tree 索引 InnoDB 引擎的默认索引类型是 B+ Tree，按照原数据格式进行存储。 B-Tree 意味着所有的值都是按顺序存储的，并且每一个叶子到根的距离相同。B-Tree 索引能够加快访问数据的速度，通过根节点的指针不断向下比较查找，最终存储引擎要么找到对应的值，要么记录不存在。B-Tree 对索引列的顺序存储结构适合查找范围数据，如全值匹配、匹配最左前缀、匹配范围值等。除了按值查找，索引还可以用于 ORDER BY 操作。 B-Tree 索引存在以下限制： 如果不是按照索引的最左列开始查找，则无法使用索引。对于复合索引(A,B,C)，查询条件必须包含A列才能有效使用该索引。如果查询只使用B或C列，索引通常不会被使用。 不能跳过索引中的列，必须按照索引定义的列顺序使用。 如果查询中有某个列的范围查询，则其右边所有列都无法使用索引优化查询。 哈希索引 哈希索引是基于哈希表实现的索引类型，通过哈希函数将索引列值转换为哈希码来快速定位数据行。在MySQL中，只有MEMORY存储引擎显式支持哈希索引，并且这是MEMORY引擎的默认索引类型。 哈希索引是无序存储，而且只支持精确匹配。哈希索引的限制如下： 不支持范围查询，如>、<、BETWEEN等。 不支持部分列匹配，必须使用索引的所有列才能生效，因为哈希索引始终是使用索引项的全部内容来计算哈希值的。 哈希冲突问题，不同值可能产生相同哈希值，需要额外处理。 InnoDB 有一个自适应哈希索引，InnoDB 引擎会自动监控查询模式，对频繁访问的索引值创建自适应哈希索引。这实际上是 B-Tree 索引上的优化层，使用哈希值而非键本身进行查找。 空间数据索引（R-Tree） 空间数据索引是一种专门用于处理多维空间数据(如地理坐标、几何图形等)的索引技术，主要解决传统 B-Tree 索引无法有效处理空间数据的问题。 全文索引 全文索引是专门为文本内容搜索设计的索引技术，通过建立倒排索引实现高效文本检索。 高性能的索引策略 独立的列 索引列必须作为独立的表达式存在，不能参与计算或作为函数参数，否则索引会失效。MySQL 无法解析包含运算或函数的表达式，必须将列单独提取为查询条件，才能触发索引优化。 前缀索引与索引选择性 针对长字符串或文本类型，通过截取前 N 个字符建立索引，减少存储空间和 I/O 消耗。 关于如何选择合适的前缀长度，可以通过计算选择性进行评估： 1 SELECT COUNT(DISTINCT LEFT(column, N)) / COUNT(*) FROM table; 选择接近完整列选择性的最短前缀（如对邮箱地址反转后建前缀索引）。 复合索引与最左前缀原则 最左前缀原则：查询必须从复合索引的最左列开始，且不能跳过中间列。示例：索引 (A,B,C) 支持 A=1 AND B=2 ，但不支持 B=2 或 B=2 AND C=3 。使用复合索引时要注意范围查询限制，若某一列使用范围查询，其右侧的列无法使用索引优化。...

《Kubernetes编程》记录 概论 控制器和 Operator 控制器实现了一个控制循环，通过 API 服务器监测集群中的共享状态，进行必要的变更。Operator 也是一种控制器，但是包含了一些运维逻辑，如应用程序的生命周期管理。 控制循环的基本流程如下： 读取资源的状态，通常采用事件驱动模式，使用 Watch 来实现。 改变集群中的对象状态或集群外部系统的状态。 通过 API 服务器更新第 1 步中所提到的资源的状态，状态放在 etcd 中。 循环执行这些逻辑。 控制器通常会使用以下的数据结构： Informer ：Informer 负责观察资源的目标状态，它还负责实现重新同步机制从而保证定时地解决冲突。 工作队列：事件处理器把状态变化情况放入工作队列。 多个相互独立的控制循环通过 API 服务器上的对象状态变化相互通信，对象状态的变化由 Informer 以事件的方式通知到控制器。这些通过 Watch 机制发送的事件对用户来说几乎不可见，在 API 服务器的审计机制中也看不到这些事件，只能看到对象更新的动作。控制器在处理事件时，以输出日志的方式记录它做的动作。 Watch 事件：在 API 服务器与控制器之间通过 HTTP 流的方式发送，用于驱动 Informer 。 Event 对象：是一种用户可见的日志机制，如 kubelet 通过 Event 来汇报 Pod 的生存周期事件。 乐观并发 Kubernetes 采用乐观并发机制，假设多用户操作同一资源的冲突概率较低，允许并发修改，仅在提交时检测冲突。 每个 Kubernetes 资源对象（如 Pod、Deployment）的元数据中都有一个 resourceVersion 字段，用于标识资源的当前版本号（由 etcd 生成）。这是乐观并发的核心： 读取资源时：客户端获取对象的 resourceVersion（例如 123）。 更新资源时：客户端必须在请求中携带该版本号（通过 metadata.resourceVersion 字段）。 服务器端校验：API Server 比较请求中的 resourceVersion 与当前存储中的版本： 匹配：允许更新，resourceVersion 递增。 不匹配：返回 409 Conflict 错误，拒绝更新（说明资源已被其他客户端修改过）。 当发生冲突时，客户端需重新获取资源的最新状态，然后基于最新数据重新提交修改。...

《Kafka权威指南》记录 初识 Kafka 消息和批次 消息有一个可选的元数据，也称为键。键是一个字节数组，可以用来实现如分布式键等应用。 为了提高效率，消息会被分批次写入 Kafka，批次包含了一组同属于一个主题和分区的消息。 模式 模式就是消息的格式，如Json、XML。 主题和分区 消息通过主题进行分类，主题又被分为若干个分区。 生产者和消费者 默认情况下，生产者会把消息均衡地分布到主题的所有分区中，也可以通过自定义设置决定消息发布到哪里。 消费者通过检查消息的偏移量来区分已经读取过的消息。 broker 和集群 一台单独的 Kafka 服务器称为 broker，单个 broker 可以处理数千个分区和每秒百万级的消息量。 集群由 broker 组成，同时也有集群中都有的分布式共识算法。Kafka 使用 ZAB 作为共识算法，2.8 版本后支持 KRaft 管理元数据。 Kafka 与其他消息队列的区别 Kafka 与其他消息队列相比，有以下几个显著的区别： 高吞吐量与低延迟 Kafka 设计上支持高吞吐量和低延迟，能够处理海量数据和高并发写入、读取场景。 其他消息队列（如 RabbitMQ、ActiveMQ）通常适用于较小规模或实时性要求较高的场景，但在海量数据和高并发场景下可能会遇到性能瓶颈。 持久化与分布式存储 Kafka 使用磁盘持久化和日志分段技术，并通过分区（Partition）和副本（Replica）机制实现分布式存储和容错。 其他消息队列有的采用内存队列（例如 RabbitMQ 默认使用内存），虽然也支持持久化，但在大规模数据存储和高可靠性需求下不如 Kafka 灵活。 消息模型与消费模式 Kafka 基于发布-订阅模型，采用拉取（Pull）的消费模式。消费者主动拉取消息，可以灵活控制消费速率和消息重放。 其他消息队列（例如 RabbitMQ）多采用推送（Push）模式，消息直接推送给消费者，实时性较好，但可能在处理慢消费者时需要额外机制（如 ACK、流控等）。 数据持久性和消息重放 Kafka 中的消息存储在日志中，并且消息不会在被消费后自动删除（可以根据保留策略删除），这使得消费者可以根据需求重放消息。 其他消息队列通常在消息被消费确认后就删除，无法轻易重放历史消息。 扩展性与容错性 Kafka 天生支持分布式集群部署，通过增加 Broker 节点来横向扩展，且内置副本机制保证容错。 其他消息队列虽然也有集群部署方案，但在大规模扩展和高容错要求下往往不如 Kafka 那样简单高效。 应用场景不同 Kafka 更适用于日志收集、流处理、大数据实时分析等场景。 其他消息队列则更适合需要复杂路由、即时响应、任务队列等场景，比如电商下单、实时通知等。 Kafka 生产者 消息发布方式：...

《MongoDB 权威指南》记录 MongoDB 简介 MongoDB 是面向文档的非关系型数据库。 MongoDB 具有以下特点： 易于使用：没有“行记录”的概念，而使用“文档”模型取代之。同时也没有预定义模式，文档键值的类型和大小是动态的。 易于扩展：MongoDB 采用了横向扩展方式，面向文档的数据模型使得跨多台服务器拆分数据更加容易。 性能强大：使用了机会锁，提高并发和吞吐量。同时会尽可能多的使用内存作为缓存，并尝试为查询自动选择合适的索引。 入门指南 文档 文档是一组有序键值的集合，如以下形式： 1 {"q": "ans"} 集合 集合就是一组文档，相当于关系型数据库的表结构。 集合具有动态模式的特性，每个文档的长度大小、键数量都可以不一样。不过开发中并不推荐这样做，还是将“形状”相同的文档存在同一个集合中好，因为这样查询起来性能不会受到影响。 在 MongoDB 中通常会用 . 字符分隔不同命名空间的子集合，如 blog.posts 。 数据库 MongoDB 使用数据库对集合进行分组。 数据类型 基本数据类型：除了 int 等，还有 Regex、Array、ObjectID（12字节的文档的唯一ID 标识）、Bytes、JSCode。 Array： {"things": ["pie", 3.14]}，数组内可以混有不同类型的数据。 内嵌文档：文档作为值。 ObjectID：每个文档都有一个 _id ，默认是 ObjectID ，这个 ID 在集合内是唯一的。可以看到这个 ID 不是自增的，类似于 UUID，这说明 MongoDB 在设计之初就是作为分布式数据库存在的。以下是它的生成规则： 前 4 字节为时间戳，中间 5 个字节是随机值，后 3 个字节是计数器（起始值随机）。 索引 MongoDB 中可以设置单一索引和复合索引，方式如下： 1 db.users.createIndex({"age": 1, "username": 1}) # 复合索引 MongoDB 的默认存储引擎是 WiredTiger ，索引是 B+ 树实现的。所以在索引的优化上，可以参照相关关系型数据库的索引优化经验与原则。下面是部分经验：...

《HTTP权威指南》记录 本书中的 HTTP 协议版本为 HTTP/1.1 。 URL 与资源 URL 语法 在 URL 中以分号 ; 作为参数的分隔符，如下： 1 http://xxx.xxxx.com/hammers;sale=false/index.html;graphics=true 有些资源需要通过查询字符串来缩小查找范围，查询字符串通过 ? 分割，如常见的 GET 请求中的查询参数。 URL 支持使用片段组建来表示一个资源内部的片段，以 # 进行分割： 1 http://xxx.xxx.com/index.html#head Web 服务器 Web 服务器应该做的： 接受客户端连接：客户端收到一条连接之后，那么它将会把新连接添加到现存web服务器连接列表中，用于监视当前连接上的数据传输情况。期间服务器还应该做到通过一定的设备机制阻止未认证或已知恶意黑名客户端的连接。 接收请求报文： 这一步需要解析请求报文： 解析请求行，查找请求方式、URI 、版本号以及 CRLF 分隔符。 读取以 CRLF 结尾的报文首部。 检测到以 CRLF 结尾的，标识首部结尾的空行。 解析得到请求体。 处理请求：其他章节会详解。 对资源的映射及访问：找到客户端请求资源在服务器的上的目录路径。 Web 服务器存放内容的文件夹称为文档的根目录（doc root），Web 服务器会从请求报文中获取 URI ，并将其附加在 doc root 的后面。 在一个服务器上挂载多个 Web 站点，那么这样当请求的资源路径相同时，服务器应该从请求报文首部的 HOST 和 URI 字段找出真正的资源目录，这些目录都可以更改配置。 构建响应： 正确设置响应主体的长度（content-length）。 设置报文的 MIME 类型（content-type）。 有时候资源不在原地，需要进行重定向。 发送响应。 记录事务日志。 代理 Web 的中间实体 Web 代理服务器是代表客户端对事务请求处理的中间人，代理分为私有代理（只代理一个客户端）和公共代理（代理多个客户端）。 代理和网关的对比：代理的两端使用相同的协议，而网关的两端使用不同的协议，网关负责协议转换。 代理应用 内容过滤。 文档访问控制。 安全防火墙。 Web 缓存：缓存资源的副本。 反向代理：反向代理伪装成原始服务器，不过与服务器不同的是反向代理还可以向其他服务器发送请求，以便实现按需定位所请求的内容。 ……....

《深入理解设计模式》记录 这里只记录了相对常用、面试常问的设计模式。 单例模式 单例模式（Singleton Pattern）是一种创建型设计模式，其核心目标是确保一个类仅有一个实例，并提供全局访问点。它适用于需要全局唯一对象且频繁访问的场景，例如配置管理、线程池、日志记录器等。 单例模式需要注意三点： 私有化构造函数：防止外部通过 new 直接创建实例。 自行创建实例：类内部负责生成唯一实例。 全局访问方法：提供静态方法供外部获取实例。 懒汉模式 特点：延迟实例化，首次调用时创建实例，需处理线程安全问题。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 package singleton import "sync" type lazySingleton struct { } var ( instance *lazySingleton once sync.Once ) func GetLazyInstance() *lazySingleton { once.Do(func() { instance = &lazySingleton{} }) return instance } 饿汉模式 特点：在包加载时直接初始化实例，无需考虑线程安全。 1 2 3 4 5 6 7 8 9 10 11 package singleton type eagerSingleton struct { } var instance = &eagerSingleton{} func GetEagerInstance() *eagerSingleton { return instance } 懒汉模式的另一实现形式：静态内部类 特点：通过嵌套结构体延迟加载，结合 sync....

动态规划经典问题学习记录 0-1 背包 问题描述 有 $n$ 个物品，第 $i$ 个物品的体积为 $w[i]$ ，价值为 $v[i]$ ，每个物品最多选一次，求体积和不超过 $capacity$ 时的最大价值和。 通过回溯去思考解题思路 先去思考当前的操作，即枚举第 $i$ 个物品选与不选： 不选，剩余容量不变。 选，剩余容量减少 $w[i]$ 。 递归到子问题，在剩余容量为 $c$ 时，从前 $i$ 个物品中得到的最大价值和。 下一个递归子问题： 不选，在剩余容量为 $c$ 时，从前 $i-1$ 个物品中得到的最大价值和。 选，在剩余容量为 $c-w[i]$ 时，从前 $i-1$ 个物品中得到的最大价值和。 最终得到的递归公式：$dfs(i,c) = max(dfs(i-1, c),dfs(i-1, c-w[i])+v[i])$ 对应的代码就是： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 def zero_one_backpack(capacity: int, w: List[int], v: List[int]) -> int: n = len(w) @cache # 记忆化搜索数组 def dfs(i: int, c: int) -> int: # 跳出递归条件 if i < 0: return 0 # 容量不足时 if c < w[i]: return dfs(i-1, c) # 将问题进一步分解 return max(dfs(i-1, c), dfs(i-1, c-w[i]) + v[i]) return dfs(n-1, capacity) 以上就是 0-1 背包的“至多装 capacity”的递归+记忆化搜索形式，其实也可以写成递推式：$dp[i][c] = max(dp[i-1][c],dp[i-1] [c-w[i]]+v[i])$...

《深入理解分布式共识算法》记录 从 ACID 和 BASE 到 CAP BASE 理论 BASE 包含； BA（Basically Available）：基本可用，当分布式系统出现故障的时候，允许损失部分可用性。这里损失指响应时间的损失和功能上降级，前者是在增加响应时间上来提供服务，后者是在高峰期不请求后端而直接返回降级数据、以保证系统的稳定性。 S（Soft State）：软状态，允许系统中的数据存在中间状态，并认为该状态不会影响系统的整体可用性，即允许节点之间的数据同步存在延迟。 E（Eventually Consistent）：最终一致性。 为应用 BASE 理论，可以采用异步补偿机制。如果用这个机制，需要明确哪些操作属于非关键操作，如果非关键操作失败，应允许业务流程继续执行，然后在异步补偿非关键操作。 补偿指事务补偿：在分布式事务中，由于各个服务可能分布在不同的节点上，无法像单机事务那样简单地通过“回滚”来撤销操作。因此，事务补偿通过执行与原始操作相反的操作来达到类似的效果。 补偿操作需要注意两点： 幂等性：补偿操作可能需要多次执行，因此需要保证其幂等性，即多次执行的效果与一次执行相同。 最终一致性：补偿机制通常用于实现最终一致性，而不是强一致性，因此需要权衡一致性和性能。 CAP 理论 CAP 包含： C（Consistency）一致性：分布式系统的全序线性一致性。 A（Availability）可用性：任何情况都能够处理客户端的每个请求。 P（Partition Tolerance）分区容错性：发生网络分区时，系统仍能提供服务。 任何分布式系统都可分为三类架构： CP（锁定事务资源）：所有节点的数据需要实时保持一致性，这需要锁定各分支事务的资源。当发生分区时，此期间为确保返回客户端数据的准确性且不破坏一致性，可能会因为无法响应最新数据而拒绝响应，即放弃 A 。 AP（尽力提供服务）：要求每个节点拥有集群的所有能力或数据，能独立处理客户端的每个请求。发生分区时，可以通过缓存后本地副本来处理请求，以达到可用性，但会出现各节点不一致性，即放弃 C 。 CA（本地一致性）：在不发生分区时，C、A 正常满足。一旦发生分区，会保证各子分区满足 CA 。 但是网络分区不可避免，CAP 理论就变成了在 C 和 A 中的权衡问题。 2PC、3PC，分布式事务的解决方案 2PC 2PC 中的字母含义是 P（Participant，参与者），C（Coordinator，协调者）。 2PC 即两阶段提交协议，用于解决分布式事务问题。第一阶段用于各个分支事务的资源锁定，第二阶段用于全局事务的提交或回滚： 第一阶段，准备： 开启全局事务。当协调者收到客户端的请求后，它将各个分支事务需要处理的内容通过 Prepare 请求发送给所有参与者，并询问能否正常处理自己的分支事务，然后等待各个参与者的响应。 处理分支事务。当参与者收到 Prepare 请求后便锁定事务资源，然后尝试执行，记录 Undo 和 Redo 信息，但不提交分支事务。 汇报分支事务状态。参与者根据第 2 步执行的结果，向协调者汇报各自的分支事务状态，Yes 表示可以提交，No 表示不能提交。 第二阶段，提交/回滚：...

Leetcode-75 总结 代码链接：KurongTohsaka/my-lc75-go Array&String 151 反转字符串中的单词：双指针。 238 除自身以外数组的乘积：线性 DP 。 334 递增的三元子序列：双指针。 345 反转字符串中的元音字母：双指针。 443 压缩字符串：双指针。 605 种花问题：列出三种种花情况，依次进行处理即可。 1071 字符串的最大公因式：根据特殊的 str1 + str2 == str2 + str1 公式和辗转相除法解题。 1431 拥有最多糖果的孩子：先找最大值，然后进行比较。 1768 交替合并字符串：取较小长度最为切割位置，然后交替合并，最后处理剩余部分。 DoublePointers 11 接水问题：双指针的首尾指针。 283 移动零：双指针的快慢指针。 392 判断子序列：双指针的快慢指针。 1679 K 和数对的最大数目：解法与两数之和相似，使用哈希表记录为匹配数组次数，然后更新 hashMap[k-v] 的数值。 SlidingWindow 643 子数组最大平均数-1 ：定长滑动窗口，应用通用解法，即新元素进入、更新统计量、right-left+1 元素离开三步。 1004 最大连续1的个数-2 ：变长滑动窗口，通过快慢指针实现。 1456 定长子串中元音的最大数目：定长滑动窗口，通用解法。 1493 删掉一个元素后全为1的最长子数组：变长滑动窗口，解法与 1004 高度相似。 PrefixSum 724 寻找数组的中心下标：双指针可解，不过还是推导出的公式更快。 1732 找到最高海拔：很简单，直接秒。 HashMap 1207 独一无二的出现次数：用了两个哈希，第一个是对数组中所有元素进行计数，第二个是对第一个哈希元素的出现次数进行计数，目的是得到独一无二的出现次数。 1657 确定两个字符串是否接近：操作 1 和 2 能实现的大前提是两个字符串的长度一致，操作 1 只要两个字符串对应的字母的计数一致就成立，操作 2 则进一步要求每个“次数”一致。 2215 找出两数组的不同：双哈希表记录每个元素出现次数，然后分别进行比较。 2352 相等行列对：一个哈希表解决。先行遍历，把每一行作为键存储，然后记录相同的行出现的次数。再列遍历，把每列作为键去查询，然后把次数加上相同的行的个数。 Stack 394 字符串解码： 本题要点在于只要遇到右括号就开始处理栈内元素： 先处理直到左括号内的所有元素，拼接后再反转（顺序是反的🐎），然后别忘记让左括号出栈。 之后统计出现次数，此时注意数字可能为两位数。在处理完成后，就开始按照次数重复拼接子串，然后再把该子串入栈（处理嵌套字符串的方式）。 735 小行星碰撞：只有当栈顶向右（正）且当前行星向左（负）时才处理碰撞，使用循环处理可能的多次碰撞，直到当前行星被摧毁或无法继续碰撞。 2390 从字符串中移除星号：常规栈解法，很简单。 Queue 649 Dota2 参议院：使用两个队列存储每位参议院出现的位置，通过比较位序来选择被淘汰的议员，同时保证每轮必有两名议员被踢出队列。 933 最近的请求次数：维护一个队列，本题想要的结果就是最终的队列长度。超出时间范围的请求出队、新请求进队。 LinkedList 206 反转链表：经典操作，三指针反转链表，属于基本功了。 328 奇偶链表：用两个变量记录奇偶两个链表的头节点，再用两个变量作为构建奇偶链表的指针。然后遍历整个链表去构建奇偶链表，最后把奇链表的指针指向偶链表的头部。 2095 删除链表中的中间节点：通过快慢指针找到中间节点，同时记录慢指针的前一个节点方便后续删除操作。 2130 链表最大孪生和：本题属于缝合题，先是快慢指针找中间节点，再是反转后半部分链表，最后又是一个双指针遍历。 Tree - DFS 所有题都是。DFS （深度优先遍历）。...

《数据密集型系统设计》记录 本书的电子版本链接：Vonng/ddia: 《Designing Data-Intensive Application》DDIA中文翻译 3. 存储与检索 本章围绕两大类存储引擎：日志结构（log-structured）的存储引擎，以及面向页面（page-oriented）的存储引擎（例如 B 树）。 数据库核心：数据结构 这里所使用的“日志”是一个更一般性的概念：一个支持 append-only 仅追加操作的记录序列。 为了高效查找数据库中特定键的值，需要用到索引。索引是从主要数据中衍生的额外结构，维护它会产生额外开销，特别是写入时。任何类型的索引通常都会减慢写入速度，因为每次写入数据时都需要更新索引。这是存储系统中一个重要的权衡：精心选择的索引加快了读查询的速度，但是每个索引都会拖慢写入速度。因为这个原因，数据库默认并不会索引所有的内容，而需要程序员或数据库管理员（DBA），基于对应用的典型查询模式的了解来手动选择索引。 SSTable 把键值对的序列按照键进行排序，这个格式称为排序字符串表（Sorted String Table, SSTable）。此时再要求每个键值在每个合并的段文件中出现一次。与使用散列索引的日志段相比，SSTable 有几个大的优势： 即使文件大于可用内存，合并段的操作仍然是简单高效： 一开始并排读取多个输入文件，查看每个文件中的第一个键，复制最低的键（根据排序顺序）到输出文件，不断重复此步骤，将产生一个新的合并段文件，而且它也是也按键排序的。 如果在几个输入段中出现相同的键，该怎么办？请记住，每个段都包含在一段时间内写入数据库的所有值。这意味着一个输入段中的所有值一定比另一个段中的所有值都更近（假设我们总是合并相邻的段）。当多个段包含相同的键时，我们可以保留最近段的值，并丢弃旧段中的值。 为了在文件中找到一个特定的键，你不再需要在内存中保存所有键的索引： 假设你正在内存中寻找键 handiwork，但是你不知道这个键在段文件中的确切偏移量。然而，你知道 handbag 和 handsome 的偏移，而且由于排序特性，你知道 handiwork 必须出现在这两者之间。这意味着你可以跳到 handbag 的偏移位置并从那里扫描，直到你找到 handiwork（或没找到，如果该文件中没有该键）。 由于读取请求无论如何都需要扫描所请求范围内的多个键值对，因此可以将这些记录分组为块（block），并在将其写入硬盘之前对其进行压缩。稀疏内存索引中的每个条目都指向压缩块的开始处。除了节省硬盘空间之外，压缩还可以减少对 I/O 带宽的使用。 那么，可以构建 SSTable 了，可以让存储引擎这样工作： 有新写入时，将其添加到内存中的平衡树数据结构（例如红黑树），这个内存树有时被称为内存表（memtable）。 当内存表大于某个阈值（通常为几兆字节）时，将其作为 SSTable 文件写入硬盘。这可以高效地完成，因为树已经维护了按键排序的键值对。新的 SSTable 文件将成为数据库中最新的段。当该 SSTable 被写入硬盘时，新的写入可以在一个新的内存表实例上继续进行。 收到读取请求时，首先尝试在内存表中找到对应的键，如果没有就在最近的硬盘段中寻找，如果还没有就在下一个较旧的段中继续寻找，以此类推。 后台进程周期性地执行合并和压缩过程，以合并段文件，并将已覆盖或已删除的值丢弃。 这样的索引结构被称为 LSM-Tree（Log-Structured Merge-Tree）。 当查找数据库中不存在的键时，LSM 树算法可能会很慢。为了优化这种访问，存储引擎通常会使用布隆过滤器。还可以使用大小分级和分层压缩。对于大小分级，较新和较小的 SSTables 相继被合并到较旧的和较大的 SSTable 中。对于分层压缩，键的范围被拆分到多个较小的 SSTables，而较旧的数据被移动到单独的层级，这使得压缩能够逐步进行并且使用较少的硬盘空间。 B-Tree 前面看到的日志结构索引将数据库分解为可变大小的段，通常是几兆字节或更大的大小，并且总是按顺序写入段。相比之下，B 树将数据库分解成固定大小的块或分页，传统上大小为 4KB（有时会更大），并且一次只能读取或写入一个页面。这种设计更接近于底层硬件，因为硬盘空间也是按固定大小的块来组织的。 在 B 树的底层中，写操作是用新数据覆写硬盘上的页面，并假定覆写不改变页面的位置。即当页面被覆写时，对该页面的所有引用保持完整。这与日志结构索引（如 LSM 树）形成鲜明对比，后者只追加到文件（并最终删除过时的文件），但从不修改文件中已有的内容。...

《Kubernetes微服务实战》记录 面向开发人员的 Kubernetes 简介 部分核心概念 Node：Node 是 Kubernetes 集群中的一个工作单元，表示集群中的一台物理机或虚拟机。Node 的作用是为运行容器化应用提供计算资源，一个 Node 可以运行多个 Pod。Node 分为： Master Node：负责集群的控制平面，管理所有工作节点。 Worker Node：运行实际的应用程序工作负载，实际上就是 Pod。 Pod：Pod 是 Kubernetes 中最小的可部署单位，表示一个或多个容器的集合。有以下特性： Pod 内的容器共享一个 IP 地址，可以通过 localhost 相互通信。 Pod 内的容器可以共享挂载的存储卷（Volume）。 Pod 通常包含运行同一应用程序组件的容器，如主应用程序容器、日志采集容器等。 Namespace：用于逻辑上隔离资源。可以在同一集群中运行多个项目或团队的工作负载。 Service：用于将一组 Pod 的访问暴露给外部或集群内部的其他 Pod。 Deployment：用于声明和管理 Pod 的期望状态，例如副本数、滚动更新等。 Volume：提供持久化存储，允许 Pod 重启后数据仍然保留。 Kubernetes 架构 每个集群都有一个控制平面和数据平面，数据平面由多个节点组成，控制平面将在这些节点上部署并运行 Pod（容器组），监控变更并做出响应。 控制平面包含以下组件： API 服务器。 etcd 存储。 调度器：kube 调度器负责将 Pod 调度到工作节点。 控制器管理器：kube 控制器管理器是包含多个控制器的单个进程，这些控制器监控着集群事件和对集群的更改做出响应。 节点控制器：负责在节点出现故障时进行通知和响应。 副本控制器：确保每个副本集（replica set）或副本控制器对象中有正确数量的 Pod 。 端点控制器：为每个服务分配一个列出该服务的 Pod 的端点对象。 服务账户和令牌控制器：使用默认服务账户和响应的 API 访问令牌对新的命名空间进行初始化。 数据平面是集群中将容器化工作负载转为 Pod 运行的节点的集合。...

minikube：Ubuntu 部署本地集群踩坑 官方安装教程 minikube start | minikube 再次感叹 homebrew 的伟大，一行命令就安装、后续也没有问题。 仪表盘 使用 minikube dashboard 启动仪表盘。如果在服务器上启动、本地访问，就运行类似于的下面命令： 1 kubectl proxy --address='0.0.0.0' --disable-filter=true 然后把 http://127.0.0.1:46749/api/v1/namespaces/kubernetes-dashboard/services/http:kubernetes-dashboard:/proxy/ 这样的 URL 改为 http://ServerIP:8001/api/v1/namespaces/kubernetes-dashboard/services/http:kubernetes-dashboard:/proxy/ ，就可以外网直接访问了（注意服务器开端口）。 Helm 安装 直接使用 snap 安装，方便快捷： 1 sudo snap install helm --classic kubectl 安装 snap 上大分： 1 sudo snap install kubectl --classic 安装可能遇到的问题的解决方案 The “docker” driver should not be used with root privileges 使用命令 minikube start 启动，参数 driver 默认为 docker 。如果以 root 用户运行该命令会出现如标题所示的错误，下面是解决方法： minikube - Why The “docker” driver should not be used with root privileges - Stack Overflow...

《云原生开发实践》记录 本书会包含大量的实践内容，现阶段应着重看理论内容、实践内容暂且忽略，实践内容在理论补充完毕后用到哪块补哪块。 容器化 DOCKERFILE 的多阶段构建在部署阶段很有用，可以大幅减少镜像的体积。 Docker 可以自建网络，这样就可以把很多容器纳入到同一个网络下，实现容器间按容器名访问对方。 容器编排 对于一个中大型的应用，会有很多的容器组件。而有些容器如Redis、RabbitMQ、Kafka等需要紧密的配合，这时候就需要用到容器编排。 Docker Compose 组件用于实现本地单个节点上的容器编排，它会从 docker-compose.yaml 文件中读取所需的全部容器的定义，然后运行 docker-compose up 命令启动容器编排。Docker Swarm 可以管理多个节点上的容器，即管理 Docker 集群。 云原生软件生产流程 云计算的能力： 弱化了传统 IT 硬件概念，革命性地降低了企业在基础设施上的建设成本。 实现了弹性获取计算资源，用户可以按需使用。 云计算的成熟时云原生发展的基石，使云原生的许多概念得以落地。云原生应用一般有以下特点： 在应用的设计和开发阶段就为部署到云上做适配。 应用由多个松耦合的小模块构成而不是一个庞大的单体项目，即微服务架构。 通过容器来交付和发布应用，应用代码中会加入容器化需要的文件。 和传统的软件生产方式相比，云原生的优势主要在塔提高了应用发布和运维时的效率，显著降低了运维的复杂性。 云原生基础设施 Kubernetes Kubernetes 是开源的容器编排平台，支持集群环境下部署和管理容器化应用。目前已经是容器编排领域的事实标准，成为云原生的操作系统。Kubernetes 也叫 K8s ，8指中间的8个字母。K8s 2013年由 Google 开源，相比于 Docker Swarm K8s 提供更加复杂强大的功能。 K8s 集群中包含两种节点，一种是 Control Plane 节点（master 节点），另一种是 worker 节点。K8s 中的容器运行在 Pod 中，Pod 运行在 Node 中。每个集群默认至少有一个 Pod ，否则 Pod 无法调度和运行。Control Plane 是 K8s 的容器编排层，通过它提供的 API ，可以定义和部署容器及管理容器的整个生命周期。Control Plane 有以下组件：...

《Go微服务实战》记录 本书包含很多的 Go 基础和部分进阶内容，这里只选取对现阶段有帮助的内容，毕竟 Go 已经入门过一遍了。 Go 基础 关于指针，如果涉及到修改变量本身就使用指针作为函数输入变量等，典型的如单例模式下的变量都是指针。反之如果不修改变量本身，就直接使用复制变量作为函数输入变量等，函数返回值自然也是某个新的变量。 关于 Go 中的循环，请看 code： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 package main func main() { for i := 0; i < 10; i++ { ... } // 最标准的循环 for { ... } // 就是没有显式跳出条件的 while arr := []int{1, 2, 3, 4, 5} for i, v := range arr { ... } // 这里的 range 是关键字，用法有些类似于 Python 中的 enumerate 函数 } Go 的垃圾回收策略使用的三色标记法，具体内容会单独进行学习。...

《PostgreSQL指南》记录 Why choose PostgreSQL, or not MySQL ? SQL 标准支持更好：PostgreSQL 对 SQL 标准的支持更加全面，而 MySQL 在某些情况下依赖非标准实现（如分组函数的行为）。 高级功能更强： JOSNB 的性能更优：PostgreSQL 的 JSONB 数据类型支持更高效的索引和操作，而 MySQL 的 JSON 功能较为有限。 复杂查询：支持递归查询、窗口函数等复杂功能，而 MySQL 在这些方面功能较弱或支持有限。 并行查询：PostgreSQL 提供原生的并行查询能力，能够充分利用多核 CPU，而 MySQL 直到 8.0 版本才有一定程度的改进。 扩展性更好： PostgreSQL 支持自定义数据类型、函数和插件，更适合需要扩展或复杂业务逻辑的项目。 PostGIS 插件使其在地理信息领域表现出色，而 MySQL 的 GIS 功能相对简单。 更高的性能和灵活性： 支持多种索引类型（如 GIN、GiST、BRIN 等），适合高性能全文搜索、地理查询等场景。 支持更复杂的查询优化器策略，适合复杂查询和数据分析。 更可靠的数据一致性： PostgreSQL 的 MVCC 机制更成熟，避免了常见的锁争用问题。 MySQL 的 MVCC 在某些情况下（如高并发）性能欠佳，容易导致死锁。 PostgreSQL 适用于有复杂数据分析需求、地理信息系统、高并发和大数据量等应用场景，相比于 MySQL 的应用场景更复杂。 数据库集簇、数据库和数据表 数据库集簇的逻辑结构 数据库集簇是一组数据库的集合，由一个 PostgreSQL 服务器管理。而数据库是数据对象的集合，数据库对象用于存储或引用数据的数据结构。 在 PosgreSQL 中，所有的数据库对象都通过相应的对象标识符（oid）进行管理，这些标识都是无符号 4 字节整型。...

《高效使用Redis》记录 基础数据结构解析 对象 Redis中的 RedisObject 的 c 定义： 1 2 3 4 5 6 7 8 #define LRU_BITS 24 typedef struct redisObject { unsigned type:4; // 数据类型 unsigned encoding:4; // 底层数据结构 unsigned lru:LRU_BITS; // 缓存淘汰时使用 int refcount; // 引用计数 void *ptr; // 指向实际存储位置 } robj; RedisObject 是 Redis 中数据结构的一个抽象，用它来存储所有的 key-value 数据。 下面是结构体中各个属性的。说明： type：用来表示对象类型； encoding：表示当前对象底层存储所采用的数据结构，如int、字典、压缩列表、跳跃表等等； lru：用于在配置文件中通过 maxmemory-policy 配置已用内存到最大内存限制时的缓存淘汰策略。 以 GET 命令为例，简单看看 Redis 中的 LRU 实现。使用 GET 后，会执行这段代码更新对象的 lru 属性： 1 2 3 4 5 if (server....

《gRPC与云原生应用开发》记录 gRPC 入门 gRPC 的定义 gRPC 是一项进程间通信技术，可以用来连接、调用、操作和调试分布式异构应用程序。 开发 gRPC 应用程序时，要先定义服务接口：消费者消费信息的方式、消费者能够远程调用的方法以及调用方法所使用的参数和消息格式等。在服务定义中使用的语言叫作接口定义语言（IDL）。 下面是使用 protocol buffers 作为 IDL 来定义服务接口： 服务定义 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 // ProductInfo.proto syntax = "proto3"; package ecommerce; // 防止协议消息类型之间发生命名冲突 // 定义服务接口 service ProductInfo { rpc addProduct(Product) returns (ProductID); rpc getProduct(ProductID) returns (Product); } // 定义消息格式 message Product { string id = 1; string name = 2; string description = 3; } message ProductID { string value = 1; } 上面定义完成之后，就使用 protocol buffers 编译器 protoc 生成服务器端和客户端代码。...

《深入RabbitMQ》记录 RabbitMQ 基础 AMQP 协议 AMQP，即高级消息队列协议（Advanced Meesage Queuing Protocal）。它定义了一个 AMQ 应该有以下三部分： 交换器：一个接收器接收发送到 MQ 中的消息并决定把它们投递到何处； 队列：存储接收到的消息； 绑定：定义队列和交换器之间的关系。在 RabbitMQ 中，绑定或者叫绑定键即告知一个叫交换器应该将消息投递到哪些队列中。 使用 AMQ 协议与 Rabbit 进行交互 AMQP 帧类型 AMQP 规定了五种类型的帧： 协议头帧：用于连接到 RabbitMQ，仅使用一次； 方法帧：携带发送到 RabbitMQ 或从 RabbitMQ 接收到的 RPC 请求或响应； 内容头帧：包含一条消息的大小和属性； 消息体帧：包含消息的内容； 心跳帧：确保连接，一种校验机制。 将消息编组成帧 首先是方法帧、内容头帧，这两种帧比较好理解。 而消息体帧会根据消息体的大小切分成一到多个消息体帧。 要发送消息，首先发送的是方法帧，之后是内容帧，最后是若干个消息体帧。 帧结构 方法帧携带构建 RPC 请求所需的类、方法和参数。 内容头帧包含了消息的大小和其他对消息起描述作用的属性。 消息体帧可以传输很多类型的数据，可以是二进制、文本，也可以是二进制化的图片和序列化后的json、xml。 使用协议 包含下面一个基本流程： 声明交换器 声明队列 绑定队列到交换器 发布消息到 RabbitMQ 从 RabbitMQ 消费消息 消息属性详解 使用 content-type 创建显式的消息契约 在不同的语言的消费者框架中，框架可以自动的根据 content-type 类型将其反序列化为该语言中的数据结构。 使用 gzip 和 content-encoding 压缩消息大小 通过指定 content-encoding 属性可以在消息体上应用特殊的编码。...

华为云部署踩坑 Docker 国内镜像源（截止到2024.11.1） DockerHub 镜像仓库 是否正常 hub.xdark.top 正常 hub.littlediary.cn 正常 dockerpull.org 新增 hub.crdz.gq 正常 docker.1panel.live 正常 docker.unsee.tech 新增 docker.m.daocloud.io 正常 docker.kejilion.pro 正常 registry.dockermirror.com 正常 hub.rat.dev 正常 dhub.kubesre.xyz 正常 docker.nastool.de 正常 docker.hpcloud.cloud 失效 docker.hlyun.org 失效 doublezonline.cloud 失效 docker.chenby.cn 失效 ginger20240704.asia 失效 lynn520.xyz 失效 hub.docker-ttc.xyz 失效 noohub.ru 失效 docker.nat.tf 失效 dockerproxy.cn 失效 freeno.xyz 失效 docker.registry.cyou 失效 hub.yuzuha.cc 失效 docker-cf.registry.cyou 失效 docker.mrxn.net 失效 dockerproxy.github.io 失效 docker.wget.at 失效 atomhub.openatom.cn 失效 ccr.ccs.tencentyun.com 失效 dockerproxy.com 失效 dislabaiot....

牢骚 时隔一个多月才完成了基本的可视化系统的搭建，中间有着各种各样的原因：Vue3第一次用、Django-Ninja不熟悉等等再加上一些闲杂原因就一直拖到了现在，效率多少有点堪忧。 总之不算怎么说，也算是曲折的完成了原定计划，下面将从后端、前端的技术选择、功能介绍、成品展示等几个章节大致的讲述下。 后端 项目地址 KurongTohsaka/PCCKGVisualization 技术栈 Web 框架自然是选相对擅长且好用的 Django ，但是 Django 本身使用起来又过于繁重，不太适合开发Restful类型的接口，所以一般会搭配着 Django REST Framework (DRF) 使用。但是这一次我打算尝试一个新的 Django 扩展，它是 FastAPI 的 Django 版：Django-Ninja 。 Web 框架订好了以后，就该选数据库了。既然是存储图数据，那肯定是 Neo4j 。而网站数据就使用简单的 Sqlite 吧，主要就是省事。 功能与接口 下面的所有接口的最上级请求路径：pcc_kg_vs 功能主要分为两部分：认证和可视化。 首先是认证，包含以下基本功能： 用户认证：用户登陆、注册、登出 API 鉴权：token 验证 CSRF 验证：CSRF token 验证 下面是简易的接口标准： 登陆 先检查该用户是否已注册，若注册则从数据库中根据信息查询到用户，然后登陆该用户。若未注册则登陆失败 1 2 3 4 5 6 7 8 9 10 11 12 13 14 { "method": "POST", "path": "/login", "params": { "username": "", "password": "" }, "return": { "successful": bool, "code": int, "token": str, //登陆令牌 'info': str } } 登出 HTTPBearer...

拉取 neo4j Docker image 在 MAC 上用的 Docker Desktop，确实很方便操作。 直接在 Image Tab 页搜 Neo4j 就有一个官方 image，我选的 5.24.1版本，pull 下来。 这里之所以要选择一个特定的版本，原因是之后要启用的 apoc 扩展需要用对应 neo4j 版本的 jar 包。 配置容器 因为用的 Docker Desktop，很多没必要的步骤都可以直接忽略。配置好转发端口、挂载位置后，就启动容器。 Neo4j 容器启动后默认直接运行，登陆 Web 管理界面配置后用户名密码后就完成了基本配置。 Docker 真 tm 好用（ 配置 apoc 这里需要注意一点，neo4j 5.x 之后的版本中，apoc 本身的相关配置需要写在 neo4j/conf/apoc.conf 里，而不是 neo4j/conf/neo4j.conf 中，不然在启动服务时会报错！！！ 首先是 apoc 的下载地址：Index of /doc/neo4j-apoc/ 。 下载好后，把它放进 neo4j/plugins，并改名为 apoc.jar （啥名都行，这里是方面后面改配置）。 接下来修改 neo4j/conf/neo4j.conf ，修改以下两行并取消该行注释： 1 2 dbms.security.procedures.unrestricted=apoc.* dbms.security.procedures.allowlist=apoc.coll.*,apoc.load.* 最后修改 neo4j/conf/apoc.conf ： 1 2 apoc.import.file.enabled=true apoc....

Link https://arxiv.org/abs/2310.04994#:~:text=We%20propose%20DENRL,%20a%20generalizable%20framework%20that%201) Accepted by ACL 2024. Intro 联合抽取旨在使用单一模型检测实体及其关系，这是自动知识库构建中的关键步骤。为了廉价地获取大量标注的联合训练数据，提出了远程监督（Distantly Supervise，DS），通过将知识库（Knowledge Base，KB）与未标注的语料库对齐，自动生成训练数据。假设如果一个实体对在 KB 中有关系，则包含该对的所有句子都表达相应的关系。 然而，DS 带来了大量的噪声标签，显著降低了联合抽取模型的性能。此外，由于开放域 KB 中实体的模糊性和覆盖范围有限，DS 还会生成噪声和不完整的实体标签。在某些情况下，DS 可能导致 KB 中包含超过30%的噪声实例，使得学习有用特征变得不可能。 处理这些噪声标签的先前研究要么考虑弱标注的实体，即远程监督的命名实体识别（NER），要么考虑噪声关系标签，即远程监督的关系抽取（RE），它们专注于设计新颖的手工制作关系特征、神经架构和标注方案以提高关系抽取性能。此外，使用大型语言模型（LLMs）的上下文学习（ICL）也很流行。然而，它们资源需求高，对提示设计敏感，可能在处理复杂任务时表现不佳。 为了廉价地减轻两种噪声源，我们提出了 DENRL （Distantly-supervised joint Extraction with Noise-Robust Learning）。DENRL 假设 可靠的关系标签，其关系模式显著表明实体对之间的关系，应该由模型解释； 可靠的关系标签也隐含地表明相应实体对的可靠实体标签。 具体来说，DENRL应用词袋正则化（BR）引导模型关注解释正确关系标签的显著关系模式，并使用基于本体的逻辑融合（OLF）通过概率软逻辑（PSL）教授底层实体关系依赖性。这两种信息源被整合形成噪声鲁棒损失，正则化标注模型从具有正确实体和关系标签的实例中学习。接下来，如果学习到的模型能够清晰地定位关系模式并理解候选实例的实体关系逻辑，它们将被选择用于后续的自适应学习。我们进一步采样包含已识别模式中对应头实体或尾实体的负实例以减少实体噪声。我们迭代学习一个可解释的模型并选择高质量实例。这两个步骤相互强化——更可解释的模型有助于选择更高质量的子集，反之亦然。 Joint Extraction Architecture Tagging Scheme 为了同时抽取实体（提及和类型）和关系，我们为每个起始位置 $p$ 标注四元组 ${e_1, tag_1, e_2, r_e}$，并定义 “BIO” 标记来编码位置。对于一个 $T$ 个 token 的句子，我们根据不同的起始位置标注 $T$ 个不同的标记序列。 对于每个标记序列，如果 $p$ 是一个实体的起始位置（该序列是一个实例），则在 $p$ 处标注实体类型，并用关系类型标注与 $p$ 处实体有关系的其他实体。其余的令牌标注为 “O”（Outside），表示它们不对应头实体。这样，每个标记序列将生成一个关系四元组。 我们将包含至少一个关系的实例定义为正实例，没有关系的实例定义为负实例。“BIO”（Begin, Inside, Outside）标记用于指示每个实体中令牌的位置信息，以便同时提取多词实体和关系类型。注意，我们不需要尾实体类型，因为每个实体都会被查询，我们可以从 T 标记序列中获得所有实体类型及其关系。 Tagging Model Self-Match BERT...

Link [2205.09837v2] Summarization as Indirect Supervision for Relation Extraction (arxiv.org) Accepted EMNLP 2022. Intro 关系抽取（RE）旨在从文本中提取实体之间的关系。例如，给定句子“Steve Jobs 是 Apple 的创始人”，RE 模型会识别出“创立”这一关系。RE 是自然语言理解的重要任务，也是构建知识库的关键步骤。先进的 RE 模型对于对话系统、叙事预测和问答等知识驱动的下游任务至关重要。 现有的 RE 模型通常依赖于带有昂贵注释的训练数据，这限制了它们的应用。为了应对这一问题，本文提出了一种新的方法——SURE（Summarization as Relation Extraction），将 RE 转化为摘要任务，通过间接监督来提高 RE 的精度和资源效率。 图1展示了 SURE 的结构。具体来说，SURE 通过关系和句子转换技术将 RE 转化为摘要任务，并应用约束推理进行关系预测。我们采用实体信息口语化技术，突出包含实体信息的句子上下文，并将关系口语化为模板式的简短摘要。这样，转换后的RE输入和输出自然适合摘要模型。然后，我们通过在转换后的RE数据上进行微调，将摘要模型适配于RE任务。在推理过程中，设计了一种 Trie 评分技术来推断关系。通过这种方式，SURE 充分利用了摘要的间接监督，即使在资源匮乏的情况下也能获得精确的RE模型。 这项工作的贡献有两个方面。首先，据我们所知，这是首次研究利用摘要的间接监督进行RE。由于摘要的目标与 RE 自然对齐，它允许在不完全依赖直接任务注释的情况下训练出精确的 RE 模型，并在资源匮乏的情况下表现出色。其次，我们研究了有效桥接摘要和 RE 任务形式的输入转换技术，以及进一步增强基于摘要的RE推理的约束技术。我们的贡献通过在三个广泛使用的句子级 RE 数据集 TACRED、TACREV 和 SemEval 以及 TACRED 的三个低资源设置上的实验得到验证。我们观察到，SURE 在低资源设置下（使用10%的 TACRED 训练数据）优于各种基线。SURE 还在 TACRED 和 TACREV上 分别以75.1%和83.5%的 micro-F1 得分达到了SOTA 性能。我们还进行了全面的消融研究，展示了摘要的间接监督的有效性以及 SURE 输入转换的最佳选项。...

Link [2109.05362] Modular Self-Supervision for Document-Level Relation Extraction (arxiv.org) Accepted at EMNLP 2021 Intro 信息抽取的先前工作通常集中在句子内的二元关系。然而，实际应用往往需要跨大段文本提取复杂关系。这在生物医学等高价值领域尤为重要，因为获取最新发现的高召回率至关重要。例如，图1显示了一个三元（药物、基因、突变）关系，表明具有 MAP2K1 突变 K57T 的肿瘤对 cobimetinib 敏感，但这些实体从未在同一段落中同时出现。 先前的工作都将文档级关系抽取视为一个单一的整体问题，这在推理和学习上都带来了重大挑战。尽管最近取得了一些进展，但在使用最先进的神经架构（如LSTM 和 transformer）建模长文本范围时仍存在显著挑战。此外，直接监督稀缺，任务特定的自监督（如距离监督）在应用于短文本范围之外时变得极其嘈杂。 在本文中，我们通过将文档级关系抽取分解为局部关系检测和全局推理来探索一种替代范式。具体来说，我们使用 Davidsonian 语义表示 $n$ 元关系，并结合段落级关系分类和使用全局推理规则（例如，参数解析的传递性）的篇章级参数解析。每个组件问题都存在于短文本范围内，其相应的自监督错误率要低得多。我们的方法借鉴了模块化神经网络和神经逻辑编程的灵感，将复杂任务分解为局部神经学习和全局结构化集成。然而，我们不是从端到端的直接监督中学习，而是承认组件问题的模块化自监督（Modular Self-Supervision），这更容易获得。 这种模块化方法不仅使我们能够处理长文本，还能扩展到所有先前方法无法覆盖的跨段落关系。我们在精准肿瘤学的生物医学机器阅读中进行了全面评估，其中跨段落关系尤为普遍。我们的方法在最具挑战性的关系中表现尤为突出，这些关系的参数从未在段落中同时出现，其F1分数比之前的最先进方法（如多尺度学习（和图神经网络高出20多个百分点。 Document-Level Relation Extraction 设 $E,R,D$ 分别代表实体、关系、文档，那在图2中的 $R$ 为精准癌症药物反应，实体 $E_1,E_2,E_3$​ 分别药物 cobimetinib、基因 MAP2K1 和突变 K57T。这个关系跨越多个段落和几十个句子。 用新戴维森语义表示 n 元关系抽取： $$ R_D(E_1, \cdots, E_n) \equiv \exists T \in D \exists r. [R_T(r) \land A_1(r, E_1) \land \cdots \land A_n(r, E_n)] $$ 其中，$T$ 为文档 $D$ 中的片段，$r$ 为引入的事件变量以表示 $R$​ 。...

Link [2109.12008v1] Separating Retention from Extraction in the Evaluation of End-to-end Relation Extraction (arxiv.org) Accepted at EMNLP 2021 Intro 信息抽取（Information Extraction, IE）旨在将文本中表达的信息转换为预定义的结构化知识格式。这个总体目标被分解为更容易自动执行和评估的子任务。因此，命名实体识别（Named Entity Recognition, NER）和关系抽取（Relation Extraction, RE）是两个关键的 IE 任务。传统上，这些任务是通过流水线方式执行的。也可以采用联合方式处理，以建模它们的相互依赖性，减少错误传播并获得更现实的评估设置。 随着 NLP 领域的总体趋势，最近在实体和关系抽取基准测试中报告的定量改进至少部分归因于使用了越来越大的预训练语言模型（Language Models, LMs），如 BERT 来获得上下文词表示。同时，人们意识到需要新的评估协议，以更好地理解所获得的神经网络模型的优缺点，而不仅仅是对一个保留测试集上的单一整体指标。 特别是，对未见数据的泛化是评估深度神经网络的关键因素。在涉及提取提及的IE任务中，这一点尤为重要：小范围的词语可能会同时出现在评估和训练数据集中。已证明这种词汇重叠与NER中神经网络的性能相关。对于流水线 RE，神经模型过度依赖候选参数的类型或其上下文中存在的特定触发词。 在端到端关系抽取中，我们可以预期这些 NER 和 RE 会结合在一起。在这项工作中，我们认为当前的评估基准不仅衡量了从文本中提取信息的能力，还衡量了模型在训练期间简单保留标记的（头、谓词、尾）三元组的能力。当模型在训练期间看到的句子上进行评估时，很难区分这两种行为中的哪一种占主导地位。 然而，我们可以假设模型可以简单地检索先前看到的信息，像一个被压缩的知识库一样，通过相关查询进行探测。因此，在包含过多已见三元组的示例上进行测试可能会高估模型的泛化能力。 即使没有标记数据，LMs也能够学习一些单词之间的关系，可以通过填空句子进行探测，其中一个参数被掩盖。 Datasets and Models 数据集选用了 CoNLL04、ACE05、SciERC。 模型选用了三个模型： PURE：Pipeline 模型 SpERT：Joint 模型 Two are better than one（TABTO）：Joint 模型 Partitioning by Lexical Overlap（基于词汇重叠的划分） 我们根据与训练集的词汇重叠情况对测试集中的实体提及进行划分。我们区分了已见和未见的提及，并将这种划分扩展到关系上。 我们实现了一个简单的保留启发式方法（Retention Heuristic，启发式方法），将训练集中确切存在的实体提及或关系标记为其多数标签。我们在表1中报告了 NER 和 RE 的 Micro-avg....

Link [2210.13733] Better Few-Shot Relation Extraction with Label Prompt Dropout (arxiv.org) Accepted EMNLP 2022. Intro 在这项工作中，我们提出了一种称为标签提示丢弃（Label Prompt Dropout, LPD）的新方法。我们直接将文本标签和上下文句子连接在一起，并将它们一起输入到 Transformer Encoder 中。文本标签作为标签提示，通过自注意力机制引导和规范 Transformer Encoder 输出标签感知的关系表示。在训练过程中，我们随机丢弃提示标记，使模型必须学会在有和没有关系描述的情况下工作。实验表明，我们的方法在两个标准的FSRE数据集上取得了显著的改进。我们进行了广泛的消融研究，以证明我们方法的有效性。此外，我们强调了先前研究工作评估设置中的一个潜在问题，即预训练数据中包含的关系类型实际上与测试集中的关系类型重叠。我们认为这对于少样本学习来说可能不是一个理想的设置，并表明现有工作的性能提升可能部分归因于这种“知识泄漏”问题。我们建议过滤掉预训练数据中所有重叠的关系类型，并进行更严格的少样本评估。总之，我们做出了以下贡献： 我们提出了 LPD，一种新的标签提示丢弃方法，使 FSRE 中的文本标签得到了更好的利用。这种简单的设计显著优于以前使用复杂网络结构将文本标签和上下文句子融合的方法。 我们识别了文献中先前实验设置的局限性，并提出了一个更严格的FSRE评估设置。对于这两种设置，我们都显示出比以前的最先进方法更强的改进。 Related Work Few-Shot Relation Extraction Prompt-Based Fine-Tuning 基于提示的模型在小样本和零样本学习中表现出色。这一研究方向的模型尝试将下游微调任务与预训练的掩码语言建模目标对齐，以更好地利用预训练语言模型的潜在知识。 然而，与许多其他自然语言处理任务（如二元情感分析中的“正面/负面”）的标签语义直观不同，关系抽取中的关系类型可能非常复杂，通常需要较长的句子来描述。例如，FewRel 中的关系 P2094 被描述为“由监管机构进行的官方分类，主体（事件、团队、参与者或设备）符合纳入标准”。基于提示的模型在这种情况下会遇到困难，因为它们需要固定的模板（例如，提示模板中的 [MASK] 令牌数量必须固定）。以前的方法不得不依赖手动设计的提示模板，并使用关系名称而不是关系描述。 为了解决这个问题，我们提出直接使用整个关系描述作为提示，而不使用任何掩码令牌。在传统的基于提示的模型中，提示用于创建自然描述，以便模型可以在 [MASK] 位置进行更好的预测，而本研究中使用的标签提示通过自然描述来帮助规范模型输出更好的类别表示。 Approach Training with Label Prompt Dropout 对于每个支持实例，我们直接将关系描述和上下文句子用“:”连接起来。例如，句子“北京举办了2022年冬季奥运会”将变成“事件地点: 北京举办了2022年冬季奥运会。” 这个想法是创建一个自然的实例，其中定义首先给出，然后是例子。关系描述和冒号作为标签提示，引导 Transformer Encoder 输出一个标签感知的关系表示。为了防止模型完全依赖标签提示而忽略上下文句子，标签提示会以 $α_{train}$ 的概率随机丢弃。例如，上图中的支持实例“十进制数最早在印度发展起来”保持其初始形式，因为其标签提示被丢弃了。对于查询实例，我们直接输入句子而不带任何标签提示。这是因为查询集本质上与测试集相同，我们不应假设可以访问真实知识。随后，使用特殊实体标记来标记头部和尾部，并在句子的前后添加特殊的分类和分隔标记，例如“[CLS] 事件地点: [E1] 北京 [/E1] 举办了 [E2] 2022年冬季奥运会 [/E2]。” 解析后的句子然后被送入Transformer Encoder。...

Link [2402.15713] Making Pre-trained Language Models Better Continual Few-Shot Relation Extractors (arxiv.org) Accepted COLING 2024 COLING: CCF B Intro 关系抽取是自然语言处理领域中的一个基本且重要的任务，旨在从句子或文档中提取实体之间的潜在关系。传统的 RE 方法在大量标注样本上训练模型，然后在具有相同标签空间的数据上进行测试。然而，在现实生活中，新关系不断涌现，这些模型在适应新关系时可能会出现显著的性能下降。此外，这些模型严重依赖于大量标注数据，这需要大量时间和精力来收集。 因此，提出了持续少样本关系抽取（Continual Few-shot Relation Extraction, CFRE），其目标是在有限的标注数据约束下，持续学习新关系的同时保留先前学习的关系知识。这一实际任务带来了两个重大挑战： 灾难性遗忘：模型在学习新任务时突然忘记从前任务中获得的知识。最新研究指出，即使在大型语言模型中也存在灾难性遗忘问题，这使得这一问题值得研究。 过拟合：模型在训练数据上表现异常好，但由于拟合噪声或无关模式，无法有效泛化到未见数据，这在训练数据稀少的低资源场景中更为明显。 总结一下，我们的主要贡献包括： 我们利用提示学习来探索预训练语言模型（PLM）的隐含能力，并提出了 Contrastive Prompt Learning framework (CPL) 框架，将其与一种新的基于边际的对比学习目标（CFRL）结合起来，同时缓解灾难性遗忘和过拟合问题。 我们通过利用大型语言模型（LLM）的力量引入了一种记忆增强策略，以提升较小的 PLM。这种策略使用精心设计的提示来指导 ChatGPT 生成样本，从而更好地对抗过拟合。 在两个 RE 基准上的大量实验表明，我们的方法优于最先进的模型，证明了缓解灾难性遗忘和过拟合的有效性。 Related Work Continual Learning 持续学习（Continual Learning, CL）旨在从一系列任务中不断学习新知识，同时避免遗忘旧知识。CL的主要挑战是灾难性遗忘。 现有的CL方法分为三类： 正则化方法：使用额外的约束来限制参数更新，使模型能够记住更多旧知识。 动态架构方法：动态扩展模型架构，以在任务序列不断出现时存储新知识。 基于记忆的方法：存储当前任务的一些典型样本，并在学习任务序列后重放记忆以复习旧知识。 在这些方法中，基于记忆的方法在自然语言处理（NLP）任务中最为有效。然而，新任务的数据并不总是充足的，而且获取高质量数据往往既昂贵又耗时。我们也采用基于记忆的策略，但我们更注重如何更好地利用预训练语言模型（PLMs）来解决 CFRE。 Prompt Learning 提示学习随着GPT-3系列的诞生而出现，并在自然语言处理任务中取得了显著的性能，尤其是在小样本场景中。它通过添加提示词将下游任务重新表述为预训练任务，并引导预训练语言模型（PLMs）理解各种任务。之前的提示学习方法可以分为三类： 硬提示：在句子中添加手工制作的提示词，并将其转换为掩码语言建模问题。尽管有效，但它需要针对不同任务的复杂专家知识，这既繁琐又耗时。 软提示：在句子中添加可连续训练的向量，这些向量可以被模型自动学习。然而，在没有任何先验专家知识的情况下，模型并不总能学到合适的提示，尤其是在低资源场景中。 混合提示：结合不可调的硬提示和可调的软提示，使模型能够在少量人工干预下轻松学习合适的模板。它被验证为最有效的方法。 我们专注于少样本设置，并采用混合提示来帮助预训练语言模型（PLMs）缓解灾难性遗忘和过拟合问题。 Method Framework Overview 整个 CPL 框架有三个模块：...

Link [2403.16543] Efficient Information Extraction in Few-Shot Relation Classification through Contrastive Representation Learning (arxiv.org) Accepted NAACL 2024. Intro 关系分类（Relation Classification, RC）是关系抽取中的一个重要子任务，主要关注在给定文本上下文中识别实体对之间的关系类型。为了实现这一目标，RC 模型必须从句子中提取丰富的信息，包括上下文线索、实体属性和关系特征。虽然语言模型在提取文本表示方面重要，但它们在句子表示中的向量空间使用并不理想。为了改进这一点，最近的研究通过各种技术增强了句子表示。 关系抽取在许多关系类型上面临数据有限的挑战，并且数据获取成本不成比例。为了解决这一挑战，通过小样本 RC 训练模型以快速适应新关系类型，仅使用少量标记示例。 由于区分各种关系类型的内在复杂性，RC 应用通常将实体标记令牌的表示作为句子表示。最近的工作在少样本 RC 中使用对比学习以获得更具辨别力的表示。此外，研究表明，通过提示使用 [MASK] 令牌表示句子可以改善句子表示。 本文贡献如下： 新方法：我们引入了一种使用对比学习对齐多重表示的方法，用于小样本关系分类。 适应性：我们的方法能够适应各种资源限制，并扩展到包括关系描述在内的额外信息源。 资源效率：我们强调了该方法的资源效率，提升了在低资源环境下的性能。 实体标记： 实体标记技术通过在输入句子中添加标记来指示文本中的实体。例如，句子“他在2006年世界杯上为墨西哥效力”可以被标记为“他在[E1S]2006年世界杯[E1E]上为[E2S]墨西哥[E2E]效力”。 在 BERT 编码器中，句子的表示是通过连接实体开始标记的表示来构建的。这种方法增强了模型对实体及其关系的理解。 这种技术有助于模型更好地捕捉句子中的上下文线索、实体属性和关系特征，从而提高关系分类的准确性。 对比学习： 对比学习是一种用于增强模型表示能力的方法，特别是在少样本关系分类任务中。 对比学习的主要目标是使相似的样本在表示空间中更接近，而使不相似的样本更远离。 在训练过程中，对比学习会创建正样本对（相似样本）和负样本对（不相似样本），并通过优化模型使正样本对的表示更接近，负样本对的表示更远。而表现在损失函数中，对比学习的损失函数旨在最大化同一输入句子不同表示之间的相似性，同时最小化不同输入句子表示之间的相似性。 在少样本关系分类中，对比学习通过对齐多个句子表示（如[CLS]标记、[MASK]标记和实体标记）来提取补充的判别信息，从而提高模型在低资源环境中的表现。 Approach 方法一览： Sentence Representations 使用了平均池化从BERT编码器生成各种句子表示。 通过平均 token 表示来计算句子表示。同时，BERT-Base 编码器预训练期间使用 [CLS] 标记作为句子表示，捕捉整个输入序列的信息。实体标记技术通过在文本中标记实体来增强输入句子。这将输入增强为 $x = [x_0, …, [E1S], x_i, [E1E], …, x_n]$ 。句子表示通过连接实体开始标记表示 [E1S] 和 [E2S] 构建。 在 Prompt 方法中，RC 任务被重新表述为掩码语言建模问题。使用模板 T，每个输入被转换为包含至少一个 [MASK] 标记的 $x_{prompt} = T(x)$ 。这个掩码标记表示关系标签，并从上下文中预测，例如 $\hat x = [MASK]: x$​ 。 使用 dropout 掩码生成增强句子表示的方法。由于实体标记表示不适用于关系描述，我们使用提示和[CLS]表示，并使用不同的dropout掩码。 Prompt-Mask Method...

Link 2106.02401 (arxiv.org) Accepted ACL 2021。 Intro 小样本关系抽取（FSRE）大致可以分为两类： 仅使用纯文本数据，不包含外部信息。如：Siamese、Prototypical、BERT-PAIR 引入外部信息，以补偿 FSRE 的信息不足，如：TD-Proto 虽然引入文本描述的知识可以为 FSRE 提供外部信息并实现最先进的性能，但 TD-Proto 仅为每个实体引入一个 Wikidata 中的文本描述。然而，这可能会因为实体和文本描述之间的不匹配而导致性能下降。此外，由于每个实体的文本描述通常较长，提取长文本描述中最有用的信息并不容易。 与长文本描述相比，概念是对实体的直观和简洁的描述，可以从概念数据库（如 YAGO3、ConceptNet 和 Concept Graph 等）中轻松获得。此外，概念比每个实体的具体文本描述更抽象，这是对 FSRE 场景中有限信息的理想补充。 为了应对上述挑战，我们提出了一种新的实体概念增强的少样本关系抽取方案（CONCEPT-enhanced FEw-shot Relation Extraction，ConceptFERE），该方案引入实体概念以提供有效的关系预测线索。首先，如上表所示，一个实体可能有多个来自不同方面或层次的概念，只有一个概念可能对最终的关系分类有价值。因此，我们设计了一个概念-句子注意力模块，通过比较句子和每个概念的语义相似性来选择最合适的概念。其次，由于句子嵌入和预训练的概念嵌入不是在同一语义空间中学习的，我们采用自注意力机制对句子和选定概念进行词级语义融合，以进行最终的关系分类。 Model 下图为 ConceptFERE 的结构。 System Overview Sentence Representation Module 使用 BERT 作为 Encoder 来获取 Sentence Embedding，Concept Representation Module 使用 skip-grim 在 Wikipedia 文本和概念图上学习概念的表示，得到 Concept Embedding 。Relation Classifier 采用全连接层实现。 Concept-Sentence Attention Module 直观上，需要更多关注与句子语义相关度高的概念，这些概念可以为关系抽取提供更有效的线索。 首先，由于预训练的 Sentence Embedding $v_s$ 和 Concept Embedding $v_c$ 不是在同一语义空间中学习的，因此不能直接比较语义相似度。所以通过将 $v_c$ 和 $v_s$ 乘以投影矩阵 $P$ 来进行语义转换，以在同一语义空间中获得它们的表示 $v_cP$ 和 $v_sP$ ，其中 $P$ 可以通过全连接网络学习。其次，通过计算句子和每个实体概念之间的语义相似度，得到 $v_c$ 和 $v_s$ 的点积作为相似度 $sim_{cs}$ 。最后，为了从计算的相似度值中选择合适的概念，我们设计了 01-GATE 。相似度值通过 Softmax 函数归一化。如果 $sim_{cs}$ 小于设定的阈值 $α$，01-GATE 将为相应概念的注意力分数分配 0，该概念将在后续的关系分类中被排除。我们选择注意力分数为 1 的合适概念，作为参与关系预测的有效线索。...