Mutex

数据结构

mutex 互斥锁的数据结构如下：

• state：互斥锁的状态。
• sema：信号量，协程阻塞等待该信号量，解锁的协程释放信号量从而唤醒等待信号量的协程。

1
2
3
4

type Mutex struct {
    state int32
    sema  uint32
}

Mutex.state 是 32 位的整型变量，内部实现时把该变量分成四份，用于记录 Mutex 的四种状态：

• Locked：这个互斥锁是否被锁定。协程之间抢锁实际上是抢给 Locked 赋值的权利，能给 Locked 域置 1，就说明抢锁成功。
• Woken：是否有协程正在加锁过程中。
• Starving：互斥锁是否处于饥饿状态，饥饿状态说明有协程阻塞了超过 1ms。
• Waiter：表示阻塞等待锁的协程个数，协程解锁时根据此值来判断是否需要释放信号量。

加锁解锁过程

加锁

协程 A 成功加锁，协程 B 再加锁被阻塞的过程如下：

解锁

协程 A 解锁，释放信号量唤醒协程 B 过程如下。协程 A 解锁过程分为两个步骤：

• 一是把 Locked 位置 0。
• 二是查看到 Waiter>0，所以释放一个信号量，唤醒一个阻塞的协程，被唤醒的协程 B 把 Locked 位置 1，于是协程 B 获得锁。

map

数据结构

map 数据结构

map 的数据结构如下：

1
2
3
4
5
6
7
8
9
10

type hmap struct {
    count     int    // 元素的个数
    B         uint8  // buckets 数组的长度就是 2^B 个
    overflow uint16 // 溢出桶的数量

    buckets    unsafe.Pointer // 2^B个桶对应的数组指针
    oldbuckets unsafe.Pointer  // 发生扩容时，记录扩容前的buckets数组指针

    extra *mapextra //用于保存溢出桶的地址
}

底层使用哈希表作为实现，一个表里面有多个哈希表节点（哈希桶）bucket，每一个 bucket 保存了 map 中的一组键值对。

bucket 数据结构

一个 bucket 的数据结构如下：

1
2
3
4
5
6

type bmap struct {
    tophash [8]uint8 //存储哈希值的高8位
    data    byte[1]  //key value数据:key/key/key/.../value/value/value...
    overflow *bmap   //溢出bucket的地址
}

每一个 bucket 可以存放 8 个键值对。

如果满了，而且又来一个 key 落在了这个桶里，则会使用 overflow 连接下一个溢出桶。

插入和查找

插入过程

在 map 中的插入过程如下：

• 首先根据 key 计算出哈希值。取哈希值的低 hmap.B 位，来确定是几号桶。
• 遍历当前桶，查找该key是否已经存在：
  • 若存在，则更新该值。
  • 若不存在，则进行插入，找到第一个可以插入的位置进行插入。

哈希冲突：Golang 使用链地址法处理哈希冲突，在哈希桶中可以存放 8 个键值对，如果满了则通过 overflow 指针像链表一样链接下一个溢出桶。

查找过程

在 map 中的查找过程如下：

• 首先根据 key 计算出哈希值。取哈希值的低 hmap.B 位，来确定是几号桶。
• 根据 bmap.tohash 前 8 位快速确定在这个哈希桶的哪个位置。tophash 可以快速确定 key 是否正确，也可以把它理解成一种缓存措施，如果前 8 位都不对了，后面就没有必要比较了。
• 对比 key 完整的哈希值是否匹配，如果匹配则获取对应的 value。
• 如果没有找到，则去下一个溢出桶中查找。

chan

数据结构

channel 的数据结构如下：

1
2
3
4
5
6
7
8
9
10
11
12
13

type hchan struct {
    qcount   uint           // 当前队列中剩余元素个数
    dataqsiz uint           // 环形队列长度，即可以存放的元素个数
    buf      unsafe.Pointer // 环形队列指针
    elemsize uint16         // 每个元素的大小
    closed   uint32            // 标识关闭状态
    elemtype *_type         // 元素类型
    sendx    uint           // 队列下标，指示元素写入时存放到队列中的位置
    recvx    uint           // 队列下标，指示元素从队列的该位置读出
    recvq    waitq          // 等待读消息的goroutine队列
    sendq    waitq          // 等待写消息的goroutine队列
    lock mutex              // 互斥锁，chan不允许并发读写
}

可以看到，channel 的底层数据结构由一个环形队列构成。

lock 保证了 channel 的线程安全，在一个时间点上只会被一个线程（协程）访问。

环形队列

channel 内部实现了一个环形队列作为其缓冲区，环形队列的长度（dataqsiz）是创建 channel 时指定的。如下所示：

等待队列

从 channel 读数据，如果 channel 缓冲区为空或者没有缓冲区，当前 goroutine 会被阻塞。同样的，向 channel 写数据，如果 channel 缓冲区已满或者没有缓冲区，当前 goroutine 会被阻塞。

被阻塞的 goroutine 将会挂在 channel 的等待队列（recvq 和 sendq）中：

• 因读阻塞的 goroutine 会被向 channel 写入数据的 goroutine 唤醒。
• 因写阻塞的 goroutine 会被从 channel 读数据的 goroutine 唤醒。

下图展示了一个没有缓冲区的 channel，有几个 goroutine 阻塞等待读数据：

一般情况下，sendq 和 recvq 至少有一个为空。

只有一个例外，就是用同一个 goroutine 使用 select 语句向 channel 一边读数据一边写数据。

channel 读写

写数据

向一个 channel 中写数据的流程如下：

• 如果队列 recvq 不为空，则说明缓存区中没有数据或者没有缓冲区，此时从 recvq 中取出 G，并且把数据写入 G 中，最后唤醒 G。
• 如果队列 recvq 为空：
  • 如果环形队列有空位，则将数据写入环形队列中。
  • 如果环形队列没有空位，则将当前 goroutine 加入到 sendq 中，等待被唤醒。

A Novel Global Feature-Oriented Relational Triple Extraction Medel

来源：EMNLP 2021

作者：Feiliang Ren, Longhui Zhang, Shujuan Yin, Xiaofeng Zhao, Shilei Liu etc.

机构：Northeastern University

motivation：基于填表的关系抽取中，大多数只关注使用局部特性，而忽略了关系和标记对的全局关联，这可能回丢失一些重要的信息。为了克服这种缺陷，论文提出了基于全局特征的关系抽取模型，这个模型很好的利用了上述关系和标记对的全局关联。这种全局关联不仅提高了准确性，而且提高了召回率。

GitHub：https://github.com/neukg/GRTE

方法论

填表策略

对于一个长度为 n 的句子，为每一个 relation 维护一张 n×n 的表，核心在于为表中的每一项分配一个标签。标签包括：N/A，MMH，MMT，MSH，MST，SMH，SMT，SS。标签解释如下：

• N/A：第 i 个 token 和第 j 个 token 没什么关系。
• SS：第 i 个 token 到第 j 个 token 为一个实体。
• MMH，MMT，MSH，MST，SMH，SMT：第 i 个 token 和第 j 个token 与实体对相关。
  • 第一个字母代表 subject 为 multi-token entity（M）或者 single-token entity（S）。
  • 第二个字母代表 object 为 multi-token entity（M）或者 single-token entity（S）。
  • 第三个字母代表两个 token 都是 subject 和 object 的 head token（H）或者 tail token（T）。

这样的填表策略的主要优点在于：

• 每个标签不仅可以揭示一个 token 在一个 subject 或一个 object 中的位置信息。
• 还可以揭示一个subject（或一个 object）是单个 token 实体还是多个 token 实体。

模型结构

模型包括以下几个部分：

• Encoder
• Table Feature Generation（TFG）module
• Global Feature Mining（GFM）module
• Triple Generation（TG）module

TFG 和 GFM 以迭代的方式多次执行，以便逐步细化 table feature。最后，TG 根据每个表对应的细化 table feature 填充每个表，并根据这些填充的表生成所有三元组。

TDEER: An Efficient Translating Decoding Schema for Joint Extraction of Entities and Relations

来源：EMNLP 2021

作者：Xianming Li, Xiaotian Luo, Chenghao Dong, Daihuan Yang etc.

机构：Ant Group, Shanghai

贡献：提出了实体关系联合抽取模型 TDEER（Translating Decoding Schema for Joint Extraction of Entities and Relations）。

• 提出的翻译解码模式，将关系视作 subject 到 object 的翻译操作。TDEER 将关系三元组解码为 subject + relation -> objects。
• TDEER 可以很自然地处理重叠的三重问题。TDEER 遍历所有的 subject 和 relation 来识别出 object，因此可以考虑到所有的三元组，包括重叠或者不重叠的三元组。
• 为了增强模型的鲁棒性，引入了负样本来缓解不同阶段的误差积累。

GitHub：https://github.com/4AI/TDEER

模型结构

TDEER 是一个三阶段模型：

• 第一阶段，TDEER 使用一个基于 span 的实体标记模型来提取所有的 subject 和 object。
• 第二阶段，TDEER 采用多标签分类策略来检测所有的相关关系。
• 第三阶段，TDEER 迭代成对的 subject 和 relation，通过所提出的翻译解码模式来识别各自的 object。

Learning to Compose Neural Networks for Question Answering

来源： NAACL 2016

作者：Jacob Andreas, Marcus Rohrbach, Trevor Darrell, Dan Klein

机构：Department of Electrical Engineering and Computer Sciences, University of California

贡献：提出了一个适用于图像和结构化知识库的QA模型，这个模型使用自然语言字符串从一组可组合的模块中自动组装神经网络（基于注意力的组合的神经网络模块）。

GitHub：http://github.com/jacobandreas/nmn2

论文提出的模型包含两个部分：

• 第一，是可以自由组合的 neural modules 集合。
• 第二，是一个 network layout predictor，将 modules 组装成为每一个问题定制的深度神经网络。

在问答系统中，一种常见的做法是将问答映射为逻辑表达。而作者基于这种思想，先构建了一系列的神经网络模块，然后训练一个神经网络结构预测器，将每个问题，转化为一系列神经网络模块的组合，并和 world representation（图片，知识库之类的）结合产生答案。

模型

目标是从问题和 world representations 映射到答案。此过程涉及以下变量：

模型实际上是围绕着两个分布构建的：

• layout model：为一句话选择网络布局结构。

• execution model：将构建好的神经网络结构应用到 world representation，得到答案。

Evaluating modules

给定一个布局 z, 我们就可以组合相应的模块形成完整的神经网络，然后应用到 world representation 得到最后的答案。

Assembling networks

索引

Neo4j CQL 支持节点或关系属性上的索引，以提高应用程序的性能。索引操作：

• CREATE INDEX 创建索引。

1

CREATE INDEX ON :<label_name> (<property_name>)

• DROP INDEX 删除索引。

1

DROP INDEX ON :<label_name> (<property_name>)

UNIQUE 约束

使用 CREATE 命令始终会创建新的节点或者关系，即使是相同的值也会创建一个新行。有些应用场景中需要避免这种重复，所以可以在节点或者关系上应用 QNIQUE 约束。

UNIQUE 约束操作：

• CREATE CONSTRAINT 创建唯一约束索引。

1
2
3
4
5
6

CREATE CONSTRAINT ON (<label_name>)
ASSERT <property_name> IS UNIQUE

// e.g.
CREATE CONSTRAINT ON (cc:CreditCard)
ASSERT cc.number IS UNIQUE

• DROP CONSTRAINT 删除索引。

1
2

DROP CONSTRAINT ON (<label_name>)
ASSERT <property_name> IS UNIQUE

在 Cypher 中，主要分为三种类型的函数：

• 字符串函数：用于处理字符串。
• 聚合函数：用于聚合数据。
• 关系函数：关于关系的函数。

字符串函数

CQL 的常用字符串函数如下：

如：

1
2

MATCH (e:Employee) 
RETURN e.id,LOWER(e.name),e.sal,e.deptno

聚合函数

CQL 提供了一些在 RETURN 子句中使用的聚合函数，用于聚合数据：

如：

1
2

MATCH (e:Employee) 
RETURN MAX(e.sal),MIN(e.sal)

关系函数

在 CQL 中同样提供了一组关系函数，用于了解关系的细节（如获取开始节点、结束节点等）。

如：

1
2

MATCH (a)-[movie:ACTION_MOVIES]->(b) 
RETURN ID(movie),TYPE(movie)

CQL 简介

CQL（Cypher Query Language），作为 Neo4j 的查询语言。

CQL 常用关键字

CQL 的常用关键字如下：

MATCH 相当于 SQL 中的 FROM 关键字；

RETURN 相当于 SQL 中的 SELECT 关键字。

CQL 数据类型

Neo4j CQL 支持以下数据类型，这些数据类型与 Java 类似，用于定义节点或者关系的属性：

Neo4j 介绍

Neo4j 是一个世界领先的开源的基于图数据库（noSQL），它是使用Java语言完全开发的。

数据模型

Neo4j 图数据库遵循属性图模型来存储和管理其数据。属性图模型就是：

在属性图模型中，每一个顶点包括：

• 唯一标识符
• 出边的集合、入边的集合
• 属性的集合（键值对）

每一个边（关系）包括：

• 唯一标识符
• 边开始的顶点、边结束的顶点
• 表述两个顶点之间关系类型的标签
• 属性的集合（键值对）

在 Neo4j 中，关系应该是有方向性的。如果我们尝试创建没有方向的关系，那么 Neo4j 会抛出一个错误消息。