ACKRec

标题：Attentional Graph Convolutional Networks for Knowledge Concept Recommendation in MOOCs in a Heterogeneous View
作者：Jibing Gong, Shen Wang, Jie Tang, etc.
发表：SIGIR 2020

MOOCs场景下直接推荐课程忽视了知识概念的推荐。论文提出了一个基于图神经网络的端到端的方法，注意力的异质图卷积深度知识推荐（ACKRec）来进行MOOCs中知识概念的推荐。使用内容信息和上下文信息，通过图卷积网络学习实体的表征。除了学生和知识概念，还考虑课程、视频、老师等其他类型的实体来构建异质信息网络来捕获丰富的语义信息并将其结合到表征学习的过程。同时还使用元路径来指导用户偏好的传播，利用注意力机制结合不同元路径的上下文信息。使用扩展的矩阵分解（MF）方法付来学习模型参数。

推荐系统中常用的评价指标

MCRec

标题：Leveraging Meta-path based Context for Top-N Recommendation with A Neural Co-Attention Model
作者：Binbin Hu, Chuan Shi, etc.
发表：KDD 2018

异质信息网络（HIN）被广泛应用于推荐系统，但是由两个主要的不足：模型很少学习到推荐任务中路径或者元路径的显式表征；模型没有考虑交互中元路径与涉及到的用户-物品对间的相互影响。为此，论文提出了一个带有 co-attention 机制的深度神经网络来利用丰富的基于元路径的上下文来进行 top-N 推荐。

标题：基于知识图谱的推荐系统研究综述 作者：秦川, 祝恒书等 发表：中国科学：信息科学

推荐系统是一种有效解决信息泛滥的方法。其核心目标是通过分析用户行为、兴趣、需求等信息, 在海量的数据中挖掘用户感兴趣的信息, 如商品、新闻、POI (point of interest) 和试题等。主要可以分为基于内容的推荐算法、基于协同过滤的推荐算法和混合推荐算法。知识图谱作为混合推荐系统中国一类有效的辅助信息，蕴含了推荐系统中对于物品的大量背景信息，以及物品之间的关系，补充了用户与物品交互数据，可以更进一步提升推荐效果。另外，基于知识图谱的推荐方法为构建可解释推荐系统提供了一些新的思路。

推荐系统

推荐系统的形式化定义如下：给定用户集合 \(U\)，物品集合 \(V\)，并用 \(R_{i,j}\) 表示用户 \(U_i\) 对 \(V_j\) 的喜好程度，\(R \in \mathbb{R}^{|U| \times|V|}\)。随后定义一个效用函数 \(f: U \times V \rightarrow R\)，则推荐系统所研究的问题是给定任意一个用户 \(U_i\)，希望找到其喜好程度最大的物品 \(V_k\)，即 \[\forall U_{i} \in U, \quad V_{k}=\underset{V_{j} \in V}{\arg \max } f\left(U_{i}, V_{j}\right)\] 在真实的推荐场景中 \(|U|\) 和 \(|V|\) 的量级往往是非常大的，如淘宝网的日活跃用户上千万, 每天在线商品上亿, 但是我们可以观测的 \(R\) 却极其稀疏, 因此给研究推荐系统带来了极大的挑战。

推荐系统中的推荐算法可分为基于内容的推荐算法、基于协同过滤的推荐算法和混合推荐算法3类。

在 Project2 中，我们已经基于Raft构建了一个高可用的键值服务器，但是我们假设的是每个store中都只有一个Region，也就是服务器中总共只有一个raft group，这样的话每个写操作都需要访问同一个Leader，等待命令被提交并串行执行，这样虽然保证了各个节点的数据一致性，但却严重影响了执行效率，无法提供高性能的服务。

在 Project3 中，我们要实现一个带有平衡调度器的多 Region 键值服务器，每个 Region 代表键在某一个范围内的数据。新的结构如下图所示，具体的操作请求会被判断位于哪一个Region，从而访问对应Raft group中的Leader。这样使得对不同Region的操作可以并发执行，提高了执行效率。

该Project包含了三个部分，分别是：

• 在 Raft 算法中实现成员变更和领导人变更
• 实现raftstore中的配置更改和region分裂
• 引进调度器

Part A

在这一部分需要实现成员变更和领导人变更的基础raft算法。成员变更，也就是配置更改，可以为raft集群增加或者移除节点；领导人变更用于将Leader转移给其他节点，在调度中很有用。

领导人变更

要实现领导人变更，引入了 MsgTransferLeader 和 MsgTimeoutNow 两类消息类型，在进行领导人转化时，需要在当前领导人上调用 raft.Raft.Step 处理 MsgTransferLeader 消息，而消息中的 from 就是需要转移的目标节点。为了保证能够成功转移领导人并保证数据的一致性不被破坏，当前领导人需要检查目标节点是否有最新的日志，是否符合成为领导人的条件。如果不符合条件，当前领导人会停止接收新的 proposal 请求，并向目标节点发送 MsgAppend，使其日志达到同步的最新状态。符合要求后，当前领导人会向目标节点发送 MsgTimeoutNow 消息，目标节点在收到该消息后会使用更高的 Term 立刻开启一个新的选举，这样将有很大机会成为新的领导人节点。

对 MsgTransferLeader 消息的处理函数如下，需要判断目标节点状态，日志信息等。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

func (r *Raft) handleTransferLeader(m pb.Message) {
	// already leader
	if m.From == r.id {
		return
	}
	// under transfering
	if r.leadTransferee != None && r.leadTransferee == m.From {
		return
	}
	// The transferee dosen't exist
	if _, ok := r.Prs[m.From]; !ok {
		return
	}
	r.leadTransferee = m.From
	r.transferElapsed = 0
	// check transferee's log
	if r.Prs[m.From].Match == r.RaftLog.LastIndex() {
		r.sendTimeoutNow(m.From)
	} else {
		r.sendAppend(m.From)
	}
}

成员配置变更

在该系统中没有像 Raft 论文中那样实现一次性添加或移除任意多个节点，而是每次增加或删除一个节点，这样实现起来更加简单。成员变更开始于调用Leader的 raft.RawNode.ProposeConfChange，它会 propose 一个类型为 EntryConfChange 的实体，将 pb.ConfChange 写入实体的 data，当该实体被提交后，通过 RawNode.ApplyConfChange 将该配置应用，然后可以通过 raft.Raft.addNode 和 raft.Raft.removeNode 执行对应的增加或删除节点的操作。

增加或删除节点的代码如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

// addNode add a new node to raft group
func (r *Raft) addNode(id uint64) {
	// Your Code Here (3A).
	if _, ok := r.Prs[id]; ok {
		r.Prs[id] = &Progress{Next:  1}
	}
	r.PendingConfIndex = None
}

// removeNode remove a node from raft group
func (r *Raft) removeNode(id uint64) {
	// Your Code Here (3A).
	if _, ok := r.Prs[id]; ok {
		delete(r.Prs, id)
		if r.State == StateLeader {
			r.detectCommit()
		}
	}
	r.PendingConfIndex = None
}

要实现一个分布式的KV数据库，那么保证各数据库中数据的一致性就非常重要了。Project2主要就是使用一致性算法Raft实现一个高可用的KV server，主要分为三个部分：

• 实现基础的Raft算法
• 在Raft的基础上构建一个容错的KV server
• 支持raftlog的垃圾回收和快照

Part A

Part A实现基础的raft算法，需要补充的代码位于raft/，这一部分同样可以拆分为三个部分：

• Leader选举
• 日志复制
• Raw node接口

在 Project1 中，需要构建一个单机键值存储的 gRPC 服务器，并且支持 column familly(CF)，CF 类似于一个命名空间，不同 CF 中的同名的键是不同的，可以简单的将不同的CF理解成不同的mini databases。

目标与层次结构

Project1主要是实现kv中的部分代码来完成单机KV数据库服务器Server。它的层次结构如下图所示：

6.17

• torch.tensor和np.array类似，可以互相转换
• tensor.shape()获取大小，view()修改大小
• broadcasting自动改变维度相加减
• 如果要求gradient可以自动建图
• pytorch提供to(device)来确定运行设备
• 自动求gradient使用backward()
• torch.nn.Module, 如nn.Linear(d_in, d_out)
• Activation function如nn.ReLU()

6.4 剑指Offer

• 数组中重复的数字（set、原地交换）
• 二维数组中的查找（旋转45度类似二叉树，比较排除一行或一列）
• 替换空格（遍历添加、原地扩展，反向遍历）
• 从尾到头打印链表（递归、辅助栈）
• 根据前序遍历和中序遍历重建二叉树（划分左右子树递归处理）
• 两个栈实现队列（一个栈负责入队，一个栈负责出队）
• 斐波那契数列（a, b）
• 青蛙跳台阶，一步或两步（动态规划）
• 旋转数组的最小数字（二分法，与首尾元素比较）
• 矩阵中的路径组成单词（深度优先搜索+标志+剪枝）
• 机器人运动范围，矩阵索引的位数和小于某个数（DFS/BFS）
• 剪绳子，整数长度，最大乘积是多少（切成长度为3的等分段）
• 二进制数中1的个数（循环移位与1、n&(n-1)）

2021/5/28

Overview

TiKV使用Key-Value模型保存数据，并且提供有序遍历方法。可以看做一个按照Key的二进制顺序有序的巨大Map。使用开源的RocksDB作为单机存储引擎

Raft协议

Raft协议的每个副本都会处于三种状态之一：Leader、Follower、Candidate

• Leader：所有请求的处理者，接受client的更新请求，本地处理后再同步给多个其他的副本
• Follower：请求的被动更新着，从Leader接受更新请求，让后写入本地日志文件
• Candidate：如果Follower在一定时间内没有收到Leader的心跳，则判断Leader可能已经故障，此时从新启动选主过程，此时副本会变成Candidate状态，直到选主结束