0%

矩阵分解 (一)SVD及其的几种变体

背景

在矩阵分解算法出现之前,基于协同过滤实现的推荐算法,一般是依靠近邻模型,即存在一个「user-item」的评分矩阵,类似于:

这个矩阵的每一行都表示一个用户(和物品关系)的向量,每一列都表示一个物品(和用户关系)的向量,在推荐时只需要根据向量相似度推荐相似度最高的n个物品(用户)即可,但是这种模型也存在一些问题:

  • 向量的维度一般较大,计算复杂度特别高。例如 用户向量的维度是物品总数,物品向量的维度则是用户总数,但是物品之间存在相关性,信息量并不随着向量维度增加而线性增加
  • 没有关系的维度上,一般使用0作为缺省值,数据量达到一定大小时,多数情况下一个系统里任意两个user-item对是没有关系的,即一个向量中多数值都是0,对相似度计算的结果影响较大

上述问题都可以在矩阵分解中解决,那矩阵分解具体是怎么做的呢?

实现原理

直观地说,矩阵分解就是在原本的大矩阵中分解出两个小矩阵,在推荐时,不用原先的大矩阵,而使用分解出的两个小矩阵计算

具体做法是,假设原本的user-item矩阵是m维n维的矩阵,即有m个用户,n个物品。选取一个k,这个k比m,n都小很多,可能是若干个数量级。通过一套算法 得到两个矩阵U和V,矩阵U的维度是m k ,矩阵V的维度是n * k。这两个矩阵需要能够通过矩阵乘法复原本来的矩阵,即:

\[ U_{m\times{k}}V_{n\times{k}}^{T} \approx A_{m\times{n}}\]

类似这样的计算方法就是矩阵分解,或者说叫做SVD(奇异值分解),但是SVD不能和矩阵分解(MF,下同)画等号,除了SVD还有很多矩阵分解的方法

Read more »

MQTT---QOS详解

什么是QOS

在MQTT(Message Queuing Telemetry Transport)协议中,QoS(Quality of Service,服务质量)指的是在消息传递过程中对消息的可靠性和传输保证的级别。具体来说,MQTT协议定义了三个不同的QoS级别:0、1和2。

  1. QoS 0(At most once,至多一次):消息尽力地被传递给接收者,但无法保证可靠性。消息可能会丢失或重复传递,通过这种级别交付的消息不能保证到达接收者。
  2. QoS 1(At least once,至少一次):确保每条消息至少被传递一次,但可能会被重复传递。发送者在发送消息后会等待接收者的确认。如果确认超时或丢失,发送者会重新发送消息。
  3. QoS 2(Exactly once,恰好一次):提供最高级别的可靠性。确保每条消息会被精确地传递一次,没有重复或丢失。这个级别通过发送者和接收者进行握手来实现,并使用消息ID和确认ID来跟踪和确认消息传递。

选择适当的QoS级别取决于应用程序的需求。如果应用程序能够容忍一些消息丢失或重复传递,可以选择QoS 0。如果可靠性很重要,但可以容忍一些重复传递,可以选择QoS 1。如果要求确保精确一次的传递,可以选择QoS 2。

在一个完整的从发布者到订阅者的消息投递流程中,QoS 等级是由发布者在 PUBLISH 报文中指定的,大部分情况下 Broker 向订阅者转发消息时都会维持原始的 QoS 不变。不过也有一些例外的情况,根据订阅者的订阅要求,消息的 QoS 等级可能会在转发的时候发生降级。

例如,订阅者在订阅时要求 Broker 可以向其转发的消息的最大 QoS 等级为 QoS 1,那么后续所有 QoS 2 消息都会降级至 QoS 1 转发给此订阅者,而所有 QoS 0 和 QoS 1 消息则会保持原始的 QoS 等级转发。

QOS 0 - 最多交付一次

QOS 0是最低的QOS等级。在这个等级下,消息即发即弃,消息的可靠性完全依赖于底层的TCP协议

为什么会出现消息丢失:
Read more »

分布式链路追踪相关概念以及技术选型

0x00.Distributed Tracing(分布式链路追踪)介绍

a.什么是分布式链路追踪

分布式链路追踪是一种在请求通过分布式云环境传播时观察请求的方法。分布式跟踪通过使用唯一标识符标记交互来跟踪交互。该标识符在事务与微服务、容器和基础设施交互时与事务保持一致。唯一标识符提供了对用户体验的实时可见性,从堆栈的顶部到应用程序层和下面的基础设施

对于可观测性 有三大指标:Logging、Metrics 和 Tracing

  • Logging:用于记录离散的事件,包含程序执行到某一点或某一阶段的详细信息。
  • Metrics:可聚合的数据,且通常是固定类型的时序数据,包括 Counter、Gauge、Histogram 等。
  • Tracing:记录单个请求的处理流程,其中包括服务调用和处理时长等信息。

上述几种指标 都有典型的应用

  • Logging:ELK
  • Metrics:Prometheus
  • Tracing:Jaeger、Zipkin

b.分布式链路追踪标准

业界较为通用的链路追踪标准有三种

  • OpenTracing:OpenTracing是一种应用程序级追踪规范,提供了一套API和数据模型,使得开发人员可以在系统中添加分布式追踪功能。它可以让开发人员在不同的服务之间添加追踪信息,以便了解消息流的情况,从而更好地分析性能瓶颈和研究其他问题。
  • OpenCensus:OpenCensus是一个开源、跨平台、跨语言的分布式跟踪和度量库。它由Google和Census.io共同开发。OpenCensus可以收集和传输跟踪、度量和日志数据,并提供了方便的API和工具来展示和分析这些数据。OpenCensus的目标是使跨平台和跨语言的监控变得更加简单。
  • OpenTelemetry:OpenTelemetry是一个可移植的、语言无关的分布式追踪工具包,可以用于监测分布式系统。它是OpenTracing和OpenCensus的继任者,并提供了一种集成方法,以便开发人员和运营人员可以轻松地捕获、分析和存储跨越多个系统的深度数据。OpenTelemetry还支持多种编程语言和后端。

OpenCensus和OpenTelemetry基于更先进的技术和更全面的功能,对于分布式追踪和性能监测更加有优势。建议在选择时,根据实际应用场景和需求,综合考虑现有的技术栈和人员素质等方面,选择最适合的开源分布式链路追踪系统。

Read more »

Golang GMP调度器

一、进程与线程

1.进程是操作系统进行资源分配和调度的一个独立单位,不同的进程通过进程间通信来通信。由于进程比较重量,占据独立的内存,所以上下文进程间的切换开销(栈、寄存器、虚拟内存、文件句柄等)比较大,但相对比较稳定安全。

2.线程是进程的一个实体,是CPU调度和分派的基本单位,它是比进程更小的能独立运行的基本单位.线程自己基本上不拥有系统资源,只拥有一点在运行中必不可少的资源(如程序计数器,一组寄存器和栈),但是它可与同属一个进程的其他的线程共享进程所拥有的全部资源。线程间通信主要通过共享内存,上下文切换很快,资源开销较少,但相比进程不够稳定容易丢失数据

虽然线程比较轻量,但是在调度时也有比较大的额外开销。每个线程会都占用 1 兆以上的内存空间,在对线程进行切换时不止会消耗较多的内存,恢复寄存器中的内容还需要向操作系统申请或者销毁对应的资源,每一次线程上下文的切换都需要消耗 ~1us 左右的时间1,但是 Go 调度器对 Goroutine 的上下文切换约为 ~0.2us,减少了 80% 的额外开销2

Go 语言的调度器通过使用与 CPU 数量相等的线程减少线程频繁切换的内存开销,同时在每一个线程上执行额外开销更低的 Goroutine 来降低操作系统和硬件的负载。

二、Golang调度器

1.Go 语言的协程 goroutine

Go 为了提供更容易使用的并发方法,使用了 goroutine 和 channel。goroutine 来自协程的概念,让一组可复用的函数运行在一组线程之上,即使有协程阻塞,该线程的其他协程也可以被 runtime 调度,转移到其他可运行的线程上。最关键的是,程序员看不到这些底层的细节,这就降低了编程的难度,提供了更容易的并发。

Go 中,协程被称为 goroutine,它非常轻量,一个 goroutine 只占几 KB,并且这几 KB 就足够 goroutine 运行完,这就能在有限的内存空间内支持大量 goroutine,支持了更多的并发。虽然一个 goroutine 的栈只占几 KB,但实际是可伸缩的,如果需要更多内容,runtime 会自动为 goroutine 分配。

Goroutine 特点:

占用内存更小(几 kb) 调度更灵活 (runtime 调度)

2.调度器历史

今天的 Go 语言调度器有着优异的性能,但是如果我们回头看 Go 语言的 0.x 版本的调度器就会发现最初的调度器不仅实现非常简陋,也无法支撑高并发的服务。调度器经过几个大版本的迭代才有今天的优异性能,几个不同版本的调度器引入了不同的改进,也存在不同的缺陷:

  • 单线程调度器 ·0.x
    • 只包含 40 多行代码;
    • 程序中只能存在一个活跃线程,由 G-M 模型组成;
  • 多线程调度器 ·1.0
    • 允许运行多线程的程序;
    • 全局锁导致竞争严重;
  • 任务窃取调度器 ·1.1
    • 引入了处理器 P,构成了目前的 G-M-P 模型;
    • 在处理器 P 的基础上实现了基于工作窃取的调度器;
    • 在某些情况下,Goroutine 不会让出线程,进而造成饥饿问题;
    • 时间过长的垃圾回收(Stop-the-world,STW)会导致程序长时间无法工作;
  • 抢占式调度器 ·1.2~ 至今
    • 基于协作的抢占式调度器 - 1.2 ~ 1.13
      • 通过编译器在函数调用时插入抢占检查指令,在函数调用时检查当前 Goroutine 是否发起了抢占请求,实现基于协作的抢占式调度;
      • Goroutine 可能会因为垃圾回收和循环长时间占用资源导致程序暂停;
    • 基于信号的抢占式调度器 - 1.14 ~ 至今
      • 实现基于信号的真抢占式调度
      • 垃圾回收在扫描栈时会触发抢占调度;
      • 抢占的时间点不够多,还不能覆盖全部的边缘情况;

其中1.1版本之前的调度器未使用GMP模型,2012年之后golang开始引入GMP模型并实现了几个版本的调度器

先来分析被废弃的老版本调度器的设计原理与实现:

老版本的调度器只存在两个角色,即G&M

老版本的调度器包括0.x的单线程调度器(几乎不可用)和1.0的多线程调度器,总体的实现思路如下(0.x版本只有M0)

Read more »

一、安装部署

1.官网下载安装包

https://skywalking.apache.org/downloads/

image-20230601161536483
image-20230601161536483

2.下载tar包,解压

1
tar -zxvf apache-skywalking-apm-9.4.0.tar.gz

解压后文件目录为

image-20230601162235270
image-20230601162235270

Notice:!!! skywalking运行依赖java的JDK11及以上版本 如果本机的java版本在11以下 先升级java版本到11以上

通过以下命令确定java版本

1
java -version

3.对服务进行配置(可以不配 先run起来)

进入config目录 找到application.yml

1
vim application.yml

打开配置文件,找到如下段落

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
...
storage:
selector: ${SW_STORAGE:h2}
elasticsearch:
namespace: ${SW_NAMESPACE:""}
clusterNodes: ${SW_STORAGE_ES_CLUSTER_NODES:localhost:9200}
protocol: ${SW_STORAGE_ES_HTTP_PROTOCOL:"http"}
connectTimeout: ${SW_STORAGE_ES_CONNECT_TIMEOUT:3000}
socketTimeout: ${SW_STORAGE_ES_SOCKET_TIMEOUT:30000}
responseTimeout: ${SW_STORAGE_ES_RESPONSE_TIMEOUT:15000}
numHttpClientThread: ${SW_STORAGE_ES_NUM_HTTP_CLIENT_THREAD:0}
user: ${SW_ES_USER:""}
password: ${SW_ES_PASSWORD:""}
trustStorePath: ${SW_STORAGE_ES_SSL_JKS_PATH:""}
trustStorePass: ${SW_STORAGE_ES_SSL_JKS_PASS:""}
secretsManagementFile: ${SW_ES_SECRETS_MANAGEMENT_FILE:""} # Secrets management file in the properties format includes the username, password, which are managed by 3rd party tool.
......
Read more »

ubuntu部署单节点Kubernetes1.27

系统:Ubuntu22.04

1.准备工作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
curl -fsSL https://get.docker.com | sudo sh
# 使用 aliyun 的 k8s 源安装 kubeadm 和相关命令行工具
apt-get update && apt-get install -y apt-transport-https
curl https://mirrors.aliyun.com/kubernetes/apt/doc/apt-key.gpg | apt-key add -
echo "deb https://mirrors.aliyun.com/kubernetes/apt/ kubernetes-xenial main" > /etc/apt/sources.list.d/kubernetes.list
apt-get update
apt-get install -y kubelet kubeadm kubectl
systemctl enable kubelet
# 修改 docker 的 cgroup driver 选项为 systemd,与 k8s 保持一致,并修改 registry-mirror 加速下载
vi /etc/docker/daemon.json
{
"exec-opts": ["native.cgroupdriver=systemd"],
"registry-mirrors": ["https://registry.docker-cn.com", "https://docker.mirrors.ustc.edu.cn"]
}
systemctl restart docker

2.使用 kubeadm init k8s

1
2
3
# 使用阿里云上提供的 k8s 镜像(这里指定的网络与后续使用的网络插件的配置保持一致)
kubeadm init --image-repository registry.aliyuncs.com/google_containers \
--service-cidr=10.1.0.0/16 --pod-network-cidr=10.244.0.0/16

2.1 问题修复(如果上一步执行正常无报错 则跳过)

1
container runtime is not running :CRI v1 runtime API is not implemented for endpoint \"unix:///var/run/containerd/containerd.sock\": rpc error: code = Unimplemented desc = unknown service runtime.v1.RuntimeService

报错的原因是ubuntu22.04默认预装的是旧版本的containerd.io 需要下载二进制包手动替换:

以下是简单步骤(可以照做)具体详细的文档参见https://github.com/containerd/containerd/blob/main/docs/getting-started.md

1
2
3
4
5
6
7
8
9
10
#下载containerd二进制包
wget https://github.com/containerd/containerd/releases/download/v1.7.2/containerd-1.7.2-linux-amd64.tar.gz
#将其解压缩到/usr/local下:
tar Cxzvf /usr/local containerd-1.7.2-linux-amd64.tar.gz
#接下来从runc的github上单独下载安装runc,该二进制文件是静态构建的,并且应该适用于任何Linux发行版。
wget https://github.com/opencontainers/runc/releases/download/v1.1.7/runc.amd64
install -m 755 runc.amd64 /usr/local/sbin/runc
#生成containerd的配置文件
mkdir -p /etc/containerd
containerd config default > /etc/containerd/config.toml

根据官方文档指导 需要将systemd 设置为 cgroup 驱动对于使用systemd作为init system的Linux的发行版,使用systemd作为容器的cgroup driver可以确保服务器节点在资源紧张的情况更加稳定 详见https://kubernetes.io/zh-cn/docs/setup/production-environment/container-runtimes/

Read more »

上下文Context

上下文 Go 语言中用来设置截止日期、同步信号,传递请求相关值的结构体。上下文与 Goroutine 有比较密切的关系。

context.Context接口

需要实现四个方法

1
2
3
4
5
6
type Context interface {
Deadline() (deadline time.Time, ok bool)
Done() <-chan struct{}
Err() error
Value(key interface{}) interface{}
}
Deadline
  • 返回 context.Context 被取消的时间,也就是完成工作的截止日期,如果未设置截止日期,则返回ok==false;
Done
  • 返回一个 Channel,这个 Channel 会在当前工作完成或者上下文被取消后关闭,如果context永远无法取消(?)则可能返回nil,多次调用 Done 方法会返回同一个 Channel;channel的关闭可能会异步发生
Err
  • 返回 context.Context 结束的原因,它只会在 Done 方法对应的 Channel 关闭时返回非空的值;

  • 如果 context.Context 被取消,会返回 Canceled 错误;

  • 如果 context.Context 超时,会返回 DeadlineExceeded 错误;

Value
  • 从 context.Context 中获取键对应的值,对于同一个上下文来说,多次调用 Value 并传入相同的 Key 会返回相同的结果,该方法可以用来传递请求特定的数据;
    Read more »

Golang编程模式(一) Functional Options

应用场景举例:

在编程中,我们经常需要对一个对象(或是业务实体)进行相关的配置。比如下面这个业务实体

1
2
3
4
5
6
7
8
type Server struct {
Addr string
Port int
Protocol string
Timeout time.Duration
MaxConns int
TLS *tls.Config
}

在这个 Server 对象中,我们可以看到:

要有侦听的 IP 地址 Addr 和端口号 Port ,这两个配置选项是必填的

还有协议 Protocol 、 Timeout 和MaxConns 字段,这几个字段是不能为空的,但是有默认值的,比如,协议是 TCP,超时30秒 和 最大链接数1024个

还有一个 TLS ,这个是安全链接,需要配置相关的证书和私钥。这个是可以为空的。

针对这样的配置,需要多种不同的函数签名创建不同配置的Server,例如:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func NewDefaultServer(addr string, port int) (*Server, error) {
return &Server{addr, port, "tcp", 30 * time.Second, 100, nil}, nil
}

func NewTLSServer(addr string, port int, tls *tls.Config) (*Server, error) {
return &Server{addr, port, "tcp", 30 * time.Second, 100, tls}, nil
}

func NewServerWithTimeout(addr string, port int, timeout time.Duration) (*Server, error) {
return &Server{addr, port, "tcp", timeout, 100, nil}, nil
}

func NewTLSServerWithMaxConnAndTimeout(addr string, port int, maxconns int, timeout time.Duration, tls *tls.Config) (*Server, error) {
return &Server{addr, port, "tcp", 30 * time.Second, maxconns, tls}, nil
}

就很蠢🤔

有三种解决办法

第一种比较简单但不推荐:引入一个Config{},将非必填的字段放到Config里,传入时按需赋值字段(也可以传入空struct,所以Server函数中要有相应的判空操作)

Read more »

分布式系统中常见一致性算法

分布式一致性理论

1.为什么要使用分布式

​ 随着大型网站的各种高并发访问、海量数据处理等场景越来越多,如何实现网站的高可用、易伸缩、可扩展、安全等目标就显得越来越重要。为了解决这样一系列问题,大型网站的架构也在不断发展。单体架构或者说集中式系统在处理大量并发或数据的业务场景中越来越显得捉襟见肘,此时分布式架构应运而生。

​ 谈到分布式系统,就不得不提到另一种集中式系统,集中式系统有一个大型的中央处理系统,中央处理系统时一台高性能、可扩充的计算机,所有的数据、运算、处理任务全部在中央计算机系统上完成。中央计算机连接多个终端,终端用来输入和输出,不具有数据处理能力。远程终端通过网络连接到中央计算机,它们得到的信息是一致的。我们日常生活中常用的ATM机等都是用的集中式系统

​ 这种系统架构的优点主要是1.数据容易备份,只需要把中央计算机上的数据进行备份即可 2.在开发业务相对简单的系统时,总费用较低,只需要中央计算机的功能强大,终端只需要简单便宜的设备。缺点也很明显,在面对体量较大的业务时,性能扩展的成本太高,因为系统的总算力往往只取决于中央计算机的性能,另外集中式系统采用的单体架构,各业务模块之间的耦合度较高,导致架构的可拓展性较低

​ 而在一个分布式系统中,一组独立的计算机展现给用户的是一个统一的整体,就好像是一个系统似的。系统拥有多种通用的物理和逻辑资源,可以动态的分配任务,分散的物理和逻辑资源通过计算机网络实现信息交换。系统中存在一个以全局的方式管理计算机资源的分布式操作系统。通常,对用户来说,分布式系统只有一个模型或范型。在操作系统之上有一层软件中间件(middleware)负责实现这个模型 (百度百科“分布式系统”)

​ 简言之,分布式系统中的数据存储、任务的处理分布在网络中的不同机器上,每台主机都是一个独立的系统,联网的目的是为了获取更多的资源、丰富的服务。

分布式系统具有如下的特点:

  • 高度的可靠性

数据分散存储在网络中的不同主机上,系统中存在数据冗余,当一台机器发生故障时,可以使用另一台主机的备份。

  • 均衡负载

每台主机可以缓存本地最常用的数据,不需要频繁地访问服务器,减轻了服务器的负担,减少了网络的流量。

服务器也可以对任务进行分配和优化,克服几种系统中央计算机资源紧张的瓶颈。

  • 满足不同的需要

用户可以根据自己的需要在自己的主机上安装不同的操作系统、应用软件,使用不同的服务,

不再像集中式计算机系统那样受限于中央计算机的功能。

但是,分布式系统因为网络的不确定性,节点故障等情况,会带来各种复杂的问题

2.分布式系统的问题

1.通信异常:从集中式向分布式演变过程中,必然会引入网络因素,而由于网络本身的不可靠性,因此也引入了额外的问题。分布式系统需要在各个节点之间进行网络通信,因此当网络通信设备故障就会导致无法顺利完成一次网络通信,就算各节点的网络通信正常,但是消息丢失和消息延时也是非常普遍的事情。

2.网络分区(脑裂):网络发生异常情况导致分布式系统中部分节点之间的网络延时不断增大,最终导致组成分布式系统的所有节点,只有部分节点能够正常通行,而另一些节点则不能。我们称这种情况叫做网络分区(脑裂),当网络分区出现时,分布式系统会出现多个局部小集群(多个小集群可能又会产生多个master节点),所以分布式系统要求这些小集群要能独立完成原本需要整个分布式系统才能完成的功能,这就对分布式一致性提出了非常大的挑战。

3.节点故障:节点宕机是分布式环境中的常态,每个节点都有可能会出现宕机或僵死的情况,并且每天都在发生。

4.三态:由于网络不可靠的原因,因此分布式系统的每一次请求,都存在特有的“三态”概念,即:成功,失败与超时。在集中式单机部署中,由于没有网络因素,所以程序的每一次调用都能得到“成功”或者“失败”的响应,但是在分布式系统中,网络不可靠,可能就会出现超时的情况。可能在消息发送时丢失或者在响应过程中丢失,当出现超时情况时,网络通信的发起方是无法确定当前请求是否被成功处理的,所以这也是分布式事务的难点。

上面介绍的这几种情况,都有可能导致分布式系统产生数据一致性的问题。我们在分布式系统中,经常或存在数据复制的需求,主要有以下两种原因

​ 高可用:将数据复制到分布式部署的多台机器中,可以消除单点故障,防止系统由于某台(些)机器宕机导致的不可用。

​ 性能:通过负载均衡技术,能够让分布在不同地方的数据副本全都对外提供服务。有效提高系统性能。

在分布式系统引入复制机制后,不同的数据节点之间由于网络延时等原因很容易产生数据不一致的情况。复制机制的目的是为了保证数据的一致性。但是数据复制面临的主要难题也是如何保证多个副本之间的数据一致性。

对分布式数据一致性简单的解释就是:当对集群中一个副本数据进行更新的同时,必须确保能够同步更新到其他副本,否则不同副本之间的数据将不再一致。举个例子来说就是:当客户端C1将系统中的一个值K由V1更新为V2,但是客户端C2读的是另一个还没有同步更新的副本,K的值依然是V1,这就导致了数据的不一致性。其中,常见的就是主从数据库之间的复制延时问题。

Read more »