Rust String Type

string和&str

rust中操作字符串比较常用的是String和&str 比如:

1
2
3
4
5
6
let string = String::from("hello, world");

//以下三种都为&str类型
let s = "hello, world";        //字面常量 string literal, 存储在常量区
let hello = &string[..5];      //从string中得到&str
let world = &s[6..];          //从&str中得到&str

内存布局

以下是String与&str在内存中的结构,String占用了3个字长,&str占用两个字长。他们都有一个指向底层数组的指针。

实现源码

string的内部实现就是一个Vec[u8]

1
2
3
4
5
pub struct String {

 vec: Vec<u8>,

}

vec本身的实现如下

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
pub struct Vec<T, #[unstable(feature = "allocator_api", issue = "32838")] A: Allocator = Global> {

 buf: RawVec<T, A>,

 len: usize,

}

pub(crate) struct RawVec<T, A: Allocator = Global> {

 ptr: Unique<T>,

 cap: usize,

 alloc: A,

}

以上可以看出string的内存占用从何而来

str是一个原生类型,字面常量的完整类型是&‘static str, 虽然没有str的类型定义,但是从它的方法中也可以找到它的内部结构

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

let story = "Once upon a time...";

let ptr = story.as_ptr();
let len = story.len();

// story has nineteen bytes
assert_eq!(19, len);

// We can re-build a str out of ptr and len. This is all unsafe because
// we are responsible for making sure the two components are valid:
let s = unsafe {
    // First, we build a &[u8]...
    let slice = slice::from_raw_parts(ptr, len);

    // ... and then convert that slice into a string slice
    str::from_utf8(slice)
};

assert_eq!(s, Ok(story));

str的其他使用方式

理论上可以通过各种方式得到str类型本身,然而编译器并不能通过, 主要是因为str类型为unsize type, 并不能够在栈中存在。比如

1
2
3
4
5
6
7
8
9
let string = String::from("hello, world");


let s = "hello, world";  

//以下三个变量都为str类型
let ss = *s;
let h = string[..5];
let w = s[6..];

Box<str>

既然str不能在栈上存在,那么能不能显式放到堆上呢?答案是可以的,那就是Box<str>,但是Box<str>只能通过以下一种方式初始化

1
2
3
4
let string = String::from("hello, world");

//除了&str,你还可以使用Box<str>,下面是可以创建Box<str>的唯一方法
let box_s = string.into_boxed_str();

Box<str>同样是占用2个字长,事实上,当一个unsize type被放在引用或者指针后面的时候它就是一个2字长胖指针,比如&[u8], &dyn Trait都是如此, *const [T]也是一样

Cow<str>

很多时候,我们希望函数接口保持兼容性与灵活性,通常使用&str而不是String或者·&String作为接口,但是作为返回,如果这个函数并没有修改这个&str,那么我们希望可以直接返回它, 但是当这个函数改变了值,我们只能复制这个str并且返回String类型以获得owned值。这个时候Cow<str>就派上了用场。以下是定义

1
2
3
4
5
6
7
pub enum Cow<'a, B>
where
    B: 'a + ToOwned + ?Sized,
 {
    Borrowed(&'a B),
    Owned(<B as ToOwned>::Owned),
}
  1. 标准库中,对于Cow<str>的使用有from_utf8_lossy返回&str
  • 不需要分配新的内存
1
2
3
4
5
6
// some bytes, in a vector
let sparkle_heart = vec![240, 159, 146, 150];

let sparkle_heart = String::from_utf8_lossy(&sparkle_heart);

assert_eq!("💖", sparkle_heart);
  • 返回String, 由于修改了字符串内容, 重新复制了内存
1
2
3
4
5
6

// some invalid bytes
let input = b"Hello \xF0\x90\x80World";
let output = String::from_utf8_lossy(input);

assert_eq!("Hello �World", output);
  1. 在crate regex中有一个replace方法,同样使用Cow<str>作为返回值
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
 pub fn replace_all<'t, R: Replacer>(

 &self,

 text: &'t str,

 rep: R,

 ) -> Cow<'t, str> {

 self.replacen(text, 0, rep)

 }
  1. 我们可以直接使用Cow<str>, 打印或者写入文件
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
//new 一个正则表达式
let regex = Regex::new(target).unwrap();
//返回一个Cow<str>
let cow = regex.replace_all(text, replacement);
//打印字符串
println("str is {}", cow);

//输出到文件, 这个需要注意&*cow得到&str类型
// &(*cow.deref())
fs::write("output.txt", &*cow)

MapReduce

系统描述

根据Google论文mapreduce开发一个简易的mapreduce系统,可以处理多个数据文件,最后生成一个结果,课程案例主要是对文本进行WordCount,首先通过map统计每个word出现的次数,然后通过reduce计算count

设计

  • Coordinator 协调者负责分配任务,包括map任务,reduce任务。
  • Worker 执行map, reduce任务, 任务通过rpc请求Cooridnator获取
  • Coordinator要包含错误处理,错误包括任务失败与任务缓慢,处理措施都是重试

实现

  • Coordinator包含两个任务队列,一个mapTasks,由输入文件数决定; 一个reduceTasks,由reduce数量决定
  • 当worker请求任务时, Coordinator会分配一个Ready状态的任务,任务一旦分配就设置成Pending状态。
  • Worker完成任务后,通知Coorinator,此Task已完成, 等待1秒后继续请求下一个任务
  • 当所有reduceTask都完成后, 整个任务完成

错误处理

  • 当一个任务pending超过10秒后,如果状态不为Finish, 则重新设置成Ready
  • Worker执行任务失败后,直接结束当前循环,等待下一个任务请求
  • 任务执行成功后, Coordinator会对请求任务的worker返回Done标记, worker接收标记后退出;如果Coordinator已经退出, 则网络连接失败, Worker退出;其他情况Worker会一直循环请求任务
  • Map Worker将TempFile作为中间数据, 并将这些文件传输给Master,以供Reduce Worker使用。一个已经成功返回的MapTask将忽略其他的返回
  • Reduce Worker会使用TempFile作为中间输出,当前任务完成后,Rename这些文件到正确的文件目录,所以当Worker执行失败时这些文件并不可见

流程图

任务流

需求描述

  • 由于前端展示的多样性, 需要一个可以灵活配置的Api Gateway, 这个gateway不能仅仅满足http请求都后端微服务的转发, 还必须可以定义微服务返回结果之间的组合,组合的灵活性当然是不可能达到代码的程度,但是应该可以满足常见的数据拼接,比如结果集的简单Merge,比如数据集详情扩展, 比如B接口请求依赖A接口的返回值等。
  • 要能够请求多个接口,并且这些请求之间有一定的依赖关系, DAG是一个自然的选择, 如果把每个请求当成单个节点上的任务, 那么任务之间的依赖关系可以通过节点依赖关系表达出来, 同时没有依赖关系的任务还可以并行执行。
  • 一个DAG可以表示一个任务流,一个任务流应该有Request, Response, 一个任务流应该有开始节点与结束节点。一个DAG应该允许节点中存在SubDAG
  • 任务之前必须可以传递数据,我们定义A->B为B依赖A, 那么应该可以将A的执行结果传递给B。如果存在依赖关系{A->B, C->B},那么应该可以将A的结果合并C的结果。
  • 由于在Gateway中使用, 任务的主要实现应该为 Http请求, RPCX请求, GRPC请求等, 一个问题在于如何将客户端的Http请求转化为后端服务请求,通常的情况是, 一个Http请求的query string或者body加上一些用户信息传递到后端服务,但是由于接口是从已经开发完成的系统中迁移, 所以情况可能会较为复杂。Query String, Params, Header, Body, JWT,这个都可能是参数的来源
  • 认证与授权也可以当作节点来使用
  • 如果任意一个节点失败, 那么请求应该是失败的, 并且返回错误信息给前端

基本设计

  • Request 包含http所有可能的信息, 必须包含一个requestID,假如没有就生成一个
  • Response 主要包含body与header, 两个部分, header中必须包含requestID
  • 每一个接口(POST /api/username)对应一个DAG, 这个DAG可以使用JSON/YAML配置
  • DAG的执行应该是异步的, 每个Node可能在不同的协程中执行,DAG应该有一个Executor, 这个Executor应该负责Node的开始执行, 捕获Node执行完成信号, 并且通知所有满足依赖关系的Node继续执行,直到结束节点执行完毕。 这个Executor应该包含一个Context, 并且在所有Node中共享这个Context
  • Node应该在一个协程池当中执行, 一个Node完成后在Context中设置完成结果,并且通过channel通知Executor