Summer Blog

算法题002

链表

成对翻转

1->2->3->4 ==> 2->1->4->3

public Node swapNodePair(Node head){
    Node newHead = new Node(0);
    newHead.next = head;
    Node pre = newHead;

    while(pre.next != null && pre.next.next != null){
        Node n1 = pre.next;
        Node n2 = pre.next.next;
        Node n3 = pre.next.next.next;

        pre.next = n2;
        pre.next.next = n1;
        pre.next.next.next = n3;
        pre = pre.next.next;
    }

    return newHead.next;
}

LeetCode 141. Linked List Cycle

def hasCycle(self, head: ListNode) -> bool:
    p1, p2 = head, head

    while p2 and p2.next:
        p1 = p1.next
        p2 = p2.next.next
        if p1 == p2:
            return True
    return False

栈和队列

LeetCode 20. Valid Parentheses

def isValid(self, s: str) -> bool:
    stack = []
    
    for c in s:
        if c == '(' or c == '[' or c == '{':
            stack.append(c)
        if c == ')' and (len(stack) == 0 or stack.pop() != '('):
            return False
        if c == ']' and (len(stack) == 0 or stack.pop() != '['):
            return False
        if c == '}' and (len(stack) == 0 or stack.pop() != '{'):
            return False
            
    return len(stack) == 0

def isValid2(self, s: str) -> bool:
    stack = []
    param_map = {')':'(', ']':'[', '}':'{'}

    for c in s:
        if c not in param_map:
            stack.append(c)
        elif not stack or stack.pop() != param_map[c]:
            return False
    return not stack

算法题001

算法问题的学习方法很枯燥，分为以下几步：

  1. 学习知识点，整理脉络
  2. 针对性练习
  3. 反馈，看高手的代码，或请教高手

栈和队列

猫狗队列

实现队列的方法add pollAll pollDog pollCat isEmpty isDogEmpty isCatEmpty

public class Pet{
    private String type;
    public Pet(String type){this.type = type;}
    public String getType(){ return type;}
}

public class Cat {
   public Cat(){ super("cat");}
}
public class Dog {
   public Dog(){ super("dog");}
}

public class PetQueenElement{
    private Pet pet;
    private int order;

    PetQueenElement(Pet pet, int order){
        PetQueenElement element = new PetQueenElement(pet, order);
    }

    public Pet getPet(){
        return this.pet;
    }

    public int getOrder(){
        return this.order;
    }
}

public class PetQueen{
    private int order;
    private Queen<PetQueenElement> cats;
    private Queen<PetQueenElement> dogs;

    public PetQueen(){
        this.cats = new LinkedList<>();
        this.dogs = new LinkedList<>();
        this.order = 0;
    }

    public void add(Pet pet){
        if(pet instanceof Cat){
            cats.add(new PetQueenElement(pet, order)));
        }else{
            dogs.add(new PetQueenElement(pet, order)));;
        }
        allPets.add(pet);
    }

    public Pet pollAll(){
        if (!cats.isEmpty() && !dogs.isEmpty()){
            if (cats.peek().getOrder() > dogs.peek().getOrder()){
                return cats.poll().getPet();
            }else if(!cat.isEmpty()){
                return cats.poll().getPet();
            }else if(!dogs.isEmpty()){
                return dogs.poll().getPet();
            }else{
                throw new RuntimeException("err, no pet!!!")
            }
        }
    }

    public Cat pollCat(){
        if(!cat.isEmpty()){
                return cats.poll().getPet();
        }
        throw new RuntimeException("err, not cat")
    }
    // 余下省略...
}

从零开始学架构--读书笔记

本篇第一部分为我阅读《从零开始学架构》的读书笔记。如觉得有帮助，请购买正版图书学习。

第二部分为平时看到的有关架构的一些资料整理。

高性能存储

关系型数据库

数据库范式

  1. 每个属性都不可再分。即每个列不可再分。1NF 是所有关系型数据库的最基本要求。
  2. 表中的每列都和主键相关。一个表中只能保存一种数据，不可以把多种数据保存在同一张数据库表中。
  3. 每一列数据都和主键直接相关，而不能间接相关。

读写分离

业务分库

分表

唯一主键生成

  1. Snowflake：
    1. 特点：调递增，包含机器 ID、序列号、时间戳。
    2. 使用：可以嵌入代码中，也可以部署单独的 ID 服务器。
    3. 缺点：依赖系统的时间戳，如果时间不准会产生重复 ID；并发不高时，可能造成 ID 分布不均，可以用秒做结束，或者随机一个开始序号

NoSQL

K-V 存储（Redis 为例）

支持string, hash, list, set, zset, map

缺点：不完全支持 ACID

一致性 HASH 算法

Redis 集群部署时考虑容错性和可用性，采用一致性 Hash 算法计算 key 的存储节点。一致性 Hash 算法将整个哈希值空间组织成一个虚拟的圆环，如假设某哈希函数 H 的值空间为 0-2^32-1。使用一致性 Hash 算法对于节点的增减都只需重定位环空间中的一小部分数据，具有较好的容错性和可扩展性。

在服务节点太少时，容易因为节点分部不均匀而造成数据倾斜（被缓存的对象大部分集中缓存在某一台服务器上）问题。为了解决这种数据倾斜问题，一致性 Hash 算法引入了虚拟节点机制，即对每一个服务节点计算多个哈希，每个计算结果位置都放置一个此服务节点，称为虚拟节点。

文档数据库

为了解决 schema 带来的问题，最大的特点是灵活无 schema，大部分使用 json 存储数据。适合与电商游戏等场景。可作为关系型数据库的补充。

优势：

缺点：

列式数据库

一般将列式存储应用在离线的大数据分析和统计场景中，因为这种场景通常在几个列中，且不需更新删除数据。

优势：

缺点：

全文搜索引擎

传统关系型数据库可能无法满足全文搜索的需求场景，因为全文搜索的条件通常是任意组合的，如果建索引需要建很多；like 是整表扫描，效率非常底

全文搜索通常使用倒排索引实现，原理是建立单词到文档的索引。

缓存

问题：

CDN 缓存静态资源

CDN 就是将静态的资源分发到位于多个地理位置机房中的服务器上，因此它能很好地解决数据就近访问的问题，也就加快了静态资源的访问速度。

以 www.baidu.com 为例给你简单的域名解析过程：

  1. 域名解析请求先会检查本机的 hosts 文件，查看是否有 www.baidu.com 对应的 IP；
  2. 如果没有的话，就请求 Local DNS 是否有域名解析结果的缓存，如果有就返回标识是从非权威 DNS 返回的结果；
  3. 如果没有就开始 DNS 的迭代查询。先请求根 DNS，根 DNS 返回顶级 DNS（.com）的地址；再请求.com 顶级 DNS 得到 baidu.com 的域名服务器地址；再从 baidu.com 的域名服务器中查询到 www.baidu.com 对应的 IP 地址，返回这个 IP 地址的同时标记这个结果是来自于权威 DNS 的结果，同时写入 Local DNS 的解析结果缓存，这样下一次的解析同一个域名就不需要做 DNS 的迭代查询了。

消息队列

作用

  1. 削峰填谷，将峰值流量缓存在消息队列中，如秒杀场景
  2. 异步处理，处理非主要流程，如消费后发放优惠卷
  3. 解耦，不直接依赖接口，依赖消息队列降低系统间的耦合型

消息丢失

  1. 生产者发送消息时网络错误，以为发送给了 MQ，实际 MQ 没有接收到。这种情况设置正确的消息重传次数和失败处理，另外也可以设置消息同步到多个副本才算成功。
    • 设置副本数大于 1
    • 设置活跃 follower 大于 1
    • 设置 leader 需要把消息同步到最小活跃同步 follower 才算写入成功
    • 重试次数和处理设置
  2. MQ 仅接收到消息，还未来得及写入磁盘保存；只写入到 leader 没有同步到 follower 时，leader 挂了
    • 设置副本数大于 1
    • 设置活跃 follower 大于 1
    • 设置 leader 需要把消息同步到最小活跃同步 follower 才算写入成功
    • 重试次数和处理设置
  3. 消费者已经提交了确认，但消费途中没有处理完就 down 了 –> 关闭自动提交确认，手动保证处理完成后提交

消息重复消费

避免重复消费，需要保证消息的生产、消费过程的幂等性：

消息延迟

  1. 监控：
    1. 使用消息队列提供的工具，通过监控消息的堆积来完成，如kafka-consumer-groups.sh、JMX
    2. 生成监控消息的方式来监控消息的延迟情况，具体是生成一个时间戳消息，消费者消费到此消息时判断时间是否大于阈值，发送报警
  2. 减少的方法：
    1. 优化消费性能
    2. 增加消费者数量（Kafka 消费者的数量和分区数一样，需要同时增加分区数和消费者数）

Kafka 设计优点

  1. Kafka 使用硬盘存储，但做了很多优化的设计使存储性能很高
    1. 顺序存储，所有的消息在文件后面追加
    2. 通过维护一个 offset 来实现顺序访问
  2. IO 采用 0 拷贝技术，减少了从内核空间读取到用户缓存，再从用户缓存输出到网络流的时间。直接从页缓存写入网络流
  3. 网络带宽上的设计考虑，会对消息做压缩，减少带宽消耗。也可以设置消息批量发送，减少网络请求次数
  4. 分布式存储设计，有备份和主分区，保证消息不丢失。用户通过 offset 也能从宕机事故中快速恢复