2020_05_11_02

多态

编译时多态

1. 通过函数重载实现

运行时多态

1. 多态性可以概括为“一个接口，多个方法”，程序运行时才决定调用哪个具象化函数
2. 多态通过虚函数实现，虚函数允许子类重新定义成员函数，而子类重写定义父类函数的做法叫做覆盖，override

vector底层

1. vector底层实现是封装了顺序表，是一块物理上连续的空间
   1. 它的初始化元素个数是size()大小，分配的整个空间大小是capacity()大小
2. 当capacity()存满之后，它会重新分配一块够大的新的空间，这个新的空间大小可能是原来的1.5倍，也可能是原来的2倍，视编译器实现而定
   1. 分配完成之后，它会把之前的元素放到的新的空间，并销毁掉旧的空间

new和malloc

区别

1. malloc和free是C/C++标准库函数，new 和delete是C++的运算符
2. 对于非内部数据类的对象而言，malloc/free无法满足动态对象的要求。即对象在创建的同时自动执行构造，对象消亡之前要自动执行析构
3. malloc/free是库函数不是运算符，不在编译器控制权限之内，不能把构造函数和析构函数的任务强加给malloc/free</li> <li>malloc执行成功返回类型为void*，失败返回0，new执行失败抛出异常

步骤

new

1. new表达式调用一个operator new[]的标准库函数。分配一块足够大的、原始的、未命名的内存空间以便存储特定类型的对象
2. 编译器允许相应的构造函数以构造这些对象，并为其传入初始值
3. 对象被分配了空间并构造完成，返回一个指向该对象的指针

delete

1. 对指针所指向的数组或对象中元素执行对应的析构函数
2. 编译器调用operator delete[]的标准库函数释放内存空间

malloc

1. 申请一块size大小的空间，不关心内存的类型

free

1. 释放某个指针指向的内存空间

总结

1. 内存分配和初始化

   1. new运算符会先调用operator new函数分配内存，然后自动调用构造函数初始化对象
   2. malloc只是分配内存，并不设计对象的构造
   3. 用new[]分配了数组，它会分配足够的内存来储存所有元素，还会调用每个元素的构造函数
   4. malloc分配数组时，需要手动调用构造函数（如果有的话）来初始化每个元素

2. 释放内存

   1. 使用 delete 来释放 new 分配的内存，并且会自动调用对象的析构函数
   2. 使用 new[] 分配了数组，则需要使用 delete[] 来释放内存
   3. malloc 分配的内存需要使用 free 来释放，并且 free 不会调用析构函数

3. 异常处理

   1. new 在内存分配失败时会抛出 std::bad_alloc 异常
   2. malloc 返回 NULL 指针（或 0，根据标准是 NULL）
   3. 值得注意的是，可以通过 std::nothrow 语法要求 new 不抛出异常，而是返回 nullptr，这在某些情况下更为灵活

4. 重载

   1. new 和 delete 运算符可以被重载，以实现自定义的内存管理行为
   2. 相比之下，malloc 和 free 是库函数，不能重载

5. 类型安全

   1. new 是类型安全的，它返回的指针类型与要创建的对象类型一致
   2. 而 malloc 返回的指针类型总是 void*，这意味着在 C++ 中你需要进行显式类型转换

拥有3亿个数据的文件，如何去重？

方案

1. 通过位图的数据结构，可以搞定
   1. 设有char类型数x，1字节包括8个位，我们可以申请char bit_map[3亿/8+1]的空间，就足以给范围在[0,3亿)的数字去重了
2. 我们知道位图的数据结构就是一个数组，而 位图的操作（算法） 基本依赖于下面3个元操作：
3. set_bit(char x,int n)
   1. 将x的第n位置1，可以通过x |= (x<<n)实现
4. clr_bit(char x,int n)
   1. 将x的第n位清0，可以通过x &= ~(1<<n)实现
5. get_bit(char x,int n)
   1. 取出x的第n位的值，可以通过(x>>n)&1来实现

位图去重原理

1. 位图的原理
   1. 位图（BitMap）是一个非常高效的用于去重的结构，特别适合处理大量的整型数据
   2. 对于你提到的 3 亿个数据，假设数据范围在 [0, 3亿)，确实可以用位图来实现去重
   3. 具体来说，bit_map[3亿/8 + 1] 将分配约 37.5MB 的内存
   4. 这是因为 3 亿个位需要大约 37.5MB（= 3 亿 / 8）的存储空间
2. 处理流程
   1. 对于每个数据 n，你可以通过如下方式操作位图：
   2. 计算位置：index = n / 8 和 bit = n % 8
   3. 检查是否已经存在：bit_map[index] & (1 << bit)
   4. 如果不存在，则标记为存在：bit_map[index] |= (1 << bit)
3. 数据范围的假设
   1. 方案假设数据的范围在 [0, 3亿)
   2. 如果数据的范围比这个大，或者数据不是连续的整数，而是任意整数，这种方法就需要调整，例如通过哈希函数来映射数据到位图范围
4. 外部排序（如有必要）
   1. 如果内存限制较严格，无法一次性处理 3 亿个数据，你可以采用外部排序或分块处理的方式，将数据分块处理，每块使用位图去重，然后合并去重结果

如何给10^7个数据量的磁盘文件排序

1. 如何给10^7个数据量的磁盘文件排序
2. 也是用了位图的思路

3亿个数据存放到内存当中，占多大内存？

1. 结合上一条，需要申请3亿个char元素用来做标记，那么进程旧需要0.3G运行内存

数据库和备份数据库之间，如何安全同步？

方法一：基于日志的复制

1. 主从复制
   1. 主数据库记录所有的写操作（如插入、更新、删除）到日志文件中，从数据库读取这些日志并在从数据库上执行相同的操作
   2. 优点：实时性高，可以确保从数据库的数据与主数据库的一致性
   3. 缺点：如果从数据库延迟处理日志，可能会导致数据不一致
2. 同步复制
   1. 写操作在主数据库和从数据库上同时执行，只有在两者都成功时才算完成
   2. 优点：确保强一致性
   3. 缺点：由于同步操作，性能可能受到影响

方法二：快照同步

1. 定期快照
   1. 定期对主数据库进行快照，并将快照同步到备份数据库
   2. 这可以使用数据库提供的快照工具或文件系统的快照功能
   3. 优点：简单易用，可以在不影响主数据库性能的情况下进行
   4. 缺点：快照之间的数据更改不会被捕捉，可能导致数据不一致
2. 增量快照
   1. 仅同步自上次快照以来的更改部分，减少数据传输量
   2. 优点：减少网络和存储负载
   3. 缺点：实现起来可能比完整快照复杂

方法三：双向复制

1. 多主复制
   1. 多个数据库节点可以互相同步，每个节点都可以进行读写操作，并且所有的更改都被复制到其他节点
   2. 优点：提高了系统的可用性和容错能力
   3. 缺点：需要解决冲突问题，当多个节点同时修改相同的数据时，可能出现数据冲突

方法四：流复制

1. 流复制
   1. 实时地将主数据库的 WAL（Write-Ahead Log）记录传输到备份数据库并进行应用
      这是一种常用于 PostgreSQL 的复制方式
   2. 优点：实时性高，数据一致性强
   3. 缺点：网络中断可能会导致数据延迟

方法五： 数据验证

1. 校验和
   1. 对同步后的数据进行校验和验证，确保主数据库和备份数据库之间的数据一致性
   2. 优点：可以检测和纠正数据传输过程中的错误
   3. 缺点：需要额外的计算资源来生成和验证校验和
2. 双重写入
   1. 在进行写操作时，同时向主数据库和备份数据库写入数据，确保两者的数据一致
   2. 优点：强一致性
   3. 缺点：可能影响性能，并且需要处理网络问题带来的延迟

基于链接服务器的远程数据同步

1. 在特定情况下是有效的，但并不适合所有的场景
2. 适合
   1. 临时数据访问或查询
   2. 低频率的数据同步

常见方案

1. 数据库复制

   1. 适用数据库：MySQL、PostgreSQL、SQL Server、Oracle 等
   2. 概述：
      数据库复制是最常用的数据库同步方案之一，主要包括主从复制（Master-Slave Replication）、多主复制（Multi-Master Replication）和链式复制（Cascading Replication）等
   3. 优点：
      实时性：主从复制可以实现几乎实时的数据同步
      高可用性：复制可以在主服务器出现故障时快速切换到从服务器，提高系统的可用性
      读写分离：在主从复制中，主服务器处理写操作，从服务器处理读操作，提升性能。
   4. 缺点：
      一致性问题：在异步复制模式下，主服务器和从服务器之间可能会有短暂的不一致
      冲突处理：在多主复制中，数据冲突需要额外的处理逻辑

2. 日志传送

   1. 适用数据库：SQL Server、PostgreSQL、Oracle 等
   2. 概述：
      日志传送是一种备份和恢复技术，通过定期传输主数据库的事务日志到备份数据库，并在备份数据库上应用这些日志以保持同步
   3. 优点：
      灾难恢复：提供了有效的灾难恢复机制，可以在主数据库故障后快速恢复到备份数据库
      相对简单：设置和维护相对简单，适合中小规模的环境
   4. 缺点：
      延迟：同步过程通常有一定延迟，无法实现完全的实时性
      读写不可用：备份数据库在恢复时通常处于只读或不可用状态

3. 高可用性组

   1. 适用数据库：SQL Server
   2. 概述：
      Always On 可用性组是 SQL Server 提供的企业级高可用性和灾难恢复解决方案，支持多副本同步，可以配置为同步或异步模式
   3. 优点：
      高可用性：提供自动故障转移功能，支持多个同步副本，保证高可用性
      实时同步：同步模式下可以实现实时数据同步
      灵活性：支持读写分离、负载均衡和跨数据中心部署
   4. 缺点：
      复杂性：设置和维护较为复杂，需要更高的技术水平
      成本高：通常需要更高的硬件和软件成本

4. 数据镜像

   1. 适用数据库：SQL Server（在 2016 版本后被 Always On 取代）
   2. 概述：
      数据镜像是将数据库的所有事务日志记录传送到备份服务器，以保持数据库的副本始终与主数据库一致
   3. 优点：
      实时性：镜像可以实现近乎实时的数据同步
      自动故障转移：支持自动故障转移，提高系统的容错能力
   4. 缺点：
      过时性：SQL Server 2016 后，数据镜像逐渐被 Always On 取代
      只支持单副本：不支持多副本的高可用性场景

5. 云服务的数据库同步

   1. 适用数据库：AWS RDS、Azure SQL Database、Google Cloud SQL 等
   2. 概述：
      云数据库服务通常提供内置的同步和备份功能，如自动备份、跨区域复制和灾难恢复
   3. 优点：
      简化管理：云服务提供了自动化的备份和恢复，减少了运维复杂度
      全球可用性：支持跨区域部署和同步，提高全球范围的可用性和容灾能力
      弹性：根据需求自动扩展，适应业务增长
   4. 缺点：
      成本高：长时间使用可能会产生较高的云服务费用
      依赖供应商：对云服务供应商有较强的依赖性

一次性哈希是什么？

一次性哈希

UDP包最大能存放多少数据？

1. UDP 包的大小就应该是 1500 - IP头(20) - UDP头(8) = 1472(Bytes)
2. TCP 包的大小就应该是 1500 - IP头(20) - TCP头(20) = 1460 (Bytes)
3. 解释
   1. 典型的以太网中，以太网帧的 MTU（Maximum Transmission Unit，最大传输单元）为1500字节

TCP为什么是3次握手

确认双方的接收能力和发送能力

1. TCP 是一个面向连接的协议，在开始通信之前，双方需要确保彼此都能接收和发送数据
2. 三次握手的每一步都确保了通信双方的收发能力：
   1. 第一次握手（SYN）：
      客户端发送一个 SYN（Synchronize Sequence Number）包，告诉服务器客户端想要建立连接，并且告知初始序列号（ISN）
   2. 第二次握手（SYN-ACK）：
      服务器收到 SYN 包后，确认自己可以接收并处理客户端的请求，发送一个 SYN-ACK 包作为回应
      这不仅确认了服务器接收到客户端的 SYN，还包含了服务器的初始序列号，表示服务器也准备好建立连接
   3. 第三次握手（ACK）：
      客户端收到 SYN-ACK 包后，确认自己可以接收服务器的数据，并向服务器发送 ACK 包，确认连接的建立

防止旧的重复连接请求干扰

1. TCP 的三次握手机制可以防止旧的、重复的连接请求（可能由于网络延迟或其他原因滞留在网络中的数据包）意外触发新的连接
2. 假设没有三次握手，只使用两次握手：
   1. 客户端发送 SYN，服务器响应 SYN-ACK，连接就建立了
   2. 但如果有一个滞留在网络中的旧 SYN 包被服务器接收到，服务器可能错误地认为客户端想要建立一个新的连接
      详细解释见下文
3. 通过三次握手，服务器发送的 SYN-ACK 必须得到客户端的确认（ACK），才能真正建立连接
   1. 这一步防止了旧的 SYN 包误触发连接

确保双方序列号的同步

1. 序列号是 TCP 协议中用于确保数据包顺序传输和重传控制的关键部分
2. 三次握手过程中，双方会交换各自的初始序列号（ISN），以便在数据传输过程中能够正确地排序和确认接收的数据包

两次握手，为什么服务器可能错误地认为客户端想建立一个新连接

假设没有三次握手，仅有两次握手的情况

1. 第一次握手：客户端发送 SYN 包：
   1. 客户端发送一个 SYN 包，表示想要建立连接，并发送一个初始序列号（ISN）
   2. 这个 SYN 包可能由于网络问题而延迟到达服务器，或者滞留在网络中一段时间后才到达服务器
2. 第二次握手：服务器响应 SYN-ACK 包：
   1. 服务器收到 SYN 包，认为客户端想要建立连接，并返回一个 SYN-ACK 包，表示同意建立连接，并携带服务器的初始序列号（ISN）
   2. 在两次握手的假设中，此时连接就会被认为已经建立

问题的产生

1. 滞留的旧 SYN 包
   1. 假设客户端和服务器在之前已经成功建立过连接，后来因为某种原因，这个连接被关闭了
   2. 然而，之前那个连接的 SYN 包在网络中滞留了，可能在一段时间后才到达服务器
2. 服务器的误判
   1. 当服务器接收到这个滞留的旧 SYN 包时，服务器会认为客户端是新发来的连接请求（因为它没有办法区分这个 SYN 包是旧的还是新的）
   2. 于是，服务器按照两次握手的逻辑，直接回应一个 SYN-ACK，并认为新的连接已经建立
3. 没有第三次握手的确认
   1. 如果没有第三次握手，服务器已经认为连接建立了，但客户端其实可能根本没有发起新的连接请求
   2. 因此，客户端对于这个“新连接”是毫不知情的
      服务器此时会等待客户端的响应（如 ACK 或数据包），但因为客户端没有真正发起这个请求，它不会发送任何回应，导致服务器在等待中浪费资源
4. 资源浪费和潜在的攻击
   1. 这种情况下，服务器可能会出现连接超时，浪费系统资源
   2. 此外，如果这种滞留的旧 SYN 包被恶意利用，可能导致服务器被大量无效连接请求所淹没，造成拒绝服务（DoS）攻击

总结

1. 一开始客户端发送了一个SYN包，但是由于一些原因，这个包没有很快的发送到服务器，于是客户端采取了其他的策略，比如发送另一个新的SYN包或者放弃建立连接
2. 然后，过了一段时间后，服务端收到了那个滞留的SYN包，此时，如果客户端并没有一直在等着这个SYN包的对应回复，而采取了其他的策略。那么，旧的SYN包必然存在与新的策略的目的不相符合的风险
   1. 比如客户端发送了新的SYN包，建立了新的连接，那么旧的SYN对应的连接就不应该被建立
   2. 如果客户端放弃了连接的建立，旧的SYN包的连接不应该建立但是建立了
3. 之所以会这样，是因为服务端没有能力分别SYN包是新的还是旧的
4. 而且，二次握手建立连接，暴露出来的这个SYN包的问题，还会诱发其他的问题，比如攻击者发现了这个SYN包，大量发相同的SYN包，导致造成服务器拒绝服务

TCP为什么不是两次或四次握手

1. 两次握手：
   1. 不能完全避免旧的重复 SYN 包的干扰，并且无法保证双方的序列号同步和通信能力
2. 四次握手：
   1. 三次握手已经足以确保可靠的连接建立，增加额外的一次握手会增加开销而没有显著的额外好处

TCP四次挥手过程

第一次挥手：FIN（终止）报文

1. 发起方（通常是客户端）：
   1. 当客户端完成数据发送并认为不再需要继续通信时，它会发送一个 FIN（Finish）报文段给服务器
   2. 这标志着客户端已经完成数据的发送，准备关闭连接
2. 报文：
   1. 这个报文段包含 FIN 标志，并且可能还会携带 ACK（确认）标志
3. 状态变化：
   1. 此时，客户端进入 FIN-WAIT-1 状态

第二次挥手：ACK（确认）报文

1. 接收方（通常是服务器）：
   1. 服务器收到 FIN 报文后，确认客户端已经完成了数据发送
   2. 服务器会发送一个 ACK 报文段来确认已经收到了客户端的 FIN
2. 报文：
   1. 这个 ACK 报文段会确认客户端的序列号
3. 状态变化：
   1. 此时，客户端进入 FIN-WAIT-2 状态，服务器进入 CLOSE-WAIT 状态
   2. 服务器在这个状态下，仍然可以发送剩余的数据给客户端

第三次挥手：FIN（终止）报文

1. 接收方（通常是服务器）：
   1. 当服务器完成数据发送并准备关闭连接时，它会向客户端发送一个 FIN 报文段，表示服务器也要关闭连接了
2. 报文：
   1. 这个 FIN 报文段也可能带有 ACK 标志，用来确认之前的通信数据
3. 状态变化：
   1. 此时，服务器进入 LAST-ACK 状态

第四次挥手：ACK（确认）报文

1. 发起方（通常是客户端）：
   1. 客户端收到服务器的 FIN 报文段后，确认服务器已经完成了数据发送
   2. 客户端会发送一个 ACK 报文段，确认接收到服务器的 FIN
2. 报文：
   1. 这个 ACK 报文段确认了服务器的 FIN 报文段的序列号
3. 状态变化：
   1. 客户端在发送完 ACK 后进入 TIME-WAIT 状态，而服务器在接收到 ACK 报文段后进入 CLOSED 状态，释放连接资源

TCP为什么是4次挥手

1. tcp连接握手时为何ACK是和SYN一起发送，挥手时ACK却没有和FIN一起发送呢
2. 原因是因为tcp是全双工模式，接收到FIN时意味将没有数据再发来，但是还是可以继续发送数据

两次挥手可以吗

1. 如果只进行两次挥手，可能无法正确处理双方的发送和接收操作
2. 例如，A 发送 FIN，B 确认收到后直接关闭连接，而不发送自己的 FIN，这时 B 的数据发送可能未完成，导致数据丢失

三次挥手可以吗

1. 如果是三次挥手，假设 A 发送 FIN，B 回复 ACK 并同时发送 FIN，然后 A 回复 ACK
2. 这种情况中 B 的 ACK 和 FIN 是结合在一起的，但这可能无法保证 B 的数据发送已经完全结束，特别是在 B 的发送和接收时序不同的情况下