场景题集锦 | Olimi’s Blog

大数据查找

有一个40亿不重复的unsigned int数据。给出几个数据，快速找出这些数据是否在所有数据中。

思路：

位图法：如果数据量不太大，我们可以采用位图法，将每个数都映射到一个二进制位上，可以将所有的数放到一个长度为2^32的位图中，即使用一个unsigned int类型的数组来表示。时间复杂度为O(n) + 查找时间O(1)。

实现

位图（Bitmap）是一种非常高效的数据结构，它使用一个bit位来标记某个元素对应的值，而非整个int或者long的长度，所以空间效率非常高。假设我们有1到n的n个数据，我们就可以用n个bit表示。

以下是位图的基本操作：

插入一个数x：将bit位x对应的值设为1。

删除一个数x：将bit位x对应的值设为0。

查找一个数x：查看bit位x对应的值。

这里假设数据范围为0到n-1，用一个n位的位图即可表示。以下是一个基本的Python实现：

在这个例子中，我们使用一个整型数组来存储bit位，每个整型数可以存储32个bit位（假设整数是32位的）。我们使用位操作来设置、重置和测试bit位。

需要注意的是，位图的主要限制是它只能处理非负整数，并且无法处理重复的数字。此外，如果数据的范围非常大，位图可能需要消耗大量的内存。例如，如果数据的范围是1到10^9，那么我们需要的位图大小将会是10^9 bit，大约120MB，这在很多情况下是可以接受的。但如果数据范围更大，例如1到10^12，那么位图的大小就会达到120GB，这对于绝大多数应用来说是无法接受的。

最高位二分（编程珠玑）：

将这40亿个数分成两类：1.最高位为0；2.最高位为1。

并将这两类分别写入到两个文件中，其中一个文件中数的个数<=20亿，而另一个>=20亿（这相当于折半了）；

与要查找的数的最高位比较并接着进入相应的文件再查找

再然后把这个文件为又分成两类：1.次最高位为0；2.次最高位为1。

并将这两类分别写入到两个文件中，其中一个文件中数的个数<=10亿，而另一个>=10亿（这相当于折半了）；与要查找的数的次最高位比较并接着进入相应的文件再查找。

.......

以此类推，就可以找到了,而且时间复杂度为O(logn)。

布隆过滤器：上述两种解法都默认数据范围在40亿左右，但这个假设可能不成立，40亿条数据，但数据范围可能更大的多。如果数据范围更大，例如1到10^12，那么位图的大小就会达到120GB。此时，我们可以使用Bloom Filter（布隆过滤器），一种快速判断一个元素是否存在于一个集合中的算法。Bloom Filter可以利用位图和哈希函数，将所有的数哈希到一个长度为k的位数组中，并将每一位都置为1。当给出一个数时，我们可以将这个数哈希到这个位数组中，并检查哈希到的k个位置是否都为1，若都为1，则说明该数在这40亿个数中。Bloom Filter具有空间效率高、时间效率高、支持动态增加元素等特点，被广泛应用于大数据场景下的快速查找和去重。

实现

在构造布隆过滤器时，需要定义位数组的大小（m位）和哈希函数的个数（k个）。以下是其基本操作：

插入： 对于要插入的元素，将其分别通过k个哈希函数计算得到k个哈希值，然后根据这些哈希值找到位数组中的k个位置，将这些位置的位设为1。

查询： 对于要查询的元素，同样将其通过k个哈希函数计算得到k个哈希值，然后根据这些哈希值找到位数组中的k个位置，如果所有这些位置的位都为1，那么认为这个元素可能在集合中；如果有任何一个位置的位为0，那么这个元素肯定不在集合中。

下面是一个简单的Python实现：

在这个例子中，我们首先创建了一个大小为size的位数组。然后，对于每个要插入或查询的元素，我们使用hash_num个哈希函数（在这个例子中，我们使用Python的内置hash函数和不同的种子模拟多个哈希函数）计算哈希值，然后根据哈希值找到位数组中的位置。

需要注意的是，由于布隆过滤器的误报率，它通常用在需要快速判断元素是否可能在集合中的场景，例如网页爬虫判断一个URL是否被访问过，或者垃圾邮件过滤等。如果需要精确的判断，那么可能需要结合其他数据结构或方法。

具体实现中，可实现到误判率为0.03这个程度。

ref：

排序、位图、最高位二分

位图、布隆过滤器

位图实现

荣耀数据传输开放题

荣耀北京和深圳都有数据中心，假设从深圳数据中心每天要把其所有数据传递给北京，当天传完，日结。问这里的难点是什么、以及设计哪些哪些功能模块。

参考思路：（主要在数据传递上而不是系统层面，分析的可以深入而具体）

难点：

数据量：如果数据量非常大，那么数据传输可能会需要很长的时间，甚至可能超过一天。

网络带宽和稳定性：网络带宽限制了每秒可以传输的数据量。另外，网络中断或延迟也可能影响数据传输。

数据完整性：在传输过程中，数据可能会遭受损坏或丢失，所以需要有办法检测和纠正这些问题。

安全性：数据在传输过程中可能会被拦截或篡改，所以需要使用加密和身份验证等安全措施。

数据一致性：如果深圳的数据在传输过程中发生更改，那么需要有一种方法来保证北京的数据能够反映这些更改。

功能模块：

数据压缩：为了减少传输的数据量，可以在发送前对数据进行压缩。

数据分片：如果数据量非常大，可以将数据分成小块，然后并行传输。

错误检测和纠正：可以使用如CRC、校验和、奇偶校验等方法来检测数据是否在传输过程中被损坏，如果可能的话，也可以使用纠错码来纠正错误。

重试和恢复：如果数据传输失败，需要有一种方法来重新开始传输，或者从失败的地方继续传输。

安全措施：可以使用TLS或SSL等协议来对数据进行加密，并使用数字证书进行身份验证。

数据同步：这可能包括锁定源数据以防止在传输过程中进行更改，以及在目标端应用更改以保持数据一致性。

日志和监控：记录数据传输的详细信息，包括开始和结束的时间，传输了多少数据，是否存在错误等。同时，实时监控数据传输的状态，以便在出现问题时及时发现和解决。

快手重I/O服务器优化性能

I/O多路复用模型。select，poll，epoll。比如epoll模式中，考虑CPU占用率高的话可能在哪些部分。比如系统调用，用户态到内核态的切换会有损耗。如何减小这个开销。提了一个批处理思路。还给了一个DMA技术。

使用epoll模型时，可能出现CPU占用率高的情况。这主要可能在以下几个方面：一是在处理大量的并发连接时，需要频繁地调用epoll_ctl函数来添加、修改或删除监视的文件描述符，这可能会消耗大量的CPU资源；二是在调用epoll_wait函数等待文件描述符准备好进行I/O操作时，如果设置的超时时间过短，或者在非阻塞模式下频繁地调用epoll_wait函数，可能会导致CPU忙等，从而占用大量的CPU资源；三是在接收到I/O通知后，需要进行数据的读取或写入，如果数据处理的逻辑复杂，也可能会消耗大量的CPU资源。

为了优化这些问题，可以采取以下几种策略：

合理设置epoll_wait的超时时间：设置合理的超时时间可以避免频繁地调用epoll_wait函数，从而减少CPU的忙等。
使用线程池处理I/O操作：当接收到I/O通知后，可以将数据的读取或写入操作交给线程池来处理，这样可以利用多核CPU的并行处理能力，从而提高处理效率。
使用边缘触发模式：epoll支持两种触发模式：水平触发（Level Triggered）和边缘触发（Edge Triggered）。边缘触发模式只在文件描述符的状态发生变化时发出通知，而不是在文件描述符准备好进行I/O操作时就发出通知，这样可以减少不必要的通知，从而降低CPU的使用率。
优化数据处理逻辑：在接收到I/O通知后，需要进行数据的读取或写入。如果这个过程中的逻辑复杂，可能会消耗大量的CPU资源。因此，优化这部分的代码，比如通过使用更高效的数据结构和算法，可以帮助降低CPU的使用率。

直接内存访问（Direct Memory Access, DMA）是一种可以让某些硬件子系统在主内存和设备间直接传输数据，而无需通过CPU的技术。这种技术在需要处理大量数据，尤其是I/O操作时，可以大幅度降低CPU的负载，因为CPU不需要参与每一次数据传输。

在网络通信中，DMA技术可以用于实现零拷贝（Zero-Copy）数据传输，这对于I/O密集型服务器的性能优化非常关键。以下是一些使用DMA技术优化CPU占用高问题的策略：

使用零拷贝技术：在传统的网络通信中，数据需要从内核空间拷贝到用户空间，然后再从用户空间拷贝到内核空间，这种多次拷贝操作会占用大量的CPU资源。零拷贝技术利用DMA，使数据可以直接从网络接口卡（NIC）传输到内存，或者从内存直接传输到NIC，无需通过CPU，从而降低CPU的使用率。
使用内核旁路（Kernel Bypass）技术：内核旁路技术可以让应用程序直接访问网络接口卡，绕过内核的网络栈，从而避免了内核空间与用户空间之间的上下文切换和数据拷贝，降低了CPU的使用率。这种技术需要硬件和驱动的支持，例如Intel的DPDK（Data Plane Development Kit）和Mellanox的RDMA（Remote Direct Memory Access）技术。
使用异步I/O模型：在异步I/O模型中，应用程序发起I/O操作后，无需等待I/O操作完成，可以立即进行其他操作。当I/O操作完成后，应用程序会收到一个通知。这种模型可以充分利用DMA技术，因为数据的传输可以在后台，无需通过CPU进行。

epoll水平触发和边缘触发的实现。边缘触发的话，如果有100 byte，然后读了50byte，之后再来了2byte数据，那剩下52byte数据会触发事件回调吗。

当你第一次读取50 byte数据后，剩下的50 byte数据不会再触发epoll的事件。只有当再有新的数据（也就是这里的2 byte）到来时，epoll才会触发事件。这时你在处理事件时，会读取到52 byte的数据（之前剩下的50 byte和新到来的2 byte）。