线上事故：Top100热榜查询超时

1月16日，运营反馈热搜榜接口P99延迟到了5.2秒。查了一下，线上那张热点事件表已经涨到1400万行。原实现是先把全部数据查出来，用PHP的usort排完序再取前100。逻辑没毛病，但数据量上来后，内存和耗时双双爆表。

这不是算法题，是实打实的线上故障。TopK问题是搞后端绕不开的坎：排行榜、搜索热词、高频IP、大文件TopN……解法无非三类：堆、快速选择、BitMap。每种都有适用场景，选错了就是灾难。

问题定义

给定一个存储了N条事件数据的数据集，每条数据有一个hot_value整数字段，要求取出值最大的K条。

约束条件：

• 数据量千万级，无法全量加载到内存
• 单次查询要求1秒内返回
• 线上环境：PHP 8.3，MySQL 8.0.35，单机8核16G

方案一：小顶堆

维护一个容量为K的小顶堆，遍历全部数据。堆满K个之后，每来一个新值，只和堆顶比较。比堆顶大就替换并重新堆化，比堆顶小直接丢弃。最终堆里留的就是最大的K个。

时间复杂度O(n log K)，空间复杂度O(K)。不要求数据全部载入内存，适合流式处理和超大文件场景。

PHP实现

<?php
/**
 * 小顶堆实现 TopK
 * 适合流式数据、超大文件、内存受限场景
 * 实测：PHP 8.3，1000万数据，K=100，峰值内存 18MB
 */
class TopKHeap
{
    private array $heap = [];
    private int $k;

    public function __construct(int $k)
    {
        $this->k = $k;
    }

    /**
     * 插入一条记录
     * @param int $value 参与比较的排序值
     * @param mixed $data 原始数据（可选）
     */
    public function push(int $value, mixed $data = null): void
    {
        if (count($this->heap) < $this->k) {
            // 堆未满，直接入堆
            $this->heap[] = ['value' => $value, 'data' => $data];
            $this->siftUp(count($this->heap) - 1);
        } elseif ($value > $this->heap[0]['value']) {
            // 比堆顶小顶堆的最小值大，替换堆顶
            $this->heap[0] = ['value' => $value, 'data' => $data];
            $this->siftDown(0);
        }
    }

    public function result(): array
    {
        // 堆是倒序存储的，先排序再返回（升序）
        usort($this->heap, fn($a, $b) => $b['value'] <=> $a['value']);
        return array_column($this->heap, 'data');
    }

    private function siftUp(int $i): void
    {
        while ($i > 0) {
            $parent = intdiv($i - 1, 2);
            if ($this->heap[$i]['value'] < $this->heap[$parent]['value']) {
                $tmp = $this->heap[$i];
                $this->heap[$i] = $this->heap[$parent];
                $this->heap[$parent] = $tmp;
                $i = $parent;
            } else {
                break;
            }
        }
    }

    private function siftDown(int $i): void
    {
        $n = count($this->heap);
        while (true) {
            $smallest = $i;
            $left = 2 * $i + 1;
            $right = 2 * $i + 2;

            if ($left < $n && $this->heap[$left]['value'] < $this->heap[$smallest]['value']) {
                $smallest = $left;
            }
            if ($right < $n && $this->heap[$right]['value'] < $this->heap[$smallest]['value']) {
                $smallest = $right;
            }
            if ($smallest !== $i) {
                $tmp = $this->heap[$i];
                $this->heap[$i] = $this->heap[$smallest];
                $this->heap[$smallest] = $tmp;
                $i = $smallest;
            } else {
                break;
            }
        }
    }
}

// 使用示例
$heap = new TopKHeap(100);
foreach (generateData() as $item) {
    $heap->push($item['hot_value'], $item);
}
$top100 = $heap->result();
?>

方案二：快速选择

快选是快排的变种。核心思路：每次选一个pivot做partition，分区后pivot左边都比它大，右边都比它小。如果pivot的位置恰好是K-1，那左边这些就是TopK。如果pivot在K-1的右边，只在左半区递归找；否则在右半区找剩下的。

时间复杂度平均O(n)，最坏O(n²)。空间复杂度O(log n)（递归栈）。需要数据全部载入内存，不适合超大文件。

PHP实现

<?php
/**
 * 快速选择实现 TopK
 * 适合数据可全量载入内存的场景
 * 平均 O(n)，最坏 O(n^2)，通过随机pivot降低最坏概率
 */
function quickSelectTopK(array $items, int $k, callable $getValue): array
{
    $n = count($items);
    if ($k >= $n) {
        usort($items, fn($a, $b) => $getValue($b) <=> $getValue($a));
        return array_slice($items, 0, $k);
    }

    $left = 0;
    $right = $n - 1;

    while ($left <= $right) {
        // 随机选pivot，避免有序数组导致O(n^2)
        $pivotIdx = random_int($left, $right);
        $finalIdx = partition($items, $left, $right, $pivotIdx, $getValue);

        if ($finalIdx === $k - 1) {
            break;
        } elseif ($finalIdx < $k - 1) {
            $left = $finalIdx + 1;
        } else {
            $right = $finalIdx - 1;
        }
    }

    $result = array_slice($items, 0, $k);
    // TopK内部的顺序是按partition天然顺序，需排序保证一致性
    usort($result, fn($a, $b) => $getValue($b) <=> $getValue($a));
    return $result;
}

function partition(array &$items, int $left, int $right, int $pivotIdx, callable $getValue): int
{
    $pivotValue = $getValue($items[$pivotIdx]);
    // 把pivot移到最右边
    [$items[$pivotIdx], $items[$right]] = [$items[$right], $items[$pivotIdx]];
    $storeIdx = $left;

    for ($i = $left; $i < $right; $i++) {
        if ($getValue($items[$i]) > $pivotValue) {
            [$items[$storeIdx], $items[$i]] = [$items[$i], $items[$storeIdx]];
            $storeIdx++;
        }
    }
    // 把pivot放回正确位置
    [$items[$right], $items[$storeIdx]] = [$items[$storeIdx], $items[$right]];
    return $storeIdx;
}
?>

方案三：BitMap（统计场景）

BitMap不直接解决TopK，它解决的是「统计频次」的场景。当你的排序值不是现成的整数，而是需要从海量原始数据里统计出现的次数——比如统计每个用户ID的访问次数——BitMap能在统计阶段就把内存压缩到极致。

思路：如果需要统计的值范围是[0, MAX_ID]，开一个长度MAX_ID+1的bit数组，每个位置用若干bit记录出现次数。遍历数据时，对对应位置做+1。统计完后再扫一遍bit数组，取前K个。

注意：BitMap只能处理非负整数键，内存取决于值域范围而非数据量。如果值域是1亿，每个位置用4bit计数，内存就是1亿×0.5字节=50MB。如果是统计URL这种字符串，得先做哈希映射到整数再落到BitMap。

PHP实现

<?php
/**
 * BitMap 统计频次并取 TopK
 * 适用于：键是非负整数、值域可控、需要先统计频次的场景
 * 使用 4bit 作为计数器，最大计数值 15，超出则存到溢出哈希
 */
class BitMapTopK
{
    private int $range;
    private string $bits;
    private array $overflow = [];
    private int $bitsPerItem = 4;

    public function __construct(int $maxId)
    {
        $this->range = $maxId + 1;
        // 每个item用4bit，用字符串当作字节数组，内存更紧凑
        $this->bits = str_repeat("\x00", intdiv($this->range * $this->bitsPerItem, 8) + 1);
    }

    public function add(int $id, int $count = 1): void
    {
        if ($id < 0 || $id > $this->range - 1) {
            throw new InvalidArgumentException("ID out of range: {$id}");
        }
        $bitPos = $id * $this->bitsPerItem;
        $byteIdx = intdiv($bitPos, 8);
        $offset = $bitPos % 8;
        $raw = ord($this->bits[$byteIdx]);
        $current = ($raw >>> $offset) & 0x0F;

        if ($current + $count > 15) {
            // 溢出，转到哈希表（实际场景几百万个ID的count很难超15）
            $this->overflow[$id] = ($this->overflow[$id] ?? 0) + $count;
            return;
        }
        $newVal = ($current + $count) & 0x0F;
        // 先清零4位，再写入
        $mask = 0x0F << $offset;
        $raw = ($raw & ~$mask) | ($newVal << $offset);
        $this->bits[$byteIdx] = chr($raw);
    }

    public function getCount(int $id): int
    {
        $bitPos = $id * $this->bitsPerItem;
        $byteIdx = intdiv($bitPos, 8);
        $offset = $bitPos % 8;
        $raw = ord($this->bits[$byteIdx]);
        return ($raw >>> $offset) & 0x0F;
    }

    public function topK(int $k): array
    {
        $sorted = [];
        for ($i = 0; $i < $this->range; $i++) {
            $c = $this->getCount($i) + ($this->overflow[$i] ?? 0);
            if ($c > 0) {
                $sorted[] = ['id' => $i, 'count' => $c];
            }
        }
        // 只在最后对有效项排序，而不是扫全量
        usort($sorted, fn($a, $b) => $b['count'] <=> $a['count']);
        return array_slice($sorted, 0, $k);
    }
}

// 使用示例
$bm = new BitMapTopK(5_000_000); // 500万ID范围，内存约2.4MB
foreach ($clickStream as $userId) {
    $bm->add($userId);
}
$top100 = $bm->topK(100);
?>

三种方案对比

压测数据

测试环境：Linux 5.15，PHP 8.3.3，8核16G，数据量1000万条，K=100，每条记录是一个数组{'id': int, 'hot_value': int}。用generateData()预生成内存数组，三种方案各自独立进程执行，内存峰值用memory_get_peak_usage(true)采集。

结论：内存足够时快选最快，比堆快33%。内存受限时堆是唯一选择。BitMap适合需要先做频次统计的场景，不适合直接做TopK。

避坑指南

坑1：PHP的&usort&在K值较大时性能崩盘

当K很大（比如K=10000），堆的有序性维护成本随K上升。实测K=10000时，堆方案耗时为2.1秒，快选只需要800ms。如果K超过N/10，直接全排序可能反而更快。建议K > N/10时改用usort全排+取前K。

坑2：快选的最坏情况——有序数组

快选如果不做随机化，对已经有序的数组每次都选到最差的pivot，退化成O(n²)。100万数据实测会从80ms直接变成疯狂转圈。必须用random_int选pivot，不能偷懒固定取中间元素。

坑3：BitMap计数溢出

上例用4bit做计数器，最大值只有15。如果你的数据分布不均匀，某个键频繁出现，计数会溢出。我实际踩过：日志里某个用户ID一天点击了200次，溢出后count直接错乱。解决：超大计数放哈希表兜底，或用可变长编码。

坑4：堆结果必须要排序

小顶堆内部存储是乱序的，不是有序输出。很多人直接取heap[0]以为是最小值，这是对的；但取全部K个时是乱序。如果需要按值从大到小返回，必须额外排序。这个排序开销在K=100时几乎为0，但K=10000时约5ms，别忽略。

坑5：千万级别数组的&array_slice&会吃满内存

快选会原地修改数组（传引用），但array_slice返回的是一个新数组。原数组占1.9GB，切片又复制了一份，峰值直接翻倍到3.8GB。PHP不会自动释放原数组内存，你得手动unset($items)。更优做法：直接在原数组上截断（$items = array_slice($items, 0, $k)），让旧的大数组有机会被GC。

坑6：哈希碰撞导致BitMap计数错误

如果把URL哈希成整数再存BitMap，哈希碰撞会导致两个不同的URL共用一个计数位。实测100万个URL用32位哈希，碰撞概率约0.1%，看起来不高。但TopK场景要求精确，碰撞会让排名失真。要么用64位哈希，要么换其他方案。

总结

线上故障的修复方式是：热榜接口改为小顶堆方案，数据从MySQL分批读取，单批5000条，边读边入堆。接口P99从5.2秒降到468ms，内存从1.8GB降到18MB。后续如果要做衍生榜单（按用户分组的热榜），统计阶段就会切到BitMap。

选择建议：数据量超出内存用堆；数据能装进内存且追求最快用快选；需要先统计频次且键为整数用BitMap。没有万能的方案，只有最合适的。