前言
最近工期紧、任务多，没有时间更新博客，就水一期吧。虽然是水，也不能太水，刚好最近工作中遇到一个 sorter 多条件排序的问题，花费了半天时间来定位解决，就说说它吧。
背景
公司产品是一个跨端的数据传输 sdk，当下载资源时，会先从服务器拉取一批 peer，每个 peer 是包含要下载资源分片的 p2p 端，每个节点有一个序号，sdk 根据这个值从小到大排序后依次选取 peer 进行连接，序号是由服务器决定的，主要根据地域、连通率、带宽等决定的，可以简化为下面的 demo：
代码语言：javascript复制#include <stdio.h>
#include <vector>
#include <string>
#include <algorithm>
struct PeerInfo
{
std::string peerid;
std::string ip;
short port;
int begin;
int end;
int seq;
void print(void);
};
void PeerInfo::print(void)
{
printf ("peer %s: %d, %s:%d, %d-%dn",
peerid.c_str(), seq,
ip.c_str(), port, begin, end);
}
struct PeerInfoSorter
{
bool operator() (PeerInfo const& lhs, PeerInfo const& rhs) {
return lhs.seq < rhs.seq;
}
};
int main (void)
{
std::vector<PeerInfo> vpi;
// init this vector by server response
// ...
std::sort (vpi.begin(), vpi.end(), PeerInfoSorter());
for (auto it = vpi.begin(); it != vpi.end(); it)
{
it->print();
}
}在下载过程中会向服务器请求多次，每批返回的 peer 都放在一个容器中排序，但是序号是基于批的，多个批次之间的 peer 如果仅按照 seq 排序的话，就会将前面批次旧的 peer 排在前面，从而导致一些新 peer 没有机会被用到，发生饥饿现象。
问题的产生
了解到这个情况后，采取了按批和序号同时排序的方案，即为 peer 增加一个 batch 字段用于记录批号，在排序时只有 batch 相同时才去比较 seq，代码类似下面这样：
代码语言：javascript复制struct PeerInfo
{
std::string peerid;
std::string ip;
short port;
int begin;
int end;
int seq;
int batch;
void print(void);
};
void PeerInfo::print(void)
{
printf ("peer %s: %d-%d, %s:%d, %d-%dn",
peerid.c_str(), batch, seq,
ip.c_str(), port, begin, end);
}
struct PeerInfoSorter
{
bool operator() (PeerInfo const& lhs, PeerInfo const& rhs) {
return lhs.batch < rhs.batch || lhs.seq < rhs.seq;
}
};当时的想法比较直接，先比较 batch，如果 batch 已经小了就直接短路返回结果；再比较 seq。看着逻辑没什么问题，但是运行起来后发现还是有旧批次的 peer 排在前面，以上面那个 demo 为例，制造一些测试数据：
代码语言：javascript复制 // ...
vpi.push_back ({"1a2b", "10.0.1.29", 8001, 0, 16384, 1, 1});
vpi.push_back ({"3c4d", "10.0.1.30", 8002, 16384, 32768, 2, 1});
vpi.push_back ({"5e6f", "10.0.1.31", 8003, 8192, 24576, 1, 2});
vpi.push_back ({"7a8b", "10.0.5.22", 8081, 32768, 49152, 2, 2});
vpi.push_back ({"9c0d", "10.0.5.23", 8082, 49152, 65536, 1, 3});
vpi.push_back ({"afec", "10.0.5.24", 8083, 0, 65536, 2, 3}); 其中最后两个字段分别是 seq 与 batch 的初始值。执行后输出如下：
代码语言：javascript复制$ ./peer
peer 1a2b: 1-1, 10.0.1.29:8001, 0-16384
peer 5e6f: 2-1, 10.0.1.31:8003, 8192-24576
peer 9c0d: 3-1, 10.0.5.23:8082, 49152-65536
peer 3c4d: 1-2, 10.0.1.30:8002, 16384-32768
peer 7a8b: 2-2, 10.0.5.22:8081, 32768-49152
peer afec: 3-2, 10.0.5.24:8083, 0-65536peer 1-2 排在 2-1 后面明显不是我们想要的，那是哪里出了问题呢？
问题的解决
看起来是 sorter 写的有问题，重新考察一下它的逻辑：
- lhs.batch < rhs.batch 时，直接返回 true 并短路后面的条件，这是正确的
- lhs.batch = rhs.batch 时，结果退化为 seq 之间的比较，也是正确的
- lhs.batch > rhs.batch 时，结果退化为 seq 之间的比较，问题出在这里，此时应当直接返回 false
因此 sorter 正确的写法应该是这样：
代码语言：javascript复制struct PeerInfoSorter
{
bool operator() (PeerInfo const& lhs, PeerInfo const& rhs) {
if (lhs.batch != rhs.batch)
return lhs.batch < rhs.batch;
return lhs.seq < rhs.seq;
}
};前面的条件只要不相等就直接短路了，更正后输出正常了：
代码语言：javascript复制$ ./peer
peer 1a2b: 1-1, 10.0.1.29:8001, 0-16384
peer 3c4d: 1-2, 10.0.1.30:8002, 16384-32768
peer 5e6f: 2-1, 10.0.1.31:8003, 8192-24576
peer 7a8b: 2-2, 10.0.5.22:8081, 32768-49152
peer 9c0d: 3-1, 10.0.5.23:8082, 49152-65536
peer afec: 3-2, 10.0.5.24:8083, 0-65536现在回过头来看前面错误的代码，看上去它至少保证了 batch 的顺序，那么这是真的吗？稍微调整一下容器数据的初始顺序：
代码语言：javascript复制 vpi.push_back ({"9c0d", "10.0.5.23", 8082, 49152, 65536, 1, 3});
vpi.push_back ({"afec", "10.0.5.24", 8083, 0, 65536, 2, 3});
vpi.push_back ({"1a2b", "10.0.1.29", 8001, 0, 16384, 1, 1});
vpi.push_back ({"3c4d", "10.0.1.30", 8002, 16384, 32768, 2, 1});
vpi.push_back ({"5e6f", "10.0.1.31", 8003, 8192, 24576, 1, 2});
vpi.push_back ({"7a8b", "10.0.5.22", 8081, 32768, 49152, 2, 2}); 得到的输出打破了这一"幻觉"：
代码语言：javascript复制$ ./peer
peer 1a2b: 1-1, 10.0.1.29:8001, 0-16384
peer 5e6f: 2-1, 10.0.1.31:8003, 8192-24576
peer 3c4d: 1-2, 10.0.1.30:8002, 16384-32768
peer 7a8b: 2-2, 10.0.5.22:8081, 32768-49152
peer 9c0d: 3-1, 10.0.5.23:8082, 49152-65536
peer afec: 3-2, 10.0.5.24:8083, 0-65536很显然 1-2 排在了 2-1 之后。再分析之前的逻辑，当 lhs.batch > rhs.batch 时，结果是由 seq 决定的，所以完全可能出现上面的场景。而到底对哪些元素进行对比完全是由输入序列和对比算法决定的，怎么构造反例还真不好设计，只有当数据量大时才会表现的比较明显。
总结
再回头来看逻辑短路操作，如果写成下面形式：
代码语言：javascript复制struct PeerInfoSorter
{
bool operator() (PeerInfo const& lhs, PeerInfo const& rhs) {
return lhs.batch < rhs.batch || lhs.seq < rhs.seq;
}
};则当 lhs.batch > rhs.batch 时不会短路，从而引发错误。如果写成下面的形式：
代码语言：javascript复制struct PeerInfoSorter
{
bool operator() (PeerInfo const& lhs, PeerInfo const& rhs) {
return lhs.batch < rhs.batch && lhs.seq < rhs.seq;
}
};则当 lhs.batch < rhs.batch 时不会短路，也引发错误。
总结一下就是，我们需要返回 batch 或 seq 的 operator < 结果来作为比较结果，但是这个条件对于 || 和 && 在一半的情况下是不会短路的，具体而言就是：
- 使用 || 逻辑短路时，lhs.batch < rhs.batch 得到满足，lhs.batch > rhs.batch 没有得到满足
- 使用 && 逻辑短路时， lhs.batch > rhs.batch 得到满足，lhs.batch < rhs.batch 没有得到满足
那它们能得到全部满足吗？当短路发生时，lhs.batch < rhs.batch 这一条件有 true 和 false 两种情况需要返回，而短路逻辑 || 和 && 只能允许其中一种通过，所以答案是不能。除非可以预判只有其中一种条件发生 (只返回 true 或 false)，然后有针对性的写 || 或 && 语句，不过那样的话这个字段也就没有参与比较的意义了。
最终结论就是，不要使用短路逻辑处理 sorter 多条件之间的判断。
后记
回到前面项目中，再给它加一点需求：服务器返回不同批次的 peer 可能重复，通过 peerid 可以去重，但当新 batch 中的 peer 在之前出现并连接过时，我们希望它的优先级变低，以保证未连接过的 peer 不发生饥饿现象。对于这样的需求，怎么改呢？想必大家心中已经有了答案，现在和正确答案对比一下吧：
代码语言：javascript复制struct PeerInfoSorter
{
bool operator() (PeerInfo const& lhs, PeerInfo const& rhs) {
if (lhs.connect_cnt != rhs.connect_cnt)
return lhs.connect_cnt < rhs.connect_cnt;
if (lhs.batch != rhs.batch)
return lhs.batch < rhs.batch;
return lhs.seq < rhs.seq;
}
};其中 connect_cnt 新字段表示连接的次数，每连接一次增加一个计数，将这个条件放在最前面以便保证连接次数最少的 peer 排在最前面，只有当连接次数相同时 (新 peer 的 connect_cnt == 0)，才对比 batch 与 seq。
举这个例子的目的是为了说明，sorter 多条件对比时，只要按重要性一个个排就可以了，你学会了吗？
