滴滴打车派单系统思考数据库设计与实现 - 每月投入6140元, 1天最多可盈利117亿 -_-!

14 minute read

背景

打车类应用，如果完全按调度系统来派单，而非抢单的话，调度系统要非常的健硕。

比如滴滴打车，如何处理供给双方的需求，并高效的完成派单呢？

随着业务的需求增多，调度规则也会增加，比如拼车，预约，等。

下面是一个简单的派单系统的思考，如何使用PostgreSQL与空间数据库插件PostGIS来实现一个简单的距离优先派单、拼车撮合。

采用skip lock或advisory lock来避免锁冲突。应对高峰期问题。

《HTAP数据库 PostgreSQL 场景与性能测试之 30 - (OLTP) 秒杀 - 高并发单点更新》

《聊一聊双十一背后的技术 - 不一样的秒杀技术, 裸秒》

《PostgreSQL 秒杀场景优化》

PostgreSQL 设计

1、空间数据库插件PostGIS

在PostgreSQL中创建空间数据库

postgres=# create extension postgis;  
CREATE EXTENSION  

1、滴滴车辆位置表

记录车辆的实时位置，是否被下单，有无剩余座位（不拼单的订单直接把剩余座位设为0）

create table car (  
  id int primary key,                          -- 车辆ID，主键  
  pos geometry,                                -- 实时位置, 使用PostGIS，geometry类型  
  sites int2 not null default 4,               -- 总座位数  
  rest_sites int2,                             -- 剩余座位数 (因为有拼车业务)  
  mod_time timestamp,                          -- 位置修改时间  
  order_pos geometry[],                        -- 当前订单对应用户打车的目的地位置  
  check (rest_sites <= sites and rest_sites>=0 and sites>0)  
);  

2、用户表

create table users (  
  id int8 primary key,  -- ID  
  otherinfo jsonb       -- 其他信息，请允许我偷懒一下使用JSON，实际上我这里派单只需要记录ID  
);  

3、订单表

记录每一笔订单，以及订单的状态

create table orders (  
  id serial8 primary key,   -- 订单号  
  carid int,             -- 车辆ID  
  uid int8,              -- 用户ID  
  crt_time timestamp,    -- 订单创建时间  
  pos1 geometry,         -- 上车位置  
  pos2 geometry,         -- 目的地  
  sites int2,            -- 乘坐几人  
  status int2            -- 订单状态(进行中 2, 取消 1, 结束 0)  
);  

4、车辆位置实时更新

每N秒(比如5秒)，上报并更新位置。

《HTAP数据库 PostgreSQL 场景与性能测试之 29 - (OLTP) 空间应用 - 高并发空间位置更新（含空间索引）》

假设这个城市一共有1000万量车

假定车辆的活动范围经纬度(110~120, 25~30)  
  
vi test.sql  
  
\set id random(1,10000000)  
insert into car(id, pos, mod_time) values (  
  :id,   
  ST_SetSRID(ST_Point(round((random()*(120-110)+110)::numeric,6), round((random()*(30-25)+25)::numeric,6)), 4326),  
  now()  
) on conflict (id) do update set pos=ST_SetSRID(ST_Point(ST_X(excluded.pos)+random()-0.5, ST_Y(excluded.pos)+random()-0.5), 4326), mod_time=excluded.mod_time  
where car.sites <> car.rest_sites or car.rest_sites is null;     -- 不能被叫的车辆不更新位置(例如他的座位满了)  

(含空间索引)压测如下：

pgbench -M prepared -n -r -P 1 -f ./test.sql -c 56 -j 56 -T 120  
  
  
progress: 4.0 s, 200614.4 tps, lat 0.279 ms stddev 0.357  
progress: 5.0 s, 202598.0 tps, lat 0.276 ms stddev 0.336  
progress: 6.0 s, 196562.4 tps, lat 0.285 ms stddev 0.785  
progress: 7.0 s, 200305.4 tps, lat 0.280 ms stddev 0.534  
progress: 8.0 s, 207505.2 tps, lat 0.270 ms stddev 0.270  
progress: 9.0 s, 204128.0 tps, lat 0.274 ms stddev 0.347  

5、叫车，派单

1、用户上报位置

2、查询附近可用车辆(按gist索引顺序返回，同时过滤锁、SITES、距离等条件)

3、采用空间部分索引

拼车索引

create index idx_car_pos_1 on car using gist(pos) where rest_sites>0 or rest_sites is null;  

不拼车索引

create index idx_car_pos_2 on car using gist(pos) where rest_sites=sites or rest_sites is null;  

4、判断是否与之拼车的函数（输入参数为目的地，以及车上已有乘客目的地）

create or replace function f_isbulk(  
  i_pos geometry,      -- 目的地  
  i_poss geometry[]    -- 该车已有乘客目的地  
) returns boolean as $$  
declare  
  vspheroid spheroid := 'SPHEROID["WGS84",6378137,298.257223563]' ;  -- WGS84椭球体参数定义  
begin  
  -- 先使用最简单的算法，例如任意已有乘客目的地与当前请求目的地距离在2000米以内则返回TRUE，允许拼车  
  -- 测试时，建议把允许的拼车目的地距离调大一点，否则可能很难找到合适的车辆  
  -- perform 1 from unnest(i_poss) t(pos) where ST_DistanceSpheroid(i_pos, pos, vspheroid) <= 2000 limit 1;   
  perform 1 from unnest(i_poss) t(pos) where ST_DistanceSpheroid(i_pos, pos, vspheroid) <= 200000000 limit 1;   
  if found then   
    return true;   
  else   
    return false;  -- 距离超过2000米，不与之拼车  
  end if;   
end;   
$$ language plpgsql strict;   
  
测试时，建议把允许的拼车目的地距离调大一点，否则可能很难找到合适的车辆  

5、选择拼车的用户，使用以下函数生成订单，返回订单号，车辆ID，等

create or replace function getcar_isbulk(  
  i_uid int8,        -- 用户ID  
  i_pos1 geometry,   -- 上车位置  
  i_pos2 geometry,   -- 目的地  
  i_sites int2       -- 乘坐几人  
) returns int8 as $$  -- 返回订单号  
declare  
  v_car_ctid tid;  -- car表被请求到的CAR的记录行号  
  v_carid int;     -- carid  
  v_orderid int8;  -- 订单号  
  v_pos geometry;  -- 锁定的车辆位置  
  vspheroid spheroid := 'SPHEROID["WGS84",6378137,298.257223563]' ;  -- WGS84椭球体参数定义  
begin  
  set local enable_seqscan=off;  
  set local enable_bitmapscan=off;  
    
  -- 根据条件锁定车辆ID，同时使用了try advisory lock避免行锁冲突  
  -- 与秒杀方法类似，大幅度提高吞吐，PG中锁定单条记录的吞吐可以达到将近 30万tps  
  select ctid,pos into v_car_ctid,v_pos from car where   
    (rest_sites > 0                                   -- 剩余座位数大于0    
    and rest_sites >= i_sites or rest_sites is null)  -- 剩余座位数大于等于请求座位数    
    and (order_pos is null or f_isbulk(i_pos2, order_pos))    -- 目的地满足拼车要求  
    and pg_try_advisory_xact_lock(id)                         -- adlock，提高秒杀吞吐  
    order by i_pos1 <-> pos for update limit 1;               -- 根据距离排序，以上条件满足，锁定1条即可  
    
  -- 如果车辆位置超出一定公里数(比如5公里)，直接返回，不生成订单  
  -- 测试时，建议把公里数调大，便于找到车辆  
  -- if not found or ST_DistanceSpheroid(i_pos1, v_pos, vspheroid) > 5000 then  
  if not found or ST_DistanceSpheroid(i_pos1, v_pos, vspheroid) > 500000000 then  
    -- raise notice 'no car near your pos, the car leave you % meters', ST_DistanceSpheroid(i_pos1, v_pos, vspheroid);  
    return -1;  
  end if;  
    
  -- 更新车辆状态  
  update car set   
    rest_sites=coalesce(rest_sites-i_sites, sites-i_sites),         -- 减少剩余座位  
    order_pos=coalesce(order_pos||i_pos2, array[i_pos2])            -- 将目的地追加到车辆所有目的地中  
    where ctid=v_car_ctid    
    and coalesce(rest_sites-i_sites, sites-i_sites) >= 0  
    returning id into v_carid;         -- 返回车辆ID  
  
  if found then  
  -- 生成订单  
  insert into orders (carid, uid, crt_time, pos1, pos2, sites, status)   
    values(v_carid, i_uid, now(), i_pos1, i_pos2, i_sites, 2)   -- 状态为进行中  
    returning id into v_orderid;  -- 返回订单号  
  else  
    return -2;  
  end if;  
    
  return v_orderid;  
  
end;  
$$ language plpgsql strict;  

2018-04-16优化

create index idx_car_pos_pc_1 on car using gist(pos) where rest_sites=1;  
create index idx_car_pos_pc_2 on car using gist(pos) where rest_sites=2;  
create index idx_car_pos_pc_3 on car using gist(pos) where rest_sites=3;  
create index idx_car_pos_pc_4 on car using gist(pos) where rest_sites=4;  
create index idx_car_pos_pc_5 on car using gist(pos) where rest_sites>4;  
create index idx_car_pos_pc_6 on car using gist(pos) where rest_sites is null;  


CREATE OR REPLACE FUNCTION public.f_isbulk(i_pos geometry, i_poss geometry[])
 RETURNS int
 LANGUAGE plpgsql
 STRICT
AS $function$  
declare  
  vspheroid spheroid := 'SPHEROID["WGS84",6378137,298.257223563]' ;  -- WGS84椭球体参数定义  
begin  
  -- 先使用最简单的算法，例如任意已有乘客目的地与当前请求目的地距离在2000米以内则返回TRUE，允许拼车  
  -- 测试时，建议把允许的拼车目的地距离调大一点，否则可能很难找到合适的车辆  
  perform 1 from unnest(i_poss) t(pos) where ST_DistanceSpheroid(i_pos, pos, vspheroid) <= 2000000000000 limit 1;   
  if found then   
    return 1;   
  else   
    return 0;    -- 距离超过2000米，不与之拼车  
  end if;   
end;   
$function$;

create or replace function getcar_isbulk(  
  i_uid int8,        -- 用户ID  
  i_pos1 geometry,   -- 上车位置  
  i_pos2 geometry,   -- 目的地  
  i_sites int2       -- 乘坐几人  
) returns int8 as $$  -- 返回订单号  
declare  
  v_carid int;     -- carid  
  v_orderid int8;  -- 订单号  
  v_pos geometry;  -- 锁定的车辆位置  
  vspheroid spheroid := 'SPHEROID["WGS84",6378137,298.257223563]' ;  -- WGS84椭球体参数定义  
  v_sites_step int;         -- 步调
  -- 如果车辆位置在给定范围内(比如5公里)，则退出循环，否则继续. （测试时为了更容易找到车辆，需要把范围设大一些）
  -- v_dist float8 := 5000;  -- 车辆离你的距离 , 如果5公里开外，那么说明附近没有车
  v_dist float8 := 500000000;    
begin  
  set local enable_seqscan=off;  
  set local enable_bitmapscan=off;  
  
  case 
  when i_sites <= 4 then 
    for v_sites_step in i_sites..4 loop
      -- 根据条件锁定车辆ID，同时使用了try advisory lock避免行锁冲突  
      -- 与秒杀方法类似，大幅度提高吞吐，PG中锁定单条记录的吞吐可以达到将近 30万tps  
      select id,pos into v_carid,v_pos from car where   
        rest_sites = v_sites_step                                 -- 剩余座位数等于请求座位数 (或大于, loop超过i_sites时)
        and coalesce(f_isbulk(i_pos2, order_pos),1)=1                           -- 目的地满足拼车条件
        and pg_try_advisory_xact_lock(id)                         -- adlock，提高秒杀吞吐  
        and ST_DistanceSpheroid(i_pos1, pos, vspheroid) < v_dist   -- 车辆位置在给定范围内(比如5公里) . （测试时为了更容易找到车辆，需要把范围设大一些）
        order by i_pos1 <-> pos for update limit 1;               -- 根据距离排序，以上条件满足，锁定1条即可  

      -- 如果有符合条件的车辆，则退出 case
      if found then  
        exit; 
      end if;  
    end loop;

    -- 如果有符合条件的车辆，则退出 case
    if not found then  

      -- 4个座位内都没有找到符合条件的车辆, 找剩余座位大于4个的 
      select id,pos into v_carid,v_pos from car where   
        rest_sites > 4                                            -- 剩余座位数等于请求座位数 (或大于, loop超过i_sites时)
        and coalesce(f_isbulk(i_pos2, order_pos),1)=1                           -- 目的地满足拼车条件        
	and ST_DistanceSpheroid(i_pos1, pos, vspheroid) < v_dist   -- 车辆位置在给定范围内(比如5公里) . （测试时为了更容易找到车辆，需要把范围设大一些）
        and pg_try_advisory_xact_lock(id)                         -- adlock，提高秒杀吞吐  
        order by i_pos1 <-> pos for update limit 1;               -- 根据距离排序，以上条件满足，锁定1条即可  

      -- 如果有符合条件的车辆，则退出 case 
      if not found then  

        -- 大于4个座位的车辆没有，则找刚注册的车辆，即rest_sites is null
        select id,pos into v_carid,v_pos from car where   
          rest_sites is null                                        -- 剩余座位数等于请求座位数 (或大于, loop超过i_sites时)
	  and ST_DistanceSpheroid(i_pos1, pos, vspheroid) < v_dist   -- 车辆位置在给定范围内(比如5公里) . （测试时为了更容易找到车辆，需要把范围设大一些）
          and pg_try_advisory_xact_lock(id)                         -- adlock，提高秒杀吞吐  
          order by i_pos1 <-> pos for update limit 1;               -- 根据距离排序，以上条件满足，锁定1条即可  
      end if;
    end if;

  -- 请求座位数大于4
  else

    -- 4个座位内都没有找到符合条件的车辆, 找剩余座位大于4个的 
    select id,pos into v_carid,v_pos from car where   
      rest_sites > 4                                            -- 剩余座位数等于请求座位数 (或大于, loop超过i_sites时)
      and coalesce(f_isbulk(i_pos2, order_pos),1)=1                          -- 目的地满足拼车条件      
      and ST_DistanceSpheroid(i_pos1, pos, vspheroid) < v_dist  -- 车辆位置在给定范围内(比如5公里) . （测试时为了更容易找到车辆，需要把范围设大一些）
      and pg_try_advisory_xact_lock(id)                         -- adlock，提高秒杀吞吐  
      order by i_pos1 <-> pos for update limit 1;               -- 根据距离排序，以上条件满足，锁定1条即可  

    -- 如果有符合条件的车辆，则退出 case 
    if not found then  

      -- 大于4个座位的车辆没有，则找刚注册的车辆，即rest_sites is null
      select id,pos into v_carid,v_pos from car where   
        rest_sites is null                                        -- 剩余座位数等于请求座位数 (或大于, loop超过i_sites时)
        and ST_DistanceSpheroid(i_pos1, pos, vspheroid) < v_dist   -- 车辆位置在给定范围内(比如5公里) . （测试时为了更容易找到车辆，需要把范围设大一些）
        and pg_try_advisory_xact_lock(id)                         -- adlock，提高秒杀吞吐  
        order by i_pos1 <-> pos for update limit 1;               -- 根据距离排序，以上条件满足，锁定1条即可  
    end if;
  end case;

  if not found then
    -- raise notice 'no car near your pos, the car leave you % meters', ST_DistanceSpheroid(i_pos1, v_pos, vspheroid);  
    return -1;
  end if;

  -- 更新车辆状态  
  update car set   
    rest_sites=coalesce(rest_sites-i_sites, sites-i_sites),         -- 减少剩余座位  
    order_pos=coalesce(order_pos||i_pos2, array[i_pos2])            -- 将目的地追加到车辆所有目的地中  
    where id=v_carid    
    and coalesce(rest_sites-i_sites, sites-i_sites) >= 0  
    returning id into v_carid;         -- 返回车辆ID  
  
  if found then  
  -- 生成订单  
  insert into orders (carid, uid, crt_time, pos1, pos2, sites, status)   
    values(v_carid, i_uid, now(), i_pos1, i_pos2, i_sites, 2)   -- 状态为进行中  
    returning id into v_orderid;  -- 返回订单号  
  else  
    return -2;  
  end if;  
    
  return v_orderid;  
  
end;  
$$ language plpgsql strict; 

5、选择不拼车的用户，使用以下函数生成订单，返回订单号，车辆ID，等

create or replace function getcar(  
  i_uid int8,        -- 用户ID  
  i_pos1 geometry,   -- 上车位置  
  i_pos2 geometry    -- 目的地  
) returns int8 as $$  -- 返回订单号  
declare  
  v_car_ctid tid;  -- car表被请求到的CAR的记录行号  
  v_carid int;     -- carid  
  v_orderid int8;  -- 订单号  
  v_sites int2;    -- 座位数  
  v_pos geometry;  -- 锁定的车辆位置  
  vspheroid spheroid := 'SPHEROID["WGS84",6378137,298.257223563]' ;  -- WGS84椭球体参数定义  
begin  
  set local enable_seqscan=off;  
  set local enable_bitmapscan=off;  
    
  -- 根据条件锁定车辆ID，同时使用了try advisory lock避免行锁冲突  
  -- 与秒杀方法类似，大幅度提高吞吐，PG中锁定单条记录的吞吐可以达到将近 30万tps  
  select ctid,pos into v_car_ctid,v_pos from car where   
    (rest_sites=sites or rest_sites is null)                  -- 剩余座位数等于能提供的座位数，说明没有订单在手，满足不拼车需求  
    and pg_try_advisory_xact_lock(id)                         -- adlock，提高秒杀吞吐  
    order by i_pos1 <-> pos for update limit 1;               -- 根据距离排序，以上条件满足，锁定1条即可  
    
  -- 如果车辆位置超出一定公里数(比如5公里)，直接返回，不生成订单  
  -- 测试时，建议把公里数调大，便于找到车辆  
  -- if not found or ST_DistanceSpheroid(i_pos1, v_pos, vspheroid) > 5000 then  
  if not found or ST_DistanceSpheroid(i_pos1, v_pos, vspheroid) > 500000000 then  
    -- raise notice 'no car near your pos, the car leave you % meters', ST_DistanceSpheroid(i_pos1, v_pos, vspheroid);  
    return -1;  
  end if;  
  
  -- 更新车辆状态  
  update car set   
    rest_sites=0                      -- 剩余座位减少为0  
    where ctid=v_car_ctid                
    returning id,sites into v_carid,v_sites;        -- 返回车辆ID  
    
  -- 生成订单  
  insert into orders (carid, uid, crt_time, pos1, pos2, sites, status)   
    values(v_carid, i_uid, now(), i_pos1, i_pos2, v_sites, 2)    -- 状态为进行中  
    returning id into v_orderid;                 -- 返回订单号  
    
  return v_orderid;  
end;  
$$ language plpgsql strict;  

6、结束订单，取消订单

1、更新订单状态，更新车辆剩余座位，删除拼车已到达的目的地

create or replace function change_order(  
  i_id int8,     -- 订单ID  
  i_status int2  -- 状态, 进行中2，取消1，结束0   
) returns int as $$  
declare  
  i_carid int;  
  i_pos geometry;  
  i_sites int2;  
begin  
  set local enable_seqscan=off;  
  set local enable_bitmapscan=off;    
  update orders set status=i_status where id=i_id and status<>0 returning carid, pos2, sites into i_carid, i_pos, i_sites;  
  
  if found then  
    update car set rest_sites=rest_sites+i_sites, order_pos=array_remove(order_pos, i_pos) where id=i_carid and pg_try_advisory_xact_lock(id);  
      
    -- 测试时加上这段，因为不存在锁冲突  
    if not found then  
      raise EXCEPTION '';  
    end if;  
  
    return 1;  
  end if;  
    
  raise EXCEPTION '';  
  exception when others then  
    return -1;  
end;  
$$ language plpgsql strict;  

7、压测

创建一个函数，生成打车时，用户上车的随机位置，用于压测

create or replace function gen_pos() returns geometry as $$  
  select ST_SetSRID(ST_Point(round((random()*(120-110)+110)::numeric,6), round((random()*(30-25)+25)::numeric,6)), 4326);  
$$ language sql strict;  

创建一个函数，获取未完结的订单号，用于压测

create or replace function gen_orderid() returns int8 as $$  
declare  
  res int8;  
  n int := random()*56;
begin  
  set local enable_seqscan=off;  
  set local enable_bitmapscan=off;  
  -- 随机采样得到订单ID，避免并发执行时大家得到的是同一个ID
  -- select id into res from orders TABLESAMPLE SYSTEM(0.1) where status = 2 limit 1;  
  -- 或者
  select id into res from orders where status = 2 offset n limit 1;  
  return res;  
end;  
$$ language plpgsql strict volatile;  

create index idx_orders_1 on orders (id) where status=2;

压测，假定有20亿用户

1、拼车打车

vi test1.sql  
  
\set uid random(1,2000000000)  
select getcar_isbulk(:uid, gen_pos(), gen_pos(), 1::int2);  

2、不拼车打车

vi test2.sql  
  
\set uid random(1,2000000000)  
select getcar(:uid, gen_pos(), gen_pos());  

3、结束订单

vi test3.sql  
  
select change_order(odid, 0::int2) from gen_orderid() t(odid) where pg_try_advisory_xact_lock(odid);  

4、新增车辆、更新车辆位置

vi test4.sql  
  
\set id random(1,10000000)  
insert into car(id, pos, mod_time) values (  
  :id,   
  ST_SetSRID(ST_Point(round((random()*(120-110)+110)::numeric,6), round((random()*(30-25)+25)::numeric,6)), 4326),  
  now()  
) on conflict (id) do update set pos=ST_SetSRID(ST_Point(ST_X(excluded.pos)+random()-0.5, ST_Y(excluded.pos)+random()-0.5), 4326), mod_time=excluded.mod_time  
where car.sites<>car.rest_sites or car.rest_sites is null;   -- 不能被叫的车辆不更新位置(例如他的座位满了)  

单一场景压测性能

1、新增车辆、更新车辆位置。约每秒16.7万行。

pgbench -M prepared -n -r -P 1 -f ./test4.sql -c 56 -j 56 -T 120

number of transactions actually processed: 20120910  
latency average = 0.334 ms  
latency stddev = 0.431 ms  
tps = 167648.839197 (including connections establishing)  
tps = 167663.075494 (excluding connections establishing)  

2、拼车打车。约每秒1.73万笔订单。

pgbench -M simple -n -r -P 1 -f ./test1.sql -c 13 -j 13 -T 120

tps = 17338.303267 (including connections establishing)
tps = 17339.077083 (excluding connections establishing)

3、不拼车打车。约每秒1.23万笔订单。

pgbench -M simple -n -r -P 1 -f ./test2.sql -c 13 -j 13 -T 120

tps = 26224.271953 (including connections establishing)
tps = 26225.359067 (excluding connections establishing)

4、结束订单。约每秒20万笔订单。

pgbench -M prepared -n -r -P 1 -f ./test3.sql -c 56 -j 56 -T 120

tps = 204695.541432 (including connections establishing)  
tps = 204713.293460 (excluding connections establishing)  

单一场景	TPS
更新位置	16.7 万
拼车	1.73 万
不拼车	2.6 万
结束订单	20 万

混合场景压测性能

pgbench -M prepared -n -r -P 3 -f ./test4.sql -c 16 -j 16 -T 120 > ./log1 2>&1 &  
  
pgbench -M simple -n -r -P 3 -f ./test1.sql -c 10 -j 10 -T 120 > ./log2 2>&1 &  
  
pgbench -M simple -n -r -P 3 -f ./test2.sql -c 10 -j 10 -T 120 > ./log3 2>&1 &  
  
pgbench -M prepared -n -r -P 3 -f ./test3.sql -c 16 -j 16 -T 120 > ./log4 2>&1 &

混合场景	TPS
更新位置	5.43 万
拼车	10647
不拼车	12045
结束订单	7.4 万

拼车和不拼车加起来22692。

一些压测后的数据

postgres=# select * from car where rest_sites between 1 and 2 limit 10;  
   id    |                        pos                         | sites | rest_sites |          mod_time          |      order_pos     
---------+----------------------------------------------------+-------+------------+----------------------------+----------------------------------  
 7317265 | 0101000020E6100000A489994A8FAB5D40CC44BFBDA9343D40 |     4 |          1 | 2018-04-14 22:58:03.407874 | {0101000020E6100000B6BFB33D7AA55B40D28A6F287C9A3940:0101000020E6100000B6BFB33D7AA55B40D28A6F287C9A3940:0101000020E6100000B6BFB33D7AA55B40D28A6F287C9A3940}  
 3111010 | 0101000020E6100000BB1DFDD578835B405280A6641A673C40 |     4 |          2 | 2018-04-14 23:12:53.34535  | {0101000020E6100000FEB7921D1B1E5C400CC9C9C4AD7E3B40:0101000020E6100000FEB7921D1B1E5C400CC9C9C4AD7E3B40}  
 7541005 | 0101000020E610000086554818387E5C40B728ADCD43D03D40 |     4 |          2 | 2018-04-14 23:11:29.206046 | {0101000020E61000000F9BC8CC05065D400B2AAA7EA5373A40:0101000020E61000000F9BC8CC05065D400B2AAA7EA5373A40}  
 8690828 | 0101000020E6100000000CAF61E2675C40D3DC0C1EA9D13940 |     4 |          1 | 2018-04-14 23:14:19.151509 | {}  
 6457811 | 0101000020E610000032F3008486A25D40EC2EF2553E843B40 |     4 |          2 | 2018-04-14 23:14:03.251394 | {0101000020E6100000AFD007CBD8555D402DAF5C6F9BD93D40:0101000020E6100000AFD007CBD8555D402DAF5C6F9BD93D40}  
 8742742 | 0101000020E6100000A9F5D11666C25C40BD187A2ED8943A40 |     4 |          1 | 2018-04-14 23:07:05.165694 | {0101000020E6100000B0E76B96CBC95B401CCD91955FAE3B40:0101000020E6100000B0E76B96CBC95B401CCD91955FAE3B40:0101000020E6100000B0E76B96CBC95B401CCD91955FAE3B40}  
 2817265 | 0101000020E610000039565329D09F5C403F56DACE20EF3C40 |     4 |          2 | 2018-04-14 23:11:18.579623 | {0101000020E61000005260014C19C55B407AC6BE64E3393D40:0101000020E61000005260014C19C55B407AC6BE64E3393D40}  
 7150506 | 0101000020E610000061A6600487595D405D7086861CBB3C40 |     4 |          2 | 2018-04-14 23:15:33.078539 | {0101000020E61000006743FE9941FD5D40F0FB372F4E483C40:0101000020E61000006743FE9941FD5D40F0FB372F4E483C40}  
 5583272 | 0101000020E6100000857D1D6801D25D40C58F015D4F2B3D40 |     4 |          2 | 2018-04-14 23:10:02.842235 | {0101000020E61000004B92E7FA3E9B5D40FCA6B05241193940:0101000020E61000004B92E7FA3E9B5D40FCA6B05241193940}  
 1367076 | 0101000020E610000072D31806729E5D403A3F7D95E3703D40 |     4 |          1 | 2018-04-14 23:14:02.91879  | {0101000020E61000009450FA42C88C5B4003B4AD669DCD3C40:0101000020E61000009450FA42C88C5B4003B4AD669DCD3C40:0101000020E61000009450FA42C88C5B4003B4AD669DCD3C40}  
(10 rows)  
  
postgres=# select * from orders limit 10;  
   id    |  carid  |    uid     |          crt_time          |                        pos1                        |                        pos2                        | sites | status   
---------+---------+------------+----------------------------+----------------------------------------------------+----------------------------------------------------+-------+--------  
 5350583 | 8219421 |  656330079 | 2018-04-14 22:58:50.85801  | 0101000020E6100000F1B913ECBFA55B40E86A2BF697213C40 | 0101000020E6100000A6F0A0D975CE5C40543A58FFE7BC3A40 |     4 |      0  
 5350594 |  387903 | 1251082211 | 2018-04-14 22:58:50.899007 | 0101000020E61000005E4A5D328E2F5D40BF9CD9AED0BB3B40 | 0101000020E610000073F4F8BD4D465D409DD66D50FB353C40 |     1 |      0  
 5350601 | 6032695 |  633527755 | 2018-04-14 22:58:50.901435 | 0101000020E6100000095053CBD6D45B401232906797BF3D40 | 0101000020E6100000FDFA213658D85C4010035DFB02023A40 |     1 |      0  
 5350645 | 9332236 | 1950115872 | 2018-04-14 22:58:50.906247 | 0101000020E610000021CD58349D835B400A9E42AED4F33C40 | 0101000020E6100000988922A46E9D5C40FD2E6CCD56663C40 |     4 |      0  
 5534249 | 1426569 |  982096157 | 2018-04-14 22:59:13.750311 | 0101000020E6100000115322895E535D404EB857E6ADEE3B40 | 0101000020E61000002EAEF199ECF65C40D845D1031FE33940 |     1 |      0  
 5350660 |  725764 | 1023537035 | 2018-04-14 22:58:50.907513 | 0101000020E61000004DDBBFB2D2575C404580D3BB78C73940 | 0101000020E6100000E544BB0A294E5C407CD2890453593B40 |     1 |      0  
 5534260 | 1777824 | 1176511003 | 2018-04-14 22:59:13.751194 | 0101000020E6100000FCE4284014305D404A0A2C80297B3B40 | 0101000020E610000079B29B19FD9E5B4015C8EC2C7A6B3940 |     1 |      0  
 5350677 | 9205198 | 1483861832 | 2018-04-14 22:58:50.9087   | 0101000020E61000002BD9B11188C35B4094FB1D8A024D3D40 | 0101000020E6100000F6EE8FF7AA2D5D402B685A6265203D40 |     4 |      0  
 5350704 | 4722183 | 1707309465 | 2018-04-14 22:58:50.910806 | 0101000020E610000010E7E104A66C5D4080F44D9A069D3A40 | 0101000020E61000007D2079E7509D5D4084D4EDEC2B3B3B40 |     1 |      0  
 5350729 | 1273928 | 1122725930 | 2018-04-14 22:58:50.91219  | 0101000020E6100000815CE2C803805D40AED85F764F0A3C40 | 0101000020E61000004E7B4ACE89595D404CA59F70763F3C40 |     1 |      0  
(10 rows)  
  
postgres=# select * from orders where status=2 limit 10;  
   id    |  carid  |    uid     |          crt_time          |                        pos1                        |                        pos2                        | sites | status   
---------+---------+------------+----------------------------+----------------------------------------------------+----------------------------------------------------+-------+--------  
 5432604 | 6569377 | 1058047186 | 2018-04-14 22:58:54.188969 | 0101000020E6100000CB13083BC5785C40DBA6785C54EF3C40 | 0101000020E6100000E0F42EDE8FE25B40FE43FAEDEB783940 |     1 |      2  
 5432645 |  850296 | 1314115523 | 2018-04-14 22:58:54.190902 | 0101000020E61000006878B306EF335C40A0E1CD1ABC173D40 | 0101000020E6100000139A249694D35C40F513CE6E2DE73A40 |     4 |      2  
 5432709 | 6569377 |  283077597 | 2018-04-14 22:58:54.194083 | 0101000020E6100000CB13083BC5785C40DBA6785C54EF3C40 | 0101000020E6100000E0F42EDE8FE25B40FE43FAEDEB783940 |     1 |      2  
 5432752 | 9088745 |   11001436 | 2018-04-14 22:58:54.195929 | 0101000020E61000006878B306EF335C40A0E1CD1ABC173D40 | 0101000020E6100000139A249694D35C40F513CE6E2DE73A40 |     4 |      2  
 5432817 | 1126957 |  577778747 | 2018-04-14 22:58:54.199477 | 0101000020E6100000CB13083BC5785C40DBA6785C54EF3C40 | 0101000020E6100000E0F42EDE8FE25B40FE43FAEDEB783940 |     1 |      2  
 5432857 |  480496 |  269272019 | 2018-04-14 22:58:54.201194 | 0101000020E61000006878B306EF335C40A0E1CD1ABC173D40 | 0101000020E6100000139A249694D35C40F513CE6E2DE73A40 |     4 |      2  
 5432917 | 1126957 | 1665973989 | 2018-04-14 22:58:54.203993 | 0101000020E6100000CB13083BC5785C40DBA6785C54EF3C40 | 0101000020E6100000E0F42EDE8FE25B40FE43FAEDEB783940 |     1 |      2  
 5432962 | 7515414 |   14898049 | 2018-04-14 22:58:54.206027 | 0101000020E61000006878B306EF335C40A0E1CD1ABC173D40 | 0101000020E6100000139A249694D35C40F513CE6E2DE73A40 |     4 |      2  
 5433012 | 7323377 | 1678751369 | 2018-04-14 22:58:54.208529 | 0101000020E61000006878B306EF335C40A0E1CD1ABC173D40 | 0101000020E6100000139A249694D35C40F513CE6E2DE73A40 |     4 |      2  
 5433048 | 1126957 |  281166362 | 2018-04-14 22:58:54.210329 | 0101000020E6100000CB13083BC5785C40DBA6785C54EF3C40 | 0101000020E6100000E0F42EDE8FE25B40FE43FAEDEB783940 |     1 |      2  
(10 rows)  

假设平均每笔订单30元，提成20%，以每秒结束订单为例，这一个PG库最多带来的盈利为每秒22692*6 = 13.6万RMB。一天117亿RMB。(当然不可能一直处于高潮状态，这个是夸张说法，不过一天1小时高潮还是要有的，5亿也足矣啊。)

而这样一台数据库的硬件成本，估计在2万元左右(如果要考虑搭建主备，容灾，备份，硬件成本可能不会超过30万。)。

即使采用阿里云RDS PostgreSQL，也仅需6140每月。（56核，480G内存，2TB 高效SSD云存储）(还包含了云盘本身的可靠性、数据库的高可用、备份、等等。关键是数据库内核级的支持与服务)。

优化

1、CODE瓶颈诊断

《PostgreSQL 源码性能诊断(perf profiling)指南》

2、UDF瓶颈诊断 (调优后更新了前面的测试数据)

把逻辑都写到了UDF里面，如何诊断性能呢？

load 'auto_explain';
set auto_explain.log_analyze =on;
set auto_explain.log_buffers =on;
set auto_explain.log_min_duration =0;
set auto_explain.log_nested_statements =on;
set auto_explain.log_time=on;
set auto_explain.log_verbose =on;
set client_min_messages ='log';

postgres=# select getcar_isbulk(1, st_setsrid(st_point(120,30),4326), st_setsrid(st_point(120,30.1),4326), 1::int2);
LOG:  duration: 0.047 ms  plan:
Query Text: SELECT 1 from unnest(i_poss) t(pos) where ST_DistanceSpheroid(i_pos, pos, vspheroid) <= 2000000000 limit 1
Limit  (cost=0.00..1.56 rows=1 width=4) (actual time=0.039..0.039 rows=1 loops=1)
  Output: 1
  ->  Function Scan on pg_catalog.unnest t  (cost=0.00..51.25 rows=33 width=4) (actual time=0.038..0.038 rows=1 loops=1)
        Output: 1
        Function Call: unnest('{0101000020E61000000000000000005E409A99999999193E40:0101000020E61000000000000000005E409A99999999193E40:0101000020E61000000000000000005E409A99999999193E40}'::geometry[])
        Filter: (st_distancespheroid('0101000020E61000000000000000005E409A99999999193E40'::geometry, t.pos, 'SPHEROID("WGS84",6378137,298.257223562997)'::spheroid) <= '2000000000'::double precision)


LOG:  duration: 0.485 ms  plan:
Query Text: select id,pos                    from car where   
    (rest_sites > 0                                   -- 剩余座位数大于0    
    and rest_sites >= i_sites or rest_sites is null)  -- 剩余座位数大于等于请求座位数    
    and (order_pos is null or f_isbulk(i_pos2, order_pos))    -- 目的地满足拼车要求  
    and pg_try_advisory_xact_lock(id)                         -- adlock，提高秒杀吞吐  
    order by i_pos1 <-> pos for update skip locked limit 1
Limit  (cost=0.41..1.50 rows=1 width=50) (actual time=0.482..0.482 rows=1 loops=1)
  Output: id, pos, (('0101000020E61000000000000000005E400000000000003E40'::geometry <-> pos)), ctid
  Buffers: shared hit=9
  ->  LockRows  (cost=0.41..1269428.33 rows=1169416 width=50) (actual time=0.481..0.481 rows=1 loops=1)
        Output: id, pos, (('0101000020E61000000000000000005E400000000000003E40'::geometry <-> pos)), ctid
        Buffers: shared hit=9
        ->  Index Scan using idx_car_pos_1 on public.car  (cost=0.41..1257734.17 rows=1169416 width=50) (actual time=0.465..0.465 rows=1 loops=1)
              Output: id, pos, ('0101000020E61000000000000000005E400000000000003E40'::geometry <-> pos), ctid
              Order By: (car.pos <-> '0101000020E61000000000000000005E400000000000003E40'::geometry)
              Filter: ((((car.rest_sites > 0) AND (car.rest_sites >= '1'::smallint)) OR (car.rest_sites IS NULL)) AND pg_try_advisory_xact_lock((car.id)::bigint) AND ((car.order_pos IS NULL) OR f_isbulk('0101000020E61000000000000000005E409A99999999193E40'::geometry, car.order_pos)))
              Buffers: shared hit=7


LOG:  duration: 0.102 ms  plan:
Query Text: update car set   
    rest_sites=coalesce(rest_sites-i_sites, sites-i_sites),         -- 减少剩余座位  
    order_pos=coalesce(order_pos||i_pos2, array[i_pos2])            -- 将目的地追加到车辆所有目的地中  
    where id=v_carid    
    and coalesce(rest_sites-i_sites, sites-i_sites) >= 0  
    returning id
Update on public.car  (cost=0.43..2.67 rows=1 width=86) (actual time=0.098..0.099 rows=1 loops=1)
  Output: id
  Buffers: shared hit=15
  ->  Index Scan using car_pkey on public.car  (cost=0.43..2.67 rows=1 width=86) (actual time=0.017..0.018 rows=1 loops=1)
        Output: id, pos, sites, COALESCE((rest_sites - '1'::smallint), (sites - '1'::smallint)), mod_time, COALESCE((order_pos || '0101000020E61000000000000000005E409A99999999193E40'::geometry), '{0101000020E61000000000000000005E409A99999999193E40}'::geometry[]), ctid
        Index Cond: (car.id = 1112283)
        Filter: (COALESCE((car.rest_sites - '1'::smallint), (car.sites - '1'::smallint)) >= 0)
        Buffers: shared hit=4


LOG:  duration: 0.032 ms  plan:
Query Text: insert into orders (carid, uid, crt_time, pos1, pos2, sites, status)   
    values(v_carid, i_uid, now(), i_pos1, i_pos2, i_sites, 2)   -- 状态为进行中  
    returning id
Insert on public.orders  (cost=0.00..0.02 rows=1 width=96) (actual time=0.030..0.031 rows=1 loops=1)
  Output: id
  Buffers: shared hit=8
  ->  Result  (cost=0.00..0.02 rows=1 width=96) (actual time=0.010..0.010 rows=1 loops=1)
        Output: nextval('orders_id_seq'::regclass), 1112283, '1'::bigint, now(), '0101000020E61000000000000000005E400000000000003E40'::geometry, '0101000020E61000000000000000005E409A99999999193E40'::geometry, '1'::smallint, '2'::smallint
        Buffers: shared hit=1


LOG:  duration: 1.686 ms  plan:
Query Text: select getcar_isbulk(1, st_setsrid(st_point(120,30),4326), st_setsrid(st_point(120,30.1),4326), 1::int2);
Result  (cost=0.00..0.26 rows=1 width=8) (actual time=1.681..1.681 rows=1 loops=1)
  Output: getcar_isbulk('1'::bigint, '0101000020E61000000000000000005E400000000000003E40'::geometry, '0101000020E61000000000000000005E409A99999999193E40'::geometry, '1'::smallint)
  Buffers: shared hit=56
 getcar_isbulk 
---------------
      18854017
(1 row)

分库

通常分库的目的是降低单库的请求量，但是对于时空库，如何分区好呢？

1、如果按空间分库，涉及地理边界问题

2、如果按其他分库，由于任一空间数据可能在所有分库，查询车辆时，涉及所有分库全部搜索的问题

思路：

为了降低请求量，还是需要按空间来分区，但是需要克服边界的问题，以及车辆位置迁移的问题。

1、首先，按车辆经常活动的位置分库, 构建元数据，保存：多边形 <-> 库映射关系.

2、根据用户上车位置，选择覆盖它的多边形，找到这个多边形对应的一个或多个库，多边形选择的性能，PG非常的好：

《HTAP数据库 PostgreSQL 场景与性能测试之 5 - (OLTP) 空间应用 - 空间包含查询(表内多边形包含输入空间对象)》

3、订单映射关系, 表示一个订单在哪个库生成的，这个数据可以按订单号分库，不存在空间这种交错问题。

4、最后，车辆位置修订（比如某个车辆因订单跑到很远的地方，点更新所属位置，将车辆信息进行迁移（从一个分库改到另一个分库），这样目标位置库内就有它的车辆信息了，可以被用户看到。）。

小结

PostgreSQL 是一个非常棒的全栈式数据库，本例用到了PG的几个特性：

1、空间数据库插件PostGIS

2、数组，为拼车提供了算法基础

3、部分索引，只对需要检索的数据创建索引

4、UDF，数据库端编程，本例的派单完全由PG的PLPGSQL函数完成

5、skip lock, advisorry lock。与秒杀类似，用于提高高峰期的打车吞吐，不会造成一辆车被多个客户抢锁，白白等待。

测试机位56核的阿里云ECS虚拟机，SSD云盘。

性能

在混合场景，这样一个主机，每秒约处理1万笔派单。如果峰值有达到每秒100万比订单，可以分100个库。

算笔账

而购买一个类似规格的阿里云RDS PostgreSQL实例(56核，480G内存，2TB SSD云盘存储)，成本仅需6140每月(还包含了云盘本身的可靠性、数据库的高可用、备份、等等。关键是数据库内核级的支持与服务，你值得拥有)。

优化

本文即兴而写，内容可能会很糙，主要是提供一些思路和DEMO，后面肯定还有很多的优化空间，比如下面的几个思路，仅供参考，谢谢观赏。

未来优化1：对于不能被叫的车辆，形式过程中不更新其位置。本例中已优化(insert on conflict语法内支持)。

未来优化2：高峰期，撮合同一方向的订单。可以利用类似数据库的分组提交，打车时HOLD一定时间窗口，按目标方向，比如使用k-means，按目的地位置聚集归类进行撮合（当然还可以扩展更多的撮合方法）。

未来优化3：对于同一个时刻，同一个地点，有多人打车时，如果都按同样的就近选择CAR的规则，会导致同一辆CAR被多次挑选中，本文使用了ADVISORY LOCK来避免行锁冲突。但是依旧有更好的优化，因为这种方法虽然没有了锁冲突，但是扫描依旧是从近到远的，所以可能并发时，一些会话存在多行扫描才找到没有被锁定的行。有一种方法，比如，类似组提交，对同一个地点同时打车的多人，一次取多辆CAR，在程序中分配给不同的人。还有一种方法，需要数据库内来实现，给一个离散因子，每次获取到的可能不是最近的CAR，满足多少米内的周边的CARs，随机挑选，但是这个随机挑选必须在INDEX中完成，必须保证在库中的index scan, heap scan都只扫一条。（类似索引的位点随机扫）

未来优化4：由于car表经常更新可以设计一个合理fillfactor，包括它的索引。例如设置为70.

《在PostgreSQL中如何生成测试kmean算法的数据》

《K-Means 数据聚集算法》

《一张图看懂MADlib能干什么》

《PostgreSQL 多元线性回归 - 1 MADLib Installed in PostgreSQL 9.2》

《PostGIS 空间数据学习建议》

http://postgis.net/docs/manual-2.4/