search

kohler / masstree-beta

Beta release of Masstree.
Other
430 stars 115 forks source link

mtd: asynchronous rcu quiesce for reducing latency #21

Closed mitake closed 8 years ago

mitake commented 8 years ago

This commit adds a new option --async-quiesce to mtd. This option enables asynchronous rcu quiesce for reducing request latency. The strategy is very simple: a thread collects garbage objects of its limbo list (which can be simply free()ed, not returned into threadinfo.pool_) in a vector and passes to a thread that only does reclamation.

mitake commented 8 years ago

I'm very not sure this commit is effective or not (e.g. it introduces a new lock, doesn't solve any performance problem of malloc, etc). But I'd like to share my latency measurement result. In short, the async quiesce reduces get latency but increases put latency.

without --async-quiesce

{"puts":3203073,"puts_per_sec":309270.071257,"gets":3203073,"gets_per_sec":630507.311215,"ops":6406146,"ops_per_sec":414985.60128,"get_check_key8_lat_min":0,"get_check_key8_lat_max":0.00540089607239,"put_key8_lat_min":0,"put_key8_lat_max":1.72413396835}
{"puts":3635201,"puts_per_sec":363552.751501,"gets":3635201,"gets_per_sec":723656.788983,"ops":7270402,"ops_per_sec":483968.190088,"get_check_key8_lat_min":0,"get_check_key8_lat_max":0.0100009441376,"put_key8_lat_min":0,"put_key8_lat_max":1.25188183784}
{"puts":2989057,"puts_per_sec":298917.808358,"gets":2989057,"gets_per_sec":616234.718633,"ops":5978114,"ops_per_sec":402563.564204,"get_check_key8_lat_min":0,"get_check_key8_lat_max":0.00554513931274,"put_key8_lat_min":0,"put_key8_lat_max":1.30252099037}
{"puts":2995201,"puts_per_sec":299535.825562,"gets":2995201,"gets_per_sec":663084.912017,"ops":5990402,"ops_per_sec":412660.311138,"get_check_key8_lat_min":0,"get_check_key8_lat_max":0.0112009048462,"put_key8_lat_min":0,"put_key8_lat_max":1.25233197212}
{"puts":3207169,"puts_per_sec":320741.600054,"gets":3207169,"gets_per_sec":629704.78451,"ops":6414338,"ops_per_sec":425005.604579,"get_check_key8_lat_min":0,"get_check_key8_lat_max":0.00557589530945,"put_key8_lat_min":0,"put_key8_lat_max":1.25250387192}
{"puts":2931969,"puts_per_sec":283074.546409,"gets":2931969,"gets_per_sec":609752.822032,"ops":5863938,"ops_per_sec":386649.221606,"get_check_key8_lat_min":0,"get_check_key8_lat_max":0.00662803649902,"put_key8_lat_min":0,"put_key8_lat_max":1.70312714577}
{"puts":3203073,"puts_per_sec":320304.741719,"gets":3203073,"gets_per_sec":688227.710707,"ops":6406146,"ops_per_sec":437155.192362,"get_check_key8_lat_min":0,"get_check_key8_lat_max":0.00934791564941,"put_key8_lat_min":0,"put_key8_lat_max":1.65293383598}
{"puts":3400193,"puts_per_sec":328166.290407,"gets":3400193,"gets_per_sec":656192.83513,"ops":6800386,"ops_per_sec":437523.994871,"get_check_key8_lat_min":0,"get_check_key8_lat_max":0.00448489189148,"put_key8_lat_min":0,"put_key8_lat_max":1.85416197777}
{"puts":3172353,"puts_per_sec":306991.514616,"gets":3172353,"gets_per_sec":647658.592058,"ops":6344706,"ops_per_sec":416541.496701,"get_check_key8_lat_min":0,"get_check_key8_lat_max":0.00407814979553,"put_key8_lat_min":0,"put_key8_lat_max":1.75334906578}
{"puts":2929921,"puts_per_sec":292994.321398,"gets":2929921,"gets_per_sec":635247.117953,"ops":5859842,"ops_per_sec":401024.540285,"get_check_key8_lat_min":0,"get_check_key8_lat_max":0.00886702537537,"put_key8_lat_min":0,"put_key8_lat_max":1.45262813568}
{"puts":3090001,"puts_per_sec":309010.355394,"gets":3090001,"gets_per_sec":598315.284993,"ops":6180002,"ops_per_sec":407539.720303,"get_check_key8_lat_min":0,"get_check_key8_lat_max":0.00618100166321,"put_key8_lat_min":0,"put_key8_lat_max":1.30435585976}
{"puts":2978924,"puts_per_sec":297921.650177,"gets":2978924,"gets_per_sec":738534.512416,"ops":5957848,"ops_per_sec":424572.555199,"get_check_key8_lat_min":0,"get_check_key8_lat_max":0.0130431652069,"put_key8_lat_min":0,"put_key8_lat_max":1.36080098152}
total 75472270
puts: n 12, total 37736135, average 3144678, min 2929921, max 3635201, stddev 210148
gets: n 12, total 37736135, average 3144678, min 2929921, max 3635201, stddev 210148
puts/s: n 12, total 3730481, average 310873, min 283075, max 363553, stddev 20918
gets/s: n 12, total 7837117, average 653093, min 598315, max 738535, stddev 43969
minimum get check key8 latency: 0.000000 sec
maximum get check key8 latency: 0.013043 sec
minimum put key8 latency: 0.000000 sec
maximum put key8 latency: 1.854162 sec
{"puts":3021825,"puts_per_sec":276373.045907,"gets":3021825,"gets_per_sec":628077.567277,"ops":6043650,"ops_per_sec":383843.424515,"get_check_key8_lat_min":0,"get_check_key8_lat_max":0.00623989105225,"put_key8_lat_min":0,"put_key8_lat_max":2.05801296234}
{"puts":3357953,"puts_per_sec":306953.429157,"gets":3357953,"gets_per_sec":644774.564723,"ops":6715906,"ops_per_sec":415908.253088,"get_check_key8_lat_min":0,"get_check_key8_lat_max":0.012521982193,"put_key8_lat_min":0,"put_key8_lat_max":1.25235509872}
{"puts":3603201,"puts_per_sec":360342.222412,"gets":3603201,"gets_per_sec":784483.311077,"ops":7206402,"ops_per_sec":493843.736866,"get_check_key8_lat_min":0,"get_check_key8_lat_max":0.00404214859009,"put_key8_lat_min":0,"put_key8_lat_max":1.01412701607}
{"puts":3416577,"puts_per_sec":312185.171795,"gets":3416577,"gets_per_sec":665645.058364,"ops":6833154,"ops_per_sec":425031.893044,"get_check_key8_lat_min":0,"get_check_key8_lat_max":0.00318789482117,"put_key8_lat_min":0,"put_key8_lat_max":1.35237383842}
{"puts":3060225,"puts_per_sec":280214.161027,"gets":3060225,"gets_per_sec":696951.690579,"ops":6120450,"ops_per_sec":399718.702676,"get_check_key8_lat_min":0,"get_check_key8_lat_max":0.00627899169922,"put_key8_lat_min":0,"put_key8_lat_max":2.20374202728}
{"puts":3410945,"puts_per_sec":311698.640438,"gets":3410945,"gets_per_sec":630067.062538,"ops":6821890,"ops_per_sec":417069.86389,"get_check_key8_lat_min":0,"get_check_key8_lat_max":0.00381898880005,"put_key8_lat_min":0,"put_key8_lat_max":1.10219907761}
{"puts":3419649,"puts_per_sec":313445.29853,"gets":3419649,"gets_per_sec":706747.252207,"ops":6839298,"ops_per_sec":434283.907079,"get_check_key8_lat_min":0,"get_check_key8_lat_max":0.0155251026154,"put_key8_lat_min":0,"put_key8_lat_max":1.75316596031}
{"puts":3381291,"puts_per_sec":338158.656504,"gets":3381291,"gets_per_sec":616907.847518,"ops":6762582,"ops_per_sec":436854.874556,"get_check_key8_lat_min":0,"get_check_key8_lat_max":0.00243401527405,"put_key8_lat_min":0,"put_key8_lat_max":1.20209002495}
{"puts":3041281,"puts_per_sec":282316.41627,"gets":3041281,"gets_per_sec":605897.329809,"ops":6082562,"ops_per_sec":385165.763386,"get_check_key8_lat_min":0,"get_check_key8_lat_max":0.00592017173767,"put_key8_lat_min":0,"put_key8_lat_max":2.05380105972}
{"puts":3023491,"puts_per_sec":302390.706349,"gets":3023491,"gets_per_sec":766803.524457,"ops":6046982,"ops_per_sec":433736.458186,"get_check_key8_lat_min":0,"get_check_key8_lat_max":0.00468397140503,"put_key8_lat_min":0,"put_key8_lat_max":2.00366187096}
{"puts":3203073,"puts_per_sec":297226.395248,"gets":3203073,"gets_per_sec":712100.505866,"ops":6406146,"ops_per_sec":419398.445002,"get_check_key8_lat_min":0,"get_check_key8_lat_max":0.0102338790894,"put_key8_lat_min":0,"put_key8_lat_max":2.62621808052}
{"puts":2923777,"puts_per_sec":271351.459326,"gets":2923777,"gets_per_sec":694849.918337,"ops":5847554,"ops_per_sec":390288.285056,"get_check_key8_lat_min":0,"get_check_key8_lat_max":0.0025269985199,"put_key8_lat_min":0,"put_key8_lat_max":2.05376982689}
total 77726576
puts: n 12, total 38863288, average 3238607, min 2923777, max 3603201, stddev 218692
gets: n 12, total 38863288, average 3238607, min 2923777, max 3603201, stddev 218692
puts/s: n 12, total 3652656, average 304388, min 271351, max 360342, stddev 26072
gets/s: n 12, total 8153306, average 679442, min 605897, max 784483, stddev 57847
minimum get check key8 latency: 0.000000 sec
maximum get check key8 latency: 0.015525 sec
minimum put key8 latency: 0.000000 sec
maximum put key8 latency: 2.626218 sec
{"puts":3030273,"puts_per_sec":291019.707729,"gets":3030273,"gets_per_sec":719300.392608,"ops":6060546,"ops_per_sec":414384.688489,"get_check_key8_lat_min":0,"get_check_key8_lat_max":0.0211999416351,"put_key8_lat_min":0,"put_key8_lat_max":1.3524711132}
{"puts":3089409,"puts_per_sec":308947.323046,"gets":3089409,"gets_per_sec":673624.788293,"ops":6178818,"ops_per_sec":423611.809614,"get_check_key8_lat_min":0,"get_check_key8_lat_max":0.00908994674683,"put_key8_lat_min":0,"put_key8_lat_max":1.95384812355}
{"puts":3058674,"puts_per_sec":305878.288011,"gets":3058674,"gets_per_sec":653937.863604,"ops":6117348,"ops_per_sec":416799.391942,"get_check_key8_lat_min":0,"get_check_key8_lat_max":0.00543904304504,"put_key8_lat_min":0,"put_key8_lat_max":1.45265507698}
{"puts":3406593,"puts_per_sec":328388.218387,"gets":3406593,"gets_per_sec":712793.724502,"ops":6813186,"ops_per_sec":449629.5059,"get_check_key8_lat_min":0,"get_check_key8_lat_max":0.00439190864563,"put_key8_lat_min":0,"put_key8_lat_max":1.35243582726}
{"puts":3094529,"puts_per_sec":309457.976101,"gets":3094529,"gets_per_sec":707807.235524,"ops":6189058,"ops_per_sec":430638.130689,"get_check_key8_lat_min":0,"get_check_key8_lat_max":0.00578594207764,"put_key8_lat_min":0,"put_key8_lat_max":2.00364089012}
{"puts":2978305,"puts_per_sec":286297.984763,"gets":2978305,"gets_per_sec":650832.17539,"ops":5956610,"ops_per_sec":397665.016357,"get_check_key8_lat_min":0,"get_check_key8_lat_max":0.00346112251282,"put_key8_lat_min":0,"put_key8_lat_max":1.40268802643}
{"puts":2999553,"puts_per_sec":262485.818403,"gets":2999553,"gets_per_sec":778309.18203,"ops":5999106,"ops_per_sec":392575.142138,"get_check_key8_lat_min":0,"get_check_key8_lat_max":0.00244903564453,"put_key8_lat_min":0,"put_key8_lat_max":1.85317993164}
{"puts":3359745,"puts_per_sec":323054.45234,"gets":3359745,"gets_per_sec":661283.432155,"ops":6719490,"ops_per_sec":434059.402531,"get_check_key8_lat_min":0,"get_check_key8_lat_max":0.00582385063171,"put_key8_lat_min":0,"put_key8_lat_max":1.3524210453}
{"puts":3434241,"puts_per_sec":329828.786331,"gets":3434241,"gets_per_sec":723392.244945,"ops":6868482,"ops_per_sec":453077.899332,"get_check_key8_lat_min":0,"get_check_key8_lat_max":0.00346803665161,"put_key8_lat_min":0,"put_key8_lat_max":1.5528960228}
{"puts":3248660,"puts_per_sec":324879.87262,"gets":3248660,"gets_per_sec":677075.270405,"ops":6497320,"ops_per_sec":439077.795318,"get_check_key8_lat_min":0,"get_check_key8_lat_max":0.00343203544617,"put_key8_lat_min":0,"put_key8_lat_max":2.05341911316}
{"puts":2578689,"puts_per_sec":257888.058821,"gets":2578689,"gets_per_sec":748727.627325,"ops":5157378,"ops_per_sec":383637.801504,"get_check_key8_lat_min":0,"get_check_key8_lat_max":0.00420808792114,"put_key8_lat_min":0,"put_key8_lat_max":2.10434412956}
{"puts":3018753,"puts_per_sec":290304.739883,"gets":3018753,"gets_per_sec":654295.862665,"ops":6037506,"ops_per_sec":402170.376994,"get_check_key8_lat_min":0,"get_check_key8_lat_max":0.00454592704773,"put_key8_lat_min":0,"put_key8_lat_max":1.60295319557}
total 74594848
puts: n 12, total 37297424, average 3108119, min 2578689, max 3434241, stddev 234418
gets: n 12, total 37297424, average 3108119, min 2578689, max 3434241, stddev 234418
puts/s: n 12, total 3618431, average 301536, min 257888, max 329829, stddev 24430
gets/s: n 12, total 8361380, average 696782, min 650832, max 778309, stddev 41424
minimum get check key8 latency: 0.000000 sec
maximum get check key8 latency: 0.021200 sec
minimum put key8 latency: 0.000000 sec
maximum put key8 latency: 2.104344 sec

with --async-quiesce

{"puts":2690561,"puts_per_sec":269019.02758,"gets":2690561,"gets_per_sec":598257.16339,"ops":5381122,"ops_per_sec":371144.883288,"get_check_key8_lat_min":0,"get_check_key8_lat_max":0.0175218582153,"put_key8_lat_min":0,"put_key8_lat_max":0.0504050254822}
{"puts":3152385,"puts_per_sec":315250.285327,"gets":3152385,"gets_per_sec":715617.620297,"ops":6304770,"ops_per_sec":437686.841841,"get_check_key8_lat_min":0,"get_check_key8_lat_max":0.0163331031799,"put_key8_lat_min":0,"put_key8_lat_max":0.0151669979095}
{"puts":4326913,"puts_per_sec":432620.346741,"gets":4326913,"gets_per_sec":814958.65743,"ops":8653826,"ops_per_sec":565202.998413,"get_check_key8_lat_min":0,"get_check_key8_lat_max":0.00894594192505,"put_key8_lat_min":0,"put_key8_lat_max":0.400744915009}
{"puts":2887681,"puts_per_sec":288760.884943,"gets":2887681,"gets_per_sec":644143.316722,"ops":5775362,"ops_per_sec":398762.046167,"get_check_key8_lat_min":0,"get_check_key8_lat_max":0.0101470947266,"put_key8_lat_min":0,"put_key8_lat_max":0.0585238933563}
{"puts":2960385,"puts_per_sec":296031.964336,"gets":2960385,"gets_per_sec":662414.686992,"ops":5920770,"ops_per_sec":409195.275968,"get_check_key8_lat_min":0,"get_check_key8_lat_max":0.0112330913544,"put_key8_lat_min":0,"put_key8_lat_max":0.0231051445007}
{"puts":2777857,"puts_per_sec":277781.977965,"gets":2777857,"gets_per_sec":667681.060771,"ops":5555714,"ops_per_sec":392336.364537,"get_check_key8_lat_min":0,"get_check_key8_lat_max":0.0119969844818,"put_key8_lat_min":0,"put_key8_lat_max":0.0346479415894}
{"puts":2831361,"puts_per_sec":283128.789407,"gets":2831361,"gets_per_sec":645300.031584,"ops":5662722,"ops_per_sec":393574.634083,"get_check_key8_lat_min":0,"get_check_key8_lat_max":0.0490620136261,"put_key8_lat_min":0,"put_key8_lat_max":0.0532538890839}
{"puts":2594817,"puts_per_sec":259446.20657,"gets":2594817,"gets_per_sec":628280.110351,"ops":5189634,"ops_per_sec":367241.317931,"get_check_key8_lat_min":0,"get_check_key8_lat_max":0.0074200630188,"put_key8_lat_min":0,"put_key8_lat_max":0.0472052097321}
{"puts":2801153,"puts_per_sec":280110.17103,"gets":2801153,"gets_per_sec":661087.752294,"ops":5602306,"ops_per_sec":393493.013046,"get_check_key8_lat_min":0,"get_check_key8_lat_max":0.00730204582214,"put_key8_lat_min":0,"put_key8_lat_max":0.0337750911713}
{"puts":3022849,"puts_per_sec":302287.53059,"gets":3022849,"gets_per_sec":654362.591087,"ops":6045698,"ops_per_sec":413538.13121,"get_check_key8_lat_min":0,"get_check_key8_lat_max":0.00433015823364,"put_key8_lat_min":0,"put_key8_lat_max":0.100301980972}
{"puts":2941185,"puts_per_sec":294112.504579,"gets":2941185,"gets_per_sec":676126.085482,"ops":5882370,"ops_per_sec":409913.888088,"get_check_key8_lat_min":0,"get_check_key8_lat_max":0.0123679637909,"put_key8_lat_min":0,"put_key8_lat_max":0.0824460983276}
{"puts":2552744,"puts_per_sec":255276.670179,"gets":2552744,"gets_per_sec":573723.703765,"ops":5105488,"ops_per_sec":353337.058228,"get_check_key8_lat_min":0,"get_check_key8_lat_max":0.0629229545593,"put_key8_lat_min":0,"put_key8_lat_max":0.0179390907288}
total 71079782
puts: n 12, total 35539891, average 2961658, min 2552744, max 4326913, stddev 463361
gets: n 12, total 35539891, average 2961658, min 2552744, max 4326913, stddev 463361
puts/s: n 12, total 3553826, average 296152, min 255277, max 432620, stddev 46322
gets/s: n 12, total 7941953, average 661829, min 573724, max 814959, stddev 60417
minimum get check key8 latency: 0.000000 sec
maximum get check key8 latency: 0.062923 sec
minimum put key8 latency: 0.000000 sec
maximum put key8 latency: 0.400745 sec
{"puts":3151361,"puts_per_sec":307318.681622,"gets":3151361,"gets_per_sec":685115.70656,"ops":6302722,"ops_per_sec":424307.859957,"get_check_key8_lat_min":0,"get_check_key8_lat_max":0.0391600131989,"put_key8_lat_min":0,"put_key8_lat_max":0.751799106598}
{"puts":3394817,"puts_per_sec":339500.203605,"gets":3394817,"gets_per_sec":740293.795839,"ops":6789634,"ops_per_sec":465514.523223,"get_check_key8_lat_min":0,"get_check_key8_lat_max":0.0105578899384,"put_key8_lat_min":0,"put_key8_lat_max":1.302257061}
{"puts":2957569,"puts_per_sec":288741.183653,"gets":2957569,"gets_per_sec":662260.588742,"ops":5915138,"ops_per_sec":402148.36992,"get_check_key8_lat_min":0,"get_check_key8_lat_max":0.00900483131409,"put_key8_lat_min":0,"put_key8_lat_max":1.15249896049}
{"puts":3049985,"puts_per_sec":296881.661335,"gets":3049985,"gets_per_sec":655637.236494,"ops":6099970,"ops_per_sec":408698.814159,"get_check_key8_lat_min":0,"get_check_key8_lat_max":0.0145168304443,"put_key8_lat_min":0,"put_key8_lat_max":0.810622930527}
{"puts":3081985,"puts_per_sec":300534.103081,"gets":3081985,"gets_per_sec":650883.405891,"ops":6163970,"ops_per_sec":411202.566181,"get_check_key8_lat_min":0,"get_check_key8_lat_max":0.013521194458,"put_key8_lat_min":0,"put_key8_lat_max":0.80414891243}
{"puts":2688769,"puts_per_sec":268888.708705,"gets":2688769,"gets_per_sec":643169.380157,"ops":5377538,"ops_per_sec":379232.389299,"get_check_key8_lat_min":0,"get_check_key8_lat_max":0.00822496414185,"put_key8_lat_min":0,"put_key8_lat_max":1.45387601852}
{"puts":3020033,"puts_per_sec":302005.992944,"gets":3020033,"gets_per_sec":632438.232215,"ops":6040066,"ops_per_sec":408799.436399,"get_check_key8_lat_min":0,"get_check_key8_lat_max":0.0357110500336,"put_key8_lat_min":0,"put_key8_lat_max":1.10201096535}
{"puts":3139073,"puts_per_sec":305566.110089,"gets":3139073,"gets_per_sec":682574.277937,"ops":6278146,"ops_per_sec":422149.665135,"get_check_key8_lat_min":0,"get_check_key8_lat_max":0.00691986083984,"put_key8_lat_min":0,"put_key8_lat_max":0.801585197449}
{"puts":3197441,"puts_per_sec":311266.444429,"gets":3197441,"gets_per_sec":656439.578176,"ops":6394882,"ops_per_sec":422292.739134,"get_check_key8_lat_min":0,"get_check_key8_lat_max":0.00887703895569,"put_key8_lat_min":0,"put_key8_lat_max":0.701803922653}
{"puts":2954497,"puts_per_sec":287642.680612,"gets":2954497,"gets_per_sec":638452.340783,"ops":5908994,"ops_per_sec":396603.239415,"get_check_key8_lat_min":0,"get_check_key8_lat_max":0.0176320075989,"put_key8_lat_min":0,"put_key8_lat_max":1.05269002914}
{"puts":3214081,"puts_per_sec":312709.036896,"gets":3214081,"gets_per_sec":637824.437397,"ops":6428162,"ops_per_sec":419666.368247,"get_check_key8_lat_min":0,"get_check_key8_lat_max":0.00470805168152,"put_key8_lat_min":0,"put_key8_lat_max":0.601804018021}
{"puts":3258113,"puts_per_sec":316465.632051,"gets":3258113,"gets_per_sec":680203.239355,"ops":6516226,"ops_per_sec":431960.813147,"get_check_key8_lat_min":0,"get_check_key8_lat_max":0.0201280117035,"put_key8_lat_min":0,"put_key8_lat_max":0.651580095291}
total 74215448
puts: n 12, total 37107724, average 3092310, min 2688769, max 3394817, stddev 180321
gets: n 12, total 37107724, average 3092310, min 2688769, max 3394817, stddev 180321
puts/s: n 12, total 3637520, average 303127, min 268889, max 339500, stddev 17447
gets/s: n 12, total 7965292, average 663774, min 632438, max 740294, stddev 30066
minimum get check key8 latency: 0.000000 sec
maximum get check key8 latency: 0.039160 sec
minimum put key8 latency: 0.000000 sec
maximum put key8 latency: 1.453876 sec
{"puts":3252993,"puts_per_sec":325303.790635,"gets":3252993,"gets_per_sec":685507.216362,"ops":6505986,"ops_per_sec":441226.093596,"get_check_key8_lat_min":0,"get_check_key8_lat_max":0.0604450702667,"put_key8_lat_min":0,"put_key8_lat_max":0.66405582428}
{"puts":2783489,"puts_per_sec":278366.63347,"gets":2783489,"gets_per_sec":584904.84883,"ops":5566978,"ops_per_sec":377211.565556,"get_check_key8_lat_min":0,"get_check_key8_lat_max":0.013011932373,"put_key8_lat_min":0,"put_key8_lat_max":0.751347064972}
{"puts":3979521,"puts_per_sec":357389.438601,"gets":3979521,"gets_per_sec":848839.145322,"ops":7959042,"ops_per_sec":502999.430875,"get_check_key8_lat_min":0,"get_check_key8_lat_max":0.00882196426392,"put_key8_lat_min":0,"put_key8_lat_max":1.40562200546}
{"puts":3317649,"puts_per_sec":331780.760091,"gets":3317649,"gets_per_sec":640988.802218,"ops":6635298,"ops_per_sec":437241.789319,"get_check_key8_lat_min":0,"get_check_key8_lat_max":0.0193510055542,"put_key8_lat_min":0,"put_key8_lat_max":0.252159118652}
{"puts":2837249,"puts_per_sec":283746.521081,"gets":2837249,"gets_per_sec":711359.890275,"ops":5674498,"ops_per_sec":405677.004587,"get_check_key8_lat_min":0,"get_check_key8_lat_max":0.00216603279114,"put_key8_lat_min":0,"put_key8_lat_max":0.701433181763}
{"puts":3086839,"puts_per_sec":308688.904608,"gets":3086839,"gets_per_sec":683413.546941,"ops":6173678,"ops_per_sec":425283.051906,"get_check_key8_lat_min":0,"get_check_key8_lat_max":0.0398800373077,"put_key8_lat_min":0,"put_key8_lat_max":0.651923894882}
{"puts":3152234,"puts_per_sec":315235.628212,"gets":3152234,"gets_per_sec":696863.770419,"ops":6304468,"ops_per_sec":434100.225221,"get_check_key8_lat_min":0,"get_check_key8_lat_max":0.021693944931,"put_key8_lat_min":0,"put_key8_lat_max":0.701756000519}
{"puts":2865921,"puts_per_sec":286589.462529,"gets":2865921,"gets_per_sec":614027.728482,"ops":5731842,"ops_per_sec":390785.071482,"get_check_key8_lat_min":0,"get_check_key8_lat_max":0.0444490909576,"put_key8_lat_min":0,"put_key8_lat_max":0.801948070526}
{"puts":2794497,"puts_per_sec":279445.029595,"gets":2794497,"gets_per_sec":573956.693316,"ops":5588994,"ops_per_sec":375882.402963,"get_check_key8_lat_min":0,"get_check_key8_lat_max":0.0274219512939,"put_key8_lat_min":0,"put_key8_lat_max":0.601733922958}
{"puts":2911818,"puts_per_sec":291194.171731,"gets":2911818,"gets_per_sec":682152.743316,"ops":5823636,"ops_per_sec":408156.434285,"get_check_key8_lat_min":0,"get_check_key8_lat_max":0.0219469070435,"put_key8_lat_min":0,"put_key8_lat_max":0.601363897324}
{"puts":3569759,"puts_per_sec":356992.463114,"gets":3569759,"gets_per_sec":711432.622252,"ops":7139518,"ops_per_sec":475421.417254,"get_check_key8_lat_min":0,"get_check_key8_lat_max":0.0139927864075,"put_key8_lat_min":0,"put_key8_lat_max":0.302786111832}
{"puts":2904321,"puts_per_sec":290421.727558,"gets":2904321,"gets_per_sec":622031.896512,"ops":5808642,"ops_per_sec":395968.788365,"get_check_key8_lat_min":0,"get_check_key8_lat_max":0.0348989963531,"put_key8_lat_min":0,"put_key8_lat_max":1.05238389969}
total 74912580
puts: n 12, total 37456290, average 3121358, min 2783489, max 3979521, stddev 363503
gets: n 12, total 37456290, average 3121358, min 2783489, max 3979521, stddev 363503
puts/s: n 12, total 3705155, average 308763, min 278367, max 357389, stddev 28734
gets/s: n 12, total 8055479, average 671290, min 573957, max 848839, stddev 73498
minimum get check key8 latency: 0.000000 sec
maximum get check key8 latency: 0.060445 sec
minimum put key8 latency: 0.000000 sec
maximum put key8 latency: 1.405622 sec
kohler commented 8 years ago

Hi Hitoshi,

There are a couple ways I think this commit should do things differently.

Specifically, I don't like allocating and populating a std::vector<> for each RCU call, and there has been a reason we keep free lists local to each core.

In commit fd8c6782bb74ac4d506c417d906e06ace5ef3db9 we can experiment with a different way to reduce latency variability. This commit processes the RCU list gradually. At most rcu_free_count entries are freed per call to rcu_stop() or rcu_quiesce(). Currently that's 128, but it might be wiser to set that lower to reduce tail latency. The idea is that since we process at most rcu_free_count entries per txn, we'll never get an enormous tail latency.

Now for true robustness we would want to make this even smarter. Specifically, we would want to make sure that the RCU list never grew without bound; so if txns started freeing more than 128 items each, we should compensate by raising rcu_free_count.

I'm curious if this commit helps you observe lower tail latency. If you prefer a mechanism like yours, then I would suggest passing limbo_group objects off to the asynchronous freeing thread as a whole. Maybe we could compare the performance.

kohler commented 8 years ago

Also a bit on the measurement infrastructure. I won't be taking commits that add measurements unconditionally. Stuff like the has_threadcounter<> template lets us add measurements conditionally, with no overhead if they're not needed.

mitake commented 8 years ago

Hi Eddie,

Thanks for letting me know about the commit. However, I'm not sure how the approach is effective. How do you think about reclamation speed? The new scheme of limited reclamation objects will decrease the speed of reclamation. If the speed of allocation is faster than the speed of reclamation (e.g. frequent update would cause such a situation), the server can cause out of memory even if the total amount of metadata and data is smaller than usable memory. It would make capacity planning difficult.

I think the most effective way for keeping limbo lists short is configuring a smaller interval of epoch with --epoch-interval. Although the shorter interval will sacrifice throughput, it will contribute to amortizing the pause time of reclamation.

I will do a serious experiment for measuring throughput and latency from April. I'll share the result with you.

mitake commented 8 years ago

BTW, I'm not sure the async reclamation approach is effective or not for reducing latency. The approach introduces mutexes between request threads and reclamation threads, so the function record_rcu() won't be lock free anymore (though current PR doesn't do it yet). This is the problem described in section 5.2.3 of Practical Lock Freedom by Keir Fraser. And it will introduce the problem of the difficult capacity planning, too.

kohler commented 8 years ago

I agree on capacity planning issues, but am not overly concerned until we measure. I think about reclamation and latency this way. We produce N units of work per epoch (= the reclaimed data). Before fd8c678, we performed all N units of work after a single request, producing a large latency burst for that request (and slowing down later requests). After fd8c678, we perform the N units of work gradually, over several requests.

Before: req req req req req req req RECLAIM-N req req req req req req req req
After:  req req req req req req req RECLAIM-B req RECLAIM-B req RECLAIM-B req RECLAIM-B ...

where B = 128 by default. This avoids the huge latency spike since B < N. It does slow down several requests for a while, of course.

mitake commented 8 years ago

I measured performance of some configuration on GCE. 32 vCPU instance for mtd, 4 vCPU * 4 instances for mutilate.

Without the latest gradual reclamation:

#type       avg     std     min     max     5th    10th    90th    95th    99th  99.9th 99.99th
read        0.0     0.0     0.0     0.0     0.0     0.0     0.0     0.0     0.0     0.0     0.0
update    162.8  1054.4    19.2 747082.9    64.0    75.7   227.5   287.4   533.7  4131.6 13442.0
op_q        1.0     0.0     1.0     1.0     1.0     1.0     1.1     1.1     1.1     1.1     1.1

Total QPS = 186794.4 (11207668 / 60.0s)

Misses = 0 (-nan%)
Skipped TXs = 0 (0.0%)

RX   86579086 bytes :    1.4 MB/s
TX 4611344644 bytes :   73.3 MB/s

The latest master:

#type       avg     std     min     max     5th    10th    90th    95th    99th  99.9th 99.99th
read        0.0     0.0     0.0     0.0     0.0     0.0     0.0     0.0     0.0     0.0     0.0
update    153.1   459.7    17.4 195251.9    58.8    69.5   207.9   265.3   559.6  5185.1 16033.5
op_q        1.0     0.0     1.0     1.0     1.0     1.0     1.1     1.1     1.1     1.1     1.1

Total QPS = 176052.7 (10563161 / 60.0s)

Misses = 0 (-nan%)
Skipped TXs = 0 (0.0%)

RX   81357304 bytes :    1.3 MB/s
TX 4345745953 bytes :   69.1 MB/s

Latency seems to be improved, however, throughput is degraded. I also measured mtd without the gradual reclamation with --epoch-interval 0.01:

#type       avg     std     min     max     5th    10th    90th    95th    99th  99.9th 99.99th
read        0.0     0.0     0.0     0.0     0.0     0.0     0.0     0.0     0.0     0.0     0.0
update    159.4   540.3    17.4 103219.0    60.2    71.3   221.4   288.3   591.6  4953.0 20384.8
op_q        1.0     0.0     1.0     1.0     1.0     1.0     1.1     1.1     1.1     1.1     1.1

Total QPS = 172881.8 (10372910 / 60.0s)

Misses = 0 (-nan%)
Skipped TXs = 0 (0.0%)

RX   80164124 bytes :    1.3 MB/s
TX 4267496643 bytes :   67.8 MB/s

The score is almost similar to the latest master. I think enabling the gradual reclamation unconditionally is harmful for throughput. Maybe implementing it as an optional feature is safe?

mitake commented 8 years ago

FYI, on the same environment, memcached performs like below:

#type       avg     std     min     max     5th    10th    90th    95th    99th  99.9th 99.99th
read        0.0     0.0     0.0     0.0     0.0     0.0     0.0     0.0     0.0     0.0     0.0
update    164.4   244.0    21.1 60378.1    65.4    76.6   263.6   349.0   650.6  2757.7  8286.0
op_q        1.0     0.0     1.0     1.0     1.0     1.0     1.1     1.1     1.1     1.1     1.1

Total QPS = 195723.3 (11743397 / 60.0s)

Misses = 0 (-nan%)
Skipped TXs = 0 (0.0%)

RX   70467582 bytes :    1.1 MB/s
TX 2888885010 bytes :   45.9 MB/s

masstree's throughput is far better than memcached. But memcached's latency (especially standard deviation) is stabler.

mitake commented 8 years ago

Anyway, the async quiesce of this PR is too naive and slack. I'm closing it.