gistfile1.txt

# 10.2s user time, 210ms system time, 41.18M rss, 233.52M vsz
# Current date: Tue Sep 23 08:18:18 2014
# Hostname: ip-172-31-16-67
# Files: /var/lib/mysql/ip-172-31-16-67-slow.log
# Overall: 43.92k total, 45 unique, 422.35 QPS, 1.68x concurrency ________
# Time range: 2014-09-23 08:15:33 to 08:17:17
# Attribute          total     min     max     avg     95%  stddev  median
# ============     ======= ======= ======= ======= ======= ======= =======
# Exec time           174s     3us   609ms     4ms    38ms    15ms    84us
# Lock time             1s       0     4ms    30us   131us    62us       0
# Rows sent        921.16k       0   1.95k   21.47   97.36   69.97       0
# Rows examine      94.77M       0  40.94k   2.21k  40.32k   9.09k       0
# Query size       144.18M      13 1021.73k   3.36k  621.67  56.27k   31.70

# Profile
# Rank Query ID           Response time  Calls R/Call V/M   Item
# ==== ================== ============== ===== ====== ===== ==============
#    1 0x4B4B34854741F958 103.1190 59.2%  1828 0.0564  0.01 SELECT memos
#    2 0x402E13A51340C830  34.0693 19.6%   546 0.0624  0.01 SELECT memos
#    3 0x60E49B224112724D  13.5894  7.8%  6467 0.0021  0.00 SELECT memos
#    4 0x88929194AB4B746F   9.2880  5.3%   140 0.0663  0.02 INSERT UPDATE DELETE REPLACE UPDATE DELETE UPDATE DELETE REPLACE DELETE UPDATE DELETE UPDATE DELETE UPDATE DELETE UPDATE DELETE UPDATE DELETE UPDATE DELETE UPDATE DELETE REPLACE UPDATE DELETE UPDATE REPLACE UPDATE DELETE REPLACE UPDATE DELETE UPDATE memos
#    5 0x3BC270292103ADCD   6.3952  3.7%    42 0.1523  0.10 SELECT memos
# MISC 0xMISC               7.7859  4.5% 34901 0.0002   0.0 <40 ITEMS>

# Query 1: 29.97 QPS, 1.69x concurrency, ID 0x4B4B34854741F958 at byte 145295190
# Scores: V/M = 0.01
# Time range: 2014-09-23 08:16:16 to 08:17:17
# Attribute    pct   total     min     max     avg     95%  stddev  median
# ============ === ======= ======= ======= ======= ======= ======= =======
# Count          4    1828
# Exec time     59    103s    23ms   209ms    56ms    87ms    20ms    51ms
# Lock time      4    60ms    21us     2ms    32us    36us    49us    30us
# Rows sent     18 175.00k       2     202   98.03  183.58   54.63   88.31
# Rows examine  76  72.45M  40.23k  40.94k  40.58k  40.32k     363  40.32k
# Query size     0 179.74k      99     101  100.68   97.36       0   97.36
# String:
# Hosts        localhost
# Users        isucon
# Query_time distribution
#   1us
#  10us
# 100us
#   1ms
#  10ms  ################################################################
# 100ms  ##
#    1s
#  10s+
# Tables
#    SHOW TABLE STATUS LIKE 'memos'\G
#    SHOW CREATE TABLE `memos`\G
# EXPLAIN /*!50100 PARTITIONS*/
SELECT id, content, is_private, created_at, updated_at FROM memos WHERE user=302  ORDER BY created_at\G

# Query 2: 9.10 QPS, 0.57x concurrency, ID 0x402E13A51340C830 at byte 156137519
# Scores: V/M = 0.01
# Time range: 2014-09-23 08:16:17 to 08:17:17
# Attribute    pct   total     min     max     avg     95%  stddev  median
# ============ === ======= ======= ======= ======= ======= ======= =======
# Count          1     546
# Exec time     19     34s    22ms   144ms    62ms   100ms    21ms    56ms
# Lock time      1    19ms    23us   100us    34us    38us     5us    33us
# Rows sent      3  27.66k       1     106   51.88   92.72   28.52   46.83
# Rows examine  22  21.62M  40.24k  40.86k  40.55k  40.32k     316  40.32k
# Query size     0  62.23k     115     117  116.71  112.70       0  112.70
# String:
# Hosts        localhost
# Users        isucon
# Query_time distribution
#   1us
#  10us
# 100us
#   1ms
#  10ms  ################################################################
# 100ms  #####
#    1s
#  10s+
# Tables
#    SHOW TABLE STATUS LIKE 'memos'\G
#    SHOW CREATE TABLE `memos`\G
# EXPLAIN /*!50100 PARTITIONS*/
SELECT id, content, is_private, created_at, updated_at FROM memos WHERE user=30 AND is_private=0 ORDER BY created_at\G

# Query 3: 106.02 QPS, 0.22x concurrency, ID 0x60E49B224112724D at byte 145326893
# Scores: V/M = 0.00
# Time range: 2014-09-23 08:16:16 to 08:17:17
# Attribute    pct   total     min     max     avg     95%  stddev  median
# ============ === ======= ======= ======= ======= ======= ======= =======
# Count         14    6467
# Exec time      7     14s   178us    63ms     2ms     4ms     2ms     2ms
# Lock time     67   901ms    48us     4ms   139us   204us    87us   125us
# Rows sent     68 629.98k       2     201   99.75   97.36   16.52   97.36
# Rows examine   0 629.98k       2     201   99.75   97.36   16.52   97.36
# Query size     2   4.08M      53   2.38k  661.37  918.49  245.03  621.67
# String:
# Hosts        localhost
# Users        isucon
# Query_time distribution
#   1us
#  10us
# 100us  #
#   1ms  ################################################################
#  10ms  #
# 100ms
#    1s
#  10s+
# Tables
#    SHOW TABLE STATUS LIKE 'memos'\G
#    SHOW CREATE TABLE `memos`\G
# EXPLAIN /*!50100 PARTITIONS*/
SELECT * FROM memos WHERE id IN (0,22015,22014,22013,22012,22011,22008,22007,22006,22003,22001,22998,22996,22993,22992,22991,22987,22986,22984,22982,22978,22977,22976,22970,22969,22968,22965,22964,22963,22962,22960,22959,22957,22956,22955,22954,22952,22951,22947,22942,22940,22937,22935,22934,22933,22930,22929,22928,22924,22922,22921,22920,22918,22917,22915,22912,22911,22909,22908,22906,22905,22904,22903,22901,22898,22897,22895,22885,22884,22883,22882,22881,22880,22873,22871,22868,22867,22866,22865,22864,22861,22860,22859,22857,22856,22855,22852,22851,22849,22848,22844,22842,22838,22837,22834,22831,22830,22829,22828,22825,22824)\G

# Query 4: 12.73 QPS, 0.84x concurrency, ID 0x88929194AB4B746F at byte 102671852
# Scores: V/M = 0.02
# Time range: 2014-09-23 08:15:33 to 08:15:44
# Attribute    pct   total     min     max     avg     95%  stddev  median
# ============ === ======= ======= ======= ======= ======= ======= =======
# Count          0     140
# Exec time      5      9s    33ms   271ms    66ms   134ms    39ms    56ms
# Lock time      0       0       0       0       0       0       0       0
# Rows sent      0       0       0       0       0       0       0       0
# Rows examine   0       0       0       0       0       0       0       0
# Query size    95 138.38M 813.06k 1021.73k 1012.13k 1009.33k  26.04k 1009.33k
# String:
# Hosts        localhost
# Users        isucon
# Query_time distribution
#   1us
#  10us
# 100us
#   1ms
#  10ms  ################################################################
# 100ms  ########
#    1s
#  10s+
# Tables
#    SHOW TABLE STATUS LIKE 'memos'\G
#    SHOW CREATE TABLE `memos`\G
INSERT INTO `memos` VALUES (29019,281,'# Abstract\n\nThis document describes a way to add origin authentication, message integrity,\nand replay resistance to HTTP REST requests.  It is intended to be used over\nthe HTTPS protocol.\n\n# Copyright Notice\n\nCopyright (c) 2011 Joyent, Inc. and the persons identified as document authors.\nAll rights reserved.\n\nCode Components extracted from this document must include MIT License text.\n\n# Introduction\n\nThis protocol is intended to provide a standard way for clients to sign HTTP\nrequests.  RFC2617 (HTTP Authentication) defines Basic and Digest authentication\nmechanisms, and RFC5246 (TLS 1.2) defines client-auth, both of which are widely\nemployed on the Internet today.  However, it is common place that the burdens of\nPKI prevent web service operators from deploying that methodoloy, and so many\nfall back to Basic authentication, which has poor security characteristics.\n\nAdditionally, OAuth provides a fully-specified alternative for authorization\nof web service requests, but is not (always) ideal for machine to machine\ncommunication, as the key acquisition steps (generally) imply a fixed\ninfrastructure that may not make sense to a service provider (e.g., symmetric\nkeys).\n\nSeveral web service providers have invented their own schemes for signing\nHTTP requests, but to date, none have been placed in the public domain as a\nstandard.  This document serves that purpose.  There are no techniques in this\nproposal that are novel beyond previous art, however, this aims to be a simple\nmechanism for signing these requests.\n\n# Signature Authentication Scheme\n\nThe \"signature\" authentication scheme is based on the model that the client must\nauthenticate itself with a digital signature produced by either a private\nasymmetric key (e.g., RSA) or a shared symmetric key (e.g., HMAC).  The scheme\nis parameterized enough such that it is not bound to any particular key type or\nsigning algorithm.  However, it does explicitly assume that clients can send an\nHTTP `Date` header.\n\n## Authorization Header\n\nThe client is expected to send an Authorization header (as defined in RFC 2617)\nwith the following parameterization:\n\n    credentials := \"Signature\" params\n    params := 1#(keyId | algorithm | [headers] | [ext] | signature)\n    digitalSignature := plain-string\n\n    keyId := \"keyId\" \"=\" <\"> plain-string <\">\n    algorithm := \"algorithm\" \"=\" <\"> plain-string <\">\n    headers := \"headers\" \"=\" <\"> 1#headers-value <\">\n    ext := \"ext\" \"=\" <\"> plain-string <\">\n    signature := \"signature\" \"=\" <\"> plain-string <\">\n\n    headers-value := plain-string\n    plain-string   = 1*( %x20-21 / %x23-5B / %x5D-7E )\n\n### Signature Parameters\n\n#### keyId\n\nREQUIRED.  The `keyId` field is an opaque string that the server can use to look\nup the component they need to validate the signature.  It could be an SSH key\nfingerprint, an LDAP DN, etc.  Management of keys and assignment of `keyId` is\nout of scope for this document.\n\n#### algorithm\n\nREQUIRED. The `algorithm` parameter is used if the client and server agree on a\nnon-standard digital signature algorithm.  The full list of supported signature\nmechanisms is listed below.\n\n#### headers\n\nOPTIONAL.  The `headers` parameter is used to specify the list of HTTP headers\nused to sign the request.  If specified, it should be a quoted list of HTTP\nheader names, separated by a single space character.  By default, only one\nHTTP header is signed, which is the `Date` header.  Note that the list MUST be\nspecified in the order the values are concatenated together during signing. To\ninclude the HTTP request line in the signature calculation, use the special\n`request-line` value.  While this is overloading the definition of `headers` in\nHTTP linguism, the request-line is defined in RFC 2616, and as the outlier from\nheaders in useful signature calculation, it is deemed simpler to simply use\n`request-line` than to add a separate parameter for it.\n\n#### extensions\n\nOPTIONAL.  The `extensions` parameter is used to include additional information\nwhich is covered by the request.  The content and format of the string is out of\nscope for this document, and expected to be specified by implementors.\n\n#### signature\n\nREQUIRED.  The `signature` parameter is a `Base64` encoded digital signature\ngenerated by the client. The client uses the `algorithm` and `headers` request\nparameters to form a canonicalized `signing string`.  This `signing string` is\nthen signed with the key associated with `keyId` and the algorithm\ncorresponding to `algorithm`.  The `signature` parameter is then set to the\n`Base64` encoding of the signature.\n\n### Signing String Composition\n\nIn order to generate the string that is signed with a key, the client MUST take\nthe values of each HTTP header specified by `headers` in the order they appear.\n\n1. If the header name is not `request-line` then append the lowercased header\n   name followed with an ASCII colon `:` and an ASCII space ` `.\n2. If the header name is `request-line` then appened the HTTP request line,\n   otherwise append the header value.\n3. If value is not the last value then append an ASCII newline `\\n`. The string\n   MUST NOT include a trailing ASCII newline.\n\n# Example Requests\n\nAll requests refer to the following request (body ommitted):\n\n    POST /foo HTTP/1.1\n    Host: example.org\n    Date: Tue, 07 Jun 2011 20:51:35 GMT\n    Content-Type: application/json\n    Content-MD5: h0auK8hnYJKmHTLhKtMTkQ==\n    Content-Length: 123\n\nThe \"rsa-key-1\" keyId refers to a private key known to the client and a public\nkey known to the server. The \"hmac-key-1\" keyId refers to key known to the\nclient and server.\n\n## Default parameterization\n\nThe authorization header and signature would be generated as:\n\n    Authorization: Signature keyId=\"rsa-key-1\",algorithm=\"rsa-sha256\",signature=\"Base64(RSA-SHA256(signing string))\"\n\nThe client would compose the signing string as:\n\n    date: Tue, 07 Jun 2011 20:51:35 GMT\n\n## Header List\n\nThe authorization header and signature would be generated as:\n\n    Authorization: Signature keyId=\"rsa-key-1\",algorithm=\"rsa-sha256\",headers=\"request-line date content-type content-md5\",signature=\"Base64(RSA-SHA256(signing string))\"\n\nThe client would compose the signing string as (`+ \"\\n\"` inserted for\nreadability):\n\n    POST /foo HTTP/1.1 + \"\\n\"\n    date: Tue, 07 Jun 2011 20:51:35 GMT + \"\\n\"\n    content-type: application/json + \"\\n\"\n    content-md5: h0auK8hnYJKmHTLhKtMTkQ==\n\n## Algorithm\n\nThe authorization header and signature would be generated as:\n\n    Authorization: Signature keyId=\"hmac-key-1\",algorithm=\"hmac-sha1\",signature=\"Base64(HMAC-SHA1(signing string))\"\n\nThe client would compose the signing string as:\n\n    date: Tue, 07 Jun 2011 20:51:35 GMT\n\n# Signing Algorithms\n\nCurrently supported algorithm names are:\n\n* rsa-sha1\n* rsa-sha256\n* rsa-sha512\n* dsa-sha1\n* hmac-sha1\n* hmac-sha256\n* hmac-sha512\n\n# Security Considerations\n\n## Default Parameters\n\nNote the default parameterization of the `Signature` scheme is only safe if all\nrequests are carried over a secure transport (i.e., TLS).  Sending the default\nscheme over a non-secure transport will leave the request vulnerable to\nspoofing, tampering, replay/repudiaton, and integrity violations (if using the\nSTRIDE threat-modeling methodology).\n\n## Insecure Transports\n\nIf sending the request over plain HTTP, service providers SHOULD require clients\nto sign ALL HTTP headers, and the `request-line`.  Additionally, service\nproviders SHOULD require `Content-MD5` calculations to be performed to ensure\nagainst any tampering from clients.\n\n## Nonces\n\nNonces are out of scope for this document simply because many service providers\nfail to implement them correctly, or do not adopt security specfiications\nbecause of the infrastructure complexity.  Given the `header` parameterization,\na service provider is fully enabled to add nonce semantics into this scheme by\nusing something like an `x-request-nonce` header, and ensuring it is signed\nwith the `Date` header.\n\n## Clock Skew\n\nAs the default scheme is to sign the `Date` header, service providers SHOULD\nprotect against logged replay attacks by enforcing a clock skew.  The server\nSHOULD be synchronized with NTP, and the recommendation in this specification\nis to allow 300s of clock skew (in either direction).\n\n## Required Headers to Sign\n\nIt is out of scope for this document to dictate what headers a service provider\nwill want to enforce, but service providers SHOULD at minimum include the\n`Date` header.\n\n# References\n\n## Normative References\n\n* [RFC2616] Hypertext Transfer Protocol -- HTTP/1.1\n* [RFC2617] HTTP Authentication: Basic and Digest Access Authentication\n* [RFC5246] The Transport Layer Security (TLS) Protocol Version 1.2\n\n## Informative References\n\n    Name: Mark Cavage (editor)\n    Company: Joyent, Inc.\n    Email: mark.cavage@joyent.com\n    URI: http://www.joyent.com\n\n# Appendix A - Test Values\n\nThe following test data uses the RSA (2048b) keys, which we will refer\nto as `keyId=Test` in the following samples:\n\n   -----BEGIN PUBLIC KEY-----\n   MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQDCFENGw33yGihy92pDjZQhl0C3\n   6rPJj+CvfSC8+q28hxA161QFNUd13wuCTUcq0Qd2qsBe/2hFyc2DCJJg0h1L78+6\n   Z4UMR7EOcpfdUE9Hf3m/hs+FUR45uBJeDK1HSFHD8bHKD6kv8FPGfJTotc+2xjJw\n   oYi+1hqp1fIekaxsyQIDAQAB\n   -----END PUBLIC KEY-----\n\n    -----BEGIN RSA PRIVATE KEY-----\n    MIICXgIBAAKBgQDCFENGw33yGihy92pDjZQhl0C36rPJj+CvfSC8+q28hxA161QF\n    NUd13wuCTUcq0Qd2qsBe/2hFyc2DCJJg0h1L78+6Z4UMR7EOcpfdUE9Hf3m/hs+F\n    UR45uBJeDK1HSFHD8bHKD6kv8FPGfJTotc+2xjJwoYi+1hqp1fIekaxsyQIDAQAB\n    AoGBAJR8ZkCUvx5kzv+utdl7T5MnordT1TvoXXJGXK7ZZ+UuvMNUCdN2QPc4sBiA\n    QWvLw1cSKt5DsKZ8UETpYPy8pPYnnDEz2dDYiaew9+xEpubyeW2oH4Zx71wqBtOK\n    kqwrXa/pzdpiucRRjk6vE6YY7EBBs/g7uanVpGibOVAEsqH1AkEA7DkjVH28WDUg\n    f1nqvfn2Kj6CT7nIcE3jGJsZZ7zlZmBmHFDONMLUrXR/Zm3pR5m0tCmBqa5RK95u\n    412jt1dPIwJBANJT3v8pnkth48bQo/fKel6uEYyboRtA5/uHuHkZ6FQF7OUkGogc\n    mSJluOdc5t6hI1VsLn0QZEjQZMEOWr+wKSMCQQCC4kXJEsHAve77oP6HtG/IiEn7\n    kpyUXRNvFsDE0czpJJBvL/aRFUJxuRK91jhjC68sA7NsKMGg5OXb5I5Jj36xAkEA\n    gIT7aFOYBFwGgQAQkWNKLvySgKbAZRTeLBacpHMuQdl1DfdntvAyqpAZ0lY0RKmW\n    G6aFKaqQfOXKCyWoUiVknQJAXrlgySFci/2ueKlIE1QqIiLSZ8V8OlpFLRnb1pzI\n    7U1yQXnTAEFYM560yJlzUpOb1V4cScGd365tiSMvxLOvTA==\n    -----END RSA PRIVATE KEY-----\n\nAnd all examples use this request:\n\n    POST /foo?param=value&pet=dog HTTP/1.1\n    Host: example.com\n    Date: Thu, 05 Jan 2012 21:31:40 GMT\n    Content-Type: application/json\n    Content-MD5: Sd/dVLAcvNLSq16eXua5uQ==\n    Content-Length: 18\n\n    {\"hello\": \"world\"}\n\n### Default\n\nThe string to sign would be:\n\n    date: Thu, 05 Jan 2012 21:31:40 GMT\n\nThe Authorization header would be:\n\n    Authorization: Signature keyId=\"Test\",algorithm=\"rsa-sha256\",signature=\"JldXnt8W9t643M2Sce10gqCh/+E7QIYLiI+bSjnFBGCti7s+mPPvOjVb72sbd1FjeOUwPTDpKbrQQORrm+xBYfAwCxF3LBSSzORvyJ5nRFCFxfJ3nlQD6Kdxhw8wrVZX5nSem4A/W3C8qH5uhFTRwF4ruRjh+ENHWuovPgO/HGQ=\"\n\n### All Headers\n\nParameterized to include all headers, the string to sign would be (`+ \"\\n\"`\ninserted for readability):\n\n    POST /foo?param=value&pet=dog HTTP/1.1 + \"\\n\"\n    host: example.com + \"\\n\"\n    date: Thu, 05 Jan 2012 21:31:40 GMT + \"\\n\"\n    content-type: application/json + \"\\n\"\n    content-md5: Sd/dVLAcvNLSq16eXua5uQ== + \"\\n\"\n    content-length: 18\n\nThe Authorization header would be:\n\n    Authorization: Signature keyId=\"Test\",algorithm=\"rsa-sha256\",headers=\"request-line host date content-type content-md5 content-length\",signature=\"Gm7W/r+e90REDpWytALMrft4MqZxCmslOTOvwJX17ViEBA5E65QqvWI0vIH3l/vSsGiaMVmuUgzYsJLYMLcm5dGrv1+a+0fCoUdVKPZWHyImQEqpLkopVwqEH67LVECFBqFTAKlQgBn676zrfXQbb+b/VebAsNUtvQMe6cTjnDY=\"\n\n',0,'2013-10-04 04:42:51','2013-10-04 11:39:39') /*... omitted ...*/\G

# Query 5: 1.56 QPS, 0.24x concurrency, ID 0x3BC270292103ADCD at byte 145174997
# Scores: V/M = 0.10
# Time range: 2014-09-23 08:15:44 to 08:16:11
# Attribute    pct   total     min     max     avg     95%  stddev  median
# ============ === ======= ======= ======= ======= ======= ======= =======
# Count          0      42
# Exec time      3      6s     2ms   609ms   152ms   356ms   126ms    95ms
# Lock time      0     3ms    33us   123us    80us   108us    24us    84us
# Rows sent      8  79.44k     175   1.95k   1.89k   1.86k  284.81   1.86k
# Rows examine   0  79.44k     175   1.95k   1.89k   1.86k  284.81   1.86k
# Query size     0   2.57k      59      63   62.69   62.76    1.45   62.76
# String:
# Hosts        localhost
# Users        isucon
# Query_time distribution
#   1us
#  10us
# 100us
#   1ms  ##
#  10ms  #######################################################
# 100ms  ################################################################
#    1s
#  10s+
# Tables
#    SHOW TABLE STATUS LIKE 'memos'\G
#    SHOW CREATE TABLE `memos`\G
# EXPLAIN /*!50100 PARTITIONS*/
SELECT * FROM memos WHERE id > 8000 ORDER BY id ASC LIMIT 2000\G