Received: from malur.postgresql.org ([217.196.149.56]) by arkaria.postgresql.org with esmtps (TLS1.3:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1jhYH5-0007g7-NC for pgsql-bugs@arkaria.postgresql.org; Sat, 06 Jun 2020 12:50:11 +0000 Received: from localhost ([127.0.0.1] helo=malur.postgresql.org) by malur.postgresql.org with esmtp (Exim 4.92) (envelope-from ) id 1jhYH4-0006EU-JY for pgsql-bugs@arkaria.postgresql.org; Sat, 06 Jun 2020 12:50:10 +0000 Received: from makus.postgresql.org ([2001:4800:3e1:1::229]) by malur.postgresql.org with esmtps (TLS1.3:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1jhYH4-00063r-5A for pgsql-bugs@lists.postgresql.org; Sat, 06 Jun 2020 12:50:10 +0000 Received: from mail-qt1-x829.google.com ([2607:f8b0:4864:20::829]) by makus.postgresql.org with esmtps (TLS1.3:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.92) (envelope-from ) id 1jhYGu-0007tp-2j for pgsql-bugs@lists.postgresql.org; Sat, 06 Jun 2020 12:50:05 +0000 Received: by mail-qt1-x829.google.com with SMTP id e16so10978515qtg.0 for ; Sat, 06 Jun 2020 05:49:59 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=jepsen-io.20150623.gappssmtp.com; s=20150623; h=subject:to:cc:references:from:message-id:date:user-agent :mime-version:in-reply-to:content-transfer-encoding:content-language; bh=X7U9W6yBKCZxyVVIW6xv/uBBndk6X7r98bP64TqBzRw=; b=rfs4iH8grZHu9uELqeOGXMWvZyQjGxsROux/A9paFDs2o0VFyWSEzyDWmVKyk8BBj5 aB/nMVVVSbKYdIlmSoo4rENRj4t8JSS9ODtFx5dE2Z0osR5HBzer8522cLymEg5SkVwo wLqMWdxotHm0NieuzQUqw8YJm2k2LIMnzSHP7gugJ0PYBwiVa5Oyd/0VMX/gXlTyd7Hm vTqmSv2mfJuButyAzOTzlIeAyDd4LB8ayEiifh3KIUKdE61CVDmzZo8ASHHSta2QLFNR dpyvAthFm2m/X1DGFpXyaPIdwOJmw5Y/YAFh7a2GyUq6HrM4ZsY0QfIYqMfLkOfomgWB NiEQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:subject:to:cc:references:from:message-id:date :user-agent:mime-version:in-reply-to:content-transfer-encoding :content-language; bh=X7U9W6yBKCZxyVVIW6xv/uBBndk6X7r98bP64TqBzRw=; b=Wo801WeG0Vqv1awhRc9EQWGAly2e6wkc6x0y1suj/DpxHQzo19FDscNc240r7lp8UL Z8aGc8nxZ1qn+IRGTAgtM5iEcT/MvZUc45Ys9xa/jV7mag+gxTUlNhFPx+JoMnjWMSYz Dk0M7ZwfLMOiZTjhZFzA94yq7jO9pjGDZcHbMqpE79zYeHlNpsc0Jey23w+T5LpdIPsz +fA5VWgA6DND7GrQfN7pfZYjiuAlzbiYZuV528JzGIRntHfnCPE8NDdqqNrFzUwxA0Tc wYegeUkdi52Wp5gRQLJoqU/iL5Xurd60HNi2tmoAFGe5/WKKw/n98X1Gb2LyFu8pBKBj CXQg== X-Gm-Message-State: AOAM532alghmHbiuHy6SM7LB/N1hJ4O+w133fDhwAhVYQeZg0BTwKq4w nzZSLbpzQsabGeqKWHTttKDPaMZwJk0= X-Google-Smtp-Source: ABdhPJx7HMxtlXqiJxOrNzeZn4YhMYdO7ZHvd7gBMsPKeuq/IiCwqywmrpKJKCWvh6dztEV6IGUtnA== X-Received: by 2002:ac8:2df9:: with SMTP id q54mr14379162qta.215.1591447798177; Sat, 06 Jun 2020 05:49:58 -0700 (PDT) Received: from ?IPv6:2600:2b00:9456:e900:6406:3e20:13d0:34d2? ([2600:2b00:9456:e900:6406:3e20:13d0:34d2]) by smtp.gmail.com with ESMTPSA id f9sm2747650qtk.68.2020.06.06.05.49.57 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Sat, 06 Jun 2020 05:49:57 -0700 (PDT) Subject: Re: Potential G2-item cycles under serializable isolation To: Peter Geoghegan Cc: PostgreSQL mailing lists References: <80e772f7-a46d-7bfd-28d0-4017bf5cd2e5@jepsen.io> From: Kyle Kingsbury Message-ID: Date: Sat, 6 Jun 2020 08:49:56 -0400 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:68.0) Gecko/20100101 Thunderbird/68.8.1 MIME-Version: 1.0 In-Reply-To: Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit Content-Language: en-US List-Id: List-Help: List-Subscribe: List-Post: List-Owner: List-Archive: Precedence: bulk On 6/5/20 6:44 PM, Peter Geoghegan wrote: > Hopefully this helps you, Kyle. Would you mind repeating the exercise > from earlier with this new log file/execution? Here's a quick runthrough of G2-item #0: Let:   T1 = {:type :ok, :f :txn, :value [[:append 1468 3] [:r 1469 nil] [:append 1439 2]], :time 22408795244, :process 49, :index 10392}   T2 = {:type :ok, :f :txn, :value [[:append 1469 1] [:append 1456 2] [:r 1468 nil]], :time 22565885165, :process 45, :index 10464} Then:   - T1 < T2, because T1 observed the initial (nil) state of 1469, which T2 created by appending 1.   - However, T2 < T1, because T2 observed the initial (nil) state of 1468, which T1 created by appending 3: a contradiction! Classic G2: two rw-edges, where each transaction failed to observe the other's write. I restricted the log to just those processes: egrep 'process (49|45)' log_rr_recording.log I jumped to the write of 1468 with /'1468'/, then backtracked to process 45's BEGIN: [rr 316503 580915] 1591388175.849-316503-5/231-0-SHOW-5edaa7f9.4d457-jepsen process 45 LOG:  execute : SHOW TRANSACTION ISOLATION LEVEL [rr 316503 581192] 1591388175.858-316503-5/232-0-SET-5edaa7f9.4d457-jepsen process 45 LOG:  execute : SET SESSION CHARACTERISTICS AS TRANSACTION ISOLATION LEVEL SERIALIZABLE [rr 316503 581202] 1591388175.858-316503-5/233-0-BEGIN-5edaa7f9.4d457-jepsen process 45 LOG:  execute : BEGIN 45 tries to append 1 to 1469, but fails because it found zero rows: [rr 316503 581206] 1591388175.859-316503-5/233-0-UPDATE-5edaa7f9.4d457-jepsen process 45 LOG:  execute : update txn2 set val = CONCAT(val, ',', $1) where id = $2  1591388175.859-316503-5/233-0-UPDATE-5edaa7f9.4d457-jepsen process 45 DETAIL:  parameters: $1 = '1', $2 = '1469' 45 backs off to an insert: [rr 316503 581222] 1591388175.859-316503-5/233-0-SAVEPOINT-5edaa7f9.4d457-jepsen process 45 LOG:  execute : savepoint upsert 49 jumps in to start a transaction: [rr 316514 581232] 1591388175.860-316514-13/401-0-SHOW-5edaa7f9.4d462-jepsen process 49 LOG:  execute : SHOW TRANSACTION ISOLATION LEVEL [rr 316514 581242] 1591388175.860-316514-13/402-0-SET-5edaa7f9.4d462-jepsen process 49 LOG:  execute : SET SESSION CHARACTERISTICS AS TRANSACTION ISOLATION LEVEL SERIALIZABLE [rr 316514 581256] 1591388175.860-316514-13/403-0-BEGIN-5edaa7f9.4d462-jepsen process 49 LOG:  execute : BEGIN 49 tries to update 1468, which also fails, and backs off to an insert: [rr 316514 581350] 1591388175.864-316514-13/403-0-UPDATE-5edaa7f9.4d462-jepsen process 49 LOG:  execute : update txn1 set val = CONCAT(val, ',', $1) where id = $2  1591388175.864-316514-13/403-0-UPDATE-5edaa7f9.4d462-jepsen process 49 DETAIL:  parameters: $1 = '3', $2 = '1468' [rr 316514 581364] 1591388175.864-316514-13/403-0-SAVEPOINT-5edaa7f9.4d462-jepsen process 49 LOG:  execute : savepoint upsert [rr 316514 581374] 1591388175.865-316514-13/403-0-INSERT-5edaa7f9.4d462-jepsen process 49 LOG:  execute : insert into txn1 (id, sk, val) values ($1, $2, $3)  1591388175.865-316514-13/403-0-INSERT-5edaa7f9.4d462-jepsen process 49 DETAIL:  parameters: $1 = '1468', $2 = '1468', $3 = '3' 45 performs its insert of 1469: [rr 316503 581548] 1591388175.871-316503-5/233-0-INSERT-5edaa7f9.4d457-jepsen process 45 LOG:  execute : insert into txn2 (id, sk, val) values ($1, $2, $3)  1591388175.871-316503-5/233-0-INSERT-5edaa7f9.4d457-jepsen process 45 DETAIL:  parameters: $1 = '1469', $2 = '1469', $3 = '1' [rr 316503 581562] 1591388175.872-316503-5/233-1680808-RELEASE-5edaa7f9.4d457-jepsen process 45 LOG:  execute : release savepoint upsert And goes on to update 1456, which also fails, so it inserts there too: [rr 316503 581576] 1591388175.872-316503-5/233-1680808-UPDATE-5edaa7f9.4d457-jepsen process 45 LOG:  execute : update txn0 set val = CONCAT(val, ',', $1) where id = $2  1591388175.872-316503-5/233-1680808-UPDATE-5edaa7f9.4d457-jepsen process 45 DETAIL:  parameters: $1 = '2', $2 = '1456' [rr 316503 581980] 1591388175.887-316503-5/233-1680808-SAVEPOINT-5edaa7f9.4d457-jepsen process 45 LOG:  execute : savepoint upsert [rr 316503 581994] 1591388175.887-316503-5/233-1680808-INSERT-5edaa7f9.4d457-jepsen process 45 LOG:  execute : insert into txn0 (id, sk, val) values ($1, $2, $3)  1591388175.887-316503-5/233-1680808-INSERT-5edaa7f9.4d457-jepsen process 45 DETAIL:  parameters: $1 = '1456', $2 = '1456', $3 = '2' [rr 316503 582008] 1591388175.888-316503-5/233-1680808-RELEASE-5edaa7f9.4d457-jepsen process 45 LOG:  execute : release savepoint upsert 45 reads 1468, observing 0 rows: [rr 316503 582018] 1591388175.888-316503-5/233-1680808-SELECT-5edaa7f9.4d457-jepsen process 45 LOG:  execute : select (val) from txn1 where id = $1  1591388175.888-316503-5/233-1680808-SELECT-5edaa7f9.4d457-jepsen process 45 DETAIL:  parameters: $1 = '1468' And 45 commits: [rr 316503 582028] 1591388175.888-316503-5/233-1680808-COMMIT-5edaa7f9.4d457-jepsen process 45 LOG:  execute : COMMIT 49's insert succeeded, and it goes on to read 1469, finding 0 rows as well. This should cause the transaction to abort, because 1469 was written by a committed transaction performed by process 45, *and* 45 didn't observe 49's writes. [rr 316514 582409] 1591388175.902-316514-13/403-1680806-RELEASE-5edaa7f9.4d462-jepsen process 49 LOG:  execute : release savepoint upsert [rr 316514 582419] 1591388175.902-316514-13/403-1680806-SELECT-5edaa7f9.4d462-jepsen process 49 LOG:  execute : select (val) from txn2 where sk = $1  1591388175.902-316514-13/403-1680806-SELECT-5edaa7f9.4d462-jepsen process 49 DETAIL:  parameters: $1 = '1469' 49 goes on to append to 1439, which, again, fails and backs off to insert: [rr 316514 583918] 1591388175.956-316514-13/403-1680806-UPDATE-5edaa7f9.4d462-jepsen process 49 LOG:  execute : update txn0 set val = CONCAT(val, ',', $1) where id = $2  1591388175.956-316514-13/403-1680806-UPDATE-5edaa7f9.4d462-jepsen process 49 DETAIL:  parameters: $1 = '2', $2 = '1439' [rr 316514 584036] 1591388175.960-316514-13/403-1680806-SAVEPOINT-5edaa7f9.4d462-jepsen process 49 LOG:  execute : savepoint upsert [rr 316514 584283] 1591388175.970-316514-13/403-1680806-INSERT-5edaa7f9.4d462-jepsen process 49 LOG:  execute : insert into txn0 (id, sk, val) values ($1, $2, $3)  1591388175.970-316514-13/403-1680806-INSERT-5edaa7f9.4d462-jepsen process 49 DETAIL:  parameters: $1 = '1439', $2 = '1439', $3 = '2'[rr 316514 584299] 1591388175.971-316514-13/403-1680806-RELEASE-5edaa7f9.4d462-jepsen process 49 LOG:  execute : release savepoint upsert And 49 commits, resulting in a G2-item. [rr 316514 584309] 1591388175.971-316514-13/403-1680806-COMMIT-5edaa7f9.4d462-jepsen process 49 LOG:  execute : COMMIT --Kyle