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 1jgy55-0007Ui-W4 for pgsql-bugs@arkaria.postgresql.org; Thu, 04 Jun 2020 22:11:24 +0000 Received: from localhost ([127.0.0.1] helo=malur.postgresql.org) by malur.postgresql.org with esmtp (Exim 4.92) (envelope-from ) id 1jgy54-0001jj-Rf for pgsql-bugs@arkaria.postgresql.org; Thu, 04 Jun 2020 22:11:22 +0000 Received: from magus.postgresql.org ([2a02:c0:301:0:ffff::29]) by malur.postgresql.org with esmtps (TLS1.3:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1jgy54-0001jc-In for pgsql-bugs@lists.postgresql.org; Thu, 04 Jun 2020 22:11:22 +0000 Received: from mail-qk1-x742.google.com ([2607:f8b0:4864:20::742]) by magus.postgresql.org with esmtps (TLS1.3:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.92) (envelope-from ) id 1jgy51-0001wo-4R for pgsql-bugs@lists.postgresql.org; Thu, 04 Jun 2020 22:11:21 +0000 Received: by mail-qk1-x742.google.com with SMTP id c12so7839389qkk.13 for ; Thu, 04 Jun 2020 15:11:18 -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=wlWdkFYx4KIyzKUpmQJVhPfbxLsW0twBSRPcDCKu3oI=; b=i7uurznoSzvC7YHHVFkP2Yac8kS8KgLQzbnqay5imBusN7352YVPe/1W8S9GbkYqoM SxxvtVjORvn+dYStDRjCH7kt98r7bHkA7dbPkLdU8Xx1oGzzPU25XTEFCLUKOLVlPMNK b62ZhbZP4KvG4Un3Ewybodm5VucsuH0HeHVqjDol9ZN9pFEUgt5HsW8nsS7m7vcIDQzz pEShStoyuw8v/Slu57c019j0rPwil9c2BYa1gsKyDfzFY5V2aofwPUKCqcYJV8jOWrJH n0gZdaiiFb4IgP39enAzIkRHPhXW/dpHTqVfsb6ov4uhcxlejx164qBM0Dupd8K6kyke Dj7w== 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=wlWdkFYx4KIyzKUpmQJVhPfbxLsW0twBSRPcDCKu3oI=; b=ugDChbmKqmlvdOp1wtrWCbxfvE7VaQeBRhpLgCLZTq4OK4heLWRlGicnDIM809LUmo qNT5gTnwb86M+Rf9KcitAQT4urrUMPTdxxb1k2+aPLUZvl4xKuSpku2g+FENyzwTkLB1 Ux+GIasYqVoOpQ1viPNJKDfmMrBH8e8lxc6xrDBmnQRIgbu7f3xIvH+P89sAV17/QoB3 SWYzONK1AQ9t1yDKTAGhZehySmVof8ZFmzAnzjo1xrI7lR5ufThxn5SMhITGlt8H+9Zs DfBcufaDaih6lZXuSchuBLKtsMQdBlwsM3lhsnJlyEPWGDmMz5AsLgAVwDjX5a5qlqJ2 m8Ig== X-Gm-Message-State: AOAM53062oel/ZkcKMYHuKal/vI1fi1NYkfnNzJBdmiYNVSHXEkLr9lD sDKGsuSdR9x2NlODwgePdPBSMkLMBik= X-Google-Smtp-Source: ABdhPJyABHvSeI/JqjUXm5RV6wJtGkmrOpnkpTDPwQYKyG94st4xNwLZ0dAAn7fjZdMI+zPxIlQPyA== X-Received: by 2002:a05:620a:210e:: with SMTP id l14mr6117714qkl.242.1591308675957; Thu, 04 Jun 2020 15:11:15 -0700 (PDT) Received: from ?IPv6:2600:2b00:9455:c800:1f2a:9df2:b983:8576? ([2600:2b00:9455:c800:1f2a:9df2:b983:8576]) by smtp.gmail.com with ESMTPSA id x13sm5309786qkj.36.2020.06.04.15.11.15 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Thu, 04 Jun 2020 15:11:15 -0700 (PDT) Subject: Re: Potential G2-item cycles under serializable isolation To: Peter Geoghegan Cc: PostgreSQL mailing lists References: From: Kyle Kingsbury Message-ID: <80e772f7-a46d-7bfd-28d0-4017bf5cd2e5@jepsen.io> Date: Thu, 4 Jun 2020 18:11:14 -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/4/20 5:29 PM, Peter Geoghegan wrote: > I'd appreciate it if you could provide this information, so I can be > confident I didn't get something wrong. I don't really understand how > Elle detects this G2-Item anomaly, nor how it works in general. > PostgreSQL doesn't really use 2PL, even to a limited degree (unlike > Oracle), so a lot of the definitions from the "Generalized Isolation > Level Definitions"/Adya paper are not particularly intuitive to me. Hopefully you shouldn't have to think about 2PL, because the generalized phenomena are defined independently of locking--though I think the paper talks about 2PL in order to show equivalency to the locking approaches. The gist of the generalized definitions is about information flow--the anomalies (well, most of them) correspond to cycles in the dependency graph between transactions. Elle works (very loosely) by inferring this dependency graph. I think you've probably read this already, and I know it's a *lot* to throw out there all at once, but the Elle readme and paper might be helpful here. In particular, section 2 of the paper ("The Adya Formalism") gives a brief overview of what these dependencies are, and section 3 gives an intuition for how we can infer the dependency graph. https://github.com/jepsen-io/elle https://github.com/jepsen-io/elle/blob/master/paper/elle.pdf > That said, I find it easy to understand why the "G2-item: Item > Anti-dependency Cycles" example from the paper exhibits behavior that > would be wrong for Postgres -- even in repeatable read mode. Yeah! My understanding is that this behavior would be incorrect either under snapshot serializability or repeatable read, at least using the generalized definitions. It might be OK to do this under repeatable read given the anomaly interpretation of the ANSI SQL spec; not entirely sure. > If > Postgres exhibits this anomaly (in repeatable read more or > serializable mode), that would be a case of a transaction reading data > that isn't visible to its original transaction snapshot. The paper > supposes that this could happen when another transaction (the one that > updated the sum-of-salaries from the example) committed. Yes! It's not always this obvious--G2-item encompasses any dependency cycle between transactions such that at least one dependency involves a transaction writing state which was not observed by some (ostensibly prior) transaction's read. We call these "rw dependencies" in the paper, because they involve a read which must have occurred before a write. Another way to think of G2-item is "A transaction failed to see something that happened in its logical past". A special case of G2-item, G-single, is commonly known as read skew. In Elle, we tag G-single separately, so all the G2-item anomalies reported actually involve 2+ rw dependencies, not just 1+. I haven't seen G-single yet, which is good--that means Postgres isn't violating SI, just SSI. Or, of course, the test itself could be broken--maybe the SQL statements themselves are subtly wrong, or our inference is incorrect. > If each Jepsen worker has its own connection for the duration of the > test (which I guess must happen already), and each connection > specified an informative and unique "application_name", it would be > possible to see Jepsen's string from the Postgres logs, next to the > SQL text. Give Jepsen a138843d a shot! 1553 jepsen process 27 16 LOG:  execute : select (val) from txn0 where sk = $1 1553 jepsen process 27 17 DETAIL:  parameters: $1 = '9' Here, "process 27" is the same as the :process field you'll see in transactions. I'd like to be able to get a mini log of SQL statements embedded in the operation itself, so it'd be *right there* in the anomaly explanation, but... I haven't figured out how to scrape those side effects out of the guts of JDBC yet. --Kyle