Why doesn't pebble support transaction?

[zhiqiangxu]

No offense, but I'm very surprised that Transaction is explicitly not supported by pebble, how does cockroachdb detect conflict(read-write or write-write) if Transaction is not supported? Isn't Transaction a must-have for any database (whether kv or relational)?

[petermattis]

@zhiqiangxu No offense taken. It is an interesting question: how do you build transactions on top of a non-transactional foundation? Clearly it can be done. A filesystem isn't transactional, and yet transactional databases are built on top of filesystems frequently. The key is looking for what foundational attributes to build on. For filesystems, the foundational attribute is Durability which fsync provides. For Pebble/RocksDB, the attributes are Atomicity and Durability provided by the Batch primitive.

Note that while RocksDB has "transactions", they aren't used by CockroachDB. Distributed transactions could be built on top of non-distributed RocksDB transactions, but doing so is not a requirement. Rather, as mentioned above, CockroachDB relies on the Atomicity and Durability of batches, combined with lots of custom algorithms to implement replication and distributed transactions.

Is there a downside to providing transactions at the Pebble/RocksDB layer? Yes. Full transactions imply Consistency and Isolation. The mechanisms to provide Consistency and Isolation can be complex and cause significant overhead. For one example, the Consistency and Isolation mechanisms might imply a locking facility which has to deal with deadlock. These single-node transaction mechanisms may not serve the needs of the distributed transactions that CockroachDB provides.

[petermattis]

PS I didn't really answer your question of how CockroachDB detects conflicts. That's a really long topic. You might try reading some of the blog posts on CockroachDB consistency.

[zhiqiangxu]

PS I didn't really answer your question of how CockroachDB detects conflicts. That's a really long topic. You might try reading some of the blog posts on CockroachDB consistency.

Thanks, that's a great article!

[mitar]

I would also entertain some more information (in documentation somewhere) on how to detect conflicts while using Pebble. For example, if two batches both write to the same key, I would like to detect that the same key is being written to twice (and abort one). It seems this can be done by using Merge instead of Set with custom merge operator defined on the database which would return an error if value is already present?

Something like the following maybe? Or is there a simpler/better way?

type ConflictValueMerger struct {
	buf []byte
}

func (a *ConflictValueMerger) MergeNewer(value []byte) error {
	return errors.New("merge newer")
}

func (a *ConflictValueMerger) MergeOlder(value []byte) error {
	return errors.New("merge older")
}

func (a *ConflictValueMerger) Finish(includesBase bool) ([]byte, io.Closer, error) {
	return a.buf, nil, nil
}

var ConflictMerger = &pebble.Merger{
	Merge: func(key, value []byte) (pebble.ValueMerger, error) {
		res := &ConflictValueMerger{}
		res.buf = append(res.buf, value...)
		return res, nil
	},

	Name: "conflictMerger",
}

[petermattis]

@mitar I doubt this will do what you want it to do as it is detecting any time a key is overwritten, not just if it is written by two transactions concurrently. If you want simple transaction isolation, then doing something in memory above the level of Pebble is possible. For example, have each transaction keep track of which keys it is writing and when a new transaction attempts to write a key see if it is concurrently being written by another transaction. After a transaction commits, clear this in-memory data structure. Transaction isolation is a very deep and rich topic. If you need something sophisticated then you're probably better off with a full database, not just the KV engine for a database (which is all Pebble strives to be).

[mitar]

@petermattis Thank you. That makes sense.

[advdv]

I'm not an expert on the subject but the algorithm presented in the paper "A Critique of Snapshot Isolation (2012)" is not too difficulty can probably be used for this. It should be possible to find a PDF of it somewhere.