ztorkelson

I suspect the answer is: yes, via attenuation. :)

This gave players more degrees of freedom to arrange their inventory as compared to a one-dimensional slot-based system.

Such isolation levels are notoriously difficult to reason about—even for experienced practitioners—and their misuse can and does introduce persistent data anomalies that can be costly to remediate.

Generally speaking, performance issues are significantly easier to diagnose and resolve than data anomalies, and they may be address in a targeted fashion as the need arises.

There’s no substitute for thinking. But if I had to prescribe general advice, it’d be this:

(1) When given the choice, select a modern database system which supports scalable and efficient serializable and snapshot transaction isolation levels.

(2) Use serializable isolation, by default, for all transactions.

(3) In the event that your transactions are not sufficiently performant, stop and investigate. Profile the system to identify the bottleneck.

(4) If the bottleneck is contention due to the transaction isolation level, stop. Assess whether the contention is inherent or whether it is incidental to the implementation or data model.

(5a) If the contention is incidental, do not lower the isolation level. Instead, refactor to eliminate the contention point. Congratulations; you are now done.

(5b) Otherwise, lower the isolation level—only for one or more of the transaction(s) in question—by a single step. Carefully assess the anomalies you have now introduced and the ramifications on the system as a whole. Look for other transactions which could intersect concurrently in time and space. Implement compensatory controls as necessary to accommodate the new behavior.

(6) Repeat only as necessary to achieve satisfaction.

Our Team

We are a small team of experienced software engineers tasked with ensuring that Clover’s rapid growth is sustainable over the long term. Our team solves for cross-cutting non-functional requirements like the security, scalability, and fault tolerance of Clover’s backend services. Together we design and develop the core architectural components, libraries, frameworks, tooling, and distributed systems at the heart of our global payment platform.

Our Work

We recently completed a project to horizontally shard our OLTP cluster, which had grown to 10+ TB in size. Next up is building a fully autonomous service for rebalancing merchant data across the shards to distribute load and eliminate hot spots.

We just finished moving our production infrastructure from private data centers to the public cloud in an effort to streamline our global expansion. Now we’re revisiting our architecture, processes, and tooling in order to better take advantage of the cloud environment.

We are actively working on the design, development, and deployment of data pipeline infrastructure to support richer analytics and reporting for our merchants and internal business needs. Our focus is on its security, scalability, reliability, and performance.

We already have a comprehensive suite of functional unit and integration tests, and are now focused on improving our automated stress tests and supporting infrastructure. That involves building the tools to spin up full production-scale environments, synthesize load, perform fault injection, and to collect, analyze, and surface test results to help drive continual improvement of performance and availability.

Our Stack

  - Java for backend services.
  - Python for integration and stress tests.
  - MySQL for OLTP. Snowflake for OLAP.
  - Kafka for stream processing.
  - Memcached for caching (duh).
  - Redis for ephemeral shared data structures.
  - Wavefront and ELK for operational visibility.
  - Google (GCP) as our cloud service provider.
  - Docker for building containers. Kubernetes for running them.
  - Netty for speaking HTTP, behind HAProxy for load balancing.

Contact: zac at clover dot com (and mention you saw this in HN!)

More info: https://www.clover.com/job-post?gh_jid=1461732

The takeaway shouldn’t be “strings are hard”. Strings are hard, but that’s not the problem here. The problem is using inappropriate data types for the task at hand, and the takeaway should be that representation matters.

Representing an IP endpoint as a string only really makes sense at the human-computer interface. In general, the first thing a program should do with such a string is convert it into a more suitable data type. And as noted elsewhere, more often than not there will already be a library function to do so.

Strings are especially pernicious because they are ubiquitous, in that just about anything can be represented as a string, but the operations one can do on a string representation of an object do not generally correspond with the operations one would want to do on the object itself. This disparity is the source of many bugs, which the article exemplifies (though falls short of directly addressing).

Similarly problematic are assumptions that converting an object to a string and a string to an object (i.e. `parse` and `format` functions) are bijective. This is not generally the case. (Wise practitioners might choose such a mapping, though, when the opportunity presents.)

It’s been a long time since I was involved in the RunUO community, but as I recall, one of the biggest limiting factors on scalability was activated NPC/AI. Range queries and movement were the two big pieces, so I’m sure your improvements would have a big impact there.

We ran load tests on Hybrid with over 10k clients (not just idle, mind you, but moving and talking and whatever else we were able to throw in to the load generators), and the server was able to keep up just fine. That was on mid-2000 era hardware too, but then again, RunUO wasn’t built to really take full advantage of multiple cores.

There are a lot of things I’d do differently if I had the opportunity to go back and redesign it from the ground up, but the simple single-threaded concurrency model is not something I’d want to change without great care. For all the scalability problems RunUO had, I think the concurrency model contributed significantly to its approachability, and I’d be very cautious of making any changes which would complect game logic with concurrency control.

I’ve heard quite a few stories (and now I’m hearing a few more) of folks whose path into software development started by tinkering around with RunUO. In fact, a few of my closest friends (and some now colleagues) took that same path. I am filled with a weird mix of pride and abject humility whenever I have the opportunity to see how the project has touched people all over the world, often in ways I could never have anticipated.

Please do share your changes back. I’d love to take a look at them, even after so many years.

-krrios

Who we are

We’re a small team of experienced software engineers tasked with ensuring that Clover’s rapid growth is sustainable over the long term. We solve for cross-cutting non-functional requirements like the security, scalability, and fault tolerance of Clover’s back-end platform and services. We design and develop the core architectural components, libraries, frameworks, tooling, and distributed systems at the heart of Clover’s global payment platform and services.

What we're doing

We recently completed a project to horizontally shard our transactional (payment) database cluster, which had grown to 10+ TB in size. Now we’re building a fully autonomous service for rebalancing merchant data across the shards to distribute load and eliminate hot spots.

We recently completed a project to lift-and-shift our production infrastructure from private data centers to public cloud in order to streamline our global expansion. Now we’re revisiting our architecture, processes, and tooling in order to more fully leverage the cloud environment.

We are actively working on the design, development, and deployment of data pipeline infrastructure to support richer analytics and reporting for our merchants and internal business needs. Our focus is on its security, scalability, reliability, and performance.

We are paving the road towards a decomposed architecture of horizontal core services (like authentication, authorization, placement, tokenization, and inter-device replication) and vertical product services (like device management, merchant boarding, inventory propagation, and customer loyalty programs).

We already have a healthy suite of functional unit and integration tests, and we are actively enhancing our automated stress tests and supporting infrastructure. That involves building the tools to spin up full production-scale environments, synthesize load, perform fault injection, and to collect, analyze, and surface test results in order to help drive continual improvement of performance and availability.

What we use

  - Java for back-end services.
  - Python for integration and stress tests.
  - MySQL for OLTP. Snowflake for OLAP.
  - Kafka for stream processing.
  - Memcached for caching (duh).
  - Wavefront and ELK for operational visibility.
  - Redis for ephemeral shared data structures.
  - Google (GCP) as our cloud service provider.
  - Docker for building containers. Kubernetes for running them.
  - Netty for speaking HTTP, behind HAProxy for load balancing.

Contact: zac at clover dot com (please mention you saw this in HN)

The benefits of having access to that technology on GCP (or another cloud) are the usual: reduced operational burden, increased availability, flexible pricing structure, elastic scalability, etc.

Your question about pets vs cattle is a non sequitur. Nothing about this announcement or the underlying technologies are suggestive of how they should be used (or misused). It's just a new tool in the toolbox—and as a distributed systems engineer specializing in database technology, having easy access to this hardware at scale is extremely compelling.

We’re a small group of experienced software engineers tasked with ensuring that Clover’s continued growth is sustainable over the long term. Clover recently shipped its one-millionth device and we process over USD $60B in annualized GPV.

If you're interested in scalability, either at the operational level (e.g. 10,000 TPS this year to 20,000 TPS the next) or at the institutional level (e.g. growing from 150 engineers to 300), then please don’t hesitate to reach out. Some recent projects we’ve been working on:

  - Decomposing a monolithic Java backend into a set of modular services.
  - Strategic migration from on-premises infrastructure to public cloud. We use both AWS and GCP.
  - Design and development of a high-throughput, low-latency OLAP pipeline, backed by Kafka and Snowflake.
  - Design and development of a horizontally-scalable MySQL database layer for sharding tens of terabytes of tenant data.
  - Tooling for load test automation and analysis within our SDLC. We use Python and Locust to synthesize the workload.

Note that there exist hash table implementations which support incremental resizing.

I do agree, though, that it's a leap to go from "hash tables with this property are inappropriate under these constraints" to "hash tables with this property should not be considered further", precisely because there is such a broad spectrum of data structure requirements across the industry.

Conventionally, a free list would be used, though admittedly that sacrifices locality which was one of the original motivating factors. To the extent that deletion is a significant component of the workload, then yeah, this doesn't help.

In some scenarios, radix trees can overcome that with better space efficiency (i.e. implicit key storage), but I think it's fair to say that there are many scenarios (if not most!) where hash tables outperform radix trees.

Of course, that all hinges on how you measure performance. As Salvatore pointed out, if you're looking to minimize variance, hash tables might not be suitable due to their growth characteristics. Radix trees also give you efficient sorting and range scans out of the box, and are a viable immutable persistent data structure as well. If none of those are meaningful to your use cases, then hash tables could certainly be a better fit.

That said, I can see two counter-arguments:

1. Rehashing can be avoided if the table size is known in advance. 2. Rehashing is immaterial if the data structure is write-once, read-many.

In those cases, we might reasonably expect a hash table to perform better.

My comment was highlighting that Postgres' implementation of SSI is at least a better starting point than most other purely pessimistic implementations of the serializable isolation level. It does not surprise me, however, to hear that there are still performance deficiencies in practice. For example, the Postgres implementation is imprecise, which will result in spurious transaction aborts (those will presumably be retried, but it comes at a cost to latency and throughput). And even though reads are optimistic (which will perform better than pessimistic concurrency control, if contention rates are sufficiently low), maintaining transaction dependency metadata can still have a non-negligible cost.

I also think Postgres suffers from other more dubious choices--like a lack of clustered indexes--which can exacerbate things.

My work in this area has focused on revisiting various architectural and implementation design decisions which have contributed to the current state of affairs. I think the relational data model is generally the right choice, but most relational databases have some godawful characteristics around performance, scalability, reliability, and programmability which limit their efficacy in practice.

Well, sort of. Serializability allows you to reason locally for correctness, but not for performance. That is, however, a meaningful distinction.

Serializability remains a marked improvement over the status quo. Most operations aren't actually performance sensitive, so that tradeoff makes perfect sense. With serializability, we need only focus our efforts on those operations which are both performance sensitive and highly contended.

This has nice emergent properties, because the problematic transactions are immediately apparent: they are the slow ones, the ones that are not meeting their performance budget.

Performance anomalies are directly measurable and immediately visible. Correctness anomalies are generally neither.

Performance anomalies are generally localized and ephemeral. Correctness anomalies are often persistent and viral.

So the choice is either to explicitly implement required locking for RC or let the SERIALIZABLE do it implicitly under the hood (and hoping that it will do it better :).

Again, when it comes to correctness, there's no real hope to do better than serializable. When it comes to performance: sure. But in every application domain I've worked, getting to a wrong result faster is rarely useful. (I understand that this is not a universal truth, but I believe it is significantly more common than the alternative. The adage "first make it work, then make it fast" comes to mind.)

in my experience any non-trivial system wouldn't run in SERIALIZABLE without hitting the conflicts until the system gets subjected a lot to that "global reasoning" that you mentioned.

I agree that there have been (and still are) practical impediments to deploying large-scale serializable systems with incumbent technologies. But I disagree that those impediments are inherent to all implementations of the serializable isolation level, which is why these kinds of articles (and the R&D behind them) are so important.

We still have a long way to go before serializable-by-default is a tenable option for the most demanding of systems, but that is what we should be working towards.

I agree, in spirit, with all three of his hypotheses for why the situation doesn't seem to be as dire one might otherwise expect. Peter writes that "it's possible data is actually corrupted, and apps don't care". That's true, of course, but it's also that the corruption is not always prominently visible.

Historically, improper concurrency control (e.g. in multithreaded programs written in unsafe languages) could quickly result in much more than logical invariant violations. Physical data corruption and memory access violations were (and still are) prevalent, with readily apparent results.

Modern database systems, however, aren't going to crash when you hit a serialization anomaly. They're not going to physically corrupt your data: your numbers will still be numbers, your strings will still be strings, and your foreign keys will still be sound.

We do occasionally bear witness to prominent failures that stem from weak database isolation levels: "oh, look at that cryptocurrency exchange backed by [database du jour], Eve was able to overdraw her account by issuing a bunch of concurrent requests. What amateurs!" and we all point and laugh from our houses of glass.

In truth, it's not the anomaly that's abnormal, it's the visibility. Those kinds of anomalies happen all the time, even to experienced practitioners, but the failure modes will generally be much more obscure and application-specific. Most aren't going to manifest as some exception in your logs, let alone as a top post on HN. You'll only find out about the problem when a ticket comes in saying "hey, the summary and itemized reports don't add up" or "this section is overflowing because the user has 6 email addresses and we told the designers that the application limits it to 5". That's how serialization anomalies usually manifest, and it's a death-by-a-thousand-cuts situation, because each occurrence saps precious time from everyone involved.

We have to do better.

The point is that--insofar as it comes to correctness--serializability allows local reasoning, whereas weaker isolation levels require global reasoning. You can't argue against that by saying "well, if every transaction just explicitly locks the appropriate records at the appropriate times …" because that's exactly the type of global reasoning that we're trying to avoid.

There certainly is a difference between theory and practice here, but I don't think it's in favor of weaker isolation levels.

In theory, as you note, one can enforce any invariant–even in Read Committed–by taking a global lock in every transaction. In practice, nobody does that, because it takes concurrency to zero.

In theory, one can regain concurrency by judiciously breaking that global lock into some application-specific hierarchy of locks, and by having the discipline to adhere to that bespoke locking protocol for every transaction, now and in perpetuity. In practice, that is both too expensive and too error prone to be applied successfully in any non-trivial system (though some do still try).

In theory, these concerns can be addressed at the application level. In practice, it is grossly irresponsible that we (as an industry) continue to foist these concerns on application developers who–in the aggregate–cannot reasonably be expected to get it right. The number of viable database systems is small and growing slowly, while the number of database-backed applications is large and growing rapidly. To have any hope of improving the status quo, well: I know where I'd put my money.

From the article:

A more concrete reason than “nothing else makes sense” is a question of local vs. global reasoning. If a set of transactions must maintain some kind of invariant within the database (for instance, the sum of some set of fields is always greater than zero). In a database that guarantees serializability, it’s sufficient to verify that every individual transaction maintains this invariant on its own. With anything less than serializability, including Snapshot, one must consider the interactions between every transaction to ensure said invariants are upheld. This is a significant increase in the amount of work that must be done (though in reality, I think the situation is that people simply don’t do it), a point made by Alan Fekete in this talk[1] on isolation.

This bears repeating. In any non-trivial transactional application, the combination of concurrency and non-serializable transaction isolation levels is a serious bug farm. Most app/service backends fall for this trap.

Unfortunately, most OLTP database systems have incredibly poor implementations of the serializable isolation level. Postgres is a notable exception, and it's nice to see some newer database systems--like CockroachDB--making progress in this area.

[1] https://www.youtube.com/watch?v=IP-S_RHlsEQ (Thanks for the link; I hadn't seen this talk before.)

I interviewed to lead their platform engineering team, and while I ultimately decided to take my career in a different direction, the process was smooth, the offer competitive, the technology interesting, and the story compelling.

If you're interested in this space, I'd definitely recommend giving them a look.

My argument is not that such controls can't be reasoned about and applied to great effect. Rather, my argument is that having to do so is much more difficult, time consuming, and error prone than not.

Perhaps it's just a difference of domain, but in my experience, there's real value to be had by a DBMS which doesn't require a team of trained and highly-disciplined "data engineers" to use effectively. Organizations are composed of individuals with varying levels of skill and areas of expertise, but even if everyone was both interested in and capable of building correctly functioning distributed applications under weak consistency models, I'd still prefer a database system which relieves those individuals from having to do so themselves.

As I recall, Google came to the same realization, which helped motivate Spanner. They found that their highly capable engineers were spending a significant amount of time and effort working around the weaker consistency of Spanner's predecessors, to varying degrees of success. By developing Spanner, they were able to eliminate large swaths of application complexity, freeing up their software engineers to focus more on the inherent complexity of their business domain, rather than the incidental complexity of their chosen database.

YMMV.

Allowing weaker consistency is in some ways similar to the varying transaction isolation levels of other relational databases. Most practitioners won't fully consider or appreciate the anomalies that can arise when consistency is relaxed, leading to bugs. Those practitioners that do understand the anomalies can easily get bogged down in the combinatorial complexity of the problem.

Spanner is compelling in large part because it simplifies all of this for the average developer. It provides two consistency models: snapshot (read-only, point-in-time), and serializable (read-write, up-to-date). And it does so in a way that is both highly available (but not CA, despite the unfortunate wording in this paper) and with predictable performance.

This is really valuable: it reduces the cognitive burden which developers might otherwise have, and can serve to increases software reliability.