Attempt to rethink log-based replication in Ceph on fast IO path
Hi Sage and all, I would like to share some of my scattered thoughts regarding IO performance improvements in Ceph. I touch on topics such as replicated log model, atomicity and full journaling on the objectstore side and how these constraints can be relaxed on IO path in order to squeeze maximum from a hard drive, at the same time still respecting the strong data consistency between replicas. Would be great to have a chance to discuss this in Seoul. Proposal in a few lines (for time saving) ----------------------------------------- 1. IO and management requests follow different paths: 1. Slow path for management requests (object creation/deletion, locks, etc) involves replicated log and primary-copy model, as it is right now. 2. Fast IO path (read, write requests) bypasses replicated log and makes clients responsible for sending data to each replica in a group (PG), I reference it as hybrid client-driven replication further in the text. 2. For the sake of simplicity client takes fast IO path only when group of replicas (PG) is in active and healthy state (active+client in terms of Ceph), otherwise client falls back to the slow path. Thus, client is not involved in the disaster recovery process (that's why hybrid). 3. Fast IO path (is taken only if group of replicas (PG) is in active and healthy state): 1. Reads of objects happen from different primaries in a group (PG), in order to spread the read load. 2. Writes are distributed by clients themselves to all replicas in a group (PG), avoiding one extra network hop. 4. Objectstore becomes journal-less and behaves similar to RAID 1, sacrificing atomicity and erasure coding (due to the "write hole" problem) for write performance, which becomes close to the write performance of a bare hard drive, but still keeping strong data consistency between replicas. !!!!! CAUTION: many letters !!!!! Introduction ------------ The most impressive IO performance numbers among products which provide data redundancy is certainly delivered by RAID and that is not a surprise: you just write a block to several disks in parallel, nothing more. Perfect. Then why Ceph can't achieve the same performance as RAID 1 on IO path, doing plain old write-in-parallel thing, but supplemented with scalability, CRUSH object placement and all other beloved things which make Ceph so powerful? The answer to this question lies in the replication design used by Ceph, namely log-based replication (PG log in Ceph terms), which is commonly used in storage and database systems and well described in many publications [1, 2, 3, 4]). Sequential replicated log indeed resolves issues related to atomicity, consistency, isolation and durability (this famous ACID buzzword acronym), especially in DBMS world where transactions are involved. But Ceph is a storage, not a database. Modern hard drives do not provide atomicity, strict writes ordering or durability. Hardware breaks all the rules and relax the constraints for the sake of performance, and software has to deal with it. Every modern filesystem can survive crashes (journals, COW, soft-updates, etc approaches are used), each application which cares about data consistency and can't rely on weak guarantees of POSIX file API (any DBMS for example) uses same methods (journals, COW, etc) to avoid inconsistency. Why then a storage solution, which works below a filesystem and on top of a hardware, should provide such strong ACID properties for IO? So what is a log-based replication which is a core of Ceph? Very simple: duplication (mirroring) of a log which consist of records describing storage operations. In order to duplicate something we have to be sure that an object which we duplicate has not been changed on the way, i.e. actually copy-paste does what it is supposed to do without nasty surprises. When we have a log of storage operations we need not only to deliver a recent record to a replica without corruption (and wrong order of operations in a log is a corruption) but also invoke this operation, which has been described in a log record. Not only that: new record in a log and operation, which is described by that record, should happen in one transaction, atomically, thus either we see a record and operation was performed, either no updates in a log and no operation consequences is visible. Having such a wonderful log (which obviously can survive a crash or even a nuclear strike) we can very easily answer The Most Important question for a high scalable, self-healing storage product: what has happened on other replicas while one of them took a nap (crashed). In other words we need such a complicated mechanism only for one thing: just to tell the exact data difference (e.g. in blocks of data and operations), what has been changed since a crash. Short quiz: can Сeph stay Ceph, but without any log-based replication? Yes, throw it away, no need to know the difference, just copy the whole bunch of data between replicas on any disaster recovery. Very slow on resyncing but fast on doing operations and simple. I'm, of course, exaggerating, but that is not so far from the truth. Talking about log-based replication I've never mentioned why it actually impacts the IO performance. Here is why: 1. Each update operation on a group of replicas (PG in terms of Ceph) has to be strictly ordered (log should stay in the same order on all replicas) i.e. no any other operation is allowed till an operation, which has been just started, reaches a hard drive with all cache flushes involved (who poked the code knows the notorious pglock, which protects the replication log from corruption and makes it be equal on all other replicas). 2. Severe restrictions on how actually the objectstore should be implemented: data and metadata should be fully journaled, because a log record of a replicated operation is stored along with the data in atomic manner. And what is wrong with journal in terms of performance? Nothing is wrong, it is just incredibly slow. (As a hint for the curious: enable "data=journal" option for ext4 filesystem, or "allow_cow" for xfs or just run any load which performs random writes on BTRFS (cow is always enabled), and yes, I promise, you feel the difference immediately). 3. Communication with a group of replicas (PG) happens only through a primary one, where a primary is responsible for keeping log in sync with other replicas. This primary-copy model [7] increases IO latency adding one extra network hop. All of the above about log-based replication in Ceph is about strong consistency, but not about performance. But can we have both? And what is actually a strong consistency? According to formal description "The protocol is said to support strong consistency if all accesses are seen by all parallel processes (or nodes, processors, etc.) in the same order (sequentially)" [6]. In simple words: one thread produces data to the same offset of a file, other threads read from the same offset, thus if strong consistency is respected readers never observe writes in a wrong order, e.g.: Writer Reader 1 Reader 2 Reader 3 -------------- -------------- -------------- --------------- write(file, "A"); b0 = read(file); b0 = read(file); b1 = read(file); write(file, "B"); b0 = read(file); b1 = read(file); b1 = read(file); In this example, readers are able to see a block of a file in the following states: Reader 1 Reader 2 Reader 3 --------- ---------- ---------- b0 == "A" b0 == "A" b0 == "B" b1 == "B" b1 == "A" b1 == "B" But what should never be observed and can be treated as a corruption is the following: b0 == "B" b1 == "A" Having that we can develop a simple rule: writes are not blocked and can come at any order, once a reader observes a change in a block, further reads to this block see the change. Most likely I describe here a wheel, which has some vivid name and was deeply buried in some publication in early 70th, but I do not care and call the rule as READ RECENT. The READ RECENT rule contains one splendid property: if read has never happened and order of writes is unknown, writes can be reordered regardless of their actual order. Practical example: there is a distributed storage where writes are unordered by nature; a full outage has happened and now replicas contain different blocks of data on the same offsets; read of the block has never happened after it was updated, thus we are able to bring replicas in sync choosing block from *any* replica. Marvelous. I will return to this highly important property when I start describing a new replication model. It turns out that strong consistency is not about strict requests ordering in a whole group of replicas (PG) it is only about order of reads against writes to the same block of data. That's it. So the question is left unanswered: can we have both strong consistency and high performance of IO? In order to answer this question, it is necessary to once again state the main requirements for the IO replication model, which remove the strict restrictions imposed by the log-based replication, positively affect performance and do not contradict strong consistency: 1. Get rid of extra hop on fast IO path by doing client-driven replication, at least when group of replicas (PG) is in active state and not doing any sort of disaster recovery. 2. Write requests are not strictly ordered to different offsets of an object and can be submitted to a hard drive in parallel. 3. Get rid of any journaling on fast IO path on objectstore side if possible. These are major requirements of constraint relaxation which can bring storage IO performance close to a bare hard drive bandwidths keeping strong consistency. In the next chapter I will cover all the requirements and will show how it can be implemented in practice. Separation of management requests from IO requests -------------------------------------------------- Requests in a storage cluster can be divided into two parts: management requests, which are object creation/deletion/listing, attributes setting/getting, lock management, etc; and IO requests, which do read or modify content of an object. The most prevailing requests are IO read and write requests, whose latency affect the overall performance of the entire cluster. The proposed requests separation has also a clear separation on metadata and data, which should be treated differently on the objectstore side, namely no journal should be involved in data modification (this will be discussed in detail below). Separating IO from management requests makes it possible to have a different primary replicas in a group of replicas (PG). For example in order to distribute a read load, primary can be chosen by an object id using persistent hashing (e.g. hash ring as proposed here [8]) instead of having a single primary. Write requests require replication involved and as was mentioned earlier client-driven replication model can be chosen in order to minimize latencies of an extra hop. Having different paths for several types of requests can be summarised as the following: 1. Management requests go through a persistent primary replica and log-based replication keeps strict ordering of operations in the entire group (PG). There are no changes to original Ceph architecture are proposed. 2. Read object requests are sent to different primaries according to some persistent hashing rule [8]. 3. Write requests can follow two IO paths, where on one of the paths client is fully responsible for request replication and delivers requests to all replicas in a group (PG). This path is always taken when group of replicas (PG) is in active and healthy state. The second IO path always lies through a primary, thus all requests are equally ordered (like it is right now implemented in Ceph). This path is taken in order to simplify all corner cases when a group of replicas (PG) is not in an active state and performs resynchronization process. Hybrid client-driven replication -------------------------------- Client-driven replication is quite self-descriptive: client is responsible for data delivery to replicas in a group (PG) avoiding one extra network hop, which exists in a primary-copy model. If client communicates with replicas in a group (PG) directly there is no longer the central point of synchronization, thus the one possible issue that needs to be considered is the possibility of write requests from several clients to come to replicas in different order: Client 1 Client 2 -------- -------- sends A to replica1 sends B to replica1 sends A to replica2 sends B to replica2 Replica 1 Replica 2 --------- --------- A B B A ** replica1 writes B to the disk and then overwrites B with A replica2 writes A to the disk and then overwrites A with B In this example both clients access the same block of the same object, but write requests become reordered differently because of the network. If this happened, then replicas can contain different data and they are out of sync. This issue has very bad consequences: future reads are undefined, especially if one of replicas crashed and clients start reading from another. This is definitely a data corruption. In order to solve the issue the order of writes to the same offset should be synchronized between replicas. Synchronization can be performed by marking each request with a timestamp, taking into consideration, that time flows equally on clients. Sub-microsecond time synchronization is not a problem [9], especially when there is the central point for all members - distributed state machine cluster, namely cluster of monitors in terms of Ceph. Having time synchronized, client marks write requests with a timestamp. According to the Thomas Write Rule [10] outdated requests are discarded by timestamp-based concurrency control keeping the correct order. However, in the case of the client-driven replication it is impossible to discard a change on all replicas simultaneously. Instead outdated request should be repeated for all replicas in a group (PG), here is an example: Client 1 Client 2 -------- -------- marks A with stamp 1 marks B with stamp 2 sends A to replica1 sends B to replica1 sends A to replica2 sends B to replica2 Replica 1 Replica 2 --------- -------------- -- on disk -- A B -- on disk -- B A ** replica1 writes B to the disk and rejects A with RETRY replica2 writes A to the disk and then overwrites A with B Request A is not written by replica1, because it is older then B request, which has been applied recently. Instead replica1 replied on A request with the RETRY error, which forces the client to mark request A with a new timestamp and resend it again to the whole group of replicas (PG): Client 1 -------- marks A with stamp 3 sends A to replica1 sends A to replica2 Replica 1 Replica 2 --------- --------- A A -- on disk -- B -- on disk -- B A ** replica1 overwrites B with A replica2 overwrites B with A The next question rises: why do we need to repeat write operation on all replicas, but not only on those who have just replied with the error? Let's consider overlapping data (here I do not consider the reason why clients send overlapping write requests concurrently, obviously this is a bug on a client side, but nevertheless we keep replicas in sync): Client 1 marks AAAA with stamp 1 Client 2 marks BBB with stamp 2 Client 3 marks C with stamp 3 Replica 1 Replica 2 --------- --------- C 3 BBB 2 C 3 AAAAA 1 AAAAA 1 --------- --------- below the line is the state on disk ABCBA AACAA ** replica1 writes AAAA, then overwrites the middle with BBB and then with C replica2 writes AAAA and overwrites the middle with C; BBB request is rejected Client2 receives the RETRY error and has to repeat BBB: Client 2 marks BBB with stamp 4 Replica 1 Replica 2 --------- --------- BBB 4 BBB 4 -- on disk -- C 3 -- on disk -- BBB 2 C 3 AAAAA 1 AAAAA 1 -------------- -------------- below the line is the state on disk ABBBA ABBBA On a second retry blocks on replicas become synchronized and write request is considered as completed and persistent on a drive. Since concurrent writes should never happen on well written client software (I expect distributed filesystems use lock primitives in order to prevent concurrent access) I do not expect any performance degradation because of frequent write retries, so current algorithm acts as a protection which keeps replicas in sync. I would like to emphasize several points obtained from the description of the algorithm described above: 1. Time synchronization on clients does not need to be very accurate, even hundreds of millisecond accuracy is enough. Described time-based algorithm does not depend on actual physical time, also it does not depend on real (absolute) order of writes sent by concurrent clients. Instead algorithm forces distributed cluster members to have a single view on requests order, which is enough to decide should request be rejected or executed. 2. Hybrid client-driven replication does not involve clients into data recovery process, thus leaving this job to replicas (exactly as it is right now). Here I describe the fast IO path only when group of replicas (PG) is in active and fully synchronized state. When group of replicas (PG) is in resynchronization state or client sends management type of requests (not IO), then for the sake of simplicity all communication goes through the main primary replica, as it is right now implemented in Ceph. Crash of a client in the middle of a replication ------------------------------------------------ Client-driven replication in contrast with a primary-copy model has another major issue which has to be considered in detail: crash of a client in the middle of a replication, that is, when client sends write request to one of replicas in a group (PG) and then crashes, leaving other replicas out of sync. Since there is no central point which controls the whole replication process, group of replicas have no information, was the write request confirmed by a whole group or something has happened to a client and special action should be performed. The issue can be solved by immediate confirmation of a successfully completed write request sent by non-primary replicas to a primary one. As was mentioned earlier, each object has its own primary which serves reads, thus write confirmations of a modified object are sent to a particular primary, which accounts number of confirmations for the modified object. If the confirmation did not come from all replicas in a group, then after the timeout elapsed a primary can start synchronizing an object on its own. In order to be sure that confirmations are accounted correctly, each of them is marked with a timestamp taken from a source write request, thus reordered and outdated confirmations can be discarded. I would like to stress the point, that accounting of confirmations happens in RAM only at runtime and does not involve any disk operations. If one of replicas crashes after a client crash then the whole group of replicas (PG) changes its state, further write requests take another path and forwarded to the main primary in a group and objects synchronization would be started anyway. The READ RECENT rule in action ------------------------------ In client-driven replication the order in which replicas receive requests and update blocks is out of control, thus readers can receive inconsistent data (also called weak consistency model [8]). To ensure that a once read block will never return to its previous value (READ RECENT rule mentioned earlier) all attempts to read non consistent (not confirmed from all replicas) block has to be delayed or rejected with an explicit error. Consider this scenario: 1. Client1 fans out write requests to all replicas. 2. Write request reaches only the primary one, client1 crashes. 3. Concurrent client2 reads the same block, since primary replica has applied write request from client1, client2 reads the requested block successfully and observes the change made by client1. 4. Primary replica crashes and new primary is selected, resync process in a group (PG) is started. 5. Concurrent client2 reads again the same block from a new primary, but since no one else observes the change written to previous primary made by client1, client2 receives old data. This scenario breaks the READ RECENT rule and introduces data corruption. In order to guarantee that block is consistent, read from line 3. should be delayed or rejected till all replicas confirm, that block is persistent. This can be achieved by the same confirmation mechanism described earlier: block is treated as inconsistent if it was modified and not all confirmations are received. I do not expect any performance degradation for generic read loads and can quote Sage here: “Reads in shared read/write workloads are usually unaffected by write operations. However, reads of uncommitted data can be delayed until the update commits. This increases read latency in certain cases, but maintains a fully consistent behavior for concurrent read and write operations in the event that all OSDs in the placement group simultaneously fail and the write ack is not delivered” [7]. Another issue, which has to be investigated in detail, is a full outage of a group of replicas (PG). When replicas are come back some of the objects can be out of sync, and without versioned log there is no any possibility to distinguish what blocks were updated recently and thus have a higher timestamp. As was mentioned earlier READ RECENT rule has one property: if block has not been read since the modification, then it is irrelevant what version of a block can be taken as a master copy. Thus, if read of an inconsistent block is delayed till it is persistent on all replicas, any replica in a group may be a “donor” of this particular block. From the statement above it follows that non-atomic or partial writes can happen. Indeed, from a filesystem or an application which acts as a cluster client, this requires special handling of a write failure, such as log replay, for dealing with inconsistencies left behind. But it will assume that each block on all replicas in a group (PG) has just one value, so in this way group remains synchronized and future reads won’t report different content in case of a change of the primary replica which serves reads. Journal-less objectstore for IO path ------------------------------------ Write atomicity requires certain support from an underlying hardware or software. Different techniques like journals, COW or soft-updates can be used in order to guarantee atomicity, but for no doubts this feature comes with a high price of the IO performance degradation. Since each modern filesystem or a DBMS application itself can take care of data inconsistency, atomicity constraint for the objectstore can be relaxed. In order to provide performance close to a bare hard drive, each replica has to submit writes to an underlying hardware immediately and without any requirements for request ordering or data atomicity. As was mentioned earlier, the reading delay mechanism of non-persistent blocks makes synchronization of objects after a complete shutdown possible without knowing where is the recent update. However, full synchronization can take days if an object is big enough. The problem of long resync can be solved by bookkeeping a bitmap of a possibly-out-of-sync blocks of an object. The algorithm can be described in just one sentence: “Bits are set before a write commences, and are cleared when there have been no writes for a while.” [11]. In highly distributed storage solution where a group of replicas (PG) can consist of different replicas during the whole life of a cluster and members in a group constantly changing, it is important not only to track out-of-sync blocks of an object, but also to keep versions of such changes, so that to answer the following question with minimal computational cost: what has changed in the object between versions N and M? Having versions of block changes in mind, one important modification to bitmap algorithm can be proposed: bitmap of out-of-sync blocks is stored in a file with a timestamp of a first write request in the name; after a certain number of changed blocks each replica does a rotation of the bitmap file, so that new bitmap file is created with a timestamp of a first write request which initiated the bitmap rotation process. The major difference to what RAID 1 does is, that bits are never cleared, but new bitmap file is created instead. Bits of modified but not yet persistent blocks (not all confirmations are received from replicas) migrate to a new bitmap file, in order to guarantee that block synchronization will take place in the future in case of possible replica failure. As timestamps of client write requests always change forward and the time on clients is synchronized (major requirement of proposed hybrid client-driven replication model), each replica will have similar view of block changes, so the question about data difference between the two versions can be easily answered. Proposed rotation of bitmap files can occupy extra disk space on a replica, especially when new files are created and never deleted. Deletion of bitmap files of old versions is not a problem: N files can be kept, rotation process spawns new bitmap file with a recent timestamp, meanwhile a file with the oldest timestamp is removed. If for some reason there will be a need to restore changes of an object version, which bitmap file was removed, then full object resynchronization should be performed. Summary ------- Proposed changes should relax a lot of constraints on fast IO path in current Ceph implementation keeping strong data consistency between replicas and bring performance of a single client to almost bare hard drive bandwidths. Even if there are logical holes in the model described above (there are), I still believe that eliminating them will not be impossible. PS. And yes, because of the “write hole” problem [12] erasure coding replication won’t survive full group outage without atomicity guarantees on the objectstore side. Sorry for that. -- Roman [1] R. Golding, Weak-consistency group communication and membership, PhD thesis, University of California, Santa Cruz, 1992. [2] Petersen et al., “Flexible Update Propagation for weakly consistent replication”, Proc. of the 16th ACM Symposium on Operating Systems Principles (SOSP), 1997. [3] M. Rabinovich. N. Gehani. A. Kononov, “Scalable Update Propagation in Epidemic Replicated Databases”,Advances in Database Technology - EDBT'96, Lecture Notes in Computer Science Vol. 1057, Springer, pp. 207-222. [4] G. Wuu, A Bernstein. „Efficient Solutions to the Replicated Log and Dictionary Problems”, Proceedings of the third ACM Symposium on Principles of Distributed Computing, August 1984, pp. 233-242. [6] https://en.wikipedia.org/wiki/Strong_consistency [7] Sage A. Weil. Ceph: Reliable, Scalable, And High-Performance Distributed Storage, PhD thesis, University of California, Santa Cruz, 2007. [8] Jiayuan Zhang, Yongwei Wu†, Yeh-Ching Chung. PROAR: A Weak Consistency Model For Ceph [9] Precision Time Protocol (PTP/IEEE-1588) [10] R. H. Thomas, “A majority consensus approach to concurrency control for multiple copy databases,” ACM Trans. Database Syst., vol. 4, no. 2, pp. 180–209, 1979. [11] Cluster support for MD/RAID 1, https://lwn.net/Articles/674085/ [12] https://en.wikipedia.org/wiki/RAID
Hi Roman, I’ve often thought idly about what we could do if we gave up on the overbearing strict consistency Ceph provides and built something more specifically suited to serving up block devices, so it’s very cool to see somebody’s gotten more organized about it and written their thoughts down. I for one would be happy to discuss this topic at Cephalocon! I’ve read through this proposal with varying levels of attention so I may have missed something, but there are a few important points I think you’ve missed in your writeup that need addressing, and a few choices you’ve made that you’ll want to be ready to defend. :) The first and most important one is this: while a system like you describe could be *Ceph*, it is fundamentally and absolutely not *RADOS*. The transactions RADOS provides in its ordered log are not solely about recovery; we expose transactions and that ordered log in great detail to the user over the network protocol with operations like object append, object classes, compare-and-swap, the entire omap interface, and even by returning object versions on every write operation! These operations aren’t just novelties; RGW, RBD, and CephFS metadata schemes all rely on them implicitly and explicitly — and even for the “simple” RBD data objects you’re targeting, the changes you describe break how RADOS does snapshots. (I think the RBD data journal also relies on a number of these, but I’m not certain.) RADOS actually *is* a primitive database, not just a disk, and I don’t think we can usefully separate operations into the “management” and “data” division you suggest. (Among other things, any write op has the potential to change the object’s size and that needs to be ordered with truncate operations.) Now, making these changes isn’t necessarily bad if we want to develop a faster but less ridiculously-consistent storage system to better serve the needs of the interfaces that actually get deployed — I have long found it a little weird that RADOS, a strictly-consistent transactional object store, is one of the premier providers of virtual block-device IO and S3 storage. But if that’s the goal, we should embrace being not-RADOS and be willing to explicitly take much larger departures from it than just “in the happy path we drop ordering and fall back to backfill if there’s a problem”. The second big point is that if you want to have a happy path and a fallback ordered path, you’ll need to map out in a lot more detail how those interact and how the clients and OSDs switch between them. Ideas like this have come up before but almost every one (or literally every one?) has had a fatal flaw that prevented it actually being safe. Thirdly, you talk a lot about guaranteeing READ RECENCY and rejecting IOs from clients when they arrive at replicas in different orders — but I don’t see how you detect that case is occurring. If every client op has a timestamp associated with it, you need to remember all the client ops that might conflict with each other and then reject them as needed, which sounds an awful lot like an ordered log to me! You can probably do something with in-memory op logs and having the object primary tell replicas when an op is fully acked, but I haven’t thought it through… In terms of design choices you’ve suggested, I’m not really sure why you want to do client-side replication. It is frequently undesirable since OSDs tend to have lower latency and more bandwidth to their peers than the clients do to the OSDs; this system still has to do acks to a new per-object primary *anyway*; and the usual design reason to for client-side replication is because it lets the data store daemons be much simpler, but these OSDs are actually getting *more* complicated than our existing ones! Client-side replication op latency is going to be MAX(client network hop, client data transmission*3) + op permission checking + op processing time + disk commit time + client network hop whereas for primary-replication it will be client data transmission + op permission checking + max(OSD network hop, OSD data transmission*2) + op processing time + disk commit time + OSD network hop + network hop How those formulas compare in practice will vary but is often better for the OSD replication — which is certainly much simpler to work with and reason about. In a similar vein, I’m not sure what the point is of distributing reads out by having per-object read primaries. We already distribute reads by PG, and I guess the larger number of objects might fix balance problems if we have them, but that seems like it’s pushing the argument. Moreover it complicates the design by forcing replicas to keep track of more state and reduces cache efficiency of the cluster since we need at least some PG metadata in memory in more places. And I think this is more of a nit, but we really, really don’t want client clocks to be involved in any decision-making at all, even if we hope it’s just going to be for uncommon conflict resolutions. Sure, it is theoretically possible to get good clock sync if you control the environment, but it’s incredibly finicky. For instance, here’s a ticket where a monotonic clock is somehow going backwards in time: tracker.ceph.com/issues/43365 o_0 Luckily I don’t think the conflict resolution you’re using timestamps for actually needs them; we can probably design a logical clock of some description that will be safer and reasonably simple. -Greg On Thu, Jan 23, 2020 at 3:49 PM Roman Penyaev <rpenyaev@suse.de> wrote:
Hi Sage and all,
I would like to share some of my scattered thoughts regarding IO performance improvements in Ceph. I touch on topics such as replicated log model, atomicity and full journaling on the objectstore side and how these constraints can be relaxed on IO path in order to squeeze maximum from a hard drive, at the same time still respecting the strong data consistency between replicas.
Would be great to have a chance to discuss this in Seoul.
Proposal in a few lines (for time saving) -----------------------------------------
1. IO and management requests follow different paths:
1. Slow path for management requests (object creation/deletion, locks, etc) involves replicated log and primary-copy model, as it is right now.
2. Fast IO path (read, write requests) bypasses replicated log and makes clients responsible for sending data to each replica in a group (PG), I reference it as hybrid client-driven replication further in the text.
2. For the sake of simplicity client takes fast IO path only when group of replicas (PG) is in active and healthy state (active+client in terms of Ceph), otherwise client falls back to the slow path. Thus, client is not involved in the disaster recovery process (that's why hybrid).
3. Fast IO path (is taken only if group of replicas (PG) is in active and healthy state):
1. Reads of objects happen from different primaries in a group (PG), in order to spread the read load.
2. Writes are distributed by clients themselves to all replicas in a group (PG), avoiding one extra network hop.
4. Objectstore becomes journal-less and behaves similar to RAID 1, sacrificing atomicity and erasure coding (due to the "write hole" problem) for write performance, which becomes close to the write performance of a bare hard drive, but still keeping strong data consistency between replicas.
!!!!! CAUTION: many letters !!!!!
Introduction ------------
The most impressive IO performance numbers among products which provide data redundancy is certainly delivered by RAID and that is not a surprise: you just write a block to several disks in parallel, nothing more. Perfect.
Then why Ceph can't achieve the same performance as RAID 1 on IO path, doing plain old write-in-parallel thing, but supplemented with scalability, CRUSH object placement and all other beloved things which make Ceph so powerful?
The answer to this question lies in the replication design used by Ceph, namely log-based replication (PG log in Ceph terms), which is commonly used in storage and database systems and well described in many publications [1, 2, 3, 4]). Sequential replicated log indeed resolves issues related to atomicity, consistency, isolation and durability (this famous ACID buzzword acronym), especially in DBMS world where transactions are involved. But Ceph is a storage, not a database.
Modern hard drives do not provide atomicity, strict writes ordering or durability. Hardware breaks all the rules and relax the constraints for the sake of performance, and software has to deal with it. Every modern filesystem can survive crashes (journals, COW, soft-updates, etc approaches are used), each application which cares about data consistency and can't rely on weak guarantees of POSIX file API (any DBMS for example) uses same methods (journals, COW, etc) to avoid inconsistency. Why then a storage solution, which works below a filesystem and on top of a hardware, should provide such strong ACID properties for IO?
So what is a log-based replication which is a core of Ceph? Very simple: duplication (mirroring) of a log which consist of records describing storage operations. In order to duplicate something we have to be sure that an object which we duplicate has not been changed on the way, i.e. actually copy-paste does what it is supposed to do without nasty surprises. When we have a log of storage operations we need not only to deliver a recent record to a replica without corruption (and wrong order of operations in a log is a corruption) but also invoke this operation, which has been described in a log record. Not only that: new record in a log and operation, which is described by that record, should happen in one transaction, atomically, thus either we see a record and operation was performed, either no updates in a log and no operation consequences is visible.
Having such a wonderful log (which obviously can survive a crash or even a nuclear strike) we can very easily answer The Most Important question for a high scalable, self-healing storage product: what has happened on other replicas while one of them took a nap (crashed). In other words we need such a complicated mechanism only for one thing: just to tell the exact data difference (e.g. in blocks of data and operations), what has been changed since a crash.
Short quiz: can Сeph stay Ceph, but without any log-based replication? Yes, throw it away, no need to know the difference, just copy the whole bunch of data between replicas on any disaster recovery. Very slow on resyncing but fast on doing operations and simple. I'm, of course, exaggerating, but that is not so far from the truth.
Talking about log-based replication I've never mentioned why it actually impacts the IO performance. Here is why:
1. Each update operation on a group of replicas (PG in terms of Ceph) has to be strictly ordered (log should stay in the same order on all replicas) i.e. no any other operation is allowed till an operation, which has been just started, reaches a hard drive with all cache flushes involved (who poked the code knows the notorious pglock, which protects the replication log from corruption and makes it be equal on all other replicas).
2. Severe restrictions on how actually the objectstore should be implemented: data and metadata should be fully journaled, because a log record of a replicated operation is stored along with the data in atomic manner. And what is wrong with journal in terms of performance? Nothing is wrong, it is just incredibly slow. (As a hint for the curious: enable "data=journal" option for ext4 filesystem, or "allow_cow" for xfs or just run any load which performs random writes on BTRFS (cow is always enabled), and yes, I promise, you feel the difference immediately).
3. Communication with a group of replicas (PG) happens only through a primary one, where a primary is responsible for keeping log in sync with other replicas. This primary-copy model [7] increases IO latency adding one extra network hop.
All of the above about log-based replication in Ceph is about strong consistency, but not about performance. But can we have both? And what is actually a strong consistency? According to formal description "The protocol is said to support strong consistency if all accesses are seen by all parallel processes (or nodes, processors, etc.) in the same order (sequentially)" [6]. In simple words: one thread produces data to the same offset of a file, other threads read from the same offset, thus if strong consistency is respected readers never observe writes in a wrong order, e.g.:
Writer Reader 1 Reader 2 Reader 3 -------------- -------------- -------------- --------------- write(file, "A"); b0 = read(file); b0 = read(file); b1 = read(file); write(file, "B"); b0 = read(file); b1 = read(file); b1 = read(file);
In this example, readers are able to see a block of a file in the following states:
Reader 1 Reader 2 Reader 3 --------- ---------- ---------- b0 == "A" b0 == "A" b0 == "B" b1 == "B" b1 == "A" b1 == "B"
But what should never be observed and can be treated as a corruption is the following:
b0 == "B" b1 == "A"
Having that we can develop a simple rule: writes are not blocked and can come at any order, once a reader observes a change in a block, further reads to this block see the change. Most likely I describe here a wheel, which has some vivid name and was deeply buried in some publication in early 70th, but I do not care and call the rule as READ RECENT. The READ RECENT rule contains one splendid property: if read has never happened and order of writes is unknown, writes can be reordered regardless of their actual order. Practical example: there is a distributed storage where writes are unordered by nature; a full outage has happened and now replicas contain different blocks of data on the same offsets; read of the block has never happened after it was updated, thus we are able to bring replicas in sync choosing block from *any* replica. Marvelous. I will return to this highly important property when I start describing a new replication model.
It turns out that strong consistency is not about strict requests ordering in a whole group of replicas (PG) it is only about order of reads against writes to the same block of data. That's it. So the question is left unanswered: can we have both strong consistency and high performance of IO?
In order to answer this question, it is necessary to once again state the main requirements for the IO replication model, which remove the strict restrictions imposed by the log-based replication, positively affect performance and do not contradict strong consistency:
1. Get rid of extra hop on fast IO path by doing client-driven replication, at least when group of replicas (PG) is in active state and not doing any sort of disaster recovery.
2. Write requests are not strictly ordered to different offsets of an object and can be submitted to a hard drive in parallel.
3. Get rid of any journaling on fast IO path on objectstore side if possible.
These are major requirements of constraint relaxation which can bring storage IO performance close to a bare hard drive bandwidths keeping strong consistency. In the next chapter I will cover all the requirements and will show how it can be implemented in practice.
Separation of management requests from IO requests --------------------------------------------------
Requests in a storage cluster can be divided into two parts: management requests, which are object creation/deletion/listing, attributes setting/getting, lock management, etc; and IO requests, which do read or modify content of an object. The most prevailing requests are IO read and write requests, whose latency affect the overall performance of the entire cluster. The proposed requests separation has also a clear separation on metadata and data, which should be treated differently on the objectstore side, namely no journal should be involved in data modification (this will be discussed in detail below).
Separating IO from management requests makes it possible to have a different primary replicas in a group of replicas (PG). For example in order to distribute a read load, primary can be chosen by an object id using persistent hashing (e.g. hash ring as proposed here [8]) instead of having a single primary. Write requests require replication involved and as was mentioned earlier client-driven replication model can be chosen in order to minimize latencies of an extra hop.
Having different paths for several types of requests can be summarised as the following:
1. Management requests go through a persistent primary replica and log-based replication keeps strict ordering of operations in the entire group (PG). There are no changes to original Ceph architecture are proposed.
2. Read object requests are sent to different primaries according to some persistent hashing rule [8].
3. Write requests can follow two IO paths, where on one of the paths client is fully responsible for request replication and delivers requests to all replicas in a group (PG). This path is always taken when group of replicas (PG) is in active and healthy state. The second IO path always lies through a primary, thus all requests are equally ordered (like it is right now implemented in Ceph). This path is taken in order to simplify all corner cases when a group of replicas (PG) is not in an active state and performs resynchronization process.
Hybrid client-driven replication --------------------------------
Client-driven replication is quite self-descriptive: client is responsible for data delivery to replicas in a group (PG) avoiding one extra network hop, which exists in a primary-copy model. If client communicates with replicas in a group (PG) directly there is no longer the central point of synchronization, thus the one possible issue that needs to be considered is the possibility of write requests from several clients to come to replicas in different order:
Client 1 Client 2 -------- -------- sends A to replica1 sends B to replica1 sends A to replica2 sends B to replica2
Replica 1 Replica 2 --------- --------- A B B A
** replica1 writes B to the disk and then overwrites B with A replica2 writes A to the disk and then overwrites A with B
In this example both clients access the same block of the same object, but write requests become reordered differently because of the network. If this happened, then replicas can contain different data and they are out of sync. This issue has very bad consequences: future reads are undefined, especially if one of replicas crashed and clients start reading from another. This is definitely a data corruption. In order to solve the issue the order of writes to the same offset should be synchronized between replicas. Synchronization can be performed by marking each request with a timestamp, taking into consideration, that time flows equally on clients. Sub-microsecond time synchronization is not a problem [9], especially when there is the central point for all members - distributed state machine cluster, namely cluster of monitors in terms of Ceph.
Having time synchronized, client marks write requests with a timestamp. According to the Thomas Write Rule [10] outdated requests are discarded by timestamp-based concurrency control keeping the correct order. However, in the case of the client-driven replication it is impossible to discard a change on all replicas simultaneously. Instead outdated request should be repeated for all replicas in a group (PG), here is an example:
Client 1 Client 2 -------- -------- marks A with stamp 1 marks B with stamp 2 sends A to replica1 sends B to replica1 sends A to replica2 sends B to replica2
Replica 1 Replica 2 --------- -------------- -- on disk -- A B -- on disk -- B A
** replica1 writes B to the disk and rejects A with RETRY replica2 writes A to the disk and then overwrites A with B
Request A is not written by replica1, because it is older then B request, which has been applied recently. Instead replica1 replied on A request with the RETRY error, which forces the client to mark request A with a new timestamp and resend it again to the whole group of replicas (PG):
Client 1 -------- marks A with stamp 3 sends A to replica1 sends A to replica2
Replica 1 Replica 2 --------- --------- A A -- on disk -- B -- on disk -- B A
** replica1 overwrites B with A replica2 overwrites B with A
The next question rises: why do we need to repeat write operation on all replicas, but not only on those who have just replied with the error? Let's consider overlapping data (here I do not consider the reason why clients send overlapping write requests concurrently, obviously this is a bug on a client side, but nevertheless we keep replicas in sync):
Client 1 marks AAAA with stamp 1 Client 2 marks BBB with stamp 2 Client 3 marks C with stamp 3
Replica 1 Replica 2 --------- --------- C 3 BBB 2 C 3 AAAAA 1 AAAAA 1 --------- --------- below the line is the state on disk ABCBA AACAA
** replica1 writes AAAA, then overwrites the middle with BBB and then with C
replica2 writes AAAA and overwrites the middle with C; BBB request is rejected
Client2 receives the RETRY error and has to repeat BBB:
Client 2 marks BBB with stamp 4
Replica 1 Replica 2 --------- --------- BBB 4 BBB 4 -- on disk -- C 3 -- on disk -- BBB 2 C 3 AAAAA 1 AAAAA 1 -------------- -------------- below the line is the state on disk ABBBA ABBBA
On a second retry blocks on replicas become synchronized and write request is considered as completed and persistent on a drive. Since concurrent writes should never happen on well written client software (I expect distributed filesystems use lock primitives in order to prevent concurrent access) I do not expect any performance degradation because of frequent write retries, so current algorithm acts as a protection which keeps replicas in sync.
I would like to emphasize several points obtained from the description of the algorithm described above:
1. Time synchronization on clients does not need to be very accurate, even hundreds of millisecond accuracy is enough. Described time-based algorithm does not depend on actual physical time, also it does not depend on real (absolute) order of writes sent by concurrent clients. Instead algorithm forces distributed cluster members to have a single view on requests order, which is enough to decide should request be rejected or executed.
2. Hybrid client-driven replication does not involve clients into data recovery process, thus leaving this job to replicas (exactly as it is right now). Here I describe the fast IO path only when group of replicas (PG) is in active and fully synchronized state. When group of replicas (PG) is in resynchronization state or client sends management type of requests (not IO), then for the sake of simplicity all communication goes through the main primary replica, as it is right now implemented in Ceph.
Crash of a client in the middle of a replication ------------------------------------------------
Client-driven replication in contrast with a primary-copy model has another major issue which has to be considered in detail: crash of a client in the middle of a replication, that is, when client sends write request to one of replicas in a group (PG) and then crashes, leaving other replicas out of sync. Since there is no central point which controls the whole replication process, group of replicas have no information, was the write request confirmed by a whole group or something has happened to a client and special action should be performed.
The issue can be solved by immediate confirmation of a successfully completed write request sent by non-primary replicas to a primary one. As was mentioned earlier, each object has its own primary which serves reads, thus write confirmations of a modified object are sent to a particular primary, which accounts number of confirmations for the modified object. If the confirmation did not come from all replicas in a group, then after the timeout elapsed a primary can start synchronizing an object on its own.
In order to be sure that confirmations are accounted correctly, each of them is marked with a timestamp taken from a source write request, thus reordered and outdated confirmations can be discarded.
I would like to stress the point, that accounting of confirmations happens in RAM only at runtime and does not involve any disk operations. If one of replicas crashes after a client crash then the whole group of replicas (PG) changes its state, further write requests take another path and forwarded to the main primary in a group and objects synchronization would be started anyway.
The READ RECENT rule in action ------------------------------
In client-driven replication the order in which replicas receive requests and update blocks is out of control, thus readers can receive inconsistent data (also called weak consistency model [8]). To ensure that a once read block will never return to its previous value (READ RECENT rule mentioned earlier) all attempts to read non consistent (not confirmed from all replicas) block has to be delayed or rejected with an explicit error. Consider this scenario:
1. Client1 fans out write requests to all replicas.
2. Write request reaches only the primary one, client1 crashes.
3. Concurrent client2 reads the same block, since primary replica has applied write request from client1, client2 reads the requested block successfully and observes the change made by client1.
4. Primary replica crashes and new primary is selected, resync process in a group (PG) is started.
5. Concurrent client2 reads again the same block from a new primary, but since no one else observes the change written to previous primary made by client1, client2 receives old data.
This scenario breaks the READ RECENT rule and introduces data corruption. In order to guarantee that block is consistent, read from line 3. should be delayed or rejected till all replicas confirm, that block is persistent. This can be achieved by the same confirmation mechanism described earlier: block is treated as inconsistent if it was modified and not all confirmations are received.
I do not expect any performance degradation for generic read loads and can quote Sage here: “Reads in shared read/write workloads are usually unaffected by write operations. However, reads of uncommitted data can be delayed until the update commits. This increases read latency in certain cases, but maintains a fully consistent behavior for concurrent read and write operations in the event that all OSDs in the placement group simultaneously fail and the write ack is not delivered” [7].
Another issue, which has to be investigated in detail, is a full outage of a group of replicas (PG). When replicas are come back some of the objects can be out of sync, and without versioned log there is no any possibility to distinguish what blocks were updated recently and thus have a higher timestamp. As was mentioned earlier READ RECENT rule has one property: if block has not been read since the modification, then it is irrelevant what version of a block can be taken as a master copy. Thus, if read of an inconsistent block is delayed till it is persistent on all replicas, any replica in a group may be a “donor” of this particular block.
From the statement above it follows that non-atomic or partial writes can happen. Indeed, from a filesystem or an application which acts as a cluster client, this requires special handling of a write failure, such as log replay, for dealing with inconsistencies left behind. But it will assume that each block on all replicas in a group (PG) has just one value, so in this way group remains synchronized and future reads won’t report different content in case of a change of the primary replica which serves reads.
Journal-less objectstore for IO path ------------------------------------
Write atomicity requires certain support from an underlying hardware or software. Different techniques like journals, COW or soft-updates can be used in order to guarantee atomicity, but for no doubts this feature comes with a high price of the IO performance degradation. Since each modern filesystem or a DBMS application itself can take care of data inconsistency, atomicity constraint for the objectstore can be relaxed.
In order to provide performance close to a bare hard drive, each replica has to submit writes to an underlying hardware immediately and without any requirements for request ordering or data atomicity. As was mentioned earlier, the reading delay mechanism of non-persistent blocks makes synchronization of objects after a complete shutdown possible without knowing where is the recent update. However, full synchronization can take days if an object is big enough. The problem of long resync can be solved by bookkeeping a bitmap of a possibly-out-of-sync blocks of an object. The algorithm can be described in just one sentence: “Bits are set before a write commences, and are cleared when there have been no writes for a while.” [11].
In highly distributed storage solution where a group of replicas (PG) can consist of different replicas during the whole life of a cluster and members in a group constantly changing, it is important not only to track out-of-sync blocks of an object, but also to keep versions of such changes, so that to answer the following question with minimal computational cost: what has changed in the object between versions N and M?
Having versions of block changes in mind, one important modification to bitmap algorithm can be proposed: bitmap of out-of-sync blocks is stored in a file with a timestamp of a first write request in the name; after a certain number of changed blocks each replica does a rotation of the bitmap file, so that new bitmap file is created with a timestamp of a first write request which initiated the bitmap rotation process. The major difference to what RAID 1 does is, that bits are never cleared, but new bitmap file is created instead. Bits of modified but not yet persistent blocks (not all confirmations are received from replicas) migrate to a new bitmap file, in order to guarantee that block synchronization will take place in the future in case of possible replica failure.
As timestamps of client write requests always change forward and the time on clients is synchronized (major requirement of proposed hybrid client-driven replication model), each replica will have similar view of block changes, so the question about data difference between the two versions can be easily answered.
Proposed rotation of bitmap files can occupy extra disk space on a replica, especially when new files are created and never deleted. Deletion of bitmap files of old versions is not a problem: N files can be kept, rotation process spawns new bitmap file with a recent timestamp, meanwhile a file with the oldest timestamp is removed. If for some reason there will be a need to restore changes of an object version, which bitmap file was removed, then full object resynchronization should be performed.
Summary -------
Proposed changes should relax a lot of constraints on fast IO path in current Ceph implementation keeping strong data consistency between replicas and bring performance of a single client to almost bare hard drive bandwidths.
Even if there are logical holes in the model described above (there are), I still believe that eliminating them will not be impossible.
PS. And yes, because of the “write hole” problem [12] erasure coding replication won’t survive full group outage without atomicity guarantees on the objectstore side. Sorry for that.
-- Roman
[1] R. Golding, Weak-consistency group communication and membership, PhD thesis, University of California, Santa Cruz, 1992. [2] Petersen et al., “Flexible Update Propagation for weakly consistent replication”, Proc. of the 16th ACM Symposium on Operating Systems Principles (SOSP), 1997. [3] M. Rabinovich. N. Gehani. A. Kononov, “Scalable Update Propagation in Epidemic Replicated Databases”,Advances in Database Technology - EDBT'96, Lecture Notes in Computer Science Vol. 1057, Springer, pp. 207-222. [4] G. Wuu, A Bernstein. „Efficient Solutions to the Replicated Log and Dictionary Problems”, Proceedings of the third ACM Symposium on Principles of Distributed Computing, August 1984, pp. 233-242. [6] https://en.wikipedia.org/wiki/Strong_consistency [7] Sage A. Weil. Ceph: Reliable, Scalable, And High-Performance Distributed Storage, PhD thesis, University of California, Santa Cruz, 2007. [8] Jiayuan Zhang, Yongwei Wu†, Yeh-Ching Chung. PROAR: A Weak Consistency Model For Ceph [9] Precision Time Protocol (PTP/IEEE-1588) [10] R. H. Thomas, “A majority consensus approach to concurrency control for multiple copy databases,” ACM Trans. Database Syst., vol. 4, no. 2, pp. 180–209, 1979. [11] Cluster support for MD/RAID 1, https://lwn.net/Articles/674085/ [12] https://en.wikipedia.org/wiki/RAID _______________________________________________ Dev mailing list -- dev@ceph.io To unsubscribe send an email to dev-leave@ceph.io
Hi Gregory, On 2020-01-26 07:58, Gregory Farnum wrote:
Hi Roman, I’ve often thought idly about what we could do if we gave up on the overbearing strict consistency Ceph provides and built something more specifically suited to serving up block devices, so it’s very cool to see somebody’s gotten more organized about it and written their thoughts down. I for one would be happy to discuss this topic at Cephalocon!
Yes, would be great to meet and to discuss the topic in person.
I’ve read through this proposal with varying levels of attention so I may have missed something, but there are a few important points I think you’ve missed in your writeup that need addressing, and a few choices you’ve made that you’ll want to be ready to defend. :)
First of all thanks for your time. It is always hard to get through someone else’s thoughts.
The first and most important one is this: while a system like you describe could be *Ceph*, it is fundamentally and absolutely not *RADOS*. The transactions RADOS provides in its ordered log are not solely about recovery; we expose transactions and that ordered log in great detail to the user over the network protocol with operations like object append, object classes, compare-and-swap, the entire omap interface, and even by returning object versions on every write operation!
Those operations you've mentioned are perfectly fit synchronous path and can follow the log as it is right now (I attribute them to management operations). I suppose the only concurrent access which we deal with is access to a single object from different clients, right? (otherwise, why client, which issues any two operations which has to land on a disk in a specific order, does not care himself about the order? Like any fs or dbms, etc do). Append operation for example. I can imagine the situation when two clients append a record to an object which acts as a journal (I'm speculating, but the case seems valid). Those two want a chunk in the object in full ownership, which accidentally can't be overwritten by someone else. Those two append operations go through a synchronous path and two client requests eventually will be somehow ordered on the primary (the order is undefined, because access is concurrent, but nobody cares). And this "somehow ordered" has a strong guarantee that these clients eventually will have different offsets in ownership. If another client breaks the convention and issues a write IO to a random offset of this journal object, then obviously this client is naughty and introduces a data corruption. And seems from this nasty behavior there is no any protection even with the synchronous path through a single primary (there is an undefined access order from different clients, though this access is serialized on the primary). A good example is a simple variable in memory (move away from transactions and storages). Two threads have a convention introduced by a developer, that the variable is shared and can be accessed concurrently. In order to protect the variable from the concurrent access developer has to do special things (locking, atomic instructions, etc). If one of the threads break the convention (e.g. does not use an atomic instruction in order to do an increment), then you have a corruption. Developer *has* to think about many things when memory model is weak (read/write barriers, cpu caches, etc) and usually this affects the performance. But when variable is not shared, then why read/write access to that variable has to follow all the complicated conventions on a fast path? IMO this example from the programming world has a strong parallel with the data access for the distributed storage. If you maintain a journal or any object which is shared, then special API should be provided (as it is right now) to guarantee some sorts of specific data mutation effects. You also mentioned the following operations: "compare-and-swap, the entire omap interface, and even by returning object versions on every write operation!". Let me try to picture how they could be implemented. Compare-and-swap: access serialized through the primary, thus primary does compare and if compare succeeds does log update (log is persistent), then write is issued to the disk and same write operation is issued to other replicas. Other replicas do data update, without compare. If there is an inflight write IO, which bypasses compare-and-swap convention, then block will be corrupted. Corruption does not mean, that replicas will be out of sync, but corruption means that data chunk will be inconsistent, i.e. client gets what it does not expect. But this is fine! We can always return to the example with threads and variable: two threads invoke compare-and-swap operations, the third one does not. Obviously the third one corrupts the data. omap interface + xattr: is not an IO, can go fully through a log, like it is right now. object versions on every write operation: if each write has a monotonic timestamp, then why it can't be used as particular version of an object? Here this thingy can be different, to current use-cases, but frankly I do not see here the whole picture, so do not want to speculate (need some particular examples).
These operations aren’t just novelties; RGW, RBD, and CephFS metadata schemes all rely on them implicitly and explicitly — and even for the “simple” RBD data objects you’re targeting, the changes you describe break how RADOS does snapshots.
rados snapshots are based on clone, right? Clone operation should follow the sync path (through the single primary) but still can be a bit tricky (requires object to be identical on all replicas to the moment, when clone is done) and can be implemented by communicating between replicas, where primary is the main coordinator. Here is what I imagine (some sort of lazy data migration) 1. hey, replicas, do object cloning, right now! here is the timestamp when we start! [after a while, replicas notify they are done, a new object is presumably is different on replicas, but since each replica knows when clone op is started then it will not be difficult for replicas to catch-up the final object state, when clone op is finished] 2. hey, replicas, are you done? Good, here is the end timestamp, when clone is finished, let's exchange what is missing. Again, here the whole logic does not care about other IO which are coming meanwhile. What is important for cloned object is to be identical on all replicas. If IO has not been stopped while object is cloning, then, obviously, clients know what they are doing, thus cloned object can be at any state (what is guaranteed, that the state will be equal on all replicas).
(I think the RBD data journal also relies on a number of these, but I’m not certain.) RADOS actually *is* a primitive database, not just a disk, and I don’t think we can usefully separate operations into the “management” and “data” division you suggest.
Everything which is not plain read/write is treated as management or metadata requests.
(Among other things, any write op has the potential to change the object’s size and that needs to be ordered with truncate operations.)
Why these two operations have to be ordered? No, I will ask another way. Why distributed storage should care about the order of these two operations? That what I do not understand. Why client can't be responsible for proper waiting of IO and only then issuing a truncate? (direct analogy: you issue an IO to your file and do not wait for a completion, then you truncate your file, what is the result?) But if we are talking about concurrent clients case, when one of the clients issues write, meanwhile another one issues truncate, than I do not understand how does the sync log help, because the primary replica can receive these two requests at any order (we assume no proper locking is used, right?)
Now, making these changes isn’t necessarily bad if we want to develop a faster but less ridiculously-consistent storage system to better serve the needs of the interfaces that actually get deployed — I have long found it a little weird that RADOS, a strictly-consistent transactional object store, is one of the premier providers of virtual block-device IO and S3 storage. But if that’s the goal, we should embrace being not-RADOS and be willing to explicitly take much larger departures from it than just “in the happy path we drop ordering and fall back to backfill if there’s a problem”.
Current constraints are blockers for the IO performance. It does not matter how much we squeeze from the CPU (crimson project), unless we can't relax IO ordering or reduce journaling effects, the overall CPU cycles improvements can be not so impressive. so I hope Ceph can make a step forward and be less conservative, especially when we have a hardware, which breaks all the possible rules.
The second big point is that if you want to have a happy path and a fallback ordered path, you’ll need to map out in a lot more detail how those interact and how the clients and OSDs switch between them. Ideas like this have come up before but almost every one (or literally every one?) has had a fatal flaw that prevented it actually being safe.
Here I rely on a fact, that replicas know the PG state (as it is right now). If PG is active and clean then replica accepts IO. If not - IO is rejected with the proper error: "dear client, go to the primary, I'm not in the condition to serve your request, but primary can". Here several scenarios are possible. Client was the first one who observes a replica in not a healthy state. We can expect all other replicas will observe the same not healthy state sooner, but client can propagate this information to other replicas in PG (need to be discussed in detail). Another scenario is that client was slower and the whole PG on all replicas is observed as not healthy. Then client takes "the primary" path and talks to the primary while peering, syncing etc.
Thirdly, you talk a lot about guaranteeing READ RECENCY and rejecting IOs from clients when they arrive at replicas in different orders — but I don’t see how you detect that case is occurring. If every client op has a timestamp associated with it, you need to remember all the client ops that might conflict with each other and then reject them as needed, which sounds an awful lot like an ordered log to me!
There is only one client operation which we care on fast IO path: write operation. We need to remember a timestamp of write operation to a certain offset of an object in order to delay reads to a not persistent block. This structure is not a log, rather an rb-tree or hash table in-memory.
You can probably do something with in-memory op logs and having the object primary tell replicas when an op is fully acked, but I haven’t thought it through…
This is a in-memory structure, which is not supposed to be persistent. Imagine any simple rb-tree or hash table, which belongs to an object and has an offset of a block as a key and a timestamp as a value. When replica crashes the whole peering and syncing procedure is performed, where everything is serialized by a primary, thus this structure is not needed while PG is not in a clean and healthy state. In order not to bloat this structure infinitely by tracking all updates to all blocks of all objects replicas can have a protocol, where primary is an initiator and sends to all replicas in a heartbeat (or each minute, 10 minutes, does not matter) highest timestamp, and replicas evict all key-value pairs for the object, where values are lower than this timestamp. This will guarantee, that replicas won't accept requests with the timestamp lower than this value. If any comes, then replica has to reject and to ask client to repeat the request, obviously with a newer timestamp.
In terms of design choices you’ve suggested, I’m not really sure why you want to do client-side replication.
*Hybrid* client-side replication :) When client is responsible for fanning out write requests only in case of healthy pg.
It is frequently undesirable since OSDs tend to have lower latency and more bandwidth to their peers than the clients do to the OSDs;
Latency is the answer. I want to squeeze everything from RDMA. For current Ceph RDMA is dead. Basically for current implementation any per-client improvements on transport side bring nothing. (I spent some time poking the protocol v1 and had a good speed up on transport side, which is unnoticed for the whole per-client IO performance. sigh)
this system still has to do acks to a new per-object primary *anyway*;
Yes, but that affects *only* reads following writes to the same offset of an object. Acks are needed *only* to delay reads to not fully persistent blocks. (READ RECENT rule in action). Acks do not affect writes. Writes come at any order. Acks do not affect reads to other blocks of that object. Again: 1. All replicas accept write request from a client (do write to the disk, etc). 2. All replicas send ack to the client and at the same time send acks to the primary. So primary and client can receive acks at the same time (or in different order). If client is not lucky enough and then immediately (after the write request) issues a read request to the primary replica to the same object offset, then this read *can* be delayed (rejected).
and the usual design reason to for client-side replication is because it lets the data store daemons be much simpler, but these OSDs are actually getting *more* complicated than our existing ones! Client-side replication op latency is going to be MAX(client network hop, client data transmission*3) + op permission checking + op processing time + disk commit time + client network hop whereas for primary-replication it will be client data transmission + op permission checking + max(OSD network hop, OSD data transmission*2) + op processing time + disk commit time + OSD network hop + network hop How those formulas compare in practice will vary but is often better for the OSD replication — which is certainly much simpler to work with and reason about.
Your equation is a bit too much for me. My logic is simple: client writes to several replicas without any constraints, directly to disks, gets all acks and write request is considered as completed. That is fast IO path. Again, acks from replicas to the primary are not involved, this is a different mechanism.
In a similar vein, I’m not sure what the point is of distributing reads out by having per-object read primaries. We already distribute reads by PG, and I guess the larger number of objects might fix balance problems if we have them, but that seems like it’s pushing the argument. Moreover it complicates the design by forcing replicas to keep track of more state and reduces cache efficiency of the cluster since we need at least some PG metadata in memory in more places.
Frankly, I liked the idea that reads can be served by different primaries in PG. I read the paper (PROAR something something) and thought that this can be taken and applied to what I have in my mind.
And I think this is more of a nit, but we really, really don’t want client clocks to be involved in any decision-making at all, even if we hope it’s just going to be for uncommon conflict resolutions. Sure, it is theoretically possible to get good clock sync if you control the environment, but it’s incredibly finicky. For instance, here’s a ticket where a monotonic clock is somehow going backwards in time: tracker.ceph.com/issues/43365 o_0 Luckily I don’t think the conflict resolution you’re using timestamps for actually needs them; we can probably design a logical clock of some description that will be safer and reasonably simple.
We do not need clocks. Physical clocks. All we need is something ticking in one direction. Resolution is also not very much important (hundreds of ms should be pretty enough, I think). This time-based concurrency control is needed only to guarantee certain order on replicas in case of concurrent writes to the same offset of an object. If no concurrent writes happen (locks are used, etc) - then timestamp mechanism can be even stayed unnoticed. -- Roman
On Mon, Jan 27, 2020 at 2:58 PM Roman Penyaev <rpenyaev@suse.de> wrote:
rados snapshots are based on clone, right? Clone operation should follow the sync path (through the single primary) but still can be a bit tricky (requires object to be identical on all replicas to the moment, when clone is done) and can be implemented by communicating between replicas, where primary is the main coordinator. Here is what I imagine (some sort of lazy data migration)
Uh, they are clones, but not in the way you're thinking/hoping. Client IO *can* (but does not need to) include a SnapSet, which contains data about the snapshots that logically exist (but may or may not have been seen by any particular object yet). When the client does a write with a snapid the object doesn't already contain, the OSD does a clone locally. And then any subsequent write applies to the new head, not the old snapid. So unfortunately neither the client nor the OSD has the slightest idea whether a particular write operation requires any snapshot work until it arrives at the OSD. <snip>
Everything which is not plain read/write is treated as management or metadata requests.
(Among other things, any write op has the potential to change the object’s size and that needs to be ordered with truncate operations.)
Why these two operations have to be ordered? No, I will ask another way. Why distributed storage should care about the order of these two operations? That what I do not understand. Why client can't be responsible for proper waiting of IO and only then issuing a truncate? (direct analogy: you issue an IO to your file and do not wait for a completion, then you truncate your file, what is the result?)
But if we are talking about concurrent clients case, when one of the clients issues write, meanwhile another one issues truncate, than I do not understand how does the sync log help, because the primary replica can receive these two requests at any order (we assume no proper locking is used, right?)
If a client dispatches multiple operations on a single object, we guarantee they are ordered in the same order they were dispatched by the client. So he can do async truncate, async write, async read, async append, whatever from a single thread and we promise to process them in that order. Some of that could probably be maintained in the client library rather than on the OSDs, but not all of it given the timestamp-based retries you describe and the problem of snapshots I mentioned above. Basically what I'm getting at is that given the way the RADOS protocol works, we really don't have any ops which are plain read/write. Especially including some of the ones you care about most -- for instance, RBD volumes without an object map include an IO hint on every write, to make sure that any newly-created objects get set to the proper 4MB size. These IO hints mean they're all compound operations, not single-operation writes! Of course, all these issues are not the result of changing our durability guarantees, but of trying to provide client-side replication...
Now, making these changes isn’t necessarily bad if we want to develop a faster but less ridiculously-consistent storage system to better serve the needs of the interfaces that actually get deployed — I have long found it a little weird that RADOS, a strictly-consistent transactional object store, is one of the premier providers of virtual block-device IO and S3 storage. But if that’s the goal, we should embrace being not-RADOS and be willing to explicitly take much larger departures from it than just “in the happy path we drop ordering and fall back to backfill if there’s a problem”.
Current constraints are blockers for the IO performance. It does not matter how much we squeeze from the CPU (crimson project), unless we can't relax IO ordering or reduce journaling effects, the overall CPU cycles improvements can be not so impressive.
so I hope Ceph can make a step forward and be less conservative, especially when we have a hardware, which breaks all the possible rules.
The second big point is that if you want to have a happy path and a fallback ordered path, you’ll need to map out in a lot more detail how those interact and how the clients and OSDs switch between them. Ideas like this have come up before but almost every one (or literally every one?) has had a fatal flaw that prevented it actually being safe.
Here I rely on a fact, that replicas know the PG state (as it is right now). If PG is active and clean then replica accepts IO. If not - IO is rejected with the proper error: "dear client, go to the primary, I'm not in the condition to serve your request, but primary can".
Here several scenarios are possible. Client was the first one who observes a replica in not a healthy state. We can expect all other replicas will observe the same not healthy state sooner, but client can propagate this information to other replicas in PG (need to be discussed in detail).
"Not a healthy state" isn't really meaningful in Ceph — we make decisions based on the settings of the newest OSDMap we have access to, but peer OSDs might or might not match that state. When the primary processes an OSDMap marking one of the peers down and he sets it to degraded, there's a window where the peers haven't seen that update. The clients will probably take even longer. And merely not getting an op reply as fast as the client wants isn't indicative of anything that RADOS cares about. Those states and the transitions between them and the recovery logic for ops-in-flight are all very hard to get right, and having the solutions mapped out in detail is a requirement for merging any kind of change in RADOS. <snip>
*Hybrid* client-side replication :) When client is responsible for fanning out write requests only in case of healthy pg.
It is frequently undesirable since OSDs tend to have lower latency and more bandwidth to their peers than the clients do to the OSDs;
Latency is the answer. I want to squeeze everything from RDMA. For current Ceph RDMA is dead. Basically for current implementation any per-client improvements on transport side bring nothing. (I spent some time poking the protocol v1 and had a good speed up on transport side, which is unnoticed for the whole per-client IO performance. sigh)
Can you explain why client-side replication over RDMA is a better idea than over ethernet IP? Like I said with math, I think in most cases it is actually slower, and it DEFINITELY makes harder all the other kinds of changes you want to make. I think you will be a lot happier if you drop that. (Also: we are doing a lot of work where read-from-replica will become desirable for things like rack-local reads and not being able to do that would be sad.) -Greg
On 2020-02-03 13:06, Gregory Farnum wrote:
On Mon, Jan 27, 2020 at 2:58 PM Roman Penyaev <rpenyaev@suse.de> wrote:
rados snapshots are based on clone, right? Clone operation should follow the sync path (through the single primary) but still can be a bit tricky (requires object to be identical on all replicas to the moment, when clone is done) and can be implemented by communicating between replicas, where primary is the main coordinator. Here is what I imagine (some sort of lazy data migration)
Uh, they are clones, but not in the way you're thinking/hoping. Client IO *can* (but does not need to) include a SnapSet, which contains data about the snapshots that logically exist (but may or may not have been seen by any particular object yet). When the client does a write with a snapid the object doesn't already contain, the OSD does a clone locally. And then any subsequent write applies to the new head, not the old snapid. So unfortunately neither the client nor the OSD has the slightest idea whether a particular write operation requires any snapshot work until it arrives at the OSD.
Yes, here what I've missed is the fact, that there is no any special command for doing a local clone, the IO with different snapid itself is the initiator of a clone. But even this does not change the main logic: since each replica receives the same IO with different snap id which should spawns a local clone, it should not be difficult to make this cloned object in sync on all replicas and then reply to the client with IO completion. But this extra logic will be needed only in the case of client-based replication. Let's forget about it. I feel that this is quite a popular proposal for Ceph and people tend to defend exactly this particular case. I still do not refuse the idea to have a client responsible for fanning out the write IOs, but what I want to stress, that it is not that important. It is just the option which I dream to have in my-perfect-storage. But what is important in what I proposed is relaxation of strong ordering.
<snip>
Everything which is not plain read/write is treated as management or metadata requests.
(Among other things, any write op has the potential to change the object’s size and that needs to be ordered with truncate operations.)
Why these two operations have to be ordered? No, I will ask another way. Why distributed storage should care about the order of these two operations? That what I do not understand. Why client can't be responsible for proper waiting of IO and only then issuing a truncate? (direct analogy: you issue an IO to your file and do not wait for a completion, then you truncate your file, what is the result?)
But if we are talking about concurrent clients case, when one of the clients issues write, meanwhile another one issues truncate, than I do not understand how does the sync log help, because the primary replica can receive these two requests at any order (we assume no proper locking is used, right?)
If a client dispatches multiple operations on a single object, we guarantee they are ordered in the same order they were dispatched by the client. So he can do async truncate, async write, async read, async append, whatever from a single thread and we promise to process them in that order.
Yes, exactly. RADOS guarantees that a single thread can throw out many async requests and these requests have exactly the same sequence on each replica as these requests were sent from the thread. This is what imposes bunch of restrictions on major layers: PGLog and ObjectStore. So my question is: what are exactly the cases when rbd or cephfs need to throw bunch of overlapping requests? (under overlapping I mean pairs like: read and write to the same offset, create and delete of the same object, truncate and write, etc). Since I don't see the whole complicated picture I can speculate only using the simple facts: vfs layer in the kernel distinguishes metadata path from data path, so fs has to be sure that metadata is durable on the disk, before any IO comes, thus you have to wait for completion of metadata updates; block layer in its turn does not care about ordering, thus requests ordering and flushes is the responsibility of fs on top. So RBD (since it is a block device) should not care about ordering either. Of course metadata path is different (rbd layering, snapshots, etc), but again why RBD can't wait for a completion of metadata requests? And the crucial thing which I want to understand is would it be possible to change clients (cephfs and rbd) in order to relax ordering and make an explicit wait for metadata requests? The negative answer on this question makes the whole proposal and discussion on this topic senseless, because client-based replication (on which we were concentrated so far) is in my wish list and does not influence (or at least not so much) the whole picture.
Some of that could probably be maintained in the client library rather than on the OSDs, but not all of it given the timestamp-based retries you describe and the problem of snapshots I mentioned above.
Not all of them, that's why those which can not, go through the primary. But I got your point.
Basically what I'm getting at is that given the way the RADOS protocol works, we really don't have any ops which are plain read/write. Especially including some of the ones you care about most -- for instance, RBD volumes without an object map include an IO hint on every write, to make sure that any newly-created objects get set to the proper 4MB size. These IO hints mean they're all compound operations, not single-operation writes!
Seems in RBD you already have two paths: w/ and w/o object map, right? Then why a new path with a raw CEPH_OSD_OP_WRITE can't be a modification which let's IO go straight to the replica and then straight to the disk?
Of course, all these issues are not the result of changing our durability guarantees, but of trying to provide client-side replication...
Ok, let's remove client-side replication from a discussion for a while. RADOS ordering constraints - this is what seems important.
Now, making these changes isn’t necessarily bad if we want to develop a faster but less ridiculously-consistent storage system to better serve the needs of the interfaces that actually get deployed — I have long found it a little weird that RADOS, a strictly-consistent transactional object store, is one of the premier providers of virtual block-device IO and S3 storage. But if that’s the goal, we should embrace being not-RADOS and be willing to explicitly take much larger departures from it than just “in the happy path we drop ordering and fall back to backfill if there’s a problem”.
Current constraints are blockers for the IO performance. It does not matter how much we squeeze from the CPU (crimson project), unless we can't relax IO ordering or reduce journaling effects, the overall CPU cycles improvements can be not so impressive.
so I hope Ceph can make a step forward and be less conservative, especially when we have a hardware, which breaks all the possible rules.
The second big point is that if you want to have a happy path and a fallback ordered path, you’ll need to map out in a lot more detail how those interact and how the clients and OSDs switch between them. Ideas like this have come up before but almost every one (or literally every one?) has had a fatal flaw that prevented it actually being safe.
Here I rely on a fact, that replicas know the PG state (as it is right now). If PG is active and clean then replica accepts IO. If not - IO is rejected with the proper error: "dear client, go to the primary, I'm not in the condition to serve your request, but primary can".
Here several scenarios are possible. Client was the first one who observes a replica in not a healthy state. We can expect all other replicas will observe the same not healthy state sooner, but client can propagate this information to other replicas in PG (need to be discussed in detail).
"Not a healthy state" isn't really meaningful in Ceph — we make decisions based on the settings of the newest OSDMap we have access to, but peer OSDs might or might not match that state. When the primary processes an OSDMap marking one of the peers down and he sets it to degraded, there's a window where the peers haven't seen that update. The clients will probably take even longer.
Since clients are the request initiators they will immediately observe the difference in osdmap version just because one of replicas replies back with osdmap version > than client knows about. Here there is no any difference between client which acts as the primary in client- driven replication and a primary in primary-copy model.
And merely not getting an op reply as fast as the client wants isn't indicative of anything that RADOS cares about. Those states and the transitions between them and the recovery logic for ops-in-flight are all very hard to get right, and having the solutions mapped out in detail is a requirement for merging any kind of change in RADOS.
In a client-driven case I talk about raw CEPH_OSD_OP_WRITE* requests only (others follow the primary path). So recovery for this particular case (OP_WRITE* requests) is block based and does not imply any log-based replication. And yes, this brakes RADOS guarantees: WRITE requests are not ordered in respect to other requests.
<snip>
*Hybrid* client-side replication :) When client is responsible for fanning out write requests only in case of healthy pg.
It is frequently undesirable since OSDs tend to have lower latency and more bandwidth to their peers than the clients do to the OSDs;
Latency is the answer. I want to squeeze everything from RDMA. For current Ceph RDMA is dead. Basically for current implementation any per-client improvements on transport side bring nothing. (I spent some time poking the protocol v1 and had a good speed up on transport side, which is unnoticed for the whole per-client IO performance. sigh)
Can you explain why client-side replication over RDMA is a better idea than over ethernet IP?
Seems there is a confusion introduced by me. I do not want to mix RDMA and client-side replication cases, so let me rephrase my previous answer: if we have a client-driven replication and no ordering on IO then it would be great to have an RDMA transport, because then we would have a microseconds latency from a client to all replicas. If we do not have a client-drive replication, but read/write IO ordering is relaxed and writes can go directly to disk bypassing journaling on objectstore side, then it would be also great to have an RDMA transport, but with one extra network hop, so latency is increased, but ok, I can deal with it. But if we have log-based replication for IO (what we have just right now), strict ordering for the whole PG, full journaling on all the data, then it does not matter what transport to use - transport is not a bottleneck, so of course in this case TCP (UDP) socket perfectly copes with its task. No doubts. So again: I just do not want an extra hop (client-driven replication). And for me latency matters (thus RDMA).
Like I said with math, I think in most cases it is actually slower,
My equations are much simpler :) Having one extra hop on the fast IO path doubles network latency.
and it DEFINITELY makes harder all the other kinds of changes you want to make. I think you will be a lot happier if you drop that.
Let's stop discussing it for a while. RADOS API ordering constraints are of much greater importance to me. So if is possible to modify clients in order to teach them to wait for completions properly and never let overlapping IO happen (not-RADOS anymore), then would be great to continue discussion on that topic. If this is an impossible task - well, then cephfs/rbd are not good candidates and probably other cluster file systems can fit better to cope with more relaxed API.
(Also: we are doing a lot of work where read-from-replica will become desirable for things like rack-local reads and not being able to do that would be sad.)
What is this exactly rack-local reads? Could you please elaborate or give me the link? -- Roman
participants (2)
-
Gregory Farnum
-
Roman Penyaev