Tuesday, March 15, 2011

Relativity for Programmers (A.K.A. Oh CAP!!!)

When you first start to learn physics you typically learn Newtonian Mechanics. Objects have inertia. Force is mass times acceleration. For every action there is an equal and opposite reaction. These all seem straightforward.

Albert Einstein turned the world on its head. Everything is relative. Time is relative. Simultaneity is relative. There is no universal clock.

The same thing happened in the computer science world, not with a bang or the attention that was given relativistic physics, but with a small crowd paying attention. CAP Theorem has the same implications for computer scientists as relativity had for physicists, but no one is really paying attention.

Computer scientists may dream of a fully consistent database distributed across a network, capable of two-phase commit and typical consistency guarantees. Not many think about the implications of such a database.

Imagine you had your database split across two datacenters. Let's call them Foo and Bar. While at one point in time, Foo and Bar could talk, now they can't. Perhaps a clumsy janitor spilled the bucket for his mop, and it destroyed all of your routing hardware between your datacenters. Some customers are accessing Foo and some are accessing Bar. If they want to perform a read, they'll get data that's possibly stale. If they want to perform a write, what happens?

CAP Theorem

CAP Theorem is possibly the most important property of distributed systems that you can possibly understand. It's been motherfucking proven by computer scientists, bitches! So what does it state? The core idea is that consistency which is both instantaneous and global is impossible, except on a single node. As soon as you have more than node storing data for you, you either have to sacrifice availability or consistency. Much like how you can only infer the state of the universe from old light beams hitting your light cone in relativistic physics, distributed systems can only infer the state of other nodes via the protocols they communicate with. These protocols can fall into one of three different forms per the CAP theorem:
  • CP: we have masters you have to listen to, bitch slaves. You can try to change the cluster state but all changes have to go through the masters, and if your master is split, you can't modify any state you bitch submissive node
  • AP: sure, we'll accept reads and writes. We'll try to eventually resolve any conflicts in the event of a netsplit. If we're cool we'll let you specify your own conflict resolution mechanism in the event of conflicting writes, otherwise we'll just do last writer wins.
  • CA: the network broke? Whoa. I was totally not expecting that. I was just happily doing bongrips until you barged in. I'm so high I don't even know what's going on.
If you're writing a datastore you consider to be "CA", you're doing it wrong. Fortunately, most datastores that claim to have "CA" properties are actually CP. That is to say, in the event of a network partition, they sacrifice availability. Reads to the cluster hopefully work, but writes shouldn't. Writes should error or time out for a consistent system. Any system that functions this way is in fact "CP". That is to say: it provides consistency, but in the event of a netsplit, you lose availability, at least for writes. Ideally these systems still provide stale reads.

Calling your system CA is an admission of the fact that if a partition separation occurs, and due to writes each partition has a separate view of the world, when the netsplit resolves your partitions have no mechanism for resolving conflicting states between partitions and thus your datastore is just fucked. Short of a system administrator picking which view of the world they consider to be the best and blowing away the state on the other nodes, the system state is going to be inconsistent and irresolvable.

So what are the alternatives which are partition tolerant and don't break in the event that the janitor spills mopwater on the router that routes packets between your datacenters?

Option #1: sacrifice consistency for availability

This option lets clients read and write from any partition. When connectivity between partitions is restored, there's a plan for resolving all of the writes into a consistent world state. The simplest plan is last writer wins, which is used by Cassandra. Whoever was the last one to alter the cluster state provided the definitive cluster state, simply by virtue of writing last.

In an eventual consistency model, clients may have inconsistent views of the world. This is unfortunately a fact of life. State may unexpectedly change by a particular client's view, because it's being modified on a different partition and those partitions managed to sync up. The road ahead of you may be a beach, but after syncing up with another part of the world, it may turn into a cactus. Such is life.

Option #2: sacrifice availability for consistency

Say you have a master/slave data store, and someone writes to a slave. Wat do? Slave can't talk to master. What's the most obvious option? Error.

This is a "CP" system. Slaves can serve stale state, but if you want to change the state, you have to talk to the master for that state. State can be partitioned/shareded/durr between multiple masters, but if the master for the particular state a slave wants to modify isn't available, sorry, that's a paddlin', or rather an error.

Option #3: highly available, and consistent at the partition level, netsplit fixed wat???

The only other option, the "CA" option, is that each partition pretends that writes to that partition are consistent, but when the netsplits are resolved, there's no consistent way to resolve that state. That is to say, if netsplits occur, each partition is highly available and allows writes, but as soon as the netsplit resolves, the cluster state is broke and irreconcilable.

In a quick survey of NoSQL datastores, Membase, MongoDB, and the hypothetical Redis Cluster all claim to be "CA". Are they really? Or do they just sacrifice availability in the event of a netsplit? If that's true, they're actually "CP", not "CA".

You really don't want to sacrifice partition tolerance. In fact, some might go as far as to say you CAN'T sacrifice partition tolerance. If you think your system is "CA" you probably understand the the CAP theorem and its implications.

CAP is the law, and AP or CP are the only reasonable options 

If you're running an app on a distributed network, things are going to go wrong. You might idealistically claim that you can provide both consistency and availability, sacrificing partition tolerance. You can't.

Can you pick "CA"? Sure, if you're content with losing all your data if the network had any errors. That's probably not what you mean. If you're building software for a fault-tolerant world, it's probably either going to be:
  • Consistent but unavailable during netsplits (CP)
  • "Eventually" consistent but available during netsplits (AP)
The only other option is "broken after netsplits". The best option is probably AP: this is the approach was pioneered by the Amazon Dynamo system which powered Amazon's shopping cart, and by copycat open source systems like Riak and Cassandra, not that Riak and Cassandra aren't awesome too.


vdp said...

I think you're being a bit unfair to "CA", when it is perfectly fine to use as long as you're not distributed. You may think non-distributed is off-topic but I think it's included in the CAP theorem : when it says "sacrifice partitioning" it actually means "do not use partitioning at all".

CA is in fact the most widely used data store option... It's called a "file" :p

That said, I enjoyed your writeup :)

shina said...

Surveillancekart | CCTV System
Pestveda | Pest Control
Termite control
Surveillancekart | CCTV System
cctv installation services
best home security camera system

call Girl said...

Gurgaon escorts
Lucknow escorts
Guwahati escorts
Bangalore escorts
call girls in bangalore

Gurgaon escort
Lucknow escort
Guwahati escort
Bangalore escort

Faridabad call girls
Faridabad call girl
Faridabad escorts
Faridabad escort
Escort services in Faridabad

Escort services in Faridabad
Call girls in Faridabad
Call girl in Faridabad
Faridabad escort services
Faridabad escort service

Escorts in Faridabad
Escorts in Faridabad
Escorts in Faridabad
Escorts in Faridabad

Escort in Faridabad
Escort in Faridabad
Escort in Faridabad
Escort in Faridabad

Escort services in Faridabad
Escort services in Faridabad
Escort services in Faridabad
Escort services in Faridabad

Escort service in Faridabad
Escort service in Faridabad
Escort service in Faridabad
Escort service in Faridabad

naveen said...

AppVN is an outsider application store for Android. Not at all like Google Play, this application store furnishes you with someone of a kind highlights, for example, the office to download certain official premium applications for nothing.
Appvn Apk

dadyar said...

نفقه چیست اولین سوالی است که برای هر شخصی که کلمه نفقه زن را شنیده است پیش می آید. نفقه زن از مسائل بنیادی خانواده است. یکی از حقوق مالی زن نفقه است که به محض عقد نکاح برای زن به وجود می‌آید و در مقابل تکلیفی است در اسلام از نظر نظام خانوادگی بر عهده مرد گذاشته است. منظور از نفقه زن تامین مایحتاج زندگی برای زن بر اساس عرف جامعه، شئون یک زن و استطاعت مالی مرد میباشد . وجوب پرداخت نفقه همسر و نفقه فرزند از سوی شوهر از مسلمات فقه و حقوق اسلامی است و زن از این نظر هیچ مسئولیتی ندارد.

نفقه عبارت است از مخارج و هزینه هایی که برای بقای خانواده لازم است و نفقه زن هر چیزی است که زن از نظر عرف به آن نیازمند است. نفقه، ضامن استقلال خانواده می باشد و نموداری از شئون سرپرستی مرد بر مهم ترین و کوچکترین نهاد اجتماعی است . البته در نفقه بحث فقر و غنای زن مطرح نیست و در هر صورت زن مستحق نفقه است.

در صورت فقیر بودن مرد و غنی بودن زن، یقیناً فقر بنیان خانواده را از هم می پاشد لذا مسئولیت اخلاقی زن تامین مسائل خانه و خانواده می شود و مرد پس از غنی شدن مکلف به بازگرداندن کمک های زن نمی باشد. زیرا کمک های زن به منزله هدیه بوده اند. حتی اگر زن اموال (جهیزیه) خود را بفروشد نیز نمی تواند مطالبه کند .

نفقه زن و فرزند

بهتر است که زن، مال را به عنوان قرض در اختیار مرد قرار بدهد تا مرد خود را مدیون ببیند و بعدا پرداخت کند . اگر مرد و زن مالی را با مشارکت یکدیگر بخرند بایستی به نسبت سهم، آن را ثبت کنند تا در آینده دچار مشکل نشوند .

هرچند که نفقه به عهده مرد است اما از نظر اخلاقی چنانچه مرد محتاج باشد، زن میتواند جهت استحکام مبانی خانواده در این امر مشارکت کند. اما مشارکت باید به نحوی باشد که کمک های زن قابل تادیه باشد.
نفقه زن شامل چیست

در تعریف حقوقی انفاق عبارت است از صرف هزینه خوراک، پوشاک، مسکن، اثاث خانه به قدر رفع حاجت و توانایی انفاق کننده (در مورد نفقه اقارب) و خوراک، پوشاک، مسکن و اثاث خانه و خادم در حدود مناسب عرفی با وضع زوجه (در مورد نفقه زوجه).

نفقه زن در اصطلاح حقوقی شامل چیزهایی است که شخص برای زندگی به آن احتیاج دارد از قبیل خوراک، پوشاک، مسکن و اثاثیه داخل آن. بنابراین نفقه در اصطلاح حقوقی تامین ضروریات همسر و اقارب واجب النفقه است.

Amber Collins said...

Amazing! This blog looks exactly like my old one! It’s on a entirely different topic but it has pretty much the same layout and design. Outstanding choice of colors!


Susan said...

This is really an incredible read for me. I have bookmarked it and I am anticipating perusing new articles. Keep doing awesome! Looking for some inspiration for your next trip? Find great vacation ideas and inspiration from Things to do with your source for the web's best reviews and travel ...

salma said...

تنظيف منازل بالمدينة المنورة تنظيف منازل بالمدينة المنورة

تنظيف بمكة شركة تنظيف بمكة بالبخار
تنظيف بالمدينة المنورة تنظيف بالمدينة المنورة

rima said...

siliguri escorts
siliguri escort
siliguri female escorts
siliguri escort service

siliguri escorts
siliguri escort
siliguri female escorts
siliguri escort service

siliguri escorts
siliguri escort
siliguri female escorts
siliguri escort service

siliguri escorts
siliguri escort
siliguri female escorts
siliguri escort service

siliguri escorts
siliguri escort
siliguri female escorts
siliguri escort service

Rajesh said...

If you would like to book an escort likeEscorts Service in Vasant Viharfor an upcoming time, you can use our mail reservation type where you can specify a substitute woman should your perfect option not be available. You will need to provide us with your real name on the reservation type, but be confident we are very distinct and will keep your private information private and protected. Check our other Services...
Escorts Service in Vasant Vihar
Escorts Service in Vasant Vihar
Escorts Service in Vasant Vihar
Escorts Service in Vasant Vihar
Escorts Service in Vasant Vihar

digitals said...

bookmarking submission site list
social bookmarking submission sites
high pr social bookmarking sites list
social bookmarking submission
free social bookmarking sites
social bookmarking submission site list
best bookmarking sites
social bookmarking seo
new bookmarking sites
top social bookmarking sites

niramay said...

ac market apk
ac market

bandarq228 said...

dapatkan penghasilan tambahan dengan bermain di bandar togel online yang aman dan terpecaya hanya di http://masbrotogel.com/

pkv games said...

mainkan pkv games disitus ini, klik

Scott Stayris said...

Quickbooks is the advanced accounting software to handle small and medium-sized business. Users can track and manage data online.
Transfer Quickbooks data to a new pc

R1se Hluoluo said...

Ibnu Sina memiliki pendapat dalam filsafat ilmunya, “Pengajaran terdiri jadi dua: 1) Pengetahuan yang tidak abadi, 2). https://generasi-kekinian.com/ Pengetahuan yang abadi”. Tetapi berdasar maksudnya, karena itu pengetahuan bisa dipisah jadi pengetahuan yang ringkas dan teoritis. Menurut Ibn Sina, ada dua arah pengajaran: Pertama, ditujukan ke pengembang semua kekuatan yang dimiiki seorang ke arah perubahan yang prima baik perubahan fisik, cendekiawan atau budi pekerti. Ke-2 , ditujukan pada usaha dalam rencana menyiapkan seorang agar hidup bersama dalam masyarakat dengan lakukan pekerjaan atau ketrampilan yang diputuskannya sesuai talenta, persiapan, kecendrungan dan kekuatan yang dipunyainya.

opbestcom said...

Hi there! I’m at work browsing your blog from my new iphone 3gs! Just wanted to say I love reading through your blog and look forward to all your posts! Carry on the fantastic work!

my web page ➤ 부산오피


Frank said...

that functions admirably in permanent state dialects like Erlang that need to assemble their linguistic structure trees from right-to-left Buy Custom Essays because of the idea of unchanging independently connected records. These rundowns just let you attach components on the left.

Iyaz Khan said...

Anyone who has studied physics must have had first contact with mass time acceleration and Newton's laws of motion. Newton's laws of motion proved to be the first brick in the foundation of physics. Buy Assignment Online

Unknown said...

come to use the service and get real money is another way to generate income to members for sure slot

Unknown said...

with only a little money And our website is still a website that pays for real, no cheating, no deductions. betflix

toomtbdf said...

Meet the impatient people who want to make money with full entertainment. join to play slotsslot

toomtbdf said...

and every mobile phone system wants to play fish shooting games, slot games, casino games and various games to choose frombetflix

Sandee said...

Today's phones come in a variety of designs, each with different capabilities and we would like to recommend you to choose a mobile phone with accessibility. Uninterrupted online gambling games are phone models such as Samsung Vivo Oppo Huawei. pgslot

Aaasdsd said...

Watch Seriale latimp subtitrat in Romana on our website daily. We are offering the latest updates of seriale turcesti subtitrat in Romana on our website. Thousands of people like to watch seriale turcesti subtitrat in Romana. You can also watch all updates of seriale turcesti subtitrat in Romana freely.

Maxwell Lord said...

There is no inherent connection between relativity and programming. For one, the postulate of special relativity states that physical laws are the same for all observers pay someone to do my online course.

forcracks said...


Unknown said...

I enjoyed reading this post and learning more about the relativity concepts used in programming. It's fascinating how these theories apply to computer systems. By the way, Meri Sehat is an excellent online healthcare services provider that offers easy access to healthcare professionals and can help with various health concerns, including fungal infections. Keep up the good work!

valentina said...

reckless driving virginia codeThank you for sharing informative blog,