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

emma said...

cctv camera dealers in delhi
cp plus cctv camera online
hikvision camera online
cctv camera installation services in delhi
cctv camera installation services in gurugram
cctv camera installation services in gurgaon

shabnam praveen said...

Call girls in Kolkata
Call girls in Chandigarh
Call girls in Chandigarh
Call girls in Gurgaon
Call girls in Chandigarh
Call girls in Chandigarh

shabnam praveen said...

Call girls in Lucknow
Call girls in Guwahati
Call girls in Mumbai
Call girls in Jaipur
Call girls in Jaipur
Call girls in Jaipur
Call girls in Bangalore

call Girl said...

Call girls in Gurgaon
Call girls in Lucknow
Call girls in Guwahati

Call girl in Gurgaon
Call girl in Lucknow
Call girl in Guwahati
Bangalore call girls

Gurgaon call girls
Lucknow call girls
Guwahati call girls
Bangalore call girls

Gurgaon call girl
Lucknow call girl
Guwahati call girl
Bangalore call girl

Escorts in Gurgaon
Escorts in Lucknow
Escorts in Guwahati
Escorts in Bangalore

Escort services in Gurgaon
Escort services in Lucknow
Escort services in Guwahati
Escort services in Bangalore

Escort service in Gurgaon
Escort service in Lucknow
Escort service in Guwahati
Escort service in Bangalore

Gurgaon escorts
Lucknow escorts
Guwahati escorts
Bangalore escorts

Naincy said...

This is so much amazing .so,you can also visite my links.
call girls in kolkata
russian escorts in kolkata
kolkata call girls
call girls kolkata
escorts in kolkata
kolkata escort
housewife escorts in kolkata
college call girls in kolkata
call girls in park street
escorts in park street

call girls in gurgaon
call girl in gurgaon
gurgaon call girls
escorts in gurgaon
gurgaon escorts
gurgaon escort
Escort services in Gurgaon
Escort service in Gurgaon
russian escorts in gurgaon
housewife escorts in gurgaon
college call girls in gurgaon

Call girls in Noida
Call girl in Noida
Escorts in Noida
Escort services in Noida
Escort service in Noida
Noida Escorts
Noida Escort
Noida Call girls
Noida Call girl

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...

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

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

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

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

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

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

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

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

Nannie Co Pam said...

IEEE Project Domain management in software engineering is distinct from traditional project deveopment in that software projects have a unique lifecycle process that requires multiple rounds of testing, updating, and faculty feedback. A IEEE Domain project Final Year Projects for CSE system development life cycle is essentially a phased project model that defines the organizational constraints of a large-scale systems project. The methods used in a IEEE DOmain Project systems development life cycle strategy Project Centers in Chennai For CSE provide clearly defined phases of work to plan, design, test, deploy, and maintain information systems.

This is enough for me. I want to write software that anyone can use, and virtually everyone who has an internet connected device with a screen can use apps written in JavaScript. JavaScript Training in Chennai JavaScript was used for little more than mouse hover animations and little calculations to make static websites feel more interactive. Let’s assume 90% of all websites using JavaScript use it in a trivial way. That still leaves 150 million substantial JavaScript Training in Chennai JavaScript applications.

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...

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

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

indobolaku said...

Judi Online


Judi Bola


customized gifts for him said...

floral embroidered pillow
Baby Girl Nursery Pillow
burlap pillow cases wholesale

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

Aerocity Service said...

Paharganj Escorts
Dwarka Escorts
Russian Escorts Noida
Russian Escorts Delhi
Karol Bagh escorts
Delhi Escorts Service
Escorts in Delhi
Call girls in Delhi
Delhi escort
Aerocity Escorts

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 ➤ 부산오피


Tech said...

This trend has been going on for years and we're in love! - You can easily create a casual look while wearing your favorite jeans with a denim shirt. If you want to try something as unique as the look below, match your denim shirt and bodice with jeans for an innovative denim jeans look. You can also take a twist on the basic denim trend over jeans by pairing your white jeans with a blue or black denim jacket and seeing the magic of this white denim outfit.Jeans Shop

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...