S. A language-based approach to unifying events an

ALanguage-basedApproachtoUnifyingEventsandThreadsPengLiUniversityofPennsylvaniaSteveZdancewicUniversityofPennsylvaniaAbstractThispaperpresentsalanguage-basedtechniquetounifytwoseeminglyoppositeprogrammingmodelsforbuild-ingmassivelyconcurrentnetworkservices:theevent-drivenmodelandthemultithreadedmodel.Theresultisaunifiedconcurrencymodelprovidingboththreadabstractionsandeventabstractions.Usingthismodel,eachcomponentinanapplicationcanbeimplementedusingtheappropriateabstraction,simplifyingthedesignofcomplex,multithreadedsystemssoftware.Thispapershowshowtoimplementtheunifiedcon-currencymodelinHaskell,apure,lazy,functionalpro-gramminglanguage.Italsodemonstrateshowtousethesetechniquestobuildanapplication-levelthreadli-brarywithsupportformultiprocessingandasynchronousI/OmechanismsinLinux.Thethreadlibraryistype-safe,isrelativelysimpletoimplement,andhasgoodperformance.Application-levelthreadsareextremelylightweight(scalingtotenmillionthreads)andourscheduler,whichisimplementedasamodularandex-tensibleevent-drivensystem,outperformsNPTLinI/Obenchmarks.1IntroductionModernnetworkservicespresentsoftwareengineerswithanumberofdesignchallenges.Webservers,mul-tiplayergames,andInternet-scaledatastorageappli-cationsmustaccommodatethousandsofsimultaneousclientconnections.Suchmassively-concurrentprogramsaredifficulttoimplement,especiallywhenotherrequire-ments,suchashighperformanceandstrongsecurity,mustalsobemet.Eventsvs.threads:Twoimplementationstrategiesforbuildingsuchinherentlyconcurrentsystemshavebeensuccessful.Boththemultithreadedandevent-drivenapproacheshavetheirproponentsanddetractors.Thedebateoverwhichmodelis“better”haswagedformanyyears,withlittleresolution.Ousterhout[17]hasarguedthat“threadsareabadidea(formostpurposes),”citingthedifficultiesofensuringpropersynchronizationanddebuggingwiththread-basedapproaches.Acounterargument,byvonBehren,Condit,andBrewer[23],ar-guesthat“eventsareabadidea(forhigh-concurrencyservers),”essentiallybecausereasoningaboutcontrolflowinevent-basedsystemsisdifficultandtheappar-entperformancewinsoftheevent-drivenapproachcanbecompletelyrecoupedbycarefulengineering[22].Fromtheprogrammer’sperspective,bothmodelsareattractive.Sometimesitisdesirabletothinkaboutthesystemintermsofthreads(forexample,todescribethesequenceofeventsthatoccurwhenprocessingaclient’srequests),andsometimesitisdesirabletothinkaboutthesystemintermsofeventsandeventhandlers(forexam-ple,tosimplifyreasoningaboutasynchronouscommu-nicationsandresourcescheduling).Aunifiedconcurrencymodel:Thispapershowsthateventsandthreadscanbeunifiedinasingleconcur-rencymodel,allowingtheprogrammertodesignpartsoftheapplicationasifshewereusingthreads,wherethreadsaretheappropriateabstraction,andpartsofthesystemusingevents,wheretheyaremoresuitable.Sec-tion2givessomeadditionalbackgroundaboutthemulti-threadedandevent-drivenmodelsandmotivatesthede-signofourunifiedconcurrencymodel.Inourmodel,forhigher-levelapplicationcode,theprogrammercanuseuseamultithreadedprogrammingstylesimilartoCandJava,withfamiliarcontrol-flowel-ementssuchassequencing,functionscalls,conditionalsandexceptions,andwithuser-definedsystemcallsforI/Oandthreadcontrol.Figure1showstwosamplefunc-tionswritteninthemultithreadedstyle.Forlower-levelI/Ocode,theprogrammercanconve-nientlyuseasynchronousOSinterfacessuchasepollandAIOinLinux.Thethreadschedulerhasanex-tensible,modularevent-drivenarchitectureinwhichtheapplication-levelthreadscanbeseenaseventhandlers.Alanguage-basedapproach:LanguageslikeCandC++havehistoricallybeenusedtoimplementhigh-performance,concurrentsoftware.However,theysuf-ferfromwellknownsecurityandreliabilityproblemsthathavepromptedamovetowardtype-safelanguageslikeJavaandC#.Theirgeneral-purposethreadspack-agesaretypicallyquiteheavyweightthough,andnoneoftheselanguagesprovideappropriateabstractionstosim-plifyevent-drivingprogramming.Implementingscal-ablethreadoreventsystemsisfeasibleusingtheselan-guages,buttheresultscanbecumbersometouse.Tech-niquessuchascompilertransformationscanaddresstheseproblemstosomeextent[22],buteventhentheen-gineeringchallengestypicallyforcetheprogrammertochoosebetweenthreadsorevents—theydon’tgetboth.Ourcase-studyimplementationoftheunifiedconcur-rencymodel,describedindetailinSection3,iswrit-tenintheprogramminglanguageHaskell[12].Haskellisapure,lazy,strongly-typed,functionallanguagewithmanyadvancedlanguagefeatures,suchastypeclasses,thatmakeitveryconvenienttoimplementtheunifiedconcurrencymodel.OurimplementationisbasedontechniquesdevelopedsometimeagobyKoenClaessen[8]intheprogramminglanguagesresearchcommunity.Application-levelthreads:Usingthislanguagesup-port,wehavebuiltanapplication-levelthreadlibrary,inwhichthethreadedcodeandthreadschedulerarewrit-teninsidetheapplication.Section4describesthethreadlibrary,whichusesbothevent-drivenandmultithreadedprogrammingmodels,andshowshowitcanflexiblysup-portseveralsynchronizationmechanismsforinterthreadcommunicationandsharedstate.Comparedtotraditionalapproaches(bothmulti-threadedandevent-driven),ourapplication-levelthreadlibraryhasmanyadvantagesforbuil