load-balancing (empty) → 1.0.1.0

raw patch · 5 files changed

+384/−0 lines, 5 filesdep +PSQueuedep +basedep +containerssetup-changed

Dependencies added: PSQueue, base, containers, hslogger, stm

Files

• LICENSE +202/−0
• README.md +4/−0
• Setup.hs +2/−0
• load-balancing.cabal +32/−0
• src/Control/Concurrent/LoadDistribution.hs +144/−0

@@ -0,0 +1,202 @@++                                 Apache License+                           Version 2.0, January 2004+                        http://www.apache.org/licenses/++   TERMS AND CONDITIONS FOR USE, REPRODUCTION, AND DISTRIBUTION++   1. Definitions.++      "License" shall mean the terms and conditions for use, reproduction,+      and distribution as defined by Sections 1 through 9 of this document.++      "Licensor" shall mean the copyright owner or entity authorized by+      the copyright owner that is granting the License.++      "Legal Entity" shall mean the union of the acting entity and all+      other entities that control, are controlled by, or are under common+      control with that entity. For the purposes of this definition,+      "control" means (i) the power, direct or indirect, to cause the+      direction or management of such entity, whether by contract or+      otherwise, or (ii) ownership of fifty percent (50%) or more of the+      outstanding shares, or (iii) beneficial ownership of such entity.++      "You" (or "Your") shall mean an individual or Legal Entity+      exercising permissions granted by this License.++      "Source" form shall mean the preferred form for making modifications,+      including but not limited to software source code, documentation+      source, and configuration files.++      "Object" form shall mean any form resulting from mechanical+      transformation or translation of a Source form, including but+      not limited to compiled object code, generated documentation,+      and conversions to other media types.++      "Work" shall mean the work of authorship, whether in Source or+      Object form, made available under the License, as indicated by a+      copyright notice that is included in or attached to the work+      (an example is provided in the Appendix below).++      "Derivative Works" shall mean any work, whether in Source or Object+      form, that is based on (or derived from) the Work and for which the+      editorial revisions, annotations, elaborations, or other modifications+      represent, as a whole, an original work of authorship. For the purposes+      of this License, Derivative Works shall not include works that remain+      separable from, or merely link (or bind by name) to the interfaces of,+      the Work and Derivative Works thereof.++      "Contribution" shall mean any work of authorship, including+      the original version of the Work and any modifications or additions+      to that Work or Derivative Works thereof, that is intentionally+      submitted to Licensor for inclusion in the Work by the copyright owner+      or by an individual or Legal Entity authorized to submit on behalf of+      the copyright owner. For the purposes of this definition, "submitted"+      means any form of electronic, verbal, or written communication sent+      to the Licensor or its representatives, including but not limited to+      communication on electronic mailing lists, source code control systems,+      and issue tracking systems that are managed by, or on behalf of, the+      Licensor for the purpose of discussing and improving the Work, but+      excluding communication that is conspicuously marked or otherwise+      designated in writing by the copyright owner as "Not a Contribution."++      "Contributor" shall mean Licensor and any individual or Legal Entity+      on behalf of whom a Contribution has been received by Licensor and+      subsequently incorporated within the Work.++   2. Grant of Copyright License. Subject to the terms and conditions of+      this License, each Contributor hereby grants to You a perpetual,+      worldwide, non-exclusive, no-charge, royalty-free, irrevocable+      copyright license to reproduce, prepare Derivative Works of,+      publicly display, publicly perform, sublicense, and distribute the+      Work and such Derivative Works in Source or Object form.++   3. Grant of Patent License. Subject to the terms and conditions of+      this License, each Contributor hereby grants to You a perpetual,+      worldwide, non-exclusive, no-charge, royalty-free, irrevocable+      (except as stated in this section) patent license to make, have made,+      use, offer to sell, sell, import, and otherwise transfer the Work,+      where such license applies only to those patent claims licensable+      by such Contributor that are necessarily infringed by their+      Contribution(s) alone or by combination of their Contribution(s)+      with the Work to which such Contribution(s) was submitted. If You+      institute patent litigation against any entity (including a+      cross-claim or counterclaim in a lawsuit) alleging that the Work+      or a Contribution incorporated within the Work constitutes direct+      or contributory patent infringement, then any patent licenses+      granted to You under this License for that Work shall terminate+      as of the date such litigation is filed.++   4. Redistribution. You may reproduce and distribute copies of the+      Work or Derivative Works thereof in any medium, with or without+      modifications, and in Source or Object form, provided that You+      meet the following conditions:++      (a) You must give any other recipients of the Work or+          Derivative Works a copy of this License; and++      (b) You must cause any modified files to carry prominent notices+          stating that You changed the files; and++      (c) You must retain, in the Source form of any Derivative Works+          that You distribute, all copyright, patent, trademark, and+          attribution notices from the Source form of the Work,+          excluding those notices that do not pertain to any part of+          the Derivative Works; and++      (d) If the Work includes a "NOTICE" text file as part of its+          distribution, then any Derivative Works that You distribute must+          include a readable copy of the attribution notices contained+          within such NOTICE file, excluding those notices that do not+          pertain to any part of the Derivative Works, in at least one+          of the following places: within a NOTICE text file distributed+          as part of the Derivative Works; within the Source form or+          documentation, if provided along with the Derivative Works; or,+          within a display generated by the Derivative Works, if and+          wherever such third-party notices normally appear. The contents+          of the NOTICE file are for informational purposes only and+          do not modify the License. You may add Your own attribution+          notices within Derivative Works that You distribute, alongside+          or as an addendum to the NOTICE text from the Work, provided+          that such additional attribution notices cannot be construed+          as modifying the License.++      You may add Your own copyright statement to Your modifications and+      may provide additional or different license terms and conditions+      for use, reproduction, or distribution of Your modifications, or+      for any such Derivative Works as a whole, provided Your use,+      reproduction, and distribution of the Work otherwise complies with+      the conditions stated in this License.++   5. Submission of Contributions. Unless You explicitly state otherwise,+      any Contribution intentionally submitted for inclusion in the Work+      by You to the Licensor shall be under the terms and conditions of+      this License, without any additional terms or conditions.+      Notwithstanding the above, nothing herein shall supersede or modify+      the terms of any separate license agreement you may have executed+      with Licensor regarding such Contributions.++   6. Trademarks. This License does not grant permission to use the trade+      names, trademarks, service marks, or product names of the Licensor,+      except as required for reasonable and customary use in describing the+      origin of the Work and reproducing the content of the NOTICE file.++   7. Disclaimer of Warranty. Unless required by applicable law or+      agreed to in writing, Licensor provides the Work (and each+      Contributor provides its Contributions) on an "AS IS" BASIS,+      WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or+      implied, including, without limitation, any warranties or conditions+      of TITLE, NON-INFRINGEMENT, MERCHANTABILITY, or FITNESS FOR A+      PARTICULAR PURPOSE. You are solely responsible for determining the+      appropriateness of using or redistributing the Work and assume any+      risks associated with Your exercise of permissions under this License.++   8. Limitation of Liability. In no event and under no legal theory,+      whether in tort (including negligence), contract, or otherwise,+      unless required by applicable law (such as deliberate and grossly+      negligent acts) or agreed to in writing, shall any Contributor be+      liable to You for damages, including any direct, indirect, special,+      incidental, or consequential damages of any character arising as a+      result of this License or out of the use or inability to use the+      Work (including but not limited to damages for loss of goodwill,+      work stoppage, computer failure or malfunction, or any and all+      other commercial damages or losses), even if such Contributor+      has been advised of the possibility of such damages.++   9. Accepting Warranty or Additional Liability. While redistributing+      the Work or Derivative Works thereof, You may choose to offer,+      and charge a fee for, acceptance of support, warranty, indemnity,+      or other liability obligations and/or rights consistent with this+      License. However, in accepting such obligations, You may act only+      on Your own behalf and on Your sole responsibility, not on behalf+      of any other Contributor, and only if You agree to indemnify,+      defend, and hold each Contributor harmless for any liability+      incurred by, or claims asserted against, such Contributor by reason+      of your accepting any such warranty or additional liability.++   END OF TERMS AND CONDITIONS++   APPENDIX: How to apply the Apache License to your work.++      To apply the Apache License to your work, attach the following+      boilerplate notice, with the fields enclosed by brackets "[]"+      replaced with your own identifying information. (Don't include+      the brackets!)  The text should be enclosed in the appropriate+      comment syntax for the file format. We also recommend that a+      file or class name and description of purpose be included on the+      same "printed page" as the copyright notice for easier+      identification within third-party archives.++   Copyright [yyyy] [name of copyright owner]++   Licensed under the Apache License, Version 2.0 (the "License");+   you may not use this file except in compliance with the License.+   You may obtain a copy of the License at++       http://www.apache.org/licenses/LICENSE-2.0++   Unless required by applicable law or agreed to in writing, software+   distributed under the License is distributed on an "AS IS" BASIS,+   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.+   See the License for the specific language governing permissions and+   limitations under the License.

@@ -0,0 +1,4 @@+# load-balancing++The purpose of this package is to facilitate client-side load balancing in Haskell.+

@@ -0,0 +1,2 @@+import Distribution.Simple+main = defaultMain

@@ -0,0 +1,32 @@+-- Initial load-balancing.cabal generated by cabal init.  For further +-- documentation, see http://haskell.org/cabal/users-guide/++name:                load-balancing+version:             1.0.1.0+synopsis:            Client-side load balancing utilities.+-- description:         +homepage:            https://github.com/SumAll/haskell-load-balancing+license:             Apache-2.0+license-file:        LICENSE+author:              Rick Owens+maintainer:          rowens@sumall.com+-- copyright:           +-- category:            +build-type:          Simple+extra-source-files:  README.md+cabal-version:       >=1.10++library+  exposed-modules:     +    Control.Concurrent.LoadDistribution+  -- other-modules:       +  -- other-extensions:    +  build-depends:+    PSQueue    >= 1.1     && < 1.2,+    base       >= 4.8     && < 4.10,+    containers >= 0.5.6.2 && < 0.6,+    hslogger   >= 1.2.1   && < 1.3,+    stm        >= 2.4.4.1 && < 2.5+  hs-source-dirs:      src+  default-language:    Haskell2010+  ghc-options: -Wall

@@ -0,0 +1,144 @@+{-# LANGUAGE NamedFieldPuns #-}+{- |+  This module provides utilities for client-side load balancing.+-}+module Control.Concurrent.LoadDistribution (+  evenlyDistributed,+  LoadBalanced,+  withResource,+  map,+) where++import Prelude hiding (map)++import Control.Concurrent.STM (atomically)+import Control.Concurrent.STM.TVar (TVar, newTVar, readTVar, writeTVar,+  modifyTVar)+import Control.Exception (bracket)+import Data.PSQueue (PSQ, minView, adjust, Binding((:->)), alter, insert)+import Data.Set (Set, member)+import qualified Data.PSQueue as Q (empty)+import qualified Data.Set as Set (foldr, map)+import qualified System.Log.Logger as L (debugM)++{- |+  A load balancing technique that evenly load across multiple resources, where+  "even" is figured based on the current number of simultaneous threads using+  the resource.++  Some notes on implentation: The priority portion of the priority queue+  is a tuple of the form (p :: Int, r :: Int). The first element, @p@, stands+  for "processes", and indicates the number of simultaneous threads that are+  using the specific resource. This value is incremented and decremented as+  threads acquire and release the resource. The second element, @r@, stands for+  "round robin". Its purpose is to act as a tie breaker between resources that+  have the same @p@ value by giving priority to whichever resource has been+  chosen fewer times. It is always incremented and never decremented. Without+  the @r@ component, the deterministic nature of the priority queue will+  heavily favor resources that come first in the sorted list of resources.+-}+evenlyDistributed+  :: (Ord resource)+  => IO (Set resource)+    -- ^ An IO action that can be used to obtain a tagged list of+    --   resources.  This is an IO action because the set of resources+    --   is allowed to change dynamically.+  -> IO (LoadBalanced resource)+evenlyDistributed getResources = do+  psQueueT <- atomically (newTVar Q.empty)+  return LB {psQueueT, getResources}+++{- |+  An object that keeps track of load balancing across threads.+-}+data LoadBalanced resource =+  LB {+    psQueueT :: TVar (PSQ resource (Int, Int)),+    getResources :: IO (Set resource)+  }+++{- |+  Derives a new load balancer from an existing load balancer, allowing the+  resource type to be mapped from one type to another. This requires IO+  (as opposed to implementing this using @instance Functor@) because we+  have to create a new shared load balancing state.+-}+map :: (Ord b) => (a -> b) -> LoadBalanced a -> IO (LoadBalanced b)+map f lb = do+  psQueueT <- atomically (newTVar Q.empty)+  return LB {psQueueT, getResources = Set.map f <$> getResources lb}+++{- |+  Execute some kind of IO Action with the least loaded resource. If, for+  whatever reason, there are no available resources, then `Nothing` is passed+  to the user-provided action function.+-}+withResource+  :: (Show resource, Ord resource)+  => LoadBalanced resource+  -> (Maybe resource -> IO a)+  -> IO a+withResource LB {psQueueT, getResources} action = do+  resources <- getResources+  invokeResource psQueueT resources action+++{- |+  Invoke the resource.+-}+invokeResource :: (Ord resource, Show resource)+  => TVar (PSQ resource (Int, Int))+  -> Set resource+  -> (Maybe resource -> IO a)+  -> IO a+invokeResource psQueueT targets =+    bracket checkout checkin+  where+    checkout = do+      url <- atomically $ do+        queue <- updateTargets <$> readTVar psQueueT+        (newQueue, resource) <- getBest queue+        writeTVar psQueueT newQueue+        return resource+      debugM ("Choosing: " ++ show url)+      return url+      where+        getBest queue =+          case minView queue of+            Nothing -> return (queue, Nothing)+            Just (resource :-> (p, r), newQueue) ->+              if resource `member` targets+                then return (+                    insert resource (p + 1, r + 1) newQueue,+                    Just resource+                  )+                else getBest newQueue+          +    checkin Nothing = return ()+    checkin (Just resource) = atomically $+      modifyTVar+        psQueueT+        (adjust decrement resource)+      where+        decrement (p, r) = (p - 1, r)++    updateTargets queue =+      Set.foldr+        (alter insertMissing)+        queue+        targets+      where+        insertMissing Nothing = Just (0, 0)+        insertMissing (Just p) = Just p+++{- |+  Shorthand logging.+-}+debugM :: String -> IO ()+debugM = L.debugM "load-balancing"++