blacktip (empty) → 0.1.0.0
raw patch · 7 files changed
+543/−0 lines, 7 filesdep +asyncdep +basedep +bitwisesetup-changed
Dependencies added: async, base, bitwise, blacktip, bytestring, criterion, deepseq, deepseq-generics, hspec, locators, network-info, safe, split, system-fileio, system-filepath, time
Files
- LICENSE +202/−0
- Setup.hs +2/−0
- benchmarks/benches.hs +39/−0
- blacktip.cabal +62/−0
- src/Database/Blacktip.hs +146/−0
- src/Database/Blacktip/Types.hs +73/−0
- tests/tests.hs +19/−0
+ LICENSE view
@@ -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.
+ Setup.hs view
@@ -0,0 +1,2 @@+import Distribution.Simple+main = defaultMain
+ benchmarks/benches.hs view
@@ -0,0 +1,39 @@+module Main where++import Control.Monad (replicateM)+import Control.Concurrent.Async (mapConcurrently)+import Criterion.Main+import qualified Database.Blacktip as BT+import qualified Network.Info as NI+import qualified Data.Time.Clock.POSIX as PSX++import Data.Maybe (fromJust)+import System.IO.Unsafe (unsafePerformIO)++{-# NOINLINE interf #-}+interf :: NI.NetworkInterface+interf = fromJust $ unsafePerformIO $ BT.getInterfaceByName "wlan0"++wc :: BT.Config+wc = BT.defaultConfig { BT.interface = BT.NIInterface interf }++gen :: BT.Config -> IO (Either BT.NoInterfaceError BT.UniqueId)+gen = BT.generateUniqueId++genMany :: BT.Config -> Int -> IO [Either BT.NoInterfaceError BT.UniqueId]+genMany config n = mapConcurrently gen (replicate n config)++timeJustMultiply :: IO PSX.POSIXTime+timeJustMultiply = fmap (*1000) PSX.getPOSIXTime++main :: IO ()+main = defaultMain+ [ bench "one unique id" $ whnfIO (gen wc)+ , bench "sequential 1000 unique ids" $ whnfIO (replicateM 1000 (gen wc))+ , bench "sequential 100,000 unique ids" $ whnfIO (replicateM 100000 (gen wc))+ -- , bench "concurrent 1000 unique ids" $ nfIO (genMany wc 1000)+ , bench "get Unix Millis" $ whnfIO BT.getUnixMillis+ -- , bench "get POSIX time" $ nfIO PSX.getPOSIXTime+ -- , bench "POSIX time w/ mult" $ nfIO timeJustMultiply+ , bench "get interface by name" $ whnfIO (BT.getInterfaceByName "wlan0")+ ]
+ blacktip.cabal view
@@ -0,0 +1,62 @@+name: blacktip+version: 0.1.0.0+synopsis: Decentralized, k-ordered unique ID generator.+description: Clone of Boundary's Flake unique id service for Haskell, itself based on Snowflake.+homepage: https://github.com/bitemyapp/blacktip+license: Apache-2.0+license-file: LICENSE+author: Chris Allen+maintainer: cma@bitemyapp.com+copyright: 2014, Chris Allen+category: Database+build-type: Simple+cabal-version: >=1.10++source-repository head+ type: git+ location: https://github.com/bitemyapp/blacktip.git++library+ ghc-options: -Wall -threaded+ default-extensions: OverloadedStrings+ build-depends: base >=4.7 && <5+ , bitwise >= 0.1.0.0+ , locators >= 0.2.4.2+ , network-info >= 0.2+ , safe >= 0.3+ , split >= 0.2.0+ , system-fileio >= 0.3+ , system-filepath+ , time >= 1.4.0+ , deepseq-generics >= 0.1.1.0+ , deepseq+ , bytestring+ hs-source-dirs: src+ exposed-modules: Database.Blacktip+ , Database.Blacktip.Types+ default-language: Haskell2010++test-suite tests+ ghc-options: -Wall+ default-extensions: OverloadedStrings+ type: exitcode-stdio-1.0+ main-is: tests.hs+ hs-source-dirs: tests+ build-depends: base,+ blacktip,+ hspec >= 1.8+ default-language: Haskell2010++benchmark benches+ type: exitcode-stdio-1.0+ main-is: benches.hs+ ghc-options: -Wall -O2 -threaded+ hs-source-dirs: benchmarks+ build-depends:+ base,+ blacktip,+ criterion,+ network-info,+ time,+ async+ default-language: Haskell2010
+ src/Database/Blacktip.hs view
@@ -0,0 +1,146 @@+module Database.Blacktip+ ( module Database.Blacktip.Types+ , generateUniqueId+ , generateUniqueId'+ , getInterfaceByName+ , getUnixMillis+ , integerToRecord+ , toBase62+ ) where++import qualified Control.Concurrent as CC+import qualified Control.Concurrent.MVar as MV+import qualified Data.ByteString.Char8 as B+import qualified Data.Locator as DL+import qualified Data.Time.Clock.POSIX as PSX+import qualified Filesystem as FS+import qualified Filesystem.Path.CurrentOS as FPC+import qualified Network.Info as NI+import qualified Safe+import Control.Exception (mask, try)+import Control.Monad (forever, when)+import Data.Bits+import Data.Bits.Bitwise (fromListBE)+import Data.List.Split (chunksOf)+import Database.Blacktip.Types+import System.IO.Unsafe (unsafePerformIO)++-- There are only supposed to be one of these+-- babies running per node (MAC address)!+getInterfaceByName :: InterfaceName -> IO (Maybe NI.NetworkInterface)+getInterfaceByName n = fmap (Safe.headMay+ . filter ((n ==)+ . NI.name))+ NI.getNetworkInterfaces++toBase62 :: Integer -> String+toBase62 = DL.toBase62++getMac :: Interface -> IO (Maybe NI.MAC)+getMac iface = case iface of+ NIInterface interf -> return $ Just (NI.mac interf)+ IName name -> (fmap . fmap) NI.mac (getInterfaceByName name)++getUnixMillis :: IO Milliseconds+getUnixMillis = fmap (round . (*1000)) PSX.getPOSIXTime++-- We don't want multiple of these running around via inlining+{-# NOINLINE serverState #-}+serverState :: MV.MVar ServerState+-- unsafePerformIO so it doesn't create an+-- emptyMVar when I bind against serverState+serverState = unsafePerformIO $ MV.newEmptyMVar++readTimestamp :: FPC.FilePath -> IO Int+readTimestamp path = do+ result <- try $ FS.readFile path :: IO (Either IOError B.ByteString)+ case result of+ (Right "") -> return 0+ _ -> return $ either (const 0) (read . B.unpack) result++writeTimestamp :: MV.MVar ServerState -> FPC.FilePath -> IO CC.ThreadId+writeTimestamp s path = do+ CC.forkIO go+ where go = forever $ do+ ss <- MV.readMVar s+ mask $ \_ -> do+ FS.writeFile path (B.pack (show (ssTime ss)))+ -- sleep for 1 second+ CC.threadDelay 1000000++arrowOfTimeError :: (Show a, Show b) => a -> b -> c+arrowOfTimeError ts stateTime =+ error ("ERROR ARROW OF TIME BACKWARDS - Had timestamp: "+ ++ show ts+ ++ " and state time: "+ ++ show stateTime)++bumpItYo :: Milliseconds -> ServerState -> ServerState+bumpItYo ts s+ | ts == stateTime = s { ssSequence = (+1) stateSeq }+ | ts > stateTime = s { ssTime = ts, ssSequence = 0 }+ | otherwise = arrowOfTimeError ts stateTime+ where stateTime = ssTime s+ stateSeq = ssSequence s++generateUniqueId' :: Config -> IO (Either NoInterfaceError+ (UniqueId, IdentityRecord))+generateUniqueId' config = do+ millis <- getUnixMillis+ empty <- MV.isEmptyMVar serverState+ _ <- when empty (initWriter (timestampPath config))+ -- newState <- MV.modifyMVar ss (bumpItYo ms)+ mState <- MV.takeMVar serverState+ let newState = bumpItYo millis mState+ _ <- MV.putMVar serverState newState+ let sSeq = ssSequence $ newState+ mMac <- (getMac . interface) config+ case mMac of+ Nothing -> return $ Left NoInterfaceError+ Just mac -> return $ Right ((binnify millis mac sSeq), IdentityRecord millis mac sSeq)++generateUniqueId :: Config -> IO (Either NoInterfaceError UniqueId)+generateUniqueId config = do+ uid <- generateUniqueId' config+ return $ fmap fst uid++initWriter :: FPC.FilePath -> IO ()+initWriter path = do+ ms <- getUnixMillis+ stateTime <- readTimestamp path+ _ <- when (ms <= stateTime) (arrowOfTimeError ms stateTime)+ _ <- MV.putMVar serverState (ServerState ms 0)+ _ <- writeTimestamp serverState path+ return ()++binnify :: Milliseconds -> NI.MAC -> Sequence -> Integer+binnify ms (NI.MAC a b c d e f) sq = withSq+ where withTimestamp = shift (toInteger ms) 64+ withMacA = shift (toInteger a) 56 .|. withTimestamp+ withMacB = shift (toInteger b) 48 .|. withMacA+ withMacC = shift (toInteger c) 40 .|. withMacB+ withMacD = shift (toInteger d) 32 .|. withMacC+ withMacE = shift (toInteger e) 24 .|. withMacD+ withMacF = shift (toInteger f) 16 .|. withMacE+ withSq = withMacF .|. toInteger sq++-- works with Integer since I am providing range, big-endian+bitRange :: Bits a => a -> Int -> Int -> [Bool]+bitRange n lo hi = reverse $ map (testBit n) [lo..hi]++integerToRecord :: Integer -> IdentityRecord+integerToRecord n = IdentityRecord milliseconds mac recSequence+ -- extract 128 bits.+ where extractedBits = bitRange n 0 127+ milliBits = take 64 extractedBits+ macBits = chunksOf 8 $ take 48 $ drop 64 extractedBits+ sequenceBits = take 16 $ drop 112 extractedBits+ milliseconds = fromListBE milliBits :: Milliseconds+ a = fromListBE (macBits !! 0)+ b = fromListBE (macBits !! 1)+ c = fromListBE (macBits !! 2)+ d = fromListBE (macBits !! 3)+ e = fromListBE (macBits !! 4)+ f = fromListBE (macBits !! 5)+ mac = (NI.MAC a b c d e f)+ recSequence = fromListBE sequenceBits :: Sequence
+ src/Database/Blacktip/Types.hs view
@@ -0,0 +1,73 @@+{-# LANGUAGE DeriveGeneric #-}++module Database.Blacktip.Types+ ( Config(..)+ , Interface(..)+ , ServerState(..)+ , ArrowOfTimeError(..)+ , NoInterfaceError(..)+ , ParseError(..)+ , IdentityRecord(..)+ , InterfaceName+ , Milliseconds+ , Sequence+ , UniqueId+ , defaultConfig+ )+ where++import qualified Data.Int as DI+import qualified Filesystem.Path.CurrentOS as FPC+import qualified Network.Info as NI+import Control.DeepSeq+import GHC.Generics++type InterfaceName = String++data Interface = NIInterface NI.NetworkInterface+ | IName InterfaceName+ deriving Show++type Milliseconds = Int+type Sequence = DI.Int16++data Config =+ Config { interface :: Interface+ , timestampPath :: FPC.FilePath+ , allowableDowntime :: Milliseconds }+ deriving Show++defaultConfig :: Config+defaultConfig =+ Config { interface = IName "eth0"+ , timestampPath = FPC.decodeString "/tmp/blacktip-timestamp"+ -- 720 hours.+ , allowableDowntime = 2592000000 }+ ++data ServerState =+ ServerState { ssTime :: Milliseconds+ , ssSequence :: Sequence }+ deriving Show++-- {64 bit timestamp, 48 bit id (MAC address), 16 bit sequence}+type UniqueId = Integer++data IdentityRecord =+ IdentityRecord { identityTime :: Milliseconds+ , identityMac :: NI.MAC+ , identitySequence :: Sequence }+ deriving (Eq, Ord, Show)++-- if the data in the file doesn't parse+data ParseError = ParseError deriving Show++-- If our current timestamp is younger than the one in our state+data ArrowOfTimeError = ArrowOfTimeError deriving Show++-- We couldn't find an interface by that name, did you change it+-- from the default IName "eth0" ?+data NoInterfaceError = NoInterfaceError deriving (Eq, Generic, Ord, Show)++instance NFData NoInterfaceError+instance NFData NI.NetworkInterface
+ tests/tests.hs view
@@ -0,0 +1,19 @@+module Main where++import Control.Monad (replicateM)+import Database.Blacktip+import Data.List (sort)+import Test.Hspec++wirelessConfig :: Config+wirelessConfig = defaultConfig { interface = IName "wlan0" }++main :: IO ()+main = hspec $ do+ describe "identities generated are proper" $ do+ it "identities are well ordered" $ do+ results <- replicateM 100 (generateUniqueId wirelessConfig)+ sort results `shouldBe` results+ it "identities form an isomorphism" $ do+ result <- generateUniqueId' wirelessConfig+ fmap snd result `shouldBe` fmap (integerToRecord . fst) result