Apple’s (AAPL) mythical subscription-based streaming music service as been rumored for years now, but difficulties negotiating with major labels have seemingly kept it from launching. While Apple reportedly fights for  more favorable fee structures, Google (GOOG) may very well bring a similar Spotify-like service to market before Apple has the chance. “Google Inc.’s Android unit has been negotiating with music companies to start a paid subscription music-streaming service akin to Spotify AB,” The Wall Street Journal recently reported. The paper also notes that Google’s YouTube division is “trying to obtain licenses from music labels to start a paid subscription service for music videos and potentially also for audio-only songs.”